Home » Games » Illusion of Intelligence – AI for Pacman

Illusion of Intelligence – AI for Pacman

PacmanGIFAfter screwing up main game loop for Untangle (see postmortem) I really, really wanted to try using complete game-making framework, rather than writing everything from scratch. I decided to write simple pacman clone with phaser.js.

Today I’ll write about implementing AI for pacman’s ghosts. I assume that you already know rules behind ghosts behaviour (if not check awesome articles on GameInternals or Pac-man Dossier).

You can find pacman’s code on github. If you want to play newest version online click here.

  • Moving ghost!
  • So first of all we must create Phaser.Sprite and enable physics on it to allow collision checks, moving and so on. I used ARCADE physics system, because what we really need is simple (and fast) collision detection.

    ghost = game.add.sprite((Utils.TILE_SIZE*9),
    		(Utils.TILE_SIZE * 8),"blinky");
    game.physics.enable(ghost, Phaser.Physics.ARCADE);

    Enabling will add instance of ArcadePhysics.Body to Sprite as a property. To move ghost we simply apply negative or positive, horizontal or vertical velocity. Eg.

    ghost.body.velocity.x = 93;

    But… oops. Now Ghost just rushes to right end of screen, ignoring walls and obstacles. Quick fix:

    game.physics.arcade.collide(ghost,mapLayer)

    Now ghost’ll stop after colliding with specific map tiles, marked as collidable.

  • Turn and turn!
  • Of course ghost shouldn’t stop when he faces the wall! He should change moving direction. So when he face a wall AI need to check adhesive tiles to find uncollidable one. Checking starts from tile above and goes counter-clockwise. But there’s no turning back. Ghost comming from left can decide in the order of Up -> Down -> Right.

    We need to create collision callback function. ex. ghostcollide, add it as parameter to checking function:

    game.physics.arcade.collide(ghost,mapLayer,collide);

    And then implement algorithm for turning!
    First let’s collect informations about our surroundings and put it in custom property directions!

    ghost.directions[Utils.Up] = 
       map.getTileAbove(map.getLayer(), ghost.marker.x, ghost.marker.y);
    ghost.directions[Utils.Left] =
       map.getTileLeft(map.getLayer(), ghost.marker.x, ghost.marker.y);
    ghost.directions[Utils.Down] =
       map.getTileBelow(map.getLayer(), ghost.marker.x, ghost.marker.y);
    ghost.directions[Utils.Right] =
       map.getTileRight(map.getLayer(), ghost.marker.x, ghost.marker.y);

    Utils.DIRECTION are aliases for integers, UP is 0, Left is 1 ect. to remove magic numbers in conditional statements.

    And now we iterate through directions property to find first title marked as uncollidable, but because ghost can’t revert we also need another property “comingFrom” that stores forbidden direction. And – when iterating – we skip that one.

    	
    for( var i = Utils.Up; i < length;){
       if(i !== ghost.comingFrom && ghost.directions[i].index === 1){
          ghost.move(i);
          break;
       }
       else{
          ++i;
       }
    }

    Move is custom function that applies right velocity value and updates commingFrom property.

  • Decide on crossroads
  • In first two steps we created simple "looping" ghost. It'll just wander, always turning left so eventually we'll find it running around single obstacle. Something is not right, after all pacman's ghosts were clearly chasing player. We need to implement pathfinding! Luckily it just sounds difficult, because ghosts electronic brains are very short-sighted. They always plan only one step ahead, and because they can't turn back AI only make decisions at specific intersection points, marked with brown circles on map below:
    intersections

    I stored that decision points in array, and everytime ghost changes current tile I check if new one is decision point or not. If yes we perform 3 tasks:

    1. Decide target tile, where we need to go.
    2. Each ghost have four target tiles, used in different situations. Two of them are universal, shared by all ghosts, and two are different for each one. Shared target tiles are:

      • respawn point (ghosts head there after being eaten by pacman)
      • Frightened target that's basically just random tile, selected everytime any frightened ghost walks on decision point.

      Exclusive target tiles are:

      • "chasing tile" the most important of them all! It marks tile where ghost should go to eat pacman, and obviously they are connected to pacman's current position. For example chasing tile for red ghost is always pacman's current tile. Pink one uses formula: "4 tiles ahead of pacman's current tile".
      • "scatter tile" last one, it's just a map corner. Each ghost has it's own, where he moves around obstacle for some time.
      if(this.mode === GhostMode.Chase){
      // default targeting mode
         this.target.x = Utils.pixelsToTiles(player.x);
         this.target.y = Utils.pixelsToTiles(player.y);
      }
      else if(this.mode === GhostMode.Scatter){
      // from time to time, when clock ticks
         this.target.x = this.scatterTarget.x;
         this.target.y = this.scatterTarget.y;
      }
      else if(this.mode === GhostMode.Scared){
      // when pacman eat super pill
         this.target.x = Math.random() * (Utils.mapWidth - 1) + 1;
         this.target.y = Math.random() * (Utils.mapHeight - 1) + 1;
      }
      else{
      // eated by pacman
         this.target.x = this.respawnTarget.x;
         this.target.y = this.respawnTarget.y;
      }
    3. Check distance from each tile adhesive to the decision point to target tile.
    4. No surprises here, we just iterate through directions array and update distances array. If we cannot use that tile (it's wall or ghost just left that tile) we set distance to some high value.

      for(var i= 0; i < length; i++)
      {	
         if(this.directions[i].index === 1 && i !== this.comingFrom)
            this.distance[i] =
               Phaser.Point.distance(this.target,this.directions[i]);
         else
            this.distance[i] = 2000;
      }
    5. Move to tile that's nearest to target tile.
    6. Just find lovest value in distance array and pass it's index to Ghost move function.

And that's all. We have wireframe for implementing pacman's AI. Now we need to write down function that calculates chase target for each ghost, and functions to change their mode :)

Posted in Games and tagged as , ,

Comments are closed.