Storing Tile Details

The A*-Based Alien Sprite

In a similar manner to AlienQuadSprite, AlienAStarSprite is a subclass of AlienSprite and overrides its superclass's playerHasMoved( ) and move( ) methods.

The alien calculates a path to the player using the A* pathfinding algorithm. The path is stored as a sequence of tile coordinates that need to be visited to reach the player. In each call to move( ), the sprite moves to the next coordinate in the sequence, giving it a "player-chasing" behavior.

Planning a Move

Every time the user presses one of the move keys, the PlayerSprite object moves to an adjacent tile, and it notifies WorldDisplay by calling playerHasMoved( ). You don't want to recalculate a path after every player move since the change will be minimal but expensive to generate. Instead, the path is generated only when the player has moved MAX_MOVES steps. This saves on computation and makes things a bit easier for the player:

     // globals     private final static int MAX_MOVES = 5;     private int numPlayerMoves = 0;     private ArrayList path;    // tile coords going to the player     private int pathIndex = 0;     public void playerHasMoved(Point playerLoc)     { if (numPlayerMoves == 0)         calcNewPath(playerLoc);       else         numPlayerMoves = (numPlayerMoves+1)%MAX_MOVES;     }     private void calcNewPath(Point playerLoc)     { path = aStarSearch( getTileLoc( ), playerLoc );       pathIndex = 0;   // reset the index for the new path     }

The A* Algorithm

A* search finds a path from a start node to a goal node; in AlienTiles, the starting point is the alien's current tile position and the goal is the player's tile. The algorithm maintains a set of tiles it has seen but not visited. It chooses the highest scoring tile from that set and moves there. The search is finished if that tile holds the player; otherwise, it stores the locations of the adjacent tiles in its set of seen-but-not-visited tiles. The algorithm then repeats until the player's tile is found. The algorithm scores a tile (for algorithmic purposes, called a node) by estimating the cost of the best path that starts at the alien's position, goes through the node being examined, and finishes at the player's tile. The scoring formula is expressed using two functions, usually called g( ) and h( ). I'll break with tradition and call them getCostFromStart( ) and costToGoal( ) for clarity's sake:

     score(node) = node.getCostFromStart( ) + node.costToGoal( )

getCostFromStart( ) is the smallest cost of arriving at node from the starting tile (the alien's current position). costToGoal( ) is a heuristic estimate (an educated guess) of the cost of reaching the goal tile (the player's location) from node.

A* search is popular because it's guaranteed to find the shortest path from the start to the goal as long as the heuristic estimate, costToGoal( ), is admissible. Admissibility means that the node.costToGoal( ) value is always less than (or equal to) the actual cost of getting to the goal from the node. The A* algorithm has been proven to make the most efficient use of costToGoal( ), in the sense that other search techniques cannot find an optimal path by checking fewer nodes.

If costToGoal( ) is inaccurateit returns too large a valuethen the search will become unfocused, examining nodes which won't contribute to the final path. The generated path may not be the shortest possible. However, a less accurate costToGoal( ) function may be easier (and faster) to calculate, so path generation may be quicker. Speed might be preferable, as long as the resulting path isn't excessively meandering. A less accurate path gives the player more of a chance to evade capture (and death).

In visual terms, an optimal path goes directly to the goal, examining only the nodes along the edges of that path. A suboptimal path wanders about, with many more nodes examined on either side. The A* demo applet by James Macgill at http://www.ccg.leeds.ac.uk/james/aStar/ allows the costToGoal( ) function to be varied, and the incremental generation of the path is displayed.

Figure 13-16 shows the applet's calculations to find a path from a start node at the top of a grid to a goal node at the bottom, with few wasteful operations.

Figure 13-17 shows the result when the applet uses an estimation function that is much worse, resulting in unnecessary computation, though a path was found eventually.

Figure 13-16. A* applet path calculations with a good estimator

Figure 13-17. A* applet path calculations with a bad estimator

getCostFromStart( ) and costToGoal( ) rely on calculating a cost of moving from one tile to another. Various costing approaches are possible, including the distance between the tiles, the cost in time, the cost of fuel, or weights based on the terrain type. AlienTiles ignores these factors (you don't want this chapter to be longer, do you?) and uses raw distance.

A* employs two list data structures, usually called open and closed. open is a list of tiles that have not yet been examined (i.e., their adjacent tiles have not been scored). closed contains the tiles which have been examined. The tiles in open are sorted by decreasing score, so the most promising tile is always the first one. The following pseudocode shows how the A* search progresses:

     add the start tile to open;     create an empty closed list;     while (open isn't empty) {       get the highest scoring tile x from open;       if (x is the goal tile)         return a path to x;   // I'm done       else {         for (each adjacent tile y to x) {           calculate the costFromStart( ) value for y;           if ((y is already in open or closed) and               (value is no improvement))             continue;   // ignore y           else {             delete old y from open or close (if present);             calculate costToGoal( ) and the total score for y;             store y in open;           }         }       }       put x into closed;  // since I'm finished with it     }     report no path found;

This pseudocode is based on code in "The Basics of A* for Path Planning" by Bryan Stout, from Game Programming Gems (Charles River Media), edited by Mike DeLoura.

The translation of the pseudocode to the aStarSearch( ) method is quite direct:

     private ArrayList aStarSearch(Point startLoc, Point goalLoc)     {       double newCost;       TileNode bestNode, newNode;       TileNode startNode = new TileNode(startLoc);  // set start node       startNode.costToGoal(goalLoc);       // create the open queue and closed list       TilesPriQueue open = new TilesPriQueue(startNode);       TilesList closed = new TilesList( );       while (open.size( ) != 0) {  // while some node still left         bestNode = open.removeFirst( );         if (goalLoc.equals( bestNode.getPoint( ) ))   // reached goal           return bestNode.buildPath( );   // return a path to that goal         else {           for (int i=0; i < NUM_DIRS; i++) {    // try every direction             if ((newNode = bestNode.makeNeighbour(i, world)) != null) {               newCost = newNode.getCostFromStart( );               TileNode oldVer;               // if this tile already has a cheaper open or closed node               // then ignore the new node               if (((oldVer=open.findNode(newNode.getPoint( ))) !=null)&&                   (oldVer.getCostFromStart( ) <= newCost))                 continue;               else if (((oldVer = closed.findNode( newNode.getPoint( )))                                                             != null) &&                   (oldVer.getCostFromStart( ) <= newCost))                 continue;               else {   // store new/improved node, removing old one                 newNode.costToGoal(goalLoc);                 // delete the old details (if they exist)                 closed.delete( newNode.getPoint( ));  // may do nothing                 open.delete( newNode.getPoint( ));   // may do nothing                 open.add(newNode);               }             }           } // end of for block         } // end of if-else         closed.add(bestNode);       }       return null;   // no path found     }  // end of aStarSearch( )

The code is simplified by being able to rely on the TilesList and TilesPriQueue classes to represent the closed and open lists. They store tile information as TileNode objects. TilesList is essentially a wrapper for an ArrayList of TileNode objects, with additional methods for finding and deleting a node based on a supplied coordinate. TilesPriQueue is a subclass of TilesList and stores TileNodes sorted by decreasing node score (i.e., the highest scoring node comes first).

Moving the AlienAStarSprite

AlienAStarSprite overrides AlienSprite's move( ) method, so the next move is to the next tile in the path calculated by the A* algorithm:

     protected void move( )     {       if (pathIndex == path.size( ))  // current path is used up         calcNewPath( world.getPlayerLoc( ) );       Point nextPt = (Point) path.get(pathIndex);       pathIndex++;       int quad = whichQuadrant(nextPt);       setMove(nextPt, quad);     }

If move( ) finds the destination of the current path has been reached (i.e., the sprite has reached the goal node), it will initiate the calculation of a new path by calling calcNewPath( ).