The A-Based Alien Sprite

The Quadrant-Based Alien Sprite

AlienQuadSprite is a subclass of AlienSprite and overrides the playerHasMoved( ) and move( ) methods . AlienQuadSprite has the same basic statechart as AlienSprite (shown in Figure 13-15), but the plan move and move states are different.

In the plan move state, the alien calculates a quadrant direction ( NE , SE , SW , or NW ). The direction is chosen by finding the nearest pickup point to the player, and then calculating that pickup's quadrant direction relative to the alien. This gives the alien a "pickup-guarding" behavior, as the alien then moves towards the pickup that the player (probably) wants to collect.

Planning a Move

playerHasMoved( ) calculates a quadrant direction for the sprite:

// global
    private int currentQuad;


    public void playerHasMoved(Point playerLoc)
    {
      if (world.hasPickupsLeft( )) {

        Point nearPickup = world.nearestPickup(playerLoc);
               // return coord of nearest pickup to the player
        currentQuad =

calcQuadrant

(nearPickup);
      }
    }

    private int calcQuadrant(Point pickupPt)
    /* Roughly calculate a quadrant by comparing the
       pickup's point with the alien's position. */
    {
      if ((pickupPt.x > xTile) && (pickupPt.y > yTile))
        return SE;
      else if ((pickupPt.x > xTile) && (pickupPt.y < yTile))
        return NE;
      else if ((pickupPt.x < xTile) && (pickupPt.y > yTile))
        return SW;
      else
        return NW;
     }  // end of calcQuadrant( )

calcQuadrant( ) could be more complex, but the emphasis is on speed. playerHasMoved( ) and calcQuadrant( ) will be called frequentlywhenever the player movesso there is no need to spend a large amount of time processing a single move.

This is an example of the common tradeoff between accuracy and speed. calcQuadrant( ) is called often, so should be fast and doesn't need to be accurate since any errors will be smoothed out by subsequent calls. Also, I don't want to make the alien's behavior too sophisticated or the player will always be caught, which isn't much fun.

This kind of deliberately inaccurate algorithm needs to be tested in real gameplay to ensure that it's not too inadequate, and perhaps to see if it can be simplified more.

Moving the AlienQuadSprite

The sprite tries to move in the currentQuad direction. If that direction leads to a no-go tile or a tile holding a block, then the sprite randomly will try another direction.

protected void move( )
    { int quad = currentQuad;
      Point newPt;
      while ((newPt = tryMove(quad)) == null)
        quad = getRandDirection( );
        // the loop could repeat for a while,
        // but it should eventually find a way
      setMove(newPt, quad);
    }

The use of a randomly chosen direction when the sprite is blocked may lead to it repeatedly picking a blocked direction, especially if it's stuck in a cul-de-sac. This is unlikely to be a problem for long, and this kind of suboptimal behavior is endearing to a player who is use to being chased at close quarters by deadly aliens .

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.

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( )

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);
    }