Killer Game Programming in Java

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 ...