Further Reading


Storing Tile Details

A TileNode object stores details about a particular tile node, which are used by the A* algorithm when it looks at that node. The most important are values for the getCostFromStart( ) and costToGoal( ) functions so the overall score for the node can be worked out.

As explained in the last section, the getCostFromStart( ) function is the cost of the path that leads to this node from the starting tile. This algorithm's precise definition will vary from game to game, but I use the simplest measurethe length of the pathwith the step between adjacent tiles assigned a value of 1. costToGoal( ) estimates the cost of going from this tile node to the goal.

This is a little harder to calculate in AlienTiles due to the staggered layout of the tiles as detailed below.


Each TileNode stores a reference to its parent, the tile node that was visited before it. The sequence of nodes from this particular tile node back to the starting tile defines the sprite's path (in reverse).

Calculating the Cost to the Goal

costToGoal( ) TReats the tile coordinates of the current tile and the goal as points on the XY plane and calculates the length of the floor of the straight line between them:

     public void costToGoal(Point goal)     { double dist = coord.distance(goal.x, goal.y);       costToGoal = Math.floor(dist);     }

However, the tiles are positioned in staggered rows, which means the straight line distance can be an inaccurate measure. Therefore, the costToGoal( ) value may not be less than or equal to the cheapest path, so the path found by A* may not be optimal. However, the calculation is simple and fast, and the path is sufficient for AlienTiles.

This "sufficiency" was checked by playing the game and seeing how quickly and accurately the AlienAStarSprite sprites closed in on the player. The algorithm is arguably still too good since the aliens almost always take the shortest path to the player and are very fast.


The reason for using Math.floor( ) can be justified by considering an example. Figure 13-18 shows the four adjacent tiles to tile (1,3).

Figure 13-18. Tiles adjacent to (1,3)


Figure 13-19 maps the five tile points to a rectangular grid and shows the straight line distances between them.

Figure 13-19. Straight-line distances between the tiles in Figure 13-18


The cost of moving to a neighbor is 1 in all cases. However, the straight-line distances to two of the tiles (the north east and south east ones) are the square root of two. Fortunately, the floor of all the distances is one (1.414 is rounded down to one), which makes the cost function optimal.

The Math.floor( ) solution works for adjacent tiles but is less successful when the straight-line distances span multiple tiles.



Killer Game Programming in Java
Killer Game Programming in Java
ISBN: 0596007302
EAN: 2147483647
Year: 2006
Pages: 340

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net