HTML and CSS Reference
In-Depth Information
What Is A*?
A* is a grid-based path finding algorithm used to find the shortest “node” path from point A
to point B. A* is best implemented on a grid-based game screen where we consider each tile
of the grid to be a “node.” For example,
Figure 8-8
shows a simple grid made up of tiles from
a tile sheet.
Figure 8-8. Simple 5×5 tile map
In this simple five-column and five-row tile map, we have only two types of tiles. The gray
tiles are “movable” tiles, meaning that game characters can occupy those tiles, while the blue
tiles are “walls.” Wall tiles are tiles that no game character can occupy. As you can see, there
are only three movable tiles on the
Figure 8-8
tile map.
A* can be used to find the shortest path between two points on a map, as illustrated in
Fig-
ure 8-8
.Asyoucansee,thereisonlyonestraightlinethatanobjectcanmoveinonthissimple
map. Using 0,0 as the index of the first tile, the column that extends from row 0, column 1
to row 2, column 1 is this straight vertical line. This is of no use to us in practice, because
you would not need any type of path finding algorithm to figure out that a game character can
move on only those three tiles, but we are going to start simple and get more complicated as
we proceed. A* is a very useful tool, and although we are not going to code our own library
here, we will go over the basic pseudocode for the algorithm.
David M. Bourg and Glenn Seeman, in
AI for Game Developers
(O'Reilly), describe A* this
way:
A*usesnodestocreateasimplifiedsearchareatofindtheshortestpathbetweenanytwopoints.
They also provide the following simplified A* pseudocode:
//*** A* Pseudo code from AI For Game Developers
//*** David M. Bourg
//*** Glenn Seeman
//*** O'Reilly (R)
add the starting node to the open node list
