HTML5 Canvas, 2nd Edition

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 Figure 8-8. As you can see, there is only one straight line that an object can move in on this simple 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 ...