Applying the A* Algorithm

To use the A* algorithm in a game, you'll have to interpret the game environment as a graph-or, in other words, decide what the nodes and edges represent. In a top-down, tiled-based world, this is easy: The nodes represent the tiles, as in Screenshot. In this figure, the game environment is laid out on a hexagonal grid, and you can travel from one tile to any of its six neighboring tiles (unless one or more of the neighboring tiles is an obstacle).

Screenshot A tiled-based game can easily be interpreted as a graph.

In this case, the distance between neighbor nodes is the same, but the cost between neighbor nodes doesn't have to be. As mentioned before, you could make traveling on some tiles, such as muddy sand, take longer than on other tiles, such as sidewalks. If the tiles were square, traveling diagonally would have a greater cost than traveling straight north, south, east, or west because the diagonal distance between two square tiles is greater. One benefit of a top-down, tile-based world is that it's easy to dynamically modify the graph. If the player blasts a tile, changing it from an obstacle to a grassy area, the graph can be easily updated. However, tiled-based worlds aren't the only situation in which you can use the A* algorithm.