The rpg-project -- The A* algorithm

The A* algorithm

This page will not explain how to program the A* algorithm, but it will try to depict how it all works graphically.

In general, the A* (A-Star) algorithm is used in most games to realise the way finding of game characters. For this purpose, the whole game world is divided into little squares, and for each of these a value is stored, which defines whether the square is easy - more difficult - or impossible to be walked on.

In the two pictures below, the red squares mark regions, where it's not possible to walk. The blue squares are the data copied and recalculated for the figure which is walking. To find out, which way is the best, some free squares are observed ("expanded" in technical terminology). Those squares are the yellow ones.

To find the shortest (and easiest) path, for each of those yellow squares three values are calculated:

The cost to get to this point
The estimated cost to the target point
The sum of both which estimates the total cost

The goal is to find the path with the lowest cost from source to target point. To achieve this, some well thought out strategies and algorithms are applied. More detailed information on those algorithms and implementations can be found through the web.

For the Tales of Trolls and Treasures rpg-project the A*-algorithm was implemented in a very special, tailored way. Because A* is very slow in general, a lot of optimations and improvements were made due to the execution speed.

If you have questions about this topic, please go to the contact section.