Path finding is the art, or is it theory, of calculating the best route from A to B. This isn’t always straightforward, particularly when solid obstacles are placed in the way.

The A* algorithm is one of the most commonly used methods in games these days, and to avoid this web page turning into a book, I’ll keep this overview of the techniques involved as simplistic as possible - in doing so, I may take a few liberties with some of the more in-depth stuff so please excuse me if I miss anything out.

The little demo game above shows my experiment in using A*. To test it, you simply drag the green target to a new location and click the ‘GO TO TARGET >’ button. The little yellow dot will then speed off, making its way to the target.

How does this work? Well, for a start the dot sees the maze as a grid made up of squares - in this case each square is 5 x 5 pixels. A higher resolution (e.g. 1 x 1) would have led to greater accuracy, and 8 x 8 might have satisfied the true tile-game traditionalists, but 5 x 5 it is. The lack of resolution adds to the retro feel, and also helps to show that there is actually a grid involved here, giving slightly clunky turns around corners.

The grid is referenced, as in all tile-games, as a list (or array). Within the list are sub-lists. This grid is 128 squares wide x 96 squares high (640 x 480 pixels divided into 5 px segments). The list has 96 items (one for each row), and each item is in turn a list of 128 items (one for each unit in the row). Examining item [10][128] for instance would reveal the value stored in the last item of the 10th sub list. The values stored in the list are either 10 or -1, representing clear space (black) or solid walls (red) respectively.

When you click ‘GO’ the little dot starts to calculate the best way to the target. In simple terms it will start from it’s own location, and move out a square at a time, either accepting them as possible moves, or rejecting them either because they’re a solid wall or they ‘cost’ too much. It calculates the expense of a square by adding 10 points for each square it would travel from the starting point to get there, and also adding 10 for each additional square it ‘thinks’ there will be left for it to reach the target point following the current path (this is essentially a well-educated guess - google heuristic’ and you will find plenty of people who can explain it better than I can). It will do this until it reaches the target square. By this point it’ll have several likely routes to take, so it does a quick track backwards with the same calculation and arrives at the start point having decided the ‘cheapest’ route. All of this without moving at all! Once a list of squares to visit on the journey is ready, the dot simply travels through them.

You might wonder why I bothered giving clear squares a value of ten, when one would have done just as well. The reason is to allow scope to introduce other types of squares, which may have a lower cost when used on the journey, paths for instance as opposed to rough terrain would have a lower cost and therefore a lower value assigned to them. It’s using the algorithm in this slightly more advanced way that makes games more interesting and, when workload allows, I’ll work up a more game-like example of path finding across different terrains, as well as tidy up my code a little to avoid some of the slight errors of judgement that the dot makes occasionally.