A* Path Finding Demo

I found the A* algorithm interesting when I first read about it so I set about writing a demonstration implementation of the theory that I had learnt.

The demo application allows a tile map to be drawn or generated and then allows the A* algorithm to be run or single-stepped on the map in order to determine the quickest route between the specified start and end tiles.

Tile maps consist of: empty tiles that can be moved over; wall tiles that cannot be moved over; and “slow” tiles that add a movement penalty (e.g. in the context of a game this could represent hilly ground). Random maps can be generated using a depth-first algorithm to generate solvable mazes.

The A* algorithm implementation has a few options available: diagonal movement can be switched on or off; there is an option of using either the Manhattan or euclidean (diagonal shortcut) heuristics; and the algorithm can be run all in one go or one step at a time allowing the search progress to be visualised.

The demo can be downloaded here including the compiled binary and the C++ source code.