A* Pathfinding

A* Pathfinding

This is an implementation of an A* (star) pathfinding algorithm in a 2D grid based system with random terrain generation with multiple terrain types and the ability to route to specific mouse positions in real time.

The algorithm for the pathfinding runs frame agnostically and can be added to a project with a single code file.

I created this program with SDL2 and although the algorithm does rely on it for SDL point objects, these can easily be removed or modified for an SDL-less implementation.

Browse Source Code

View the GitHub page.

The algorithm works by calculating the distance between the current tile and the end goal, along with the cost to move to that tile based on the terrain value of the tile and the angle of movement.

Each pass adds a pointer to the tiles into either an open node vector (tiles to be checked) or a closed nodes vector (tiles that have been checked). The lowest cost of each tile in the open list is checked at each pass until there are no more tiles with the lowest cost remaining. After this occurs we exit the pass and re-sort the open nodes to find the new lowest value, this also helps with keeping the algorithm frame agnostic by checking our time for the set of cycles in this current frame.

Once the goal has been reached we use the parent node of tiles that was set when they were added to the open nodes vector. This parent node allows us to trace back from each node to the original source title thus giving us our path. Seeing how each parent node is only ever set when they are added to the closed nodes vector the final result will be the shortest route every time.

The included application shows off a number of features of the algorithm, such as the ability to enable or disable the use of diagonal movement and routing towards the path (forced path recalculations mid movement).

Environmental variables can be changed to create environments with more walls or water etc. to make a more diverse path calculation.