A* Pathfinding Algorithm

A* Pathfinding

During my second year of university, I developed an A* pathfinding algorithm in TL-Engine with C++ to enable game agents to navigate about a grid based map.

The core concepts behind A* are that each movement is assigned a cost by analysing the cost of moving to a specific tile, and a heuristic which is typically the distance of the tile from the player. A* is a commonly used pathfinding algorithm due to the fact it is very efficient and guarantees finding a way to the destination if a route is available (although not always the fastest route).

The video to the right demonstrates the game agent navigating about various different maps. The tiles demonstrated in the video are as follows.

  • Black tiles are walls and cannot be crossed
  • Grey tiles are path and have a cost of 1
  • Brown tiles are wooded areas and have a cost of 2
  • Blue tiles are water and have a cost of 4
  • Tiles are coloured purple once explored
  • Tiles are coloured green once chosen as a route
  • Tiles are coloured red when they are placed on the list to explore