Procedural Content Generation for C++ Game Development

A breakdown of A*

Before we start coding our own A* implementation, it will do us good to break down the algorithm into its key areas and take an isolated look at each.

Representing a level as nodes

Perhaps the most important area of understanding when we look at A* is how the algorithm will view our level. While we see tiles, the pathfinding algorithm sees only nodes. In this context, a node just represents a valid location that an entity can move to within the level.

How nodes are defined differs from game to game. For example, in our game, the level is already described as a 2D array of tiles. Therefore, each tile in that grid will act as a node. In 3D games however, we don't have this grid so navigation meshes are used to create a surface that ...