Pathfinding

One of the first algorithms to be implemented and tested in game development - especially in strategy games - is pathfinding. In “Renaissance Builders”, pathfinding should ensure that units can move reliably and efficiently along paths and roads, take into account dynamic changes such as the construction or demolition of paths and perform heuristic calculations to determine the shortest path.

With Navmesh, the Unreal Engine offers a powerful pathfinding solution that we use for navigation in open terrain. However, to ensure that units prefer roads and orient themselves along them, we need our own pathfinding implementation for these special scenarios. The A* algorithm is the obvious choice here.

The classic implementation of A* is based on dividing the entire map into an x-y grid, taking obstacles such as buildings into account and prioritizing certain paths by weighting them. Path finding is then carried out within this grid from node to node.

Classic pathfinding grid that covers the entire map. Red are blocked nodes and green are walkable nodes.

However, this method has considerable disadvantages in an open-world environment: a complete x-y grid with fine resolution would be extremely memory-intensive and inefficient, as the number of nodes and possible paths increases exponentially. In addition, it is unnecessary to capture the entire terrain, as the Navmesh already takes care of navigation in open terrain.

For our own pathfinding, therefore, only the areas that represent actual paths and roads are of interest. It is sufficient to create a reduced grid that only covers these elements. When new roads are built, new nodes are automatically generated, which are placed at short intervals along the course of the road and integrated into the pathfinding. When roads are demolished, the corresponding nodes are removed again.

In order for units to be able to move within the grid, each node only needs to know its directly connected neighbors. When streets are created, the new nodes are immediately assigned the IDs of their neighbors, creating a continuous line of connected points. In addition, new nodes must be compared with existing nodes in their vicinity in order to detect overlaps. In the event of an overlap, the nodes involved are linked to each other, ensuring seamless connections between road sections.

Pathfinding queries can then be processed using a classic A* algorithm within this specialized grid.

In this way, a lightweight, dynamic pathfinding system can be implemented that reflects the organic shapes of the paths in “Renaissance Builders” and works efficiently in an open-world environment.

Our solution, in which only new nodes are created on the roads and these are linked to each other