Pathfinding-System

Pathfinding

Since the entire resource distribution system is realised via cart-pusher NPCs (e.g. there is no “beaming” of resources or products) and furthermore NPCs also distribute the final products to residential buildings, a lot of pathfinding has to happen.

The worst case, performance-wise, for any pathfinding algorithm is when a path is requested from point A to point B, but there is no connection between these two points. Every pathfinding algorithm can only find that by exhausting the complete search space. Since we have relatively many NPCs active at the same time, a repeated occurrence of this case would lead to catastrophic performance. Therefore, we have to avoid this case at all cost.

In terms of pathfinding, our NPCs can be classified into two groups. Firstly, there are NPCS that only walk on roads and secondly, there are NPCS that walk freely on the landscape. These two types require two different solutions.

First type: NPCs who only walk on streets:

The streets in a city form a graph structure. Every crossing and curve forms a node in this graph. As the player builds his city this graph has to be updated incrementally. Depending on the action of the player, a new node may need to be added or removed. If the player places a street so that different street-networks gets a new connection between them at least two graphs have to be merged, or if the player deletes the last connecting street tile, a graph has to be broken up into two to four subgraphs. There are quite some corner cases to handle.

Every building in the game has, at least one, so called “access point”. These access points can be added as nodes into the existing graph (or form a new graph if they are alone).

For example, if a production building is done with its work it wants to send a cart pusher to the next storage. Therefore, it has to determine where to spawn the NPC and to which storage it should send it. To achieve that it first finds the nearest storage and determines if the storage has space for the specific resource. Then it tries to find a combination of access-points (one from itself and one from the storage) so that this pair of access-point belong to the same graph. If that is possible there has to be a path between these two buildings, and therefore it can spawn the cart pusher NPC and do a pathfinding request.

Second type: NPC’s who walk over terrain

These are typically resource gathering NPCs, for example a lumberjack. They spawn at their building and want to go to the next tree in the forest to harvest some wood. They need to evaluate if it is possible to reach their desired tree without doing pathfinding. To be able to do this, we have a so called “Segmentation Layer” and a segmentation graph.

The segmentation layer is generating directly after the world generation. Each tile gets assigned an id which identify its segment. All tiles in the same segment are trivially connected. Every tile which is reachable without going over cliffs or over water gets assigned the same id. To be able to generate this in a reasonable time frame a scanline fill algorithm is used, as simple flood fill was quite a bit slow.

From this data graphs are being constructed. At first each id/colour is one graph with one node. On placement (or removal) of slopes/bridges (e.g. stuff which connects different segments) these graphs are merged or split. These updates of the graph only need to happen if the first connection between different segments is made, or if the last connection between different segments is being removed, therefore it is also required to keep track of the amount of connection between different segments.

The lumberjack NPCs now can evaluate if it can reach his desired tree. To do that it need to check in which segment it is and compare that with the segment id of the desired tree. If it is the same, it is definitely possible to find a path. Otherwise it needs to get the graph which holds the lumberjack’s current segmentation id. Then this graph is queried if it also contains the segmentation id of the desired tree. If it does there has to be a valid path from the lumberjack to the tree. Therefore, the lumberjack can issue a pathfinding request, otherwise the lumberjack needs to choose a different tree and redo the same procedure.