Tech Talk: NPC Pathfinding in Nox Archaist: Part IV

In an earlier blog post about the A* based algorithm we developed in Nox Archaist for NPC pathfinding, we challenged readers to solve the following puzzle and promised to publish the solution.

How does Nox Archaist enable NPCs to navigate around dynamic obstacles like the player and other NPCs even though paths are calculated in advance rather than every time the NPC moves?

For NPCs in transition from one map location to another, the Nox Archaist movement manager will select a move from the precalculated Nox A* path only if the path coordinates are not blocked. If the path coordinates are blocked, then the movement manager identifies the next unblocked path coordinate and uses a simple flocking algorithm to select the next move. The next unblocked path coordinate is the flocking point. 

The flocking algorithm determines the direction of the flocking point relative to the NPC, without considering obstacles. For example, if the flocking point is to the west, then the NPC will move west. If the flocking point is to the northwest, then the NPC will move either north or west, determined by a random number. If the move is blocked, then the NPC moves in a random direction and will try again next turn.

Since flocking algorithms are very simple, it is certainly possible for a NPC to wander off and not find its way back to the Nox A* path. We’ve found that this is unlikely because single tile obstacles like the player or another NPC are pretty easy to navigate around. In the rare cases where an NPC does get a bit lost, we expect this behavior will add some life to the game and keep the player on their toes.