Tech Talk: NPC Pathfinding in Nox Archaist: Part III

An A* Implementation for the Apple II

Our mission for the Nox Archaist project is to explore how tile based RPG games may have evolved if significant development on the Apple II had continued beyond the 1980s.

One of the evolutions we explored was improving the intelligence of NPCs, and this is the third posting in a three part series of Tech Talk in which will discuss this topic. 

Before we begin:

Click here for Part I.

Click here for Part II.

This image contains a demonstration of Nox A* in action.

TOWN NPC SNEAK PEAK

The white character twirling a spear is the player and the other is an NPC whose movements are controlled by the algorithm.

====Solving the Resource Challenges====

Even with the modifications mentioned in Part II, it became quickly apparent that using A* in our environment resulted in unacceptable gameplay delays if the algorithm was used to calculate a path each time an NPC moved. The solution was twofold.

To solve the speed problem, Nox A* anticipates paths needed by NPCs who are scheduled to be in a different location in the next few game hours. These paths are calculated in the background and saved to auxiliary memory for future use. The Nox A* subroutine is designed to abort after 5 iterations if a player key press is detected and to resume after the player key press is processed. As a result, the player can go about his or her business in the town without observing significant delays in gameplay.

To solve the A* memory problem, we took advantage of the modular architecture we designed in the game engine. The main Nox Archaist engine resides in memory up to $9FFF and $D000-$FFFF. A swap area is reserved from $A000 - $BFFF where modules are loaded from disk for functions like NPC conversations, inventory management and combat. A* builds its database in this swap area, and when that area is needed by a module the A* database is swapped out to auxiliary memory.

Did anyone notice the logical hole in what we’ve said so far? J We mentioned that Nox A* enables NPCs to navigate around dynamic obstacles like the player and other NPCs. We’ve also said that paths are calculated in advance rather than every time the NPC moves. How is that possible, considering that the exact position of dynamic obstacles is not known in advance? 

This was a fun problem for us to solve. If you think you know the solution, email us at contest@6502workshop.com before Nov 30, 2016. The first response with the correct solution will receive a complimentary 5.25” floppy disk copy of Nox Archaist when the game is available, targeted for 2017.  The answer will be posted in the December 31, 2016 issue of Juiced.GS and on our blog.