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 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.
