Tech Talk: NPC Pathfinding in Nox Archaist: Part I

6502 Workshop's Nox Archaist
6502 Workshop's Nox Archaist

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 evolution we explored was improving the intelligence of NPCs, and this is the first posting in a three part series of Tech Talk in which will discuss this topic.
Tile-based RPGs of the era such as the early Ultima games, Deathlord (cira 1987) and Shadowforge (circa 1989) typically used a flocking style algorithm which enabled NPCs to move randomly while tethered to a specific area of the map. The most advanced implementation we found was in Ultima V (circa 1988), where most NPCs traveled between locations on a town map at scheduled time throughout the day. For example, a merchant might be found at home, at his/her shop, or at the local eatery depending on the time.
This feature was likely achieved by storing a hard coded set of x,y coordinates between locations. We observed Ultima V NPCs always took the same path and, if the player blocked that path, the NPC would stop in front of the player. Forever.
We saw an opportunity to improve gameplay by enabling NPCs in Nox Archaist to take different paths sometimes, navigate around the player and other NPCs, and detect player harassment. To this end, we decided to attempt the first ever (to our knowledge) implementation of an A* based pathfinder algorithm for regional maps in an Apple II tile based RPG.
Peter Hart, Nils Nilsson and Bertram Raphael of the Stanford Research Institute first mathematically described the A* algorithm in 1968. The documented history of the algorithm is sketchy on what happened next. It was likely implemented first on computers using low level languages such as C. Modern computers can effectively run the algorithm using almost any language. A* based algorithms have been used in many games such as Age of Empires (circa 1997) and Counter Strike (circa 2000). The challenge to implement it effectively on the Apple II was twofold:
1) How to fit it into very limited memory.
2) Make it fast enough so that the gameplay wouldn’t slow to a crawl.
In the next two posts in this series we talk about how pathfinding algorithms work, how we solved these challenges on the Apple II platform using 6502 assembly language, and how we optimized our implementation of the A* algorithm (Nox A*) for improved game play.
This image contains a demonstration of Nox A* in action.


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

This post was originally published on this site.