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.
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.
This is awesome. I've always wanted to program on the Apple2 as my older brothers did growing up. I started program for the dos environment and never got around to trying on the Apple2. I recent acquired an apple //e and this is motivating me to start!
ReplyDeleteGlad you enjoyed it! It's funny, it was my older brothers programming on the Apple II that initially motivated me as well. It is great fun. Congratulations on acquiring an Apple II! Feel free to post any questions. I don't have all the answers by far, but I'm happy to help if I can.
Deletehmmmm
ReplyDelete