Saturday, October 15, 2016

Tech Talk: NPC Pathfinding in Nox Archaist: Part I


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.

2 comments:

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

    ReplyDelete
    Replies
    1. Glad 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.

      Delete