Saturday, October 15, 2016

Tech Talk: NPC Pathfinding in Nox Archaist: Part II

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 second posting in a three part series of Tech Talk in which will discuss this topic. 

Before we begin:
Click here for Part I.

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.



===Inside Pathfinder Algorithms===
 
A* combines the principles of several pathfinding algorithms, which we’ll review as a starting point.

Consider the villager NPC in figure 1. How did the villager figure out which tiles to walk on to locate the door and enter the town hall without bumping into a few walls? The human brain can easily see a path between any two tiles on the map. We “see” the whole map at once. However, for a computer to find a path it must examine one tile at a time.


Figure 1: A villager makes his daily visit to the town hall.

The examination process involves looking at each tile to see which paths (north/south/east/west) are open and which paths are blocked by obstacles. One approach to pathfinding is for the computer to examine every tile on the map and store the open paths for each tile in a database, then look for a combination of tiles with open paths that connect the starting position to the destination. This approach is known as the Breadth First Search algorithm. It gets the job done, but it is very CPU intensive and not practical for our application. It also doesn’t take into consideration variable movement costs for terrain. For example, hills might be slower to move across than flatland.   

To start building the database, in the first iteration the algorithm examines the tiles adjacent to the starting position. Any open paths are added to the database as “neighbor tiles”. After the algorithm examines all start tiles, it examines one of the neighbor tiles it found in the first iteration and adds any new neighbors found to the database. The process of acquiring neighbors and examining neighbors continues until all tiles on the map are examined.

A more advanced algorithm known as Greedy’s Best First Search dramatically reduces the CPU cycles required by examining only a small subset of the total tiles on the map. This algorithm prioritizes by maintaining a neighbor tile queue and sorting the queue by distance with every iteration. Tiles with a shorter distance to the destination are examined first. Distance refers to the number of tiles to the destination, ignoring obstacles.

A* incorporates the techniques in Greedy’s Best First Search for finding the shortest distance and adds a terrain movement cost component to determine the shortest path.  The process is similar to the techniques used in the modern day networking protocol OSPF (open shortest past first).


========Optimizing A*========

Adding Realism & Randomness
While A* does a great job of finding the shortest path, we didn’t want our NPCs to suffer the boredom of following the same routes day in and day out. Realistically, a merchant is of course not always going to take the exact same route home every day. Not to mention, bored NPCs might mutiny and ruin the game for everybody. Just sayin’.

We found a way to inject realism into path selection and speed up the algorithm at the same time and we call this implementation Nox A*. Our method doesn’t sort the prioritization queue nearly as often as Greedy’s. With Nox A* if a new neighbor tile is found with a shorter distance to the destination than the last tile examined, the new tile is examined immediately and the queue sort is skipped for that iteration. For some paths this decreases the CPU cycles required by over 400%.

By skipping instances of queue sorting, the Nox A* algorithm will miss shorter routes that it might find if it sorted every iteration. As a result, Nox A* causes NPCs to take a slightly meandering path between two points.  However, with this change alone, the path would still be the same every time. An additional modification was needed to inject some randomness into the path chosen.

Since Nox A* immediately examines a new neighbor tile if its distance to the destination is less than the last tile examined, the order in which new neighbor tiles are identified impacts the algorithm’s prioritization. For example, if the algorithm searches for new neighbors in the order of north, east, south, west, then the tiles to the north will always be preferred over tiles to the east even if both tiles are the same distance from the destination and have the same movement cost.

Nox A* randomizes the order in which new neighbors are searched which results in NPCs not always taking the same path between two points. This effectively prioritizes the directional choices. Consider the villager in figure 2. To make is easier to see the possible paths this NPC might take to reach the X, we’ve turned the Nox Archaist line of sight algorithm off that normally hides tiles behind obstacles such as walls and mountains. The impact of the directional priority calculation on the path selected is as follows:
Priority 1 = west, priority 2 = south: left/outer path will be taken.
Priority 1 = west, priority 2 = east: left/inner path will be taken.
Priority 1 = east, priority 2 = south: right/outer path will be taken.
Priority 1 = east, priority 2 = west: right/inner path will be taken.

Figure 2: Possible paths an NPC might take

The directional priority is randomized many times during the process of calculating a path. As a result, calculating a path between two points over a long distance with a lot of corners will result in many small variances.

Stay Off the Grass!
Another important piece of functionality is obtained through the use of movement costs assigned to tile types. For example, Nox A* treats floor and street tiles as having a lower movement cost than all other terrain. This is how we keep NPCs from taking bizarre routes around town like traipsing through neighbors’ lawns and schlepping through farms fields, all in the name of taking the shortest path. We were also lobbied heavily by the shopper keepers guild to make sure NPCs walked past their shops instead of taking shortcuts.


Detecting Player Harassment
Having the ability for NPCs to figure out how to get around obstacles, including the player and other NPCs, may create the temptation for the player to block the path of the NPC repeatedly. For example, every time the NPC tries to move around the player, the player moves to block the NPC’s path again. We can detect this by incrementing a counter each time an NPC is blocked by the player and this allows for event triggers if the counter reaches a specific value. For example, the NPC might tell the player “Get out of my way!”.





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.



Thursday, October 6, 2016

Sneak Peak: Towns and NPCs


https://juiced.gs


Juiced.GS Magazine recently published an article we wrote providing a technical overview about Nox A*

Nox A* is a custom developed algorithm that NPCs in Nox Archaist use to figure out a route to take when traveling between locations on a town map at scheduled times throughout the day. For example, a blacksmith might be found at home, at his/her shop, or at the local eatery depending on the time.

The demo video below shows Nox A* in action, featuring a merchant walking from her living quarters to her store front.

Stay tuned to our blog for the premier of our first town featuring:
  • Interactive objects such as portcullis, levers and doors.
  • Many animated graphics such as fountains, wells, fireplaces and more!
  • Dozens of NPCs moving about the town on their daily schedules.
  • Conversation with NPCs in a pop-up window. 
Many thanks to our new team member Bill Giggie for his recent work on the town artwork. Bill is a professional graphics animator in the movie industry and is really helping bring the world of Nox Archaist to life!



TOWN NPC SNEAK PEAK