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:
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!”.
