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