• # Knowing the Path

Game Design and Theory

The player is presented with a new environment, having just battled his way past a hoard of enemies. The new environment is a network of corridors and rooms - and throughout the environment are enemies, bonuses, and other interactive items. The player explores the environment, taking out the enemies, collecting the bonuses, and discovering the interactive items. Now, take two. The NPC is presented with a new environment, having just been generated by the engine. The new environment is a network of corridors and rooms - and throughout the environment are enemies, bonuses, and other interactive items. The NPC heads straight for the nearest room, because it can see from the nodegraph that there is a bonus there, and then takes a route through the environment that avoids and evades all enemies. The framerate drops a little as the route is recalculated each step, to account for enemy movements. The player watches in disbelief. Sound familiar? This article is going to discuss a method for avoiding this: something I call an 'expandable path table.' It allows NPCs to both navigate through an environment, and to explore and learn it, rather than being presented with the entire thing. It's also faster than constantly recalculating a route. [size="5"]Before we start You'll need to know a pathfinding algorithm. I used Dijikstra's algorithm when researching - but the A* algorithm, or any other algorithm for finding a path through a network of nodes, will do fine. [size="5"]The Problem

The above network represents my level. The nodes are significant points - such as junctions, rooms, or corners - and the lines represent the routes between them. There are no weights on this network, but they could easily be added in a real situation (i.e. the length of the routes between the nodes). The NPC is my enemy and needs to track me through the level. I'm moving around, and so is it, so it needs to recalculate the route to my position each step. (For this article, we will assume that the NPC and I can only be at a node at any given time - in a real situation though, it could be assumed that a node will have a line-of-sight to all nodes that it connects to, so the NPC could move to the node nearest to me and be able to shoot at me). Now, while it will depend on your pathfinding algorithm, recalculating a path each step isn't fast. Especially with an algorithm such as Dijikstra's, which sometimes involves labeling the entire network. Ideally, we need a method to store all the routes between nodes beforehand. [size="5"]A concept If the shortest route from node A to node D is ABCD, then the shortest route from A to C must be ABC. I haven't yet found a case where this isn't true. For Dijikstra's, the shortest distance (and therefore, route) to each node in the network is found, and the algorithm depends on it being true. I'm not going to try and disprove it. :-) [size="5"]How does this help? As I said, we want some kind of way of pre-calculating all possible routes. Some nice data structure that we can look stuff up in - such as a tree - or, rather, a matrix. Here's the matrix we're going to use for the problem I described earlier:  To From A B C D E F G H A B C D E F G H
That'll be nice, won't it? Look up where we are, where we're going, and get... what? The answer: the next node we need to move to. I'll fill out the matrix for the network above, quickly.  To From A B C D E F G H A - B B E E F F F B A - C C A A C A C B B - D D G G G D E C C - E G G G E A A D D - F F F F A A G G E - G H G F C C D F F - H H F F G G F F G -
Does that make sense? Trace the route from any one node to another, quickly. For example, B to H.

B->H: Move to A A->H: Move to F F->H: Move to H GOAL

That demonstrates that we've got a very simple algorithm on our hands. The matrix is also easy to build, too - you just calculate the route from the 'from' node to the 'start' node, and store the first node in the route (excluding the start node itself). This network is also a little special because there are no dead ends - that is, nodes with only one connection. If there were - and in real situations, there would be - that row in the matrix is easy to do, as there's only one option for each cell. Now, what about the original problem of trying to track me? I'll show a sample 'game,' with the NPC's moves on the left, and mine on the right. Let's say that the NPC starts at node A, and I at node C. I don't know the level very well, so I may make some bad moves from time to time, but it demonstrates the AI.  A->C: Move to B C->D B->D: Move to C D->E C->E: Move to D E->F D->F: Move to G F->H G->H: Move to H Aargh!
In each case, all the NPC needs to do is to know my position, which it can use to look up where to move in the table. It's fast, no? Sure, if I'd played a little better, I could have had it running around in circles for as long as I felt like. That's partly because of the level, and partly because the bot doesn't have the option to 'rest.' If the bot stopped to rest (or, for that matter, if I did) then the outcome would have been different. Also, if there were other goals, the bot may have chosen to take a different route to pick up a bonus on the way. Ultimately, I guess, it's just a version of the Terminator algorithm (or 'tracker,' but I like Terminator better :-) ) applied to a network. Still, it's useful. [size="5"]Cheating Let's return to the scenario I originally presented you with, of the NPC entering a new environment. Rather than exploring, it uses a pre-calculated network to find the optimal route and reach its goal immediately, rather than having to explore. The matrix method that I've just demonstrated can be expanded for education. The mind is a little more complicated, but it's still understandable. [size="5"]Learning the path Another level:

This one's a little more complex. The blue lines represent walls. We can build two extra tables from this that we'll need later. The first one is one that I will call our VIS table - it contains information about which nodes can 'see' which other nodes. Our bot will only 'learn' about the existence of a node when it 'sees' it.

Sight Table - T: TRUE, BLANK: FALSE

 To From A B C D E F G H I J K L M N O P A - T T T T B T - T T T C - T T D T - T T E T T T - F - T T T G T T - T T H T T - T T I T T T - J - T T T T K T T - T T L T T T - T M T T T - T N T - T O T T T - T P T T T T -
(Yes, it is symmetrical along the To=From line - because we're working on the premise that if A can see B, B can see A. I can't think of a practical application where this isn't true, but if you can, kudos to you. :-) ) The second table we can build - a much smaller one - is a magnitude table. It lists the number of connections each node has. I won't do it yet, as we don't pre-build it, we build it as we go along. OK. Let's say that our bot starts at node A. He knows only node A, and nothing more. His route table looks like this:  To From A A
can build the magnitude table I mentioned above:  Node Magnitude A 0
Nice! B-) But, somehow, kinda useless. So, as our bot cannot move and has no higher priority goal (that is achievable - if he is hungry, for example, his limited network will not have any food in it), he decides to look around. Now, we are going to cheat a little here, but if we didn't, it'd look strange. Node A can see nodes B, L, O, and P. So, we pick the first of those, and turn the bot to face it. In actual fact, B, O, and P are all in a line. So, when the bot's field of view picks up node B, it will pick up nodes O and P as well. The first move is to add the newly discovered nodes to the route and magnitude tables, and to update the magnitude table:  To From A B O P A - B - O - P -

 Node Magnitude A 1 B 2 O 1 P 2
Now, recalculate all new rows and columns in the route table:  To From A B O P A - B B B B A - P O O P P - P P B B O -

Report Article

## User Feedback

There are no comments to display.

## Create an account

Register a new account

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 0
• 0
• 4
• 3

• 19
• 36
• 9
• 16
• 75
×