Knowing the Path
by Richard Fine

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.

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.

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.

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. :-)

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.

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.

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

From

(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
From	A

Also, we 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	-

And that's it!

There are a couple of extra things to mention. FirstLY, it's a good idea to keep a seperate, pre-calculated magnitude table for the entire network, so you can see when a node has been 'fully explored' (by comparing its value in the bot's magnitude table to that in the map's magnitude table). Exploration of the network is achieved by finding the nearest node that hasn't been 'fully explored' and looking at each of its links in turn to add them to the tables.

Incidentally, see why I said we had to cheat? If we didn't use the VIS table to look at visible nodes in turn, rather than just rotating the bot's head and seeing what it could see, what would have happened at, say, corridor corners? The bot would have stopped, done a complete 360-degree scan, and then continued. A human player would just see that the corridor bends too the right, and continue. Of course, there could be access from above - which the bot would see, but the player would probably miss. Still, it's better than stopping at each node to perform a full scan.

Secondly, what do you do when the addition of a node affects other routes? If, for example, node A was fully explored, then B, then P, the route from node L to node J would be LABPJ. However, if J was then fully explored, the route should become LKJ. How do you detect this?

I haven't been able to find a nice, neat pattern that can be expressed with a single rule yet. Perhaps there isn't one. The best I can come up with is:

After calculating values for the new cells, recalculate all rows for nodes directly connected to the new node, and then recalculate all rows for nodes with a magnitude of 3 or higher.

So, with my previous example, after adding node K to the tables and calculating the values for column K and row K, you need to recalculate rows L and J, and then nodes B and P (which would each have magnitudes of 3, but would not have already been recalculated).

Conclusion

Right, that's all. This method has plenty of room for expansion - off the top of my head, assigning 'goodness' values to each node - for strategic importance, safety, proximity to health/weapons, etc - might be useful to break out of the loop situations I mentioned earlier.

Oof. I'm going to go and eat some toast, I think. Questions, comments, etc, you can email me at rfine@lycos.com, post about this in the forums (I usually check) or catch me in #gamedev. Happy brainstorming! =]

Discuss this article in the forums

Date this article was posted to GameDev.net: 6/18/2002
(Note that this date does not necessarily correspond to the date the article was written)