sponsors gamedev.net search:

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. Page 2

Contents   Page 1   Page 2   Printable version   Discuss this article