Unite 2010GDC ChinaAsia Game Show 2010GDC 2011
|
This is a follow-up-slash-rewrite of an article I wrote a while back on a technique I called 'Precalculated Pathfinding.' There were a few problems I didn't address, partly because I didn't have answers to them and partly because they hadn't occurred to me. Well, after recently solving the problem which bugged me the most (the problem of dynamic networks), I've decided to attack this thing again. I'll give a complete description of the initial technique again too, so you don't have to go and find the other article. Precalculated Pathfinding (or "Fine's algorithms" as I hope they will come to be known ;-) ) is a way of storing all possible paths through a network, eliminating most real-time pathfinding operations. It's also a very useful way of having an AI 'learn' the paths through a network. However, it's a trade - memory for speed. Also, the fact that the routes are 'precalculated' - calculated once, before the game begins - means that you have to respond to changes in the world (which may create or block routes through the network). I'll be addressing both these problems. Initial ConceptGiven that the route ABCD is the shortest route from A to D, it can be proven that BCD is the shortest route from B to D. It's as if any given 'shortest route' is made up of smaller 'shortest routes.' If there were a shorter route from B to D, for example BED, then the shortest route from A to D would have to be ABED. And so on. So, we can say something like this: route(A->D) = AB + route(B->D) and we know for a fact that's the shortest route. While we're at A, it doesn't actually matter to us what the shortest route from B to D is; we just know that the we're going to use it. We can find out what it actually is once we get to B. All we're interested in right now is 'where to go next.' The FoundationThat 'where to go next' is a pretty powerful concept. Imagine that once we're at B, our target changes and we want to get to E? We won't have wasted any time calculating the rest of the route to D; we can instantly change our target and say 'ok, so where do we go next to get to E?' These 'where to go next' values can be stored neatly in a table. And we love tables, don't we? Let's take the sample network:
From this network, using any pathfinding algorithm you feel like (I just used visual inspection, so I might not always get the shortest path - but you'll get the idea), you can build the following table:
To recap: I built this table by finding the route From each given node to each given node, and storing the first node in the route (excluding the start node). To use the table, all you need to know is your current location, and your destination. Feeding the current location in as your 'from' value, and the destination in as your 'to' value, you get the next node you should move to. In any sensible implementation, connections between nodes are simple straight lines where no obstacles are present, so actually moving to the next node should be a cinch. This technique also has the advantage that it can cope instantly with changes both in position and destination, without having wasted any processing time (at a time when processor real-estate is at a premium). Using conventional pathfinding techniques, you have to calculate the entire route to the target - sometimes you'll do that each time the bot reaches a new node, but you may have optimised by storing the path in the bot's "memory." Let's say that you've calculated a path that is 10 nodes long. Your bot begins to move, but after traversing 2 nodes, the target changes (the enemy has moved, or the bot has been given new orders, or something). So, a new path is calculated, and the old one discarded. That means you processed 8 nodes which never got used - and yes, there's no way you could have predicted the path would have been discarded or when, but it's an obvious waste of processor time. With this technique however, you process all the nodes before the game starts - perhaps even at development time, where the table can be stored in a file - and once you're in-game, you never have to waste time looking at nodes which don't get used. Let's play a little game with our network. We'll place a 'hare' at A, set to follow the path AEDCA repeatedly. We then place our 'dog' at D, and watch it track (and, finally, catch) the hare.
Notice how, in the third row, the dog actually doubles back on itself - if it didn't, our racetrack critters would be stuck in an endless loop (symbolic maybe, but that's far too philosophical for this article). In a more usual game situation - because our dog-race example is based around the same simple 'terminator' AI that people realised wasn't terribly interesting several years ago - there'd be other information influencing the path. For example, each node could also contain the distance to and location of the nearest health-pack, so that the AI could choose to take a little detour to pick up a medikit, if not too far away. The same sort of idea can be applied to all number of in-game objects the AI might find significant - ammunition, etc - things which don't move around. Of course, each time you store something else in the table, you're using up more memory, so you need to make sure you stay efficient. If you want to be aware of nearby objects which could be moving, then it gets a little more difficult. I'll look at such a situation later on in the article.
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
