• Followers 0

# Precalculated Pathfinding Revisited

Artificial Intelligence

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 Concept

Given 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.'

## Progressive nets and subnets

Another problem people emailed me about was using networks over large worlds. Not necessarily large networks; just networks which needed to cover large distances. Particularly over open terrain (Delta Force type worlds). I think I have a solution which will help some people out. It also applies to some other situations too; large worlds with many enclosed spaces, for example. Here we go: split nodes into 'levels.' That is, have a top level (level 0) which contains a 'general' set of nodes - nodes which cover most of the world, but are very coarse. The routes between them are like Interstate roads. Into the next level, you put nodes which, while not totally in-depth, are more detailed than the Level 0 nodes. These are like your main roads. What's more, you give each Level 1 node a list of 'parent' Level 0 nodes. If you had an area of the world enclosed by routes between 4 Level 0 nodes, the Level 1 nodes inside the enclosure would have the 4 Level 0 nodes as parents. The Level 0 nodes, in return, keep lists of all Level 1 nodes which have them as parents. This means that you can take any given Level 0 node, and load into memory all 'nearby' Level 1 nodes. This goes on for as many levels as you want (is 'progressive'), right until you're down to the small routes which are like people's driveways. Each level (excluding Level 0 and the smallest level) has lists of both parent and child nodes. So, from anywhere in the world, you can follow a node back to the 'interstate,' use the Level 0 nodes to get near to your destination, and then progressively use smaller and smaller levels to get closer and closer to your destination. There are routes between nodes in any given level and the nodes in the level above - Level 1 is 'anchored' to Level 0 by such routes. So, only Level 0 is a complete network (in that of its routes and nodes are a part of it), unlike the other Levels which have dependencies on their parent levels. This concept of Levels or 'sub-networks' can be extremely useful. Imagine a world containing many buildings which can be explored. The nodes in each building can be grouped into a subnet, and only loaded when the building is actually being traversed, saving large amounts of memory.

## Conclusion

I hope you've figured out by now that you can attach pretty much any information to a node - be it a 'scent,' a mood, a warning, a reference number... you name it. And much of that information is static, and can be precalculated - found by a compiler tool, stored to a file, and then loaded and decompressed for instant use in-game. The network can be used not just for finding a route, but for deciding whether to use it. Whenever you work with node networks like these, remember your constraints:
• Minimise memory usage, mainly through minimising duplication of information.
• Process nodes 'on-demand,' rather than forcing the whole network to be processed frequently.
• Keep good connectivity in your game worlds to make the networks efficient.
• Don't be afraid to use the network for more than just pathfinding.
I think I've covered everything I wanted to cover. Feel free to email me at [email="rfine@tbrf.net"]rfine@tbrf.net[/email] - I'll be happy to answer questions, discuss problems, and merely hear about how you're using the technique and how it's working for you. So.. until next time...
0

Followers 0

## User Feedback

You need to be a member in order to leave a review