What is the most appropriate path-finding solution for a very large proceduraly generated environment?

Question

I have been reading quite a bit in order to make the following choice: which path-finding solution should one implement in a game where the world proceduraly generated, of really large dimensions?

Here is how I see the main solutions and their pros/cons:

1) grid-based path-finding - this is the only option that would not require any pre-processing, which fits well. However, as the world expands, memory used grows exponentially up to insane levels. This can be handled in terms of processing paths, trough solutions such as the Block A* or Subgoal A* algorithms. However, the memory usage is the problem difficult to circumvent;

2) navmesh - this would be lovely to have, due to its precision, fast path calculation and low memory usage. However, it can take an obscene pre-processing time.

3) visibility graph - this option also needs high pre-processing time, although it can be lessened by the use of fast pre-processing algorithms. Then, path calculation is generally fast too. But memory usage can get even more insane than grid-based depending on the configuration of the procedural world.

So, what would be best approach (others not present in this list are also welcome) for such a situation? Are there techniques or tricks that can be used to handle procedural infinite-like worlds?

Suggestions, ideas and references are all welcome.

EDIT:

Just to give more details, one should see the application I am talking about as a very very large office level, where rooms are generated prodecuraly. The algorithm works like the following. First, rooms are placed. Next, walls. Then the doors and later the furniture/obstacles that go in each room. So, the environment can get really huge and with lots of objects, since new rooms are generated once the players approaches the boundary of the already generated area. It means that there will be not large open areas without obstacles.

Answer 1

Given that the rooms are procedural built, portals created and then populated, I have a couple of ideas.

A* works really well on navigation meshes, and works hierarchically as well. I would consider building a pathfinding system that works at two levels - first, the room by room level, and second within each room, from portal to portal. I think you can do this during generation at an affordable rate. You only need to path from room to room once you enter it, so it's very affordable from a memory/cpu cost.

High level A* can be done by creating a graph of each portal and room - a room is the node, and the 'path' or edge is the portal to another room. The cost of traversal has some options - it can be from the centre point of the room to the centre point of the other room, for example. Or you might want to make specific edges from portal to portal with real distances, which is more useful, I suspect. This let's you do high level pathfinding from room A to room B. Doors can be opened and closed, enabling or disabling specific paths, which is nice for certain types of game. Because it's room/portal based it should be pretty easy and affordable to calculate - just distance calculations and graph book keeping. The great thing about this is it reduces the pathfinding memory costs dramatically in large environments since you are doing only the room-to-room finding.

The harder part will be the low level A* because it should be polygonal navigation mesh. If each room is square, you can start with a polygon. When you place obstacles, subtract the area occupied from the polygon, making holes in it. When it's all finished you'll want to tesselate it into triangles again, building up the graph. I don't think this is as slow as you think. The difficult part is performing the polygon hole cutting, which requires a good amount of book keeping on that kind of stuff, but it is well documented within half-edge structures, and established computer science graphics books. You can also perform this generation lazily, in a background graph, as you don't actual need the A* results of this level until someone is in the room - the high level takes care of basic path planning for you. Someone may never even enter the room in a run, because the high level A* never leads them there.

I know I have glossed over the low level navigation mesh generation, but I think it's one of those things you set your mind to and solve and then it's done. There are a bunch of libraries out there like CGAL (http://www.cgal.org) and others that can do this stuff, but really to get it going fast you might need to write it yourself so you only have the things you need.

Alternatively, you could make each room be a grid, and the obstacles fill up parts of the grid, and then do all the standard grid smoothing algorithms, but I like navmesh data as it is small and fast.

Hope that makes some sense.

Answer 2

I'm going to take a stab and recommend a hierarchical pathfinding algorithm, such as HPA*. Even though I'm not an expert in AI, I'm fairly confident in this guess because your generator sounds almost identical to the one in a game I'm working on, i.e. I've thought about this problem a bit too.

HPA* (Hierarchical Path-Finding A*) is a method of optimising regular A* by first clustering the map into areas that are inter-connected, then producing a high-level graph of those clusters. When pathfinding, A* (or any pathfinding algorithm) is run on the high-level graph, then in each of the clusters that form the best high-level path. Apparently it's widely used in RTS games, where lots of units will need to navigate unique paths across a large map in real time, so this should give you an idea of how efficient this method is.

Here's an image from their paper; the left is the clusters with connecting nodes, and the right is the high-level graph:

Fortunately for your generator, it is very suitable for this algorithm, because of the rooms that you place: this gives you half the clustering for free. Your high-level graph is essentially made up of all the doors of your rooms. So what HPA* is for you is: find the series of rooms/doors I need to go through, and how to navigate every room in that sequence.

Some more neat things about this algorithm:

• A* is slow because it has to find the complete path before returning any results; with HPA*, you can find the high-level path plus the path for the first room, so you can follow it immediately and defer the paths for the rest of the rooms later. This makes the algorithm responsive.
• You can cache the pathfinding results between pairs of doors for each room, since paths that traverse but don't start or end in this room are guaranteed to follow one such path.
• You can have multiple levels in this hierarchy, although this is only useful for truly gigantic maps.

Do note that HPA* is near-optimal. You can easily see why by imagining a room with so many obstacles that it takes a long time to get through it. For the same reason, you should watch out if a room has enough obstacles to effectively partition it - don't treat this room as a single cluster in the high-level graph.

For some other possible algorithms, you could try this question on cstheory.SE, which lists a ton of them.