7
\$\begingroup\$

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.

\$\endgroup\$
  • 5
    \$\begingroup\$ Could you describe your needs further? Any of these may be suitable depending on your game and the nature of the procedural generation. \$\endgroup\$ – Anko Oct 6 '15 at 8:26
  • \$\begingroup\$ Are the boundaries of your walkable features grid-aligned, or is it an open world, etc? \$\endgroup\$ – Steven Oct 6 '15 at 14:59
  • \$\begingroup\$ There is also a Quadtree-based pathfinding, that is somewhere between Grid and Navmesh approaches. It should work for both outdoor worlds and dungeon-style ones (you don't specify which one you want or both). To get the idea: youtube.com/watch?v=sn6P7xCTvvc \$\endgroup\$ – Igor S. Oct 6 '15 at 19:51
  • \$\begingroup\$ Thanks for your messages, Anko and @Steven. Please think of it as a proceduraly generated gigantic office, with lots of rooms and objects in the middle of the way. So, it's not like I have big open areas without obstacles. Also, it is so far not grid-based (I could make it so just for the pathfinding sake, and that's part of my doubt). \$\endgroup\$ – Andy Astro Oct 6 '15 at 20:54
  • 1
    \$\begingroup\$ You won't hold all of your navigational graphs in memory. That would be completely illogical to do if only a certain area is actually existing in memory at any given time. If you need to navigate across the entire world, what you would want to do is store a multi level adjacency graph. Which areas connect to which areas, Queue up those areas. Then for the current area your character is in, you navigate through that to the edges that connects to the next area. Then the next, and so on till destination is met. \$\endgroup\$ – moonshineTheleocat Mar 13 '16 at 7:35
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ many thanks for the insightful answer! So, your way of thinking is similar to what I've done so far. I was exactly working with hierarchies. I created exactly a graph where rooms are the points, so the first thing is to calculate the way trough rooms. Then, within-room path-finding looks for that room's door and that's it. I was exactly doing that by making each room have its own grid saved in an array object, with obstacles filling the cells they touch. My questioning started to arise precisely because I realized that once the world grows, the data on memory would become huge (...) \$\endgroup\$ – Andy Astro Oct 7 '15 at 6:24
  • \$\begingroup\$ (...). Like, one room with 30x10 has 300 cells. But a thousand rooms grow that to 300k, and so on. So, if I understand right your low-level suggestion, I would generate a navmesh for each room, so that would not be too costly in terms of CPU due to having much less obstacles (so vertices) to handle? This makes sense and was right now implementing that, but with visibility graphs instead of navmesh. While navmeshes use much much less storage memory than visgraphs, do you think their pre-processing can be competitive to visgraphs' pre-processing in this whole case? \$\endgroup\$ – Andy Astro Oct 7 '15 at 6:31
  • 1
    \$\begingroup\$ Btw, let me just acknowledge that while I was already thinking like you in what regards the higher level, you gave me an outstanding idea that's as powerful as it's simple: making the door be the nodes of the high-level graph instead of the rooms. Superb. \$\endgroup\$ – Andy Astro Oct 7 '15 at 6:37
  • 1
    \$\begingroup\$ Right - you would generate a navmesh for each room. As for the grid issue, do you need to pre-generate them all or can you generate them as needed - or just in time when the player gets near? 300k of grids doesn't seem too big to me - does it to you? What platform are you handling? One sound buffer or a larger texture blows that limit, so why worry about it? If grids work, use them. You could start with that and revisit generating the navmesh later, if needed. \$\endgroup\$ – Steven Oct 7 '15 at 16:46
  • \$\begingroup\$ Hi @Steven, thanks for the comment. I finally had the time to test that and I will indeed have to try the navmesh per-room. Memory usage can increase much beyond 300K after some time running the application and with the navmesh I could probably reduce it dramatically. As you've mentioned at first, processing navmeshes per room shouldn't be too slow, considering that rooms are not super-heavily detailed in terms of obstacles. Besides, I don't have to deal with floor slope or with height maps since they are constant. In such scenario, would you have any navmesh algorithm to suggest? \$\endgroup\$ – Andy Astro Oct 19 '15 at 3:57
4
\$\begingroup\$

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:

HPA*

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.

\$\endgroup\$
  • \$\begingroup\$ Many thanks! That's an awesome answer. As I've commented to Steven in the other answer, that's very close to what I've been trying to do. I was exactly using each room as one of the "big cells" of the hierarchy. But your answer helped me think of that high-level part more efficiently. Thanks. Now, for the low-level part (within-rooms), wouldn't that solution still leave me with a huge storage memory usage, due to having to save in memory anyway all cells that are part of the interior of the rooms (i.e. at the low level)? I think that's a fair concern when the number of rooms start to increase \$\endgroup\$ – Andy Astro Oct 7 '15 at 6:34
  • \$\begingroup\$ And btw, I got very interested in your project. I will certainly take a closer look a read the other posts you've put there in the past to catch up with what you have doing and discussing. Many thanks for sharing it. \$\endgroup\$ – Andy Astro Oct 7 '15 at 6:35
  • \$\begingroup\$ @AndyAstro don't be mislead by the diagram, it only illustrates one possible implementation based on a grid representation, but you can do it just as well with navmesh, which on larger rooms would be more efficient than a grid. But with pathfinding it's usually compute time that is the bigger problem, not memory. Memory use is proportional to map size, but you want efficient pathfinding which is what this hierarchical approach will help with. \$\endgroup\$ – congusbongus Oct 7 '15 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.