7
\$\begingroup\$

How would you path plan a volume for a game?

For example a 1 km cube with tunnels and caverns. Also the terrain is destructible.

You have walking and flying modes.

I would separate it into phases. Create a volume of the open space. Find a path that takes into account dynamic destruction.

Performance is a huge concern and the ability to find paths that are used in a short time.

Concrete example: Mine something deep in the ground efficiently.

The ground is destroy-able. "Caverns" are easy to dig areas. Mining is like flying. Need to see with sensors. The dataset is huge. Need to construct a transportation path to the target. May be multi-agent.

Improve this question
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Is there a fog-of-war and should it affect pathfinding? \$\endgroup\$
    – Will
    Sep 5, 2011 at 6:59
  • \$\begingroup\$ There's line of sight although you can link sensors. \$\endgroup\$
    – Fire
    Sep 7, 2011 at 5:56
  • \$\begingroup\$ Are you working on level design -- design a level, setting up the (initial, pre-damaged) tunnels and caverns weeks before the game is played? Or are you working on pathfinding -- programming computer-controlled agents so that during gameplay, they move "reasonably", rather than doing dumb things like walking into walls, falling off cliffs, etc.? \$\endgroup\$
    – David Cary
    Sep 7, 2011 at 8:05
  • \$\begingroup\$ No one is going to spend weeks designing the geology of the 1 km cube. The question is not about procedurally generating geology. It is about path planning for agents in a indoor cavern and tunnel system. This means not being lost or flipping between paths. \$\endgroup\$
    – Fire
    Sep 8, 2011 at 0:06

5 Answers 5

Reset to default
3
\$\begingroup\$

Dynamic pathfinding, to be reasonably performant, requires an algorithm specifically suited to this, like D* (Dynamic A*).

Beyond this, you may be able to find a way to perform hierarchical pathfinding. This way you have a simpler path at a lower resolution, and more complex subpaths at higher resolutions. By substituting any higher-resolution path subgraph into the lower resolution master graph, you can elaborate your path to whatever resolution you wish.

Lower resolution pathfinding is obviously great, as you can do minimal pathfinding until such time as you enter another subregion, and then perform more indepth pathfinding at that region's subdiv level.

As for the actual algorithm used to perform tunnelling through your 3D space, the biggest potential problem you'll face with this is entering 3D "dead-end" areas that you cannot get out of without crossing another passage (graph segment). See my recent monologue on planar graph embeddings here.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ HPA* is somewhat more performant. \$\endgroup\$
    – Fire
    Sep 7, 2011 at 5:58
  • \$\begingroup\$ I investigated probabilistic roads maps as they're using in robot navigation problems. \$\endgroup\$
    – Fire
    Sep 7, 2011 at 5:59
  • 2
    \$\begingroup\$ You can also use a Cellular Automaton based 'flood fill' to constrict your caverns and tunnels down to a much smaller sub-set of spaces. This can be re-run on deformation of the landscape, in the background if your map is somehow large enough for there to be a delay on this or if deformation of the map is a constant. (unlike something like minecraft or dwarf fortress) Once you have this sub-set path, you need only path to it, then along it, then from it. Ideal is if all open spaces have line-of-sight to the subset path. \$\endgroup\$
    – DampeS8N
    Sep 7, 2011 at 11:26
1
\$\begingroup\$

If by destructible terrain you mean major changes to the huge multilevel environment, this will be tough as hell, especially for walking units. It would be wise to divide flying and walking units from the very beginning, so they will have the separate graphs.

I can't say I know a definitive solution for the walking units. Depending on amount of the agents, potential terrain changes and cube node resolution, you may or may not want to use D*. In essence, D* is a brute force A*. Like Nick hinted, brute forcing just one step ahead may result in a lot of "dead-ends", since without the whole path you won't be able to immediately tell whether next node is correct or not. Also you will have to think about path cache and its partial invalidation, so you don't have to brute force constantly on per-agent basis. Overall, it's not going to be easy and may become too CPU heavy.

Going with A* instead, the simplest case would be to limit your terrain destruction to minimum and get away with hierarchical pathfinding, like "coarse" A* and some form of local avoidance. I guess it's not an option, so you may try to convert your cube's ground and walls into a navigation mesh and then change it part by part. Navmesh calculation is not fast of course, but there is a room for various optimizations to avoid complete recalculation of the said mesh upon a terrain change. General idea is to perform a local mesh updates, so only the affected regions of a navigation mesh will be changed when terrain destruction occurs. It could be done using adaptation of the construction of Voronoi diagram, but it is not a "solved area". It won't be easy either, since you'll have to speed up the navmesh recalculation, but if accomplished, path finding will be fast and reliable.

Graph for air units is much simpler. Basically, you will have to find all "air space" and convert it into the graph. Since your caverns are dynamic, the most obvious choice is to base this graph on a cube's octree. Use octree leaf centroids (point in the middle of the leaf cube) as a basis for calculating nodes and filter out all centroids in the obviously invalid positions. Check resulting centroids to remove all that are inaccessible from their neighbours. This is going to be very fast, so your major concerns remain within ground pathfinding.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Both flying and walking modes can sample from the navmesh. Then they can generate their own representations. I have no idea how to do the switch between modes. \$\endgroup\$
    – Fire
    Sep 7, 2011 at 6:00
  • \$\begingroup\$ In probabilistic road-maps one method is constructing voroni diagrams. But it relies on your sampling covering the spaces. \$\endgroup\$
    – Fire
    Sep 7, 2011 at 6:02
1
\$\begingroup\$

I have an open source implementation of pathfinding on a 3D grid as part of my voxel game SDK. It's an implementation of the A* algorithm intended exactly for minecraft-style environments and voxel terrain.

It's not a dynamic algorithm as other people have suggested, so I can't help you there. I guess it depends how dynamic you world really is. It could also use some performance improvements as it can currently take a couple of seconds to find a path maybe 100 voxels long, but you may be able to run it on a down sampled version of your volume (through take care during the downsampling as valid paths may be created/lost).

You can see it in action here http://www.youtube.com/watch?v=C8y0OzL0zpM (that's not my game though), and get the source from http://www.thermite3d.org.

Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ I specifically specified 1 km cubed to rule out the 100 voxel path-finding algos. \$\endgroup\$
    – Fire
    Sep 7, 2011 at 5:57
  • \$\begingroup\$ ... sparse voxel representations though can work at that scale though? ;) \$\endgroup\$
    – Will
    Sep 7, 2011 at 7:18
  • \$\begingroup\$ Sparse voxels means that only the hull is checked. But we only care about the open path. \$\endgroup\$
    – Fire
    Sep 7, 2011 at 7:36
  • \$\begingroup\$ depends if you are iterating the voxels or the gaps. I was only getting tired of your impatience in each and every answer. This forum doesn't do deep progressing-the-state-of-the-art questions as well as you'd like. \$\endgroup\$
    – Will
    Sep 8, 2011 at 7:30
  • \$\begingroup\$ I am quite satisfied with every answer. Stackexchange could be much worse. \$\endgroup\$
    – Fire
    Sep 8, 2011 at 20:29
1
\$\begingroup\$

If you're world is already build from discrete blocks, then it makes sense to use them as the basis for your navigation.

Pathfinders are easy, fast pathfinders a bit harder. Path following and responding to the changes in the world is the real nastiness.

There are a couple of question which can help you narrow down the potential solution: - what kind of NPCs you are trying to simulate? - how long paths are you searching? - how accurate paths you need?

If you have short paths and you're fine with "better than steering" quality, local grids [1] are good choice. They are super fast, you can make it work both 2D and 3D. You can get local grid data directly from your volume data, so the nav graph should stay in sync with the dynamic changes easily.

The problem with local grids are that if you have local minima in your world which is larger than your local grid, the agent may get stuck. It is possible to do tricks like add bread crumbs on locations where you detect local minima and try to avoid those locations when searching.

If you need long paths, I suggest some kind of hierarchical scheme. HPA* should give you good ideas how to create sparse nodes in grid a world. Local grids can solve the path finding between the high level nodes. When you make changes to the world, you will need to locally change the coarse nodes too. You can also use the nodes to detect dynamic changes in the game world, and replan the path.

If you have dynamic world, pathfinding becomes statistics. There is no more any guarantees if the agent will find its way. Keeping track of the changes in the world is really hard and replanning when something goes wrong is sluggish.

Eskil rides with this idea in Love MMO, and his path finder is just random sampling with utility function (so is his action selection :)). I would recommend to do that first if it fits your game style.

[1] http://digestingduck.blogspot.com/2010/03/local-navigation-grids.html

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

You want to adopt a navigation mesh, or, if the world is particularly noisy on the vertical rather than just platforms or if flying mode is more than just jumping or hovering then you might use navigation volumes.

Detour is a lib for path-finding that allows you to update the navigation mesh live. I've never used it, I don't know how it works at your scale. A hierarchical system seems like a good idea.

Good reading when you contemplate writing your own is recent research of symmetry breaking. Well worth a thoughtful read!

Consideration has to be given to whether fog-of-war should affect pathfinding decisions. It may be that if asked to move to a new area a unit should move in a straight line until it meets obstacles, or it may be that the unit should make a route with full map knowledge. That's a game choice.

Fun reading: Fixing Pathfinding Once and For All

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Recast/Detour voxelizes the terrain into a navmesh but it only generates planar polygons. Therefore it's only useful for ground modes. You can abuse the dynamic planning to do replanning. \$\endgroup\$
    – Fire
    Sep 7, 2011 at 7:22
  • \$\begingroup\$ Mikko benchmarked hpa* and found it to be 4-5 times faster than Detour's A*, and uses 10-20 times less memory (graph nodes). \$\endgroup\$
    – Fire
    Sep 7, 2011 at 7:25
  • \$\begingroup\$ someone somewhere has likely made the BSD-licensed nav volume lib with G-HPA*-JPS path-finding. @Fire you're so well read on this, got a link for it? \$\endgroup\$
    – Will
    Sep 7, 2011 at 7:35
  • \$\begingroup\$ Actually the generalized version of HPA* above modifies recast/detour and is released under a non-viral free license. But it only handles planar polygons. I would start there. \$\endgroup\$
    – Fire
    Sep 8, 2011 at 0:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .