3D navigation (pathfinding)

Many games (fps games at least) still use waypoint based navigation, where a user or level designer places and connects waypoints, possibly placing tags on waypoints to set them up with special properties.

A more advanced technique is to use a navigation mesh. This involves creating a navigation graph on the actual level geometry. With this you can discard unwalkable surfaces and with a pre-processing tool this could be done automatically. Quake 3 and HL2 use similar techniques to the nav mesh.

Many RTS games still use a more 2d grid approach, since many of those types of games still internally use tiles. It all depends on the game.

Quote:

Original post by DrEvil Many games (fps games at least) still use waypoint based navigation, where a user or level designer places and connects waypoints, possibly placing tags on waypoints to set them up with special properties. A more advanced technique is to use a navigation mesh. This involves creating a navigation graph on the actual level geometry. With this you can discard unwalkable surfaces and with a pre-processing tool this could be done automatically. Quake 3 and HL2 use similar techniques to the nav mesh. Many RTS games still use a more 2d grid approach, since many of those types of games still internally use tiles. It all depends on the game.

I am aware of this, but I am not going to use waypoints (at least not in outdoor places). This is my problem.

Imagine the bot standing beside some rock formation. It is possible to walk on top of this rock only from a handful of points. Ok. I could place waypoints in those points, but the map is way too big to manually place waypoints and too difficult to analyse for reachabilty (it is a very huge map, no level-type map, think Online RPG games).

I am really at loss at the moment. As I said, a 2D world (or a flying/swimming bot) do not cause so much trouble, but for a walking bot I cannot find a reliable way to use the volumetric information I get.
Maybe this is the wrong approach, but for the moment I am stuck with this and I cannot find another ways to solve the problem.

I want to add something else, when I am doing this volumetric analisys, I not only get back the portion of space that are occupied, but I could get other information like the inclination of the surface enclosed in this space or what type of object is this (terrain, walls, etc.) But I cannot find a way to chain those information in order to find a path that doesn't involve flying for a non-flying bot.

Well, you seem to have ruled out your 2 options. manually placed navigation points or analyze it with a tool and generate navigation automatically. A tool would take a non trivial amount of time to implement, but will probably more than make up for it in the time savings later.

As DrEvil has suggested, build a navmesh using the polygons that comprise the geometry of the landscape. You can find info on how to create and optimize navmeshes in the Gems/Wisdom series of books.

Alternately you could use a floodfill algorithm to automatically fill the landscape with waypoints or cells. Then optimize it.

The problem I have with navmesh and waypoints is that the map is very big (really) and the space requirements to store this info would be too much. Therefore I was looking into a more dynamic, on the fly way to get data from the sorrounding environment. Since I have the possibility to ray-trace very (very) fast, I thought, ok, I subdivide some portion of the space around the bot and use ray-trace to get volumetric info (kind of 3D image analysis).

I have run tests in 2D, by having a biggish graph with 10000 nodes and each node (placed high upon the ground) would fire a ray (downwards) to get (mainly) height data. I would then use a Dijkstra algorithm to find a path between 2 points.

The 3D version would be a lot more complicated ray-tracing (for each node/portion of space) in the 3 directions and getting both blocked portions and some inclination data.

I guess I am overkilling :( but cannot find another way to *sense* the sorrounding in those cases where I have to climb up stairs, slopes or avoid to fall in a canyon or bang on a wall.

Since I can ray-trace fast, I think I could ray-trace from the player in many directions, but it doesn't sound good, I am stuck, I probably have to re-think about it, and that is why I posted here to get some feedback.

I understand that your map is large, but the size of a navmesh is proportional to the complexity of the geometry. They are well suited to large open spaces since most of the polys can be optimised out.

(it might help if you could describe your world environment in more detail. How many polys does it consist of? What type of terrain does it represent?)

A navigation mesh isn't that expensive memory wise. Depending on your game you may already have the array of geometry in memory already. If you run it through a pre-processing step that 1) discards all unwalkable surfaces(dotproduct with world up) you should end up with a decent triangle mesh of the walkable areas. There are other ways to further eliminate polys through discarding ones that are too small and/or merging polygons together(most likely want to keep the areas convex tho)

If your game world is split into tiles, generate the nav mesh in tiles as well. Surely you are doing some sort of partitioning of the environment that would allow you do do this, as well as providing opportunity to do a heirarchial pathfinding on the larger tiles first, then within the tiles.

My suggestion is to do what you have to do, then evaluate the memory usage and start working out ways to reduce it if need be. What calculations are you using to come up with the 'too much' memory usage? How much exactly are you calculating it out to be?

If you choose to stay clear of a nav mesh, then your only other option is to perform dynamic feature analysis of the surrounding space and plan/react accordingly. This doesn't have to be as complicated as it sounds though.

Your feature space needs to map to a set of constraints on your action space, which subsequently constrain the plan solution space. So, for example, if your planning is purely pathfinding, then features of importance are local terrain gradient (directional derivatives, possibly modified by frictional coefficients) and obstacles. The former can be computed in a 2D projection of the octtree. The latter constrains which nodes in the tree can be entered, or which action prerequisites must be fulfilled in order to enter that node (for instance, climbing stairs would have as a prerequisite lifting a foot, which might equate to changing the animation state to walking up stairs of the given gradient rather than walking forward).

Obviously, this is the tradeoff; between memory required to store pre-computed results (nav-mesh or other constraint diagram) and processor time required to compute useful information in real time.

I suspect you'll find there is a happy mid-ground that provides adequate performance for minimal memory usage.

Cheers,

Timkin