How to create a navigation mesh?

I have been playing with a nav mesh at home recently. Its still very basic, but here are a few notes:

Construction:

There are several ways to go about this. The simplest is probably manual generation -- as in, someone builds the mesh by hand. While not automatic, it tends to be pretty quick to build. A large, reasonably complex game level could probably be done in an hour or two. The added benefit is that whoever builds it can insure that it doesn't go 'bad places', so you don't need to handle 'collision test, test for jumping, etc'.

Automatic generation is better (similar to what you proposed), but more complex. In this case, you would need to handle traversable space tests, looking for 'degerate' spaces (you don't want the AI to try to walk on the hand railing by the stairs), etc.

In both cases, you will probably want to invest some time looking at simplification algorithms which do not decimate (alter the shape of) the mesh. The small you can make your search space, the smaller the graph the AI will be searching.

Moving around inside a poly:

Internal to the poly is a convex shape. This means that any movement within it is unobstructed. You can take a straight line across any poly. A simple approach to pathing would be to put a waypoint on each edge the AI crosses; as the polies are convex, there will always be a straight path between the waypoints.

Other issues:

Your AI likely have width. Unless you 'shrink' the outer polies of your nav mesh, your AIs may have part of their bounding box go outside of the nav mesh. Only their center is garenteed to be internal. There are a lot of options here, including shrinking the mesh (look up computational geometry; minkowski sum) and using force vectors to push the AI away from the edges of the mesh while he is traversing it.

You will likely need to run some sort of post process step on paths generated (if the AI follows them exactly). This can be used to optimize the location of the waypoints to 'tighten' the path. Another option is to do this as the AI is running it; constantly perform a 'look ahead'. If you have a fast connection, download http://www.gdconf.com/archives/2004/booth_michael.zip as it has both a paper and videos of the counter strike bots and how they handled this issue.

I think i have that paper ... it list several nice ideas ... but still ideas.

Not sure how they did their pathing, it looks more like the bot is "following" the path, not walking it exactly.

I have no good knowledge of physics and collision. But I would think that the collision thing would bounce the npc away from walls and stuff.

..or you have an simple look ahead thing...

But are there any example code on how to construct a navigation mesh? Saw that Game Programming Gems 3?? could have something like that ... is that correct?

Yep, I do agree that there's too much ideas and not enough code about NavMeshes, but there you go. I've got the first 3 Game Gems books and both AI Wisdom books, and in total there's about 3/4 articles about NavMeshes, but thats about it.

I do remember there being some code for one of the early ones tho, if would that help you?

Dan

Does your environment change?

If not, pre-process anything you can. Also, use the artists! Use them to place node-waypoints in the maps. Much easier than spending 2 months coding and beta-testing an algorithm to selected those nodes, and will allways under perform when compared to humans.

What other ideas do you guys have about the subject?

Where I used to work, all our nav meshes were hand made by the artists.

I wish I could speak freely about what we use now, but I don't think I have the right to post about every details :/ If it can help, check out delaunay triangulisation (example) and run a simplification algorithm afterwards to keep only convex polygons.

You can then use steering to avoid dynamic obstacles within your polygon (what you call empty areas) since you know that no static obstacle will be in your way (static obstacles should lie where your nodes are, so the middle of the polygons are free). If you need an example of steering, check out Craig Reynolds' webpage.

Hope this helps, and sorry I couldn't say much more =[

Cheers

Eric

You are correct that the CS bot did not follow the path accurately; it used it as a guide line and tried to stay close. Other nav mesh implementations follow the path perfectly. There are a lot of permutations on all of this. Have you read the part of the paper which talks about the algorithm they used for following the path? Its about 2/3 of the way in. It talks about how they have 'leash' of sorts, with a max angle and distance/etc.

I would suggest ignoring physics for now. You don't want to 'use' physics to bounce your NPC around anyway; if your NPC is solid, its a liability. For now, I would suggest not having it collide with the environment at all. Once you have it working without physics, then try integrating it if needed.

Oh, you may also want to check out pathengine.com. They have a middleware navmesh library which looks pretty decent. In describing how it works and what the interface is, it may give you a decent idea about how to write one.

So many replies - how nice.

Right now I am currently separating the pathing and the creation of the nav-mesh, because I have to know how to create the nav-mesh before I start working on the pathing... and pathing have quaite a large number of examples, not directly to nav-mesh maybe, but I think that might be doable later on.

xEricx - Don't want you to give out to much either, then I only get sued. hehe. But a bit interesting site you gave there.

I don't want to create a nav-mesh by hand, I rather have a sluggish nav-mesh creating code in a good framework. Because then I can rewrite the code for creating the nav-mesh, instead of rewriting the entire AI just because you wanted to put it further.

...which is what I am really after at this point, how to create a good framework to work in...

The creation of navigation meshes is a sub problem within the area of skeletonisation, which is a state space analysis scheme that reduces the dimensionality of the problem (like the skeleton, which is approximately a 3D structure made up of a collection of 1D lines connected at nodes). Skeletonisation is a big area of research, particularly in robotics. There is plenty of literature out there on how to create navigational skeletons. Look at the robotics field... they're solved all of these problems before (or at least, come up with adequate solutions).

Cheers,

Timkin

If I'm not mistaken, 3D Path finding on arbitrary 3D space is too complex to effectivly be achieved in real time.

Therefore you'll need to "bake" your 3D space. A hybrid octree-BSP tree aproach may yeld the best results.

From these occlusion trees, create a list of Object-Aligned Bounding Boxes on convex empty space areas, then create another list that represents the connections between those OABB.

This list represents empty space in the map, and how empty areas are connected to each other.

To go from A to B, find out in which "empty-space" leafs A and B are located, then do a spatial search (A*) that will yeld the traversal result, something like:
A->D->X->M->K->B

Now, so that the bot is allways touching the ground (in case you use gravity in your FPS), get the vertex coordinates from each open-space bounding box, and use the "lower vertices" to define a "walk plane" for the bot.

To further complicate things, you'll have to take into account non-static objects that might disable the travelling between two areas (doors are a good example).

So, add to your tree's portals another property: "active". The portals connect two open-space areas. If the bot can go from one side of the portal to the other, then the portal is active.

Hope it helped, it was a bit out of the top of my head.

Hmm ... not sure if I understood the last post quite, have to look into that sort of stuff first.

But on the navigation mesh subject: nav-mesh is ok for things that is walking on the mesh, or need restrictive movement on a 2D basis. What if I then put a Dragon into this world, or airplane, or a bird in a complex map of those you find in quake?

Only thing I could think of is that those objects would have to start and stopp on the mesh, but ...

... how would pathfinding in Decent be? (the wird old indoor space 3D game)

I am not sure if a set of connected 3d convex volumes would be called a nav mesh. I don't know if there is an generally accepted term for it yet or not. I may be off here, but a nav mesh implies 2d connectivity to me.

If you have things that fly, then a traditional 2d nav mesh probably won't handle it (at least, without some sort of 3d augmentation).

Instead of a network of 2d convex shapes, things that fly (like Decent) probably would use a network of 3d convex shapes. Most of the same properties apply to a 3d mesh; some of the algorithms used for automatic construction have a higher computational complexity, but that it is still very doable.

I am pretty sure the Decent level building tool operated in convex shapes; these were probably translated fairly directly into their navigation volume system. I haven't looked at it, but it looks like the Decent code was released: http://www.descent2.com/ddn/sources/descent2/ It may be worth glancing at.

I was discussing pathfinding with another person I know at work, and he was wondering if you could create an algoritm that would just spread out tons of points, randomly .... then do pathfinding among them. The only fear I have is that the points become too many to pathfind among, and too few in some areas making the NPC wlak weird routes. Then I also wonder if this would be easy too use in A* which are weighted.

But maybe a combination of those two. Have a nav-mesh as a basis, and dropp lots of points around in space for flying creatures, and try optimize the number of points and where they are dropped, and remove as much as possible. Then create a path in the air for these flying stuff, and "follow" the path so the have some freedoms.

...Thats the only idea I have. But then we have like 2 pathfinding systems... but thats ok.

If you're interested, here's a link to an article I wrote for my GDC talk on arbitrary mesh 3D pathfinding from a couple of years ago.

The system was used in a 3D shooter with very good results, fully automated, no manual node placement or artist tweaking. If I ever work on an FPS again, I'll definately use it.

http://www.gamasutra.com/features/20020405/smith_01.htm

Hope this can be of some help.

Someone mentioned that the robotics field has done a lot of research in this are. This reminded me of an excellent paper I found a couple of weeks ago about path planning. Maybe not related directly to navigation meshes but it sure solves the same problem. The nice video presentation and the chapter about roadmap creation (like the randomly generated points mentioned above but more advanced) were very intresting. Heres the link:


Interactive Navigation in Complex Environments Using Path Planning