After spending the last days reading and brainstorming around AI, I have come to a kind of a couple of dead ends where I can't find any good information. Navigation mesh is one of them. I kinda understand the concept, but are very unsure how I would go about and implement such a map. One thing is take every poly that have an angle of less than 20 degree towards the z-axis (upwards). But then you should do a collision test, test for jumping, and maybe alter the mesh in order to get a more simplified mesh to do navigatin in. Then another thing ... let say you have a square huge plane of 2 poly ... how do you navigate around on such an "empty" area? I have read alot of blablabla ... alot of "brief easy theory". But I don't find any good examples, code, or somewhere near anything that have to do with any sub-subjects. Any suggestions?

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

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