• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
DarkSlayer

How to create a navigation mesh?

14 posts in this topic

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?
0

Share this post


Link to post
Share on other sites
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.

0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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...
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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)
0

Share this post


Link to post
Share on other sites
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.

0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0