Study: Navigation Mesh Generation
The NMGen Study is an adaptation in Java of Recast's static mesh functionality for purposes of study and experimentation. NMGen takes an arbitrary triangle mesh as input and generates data representing the traversable surface of the source mesh.
This documentation provides a thorough overview of the process NMGen uses to generate navigation meshes.
"A navigation mesh is an abstract data structure used in artificial intelligence applications to aid agents in path-finding through large spaces. ... Meshes are typically implemented as graphs, opening their use to a large number of algorithms defined on these structures." -Wikipedia
I became interested in navigation mesh generation after attending the Recast master class at AIGameDev.com. Two very productive ways of learning something are to translate it into something else, in this case Java, and to try to explain it to others, in this case through thorough documentation and visualizations.
This documentation will be useful to anyone who wants to get a high level overview of the process used by NMGen to generate navigation meshes. For those who want to go further, the NMGen source is documented to the extreme.
My goal is to make this documentation as useful as possible to others interested in this topic. So feel free to contact me if you find any of the text or visualizations confusing. I'll see if I can get it fixed up.
To Mikko Mononen for making Recast available for study and use by everyone.
(In order of importance.)
- Personal study. Especially computational geometry, voxelization, and associated data structures.
- Usefulness for study by others.
- Usefulness for follow-on projects. I.e.: Study of graph theory and associated search algorithms.
Due to these priorities, documentation is more verbose than normal, variable names are descriptive rather than concise, and code structure skews toward simple rather than efficient.
First and foremost, NMGen is an adaptation, not a port of Recast. Recast is about efficiency and concise code. Since NMGen's highest priority is the study of the algorithms, functionality found in Recast was dropped, reorganized, played around with, etc. Some specifics:
- NMGen only covers the static mesh functionality found in Recast as of version 1.4. Recast has a lot more functionality than is found in NMGen. Mikko is also continually enhancing Recast.
- While between 80 to 90% of the algorithms in NMGen closely match those found in Recast, there has been extensive refactoring of names and general structure to improve usefulness as a study tool.
- The high level structure has been adapted to fit Java standards more closely. Code is skewed toward OOP rather than the procedural programming structure used in Recast.
- While NMGen's performance and memory usage is decent, it is not as good as Recast. So the code is not suitable for generation of navigation meshes while the simulation is running.
NMGen is fully functional. But it is still only a prototype. So it is not suitable for use in professional projects without adjustments and more testing.
If you wish to benefit from studying NMGen you will need to be a beginner to intermediate level programmer who can read Java. The code is not particularly complex in structure, so people familiar with C#, C++, and similar languages shouldn't have a problem. People who are only familiar with VB and scripting languages may have difficulty with the syntax.
You will need a pre-calculus level of knowledge if you want to understand some of the more complex algorithms. I provide public sources for many of the algorithms. But without an adequate level of math you will have trouble understanding them.
If you are new to polygon meshes and their common data structures, I recommend detouring for a primer.
Documentation is broken down into three areas. The documentation on this site (overview documentation), API documentation, and detailed source code comments.
If you want to drill all the way down, then the process will likely be:
- This overview documentation.
- The API pages.
- Delving into the source code starting at the NavmeshGenerator class. (Source)
This overview documentation provides information on each step in the navigation mesh generation process with liberal visualizations, configuration information, and information on important data structures. Throughout this documentation there are links to associated API documentation.
The API documentation provides information related to structure and usage.
The source code is thoroughly commented with links to external references and extra visualizations. When I say "thoroughly" I mean that you can go through certain sections without reading any code. I do this to support the target audience which includes novices.
How you go through the documentation will depend on your level of knowledge and purpose.
Are you coming here from Recast? If so, you might want to review the differences between NMGen and Recast first, rather than last. Otherwise you may get confused with the differences in structure.
If you are a C++ developer who is familiar with computational geometry, then you can probably head right back to Recast after going through this overview documentation, skipping the API documentation and Java source. You can always pull up the associated Java source at Google Code and review its documentation if there is a particular Recast algorithm that is giving you trouble.
If you are new to navigation mesh generation or the techniques used by Recast, then start with this overview documentation. You can then move on to the API documentation and the source code, stopping at whatever level of detail you desire.
Mikko Mononen's Blog - Highly recommended for anyone interested in AI navigation and pathfinding.
Recast Navigation - C++ navigation mesh generation and pathfinding. The Wiki contains a lot of core references I don't repeat here.
Building and Traversing Navigation Meshes with Recast and Detour (Registration Required) - A video introduction to the process used by Recast to generate navigation meshes.
Navigation Mesh Generation via Voxelization and Watershed Partitioning with Mikko Mononen (Paid Membership Required) - A video interview/presentation of the process used by Recast to generate navigation meshes. (This is the interview that got me interested in the topic.)
Large-Scale Fluid AI Navigation in Complex, Changing Worlds (PowerPoint) - A presentation by David Miles that sparked Mikko's work.
More references are listed at appropriate locations within documentation.