Navigation Mesh
| Main Page | Omni-bot Releases |
|
Navigation Tests
{{#widget:Picasa|user=jswigart|album=5222265322602352481|width=400|height=300|captions=1|autoplay=1}} |
Navigation Mesh
{{#widget:YouTube|id=9qUqX2GXyPY}} |
October 4 2008
You may have already seen the pictures of the experimental navigation mesh stuff taken from Quake 4 and Half-life 2 where you can get an idea what the sectors in the navigation mesh look like. What is new today is the 2nd video, showing the actual navigation mesh being used for pathing.
Questions?
- A NavMesh provides a far more accurate representation of the underlying walkable structure of the world than waypoints.
- A NavMesh can often represent the world with fewer sectors/regions than waypoints, translating to a savings of time and faster path-finding.
- ctf_2fort shown in the video is represented by 255 sectors in the navmesh, which is almost half the number of waypoints it takes to accurately represent the map.
- A NavMesh, due to how it represents the world, eliminates some unnatural path following quirks that are often seen in a waypoint system.
Navigation Meshes are difficult to build. In the best case a NavMesh would be built by analyzing the geometry of the map and generating the mesh automatically. This obviously saves someone having to manually set up navigation, like waypoints. The downside, however is that it is extremely difficult to generate an optimized mesh, meaning a mesh with as few polygons as possible.
This system currently uses a manually built mesh. Several reasons for this.
- Omni-bot must operate in multiple game environments on multiple engines. We have no desire to figure out how to pull information from raw map files across multiple games to generate a NavMesh automatically, and no game SDK's support such low level access to raw map geometry.
- In the games where it is easy to extract raw world geometry, like Quake4, the number of potential navigation faces far exceeds the desired complexity of the navigation mesh. This would force us to perform much more processing to filter them, or manual cleanup.
The method of generating the sectors for the Omni-bot Navmesh is easy to learn, and is a quick process. Currently, the process is actually faster than waypointing, and in the long run, will likely represent a significant time savings over waypointing, as waypoints are well known for requiring extensive testing and tweaking.
What's wrong with the waypoint system you have been using all this time?
Good question. A waypoint based navigation system, while being easy to implement and use, is generally a pretty poor representation of the game world. It is an acceptable level of coarseness in most cases, but where a waypoint system really fails, is situations where very accurate movement is required.
Take for example Team Fortress 2. An Engineer can build a sentry, and to maintain his sentry he must come upgrade or repair it by wacking it with his wrench. When pathfinding back to his sentry on a waypoint graph, he will generally pathfind to the nearest waypoint to the sentry and then straight line it the rest of the way. You should be able to imagine that doing this can result in undesirable pathing behavior from the bot. The 'closest' waypoint may be from an undesired direction, and depending on where the bots path comes from, can result in an unnatural path around the sentry to the 'closest' waypoint before upgrading/repairing.
Contrast that to a Navigation Mesh. The sentry generally exists in a large convex sector. When pathing to the sentry, the bot is pathing to the sector that contains the sentry, and the path will then go directly to the sentry point regardless of which direction the bot is coming from.
Statically defined goals can be made to work a bit better by placing additional waypoints, however you can't really do that for dynamic goals that require exact movement. If you have played against Omni-bot for any length of time you probably noticed that sometimes unnatural movement can be observed sometimes when the bot is running to a dropped flag for example. A navigation mesh eliminates most of these types of unrealistic pathfinding, since it generally provides an extremely accurate and optimized representation of the underlying walkable world. In addition, often the game world can be represented with much fewer navigation sectors as a waypoint system with similar coverage.