6 ms·

Question about the navigation mesh. I'm assuming that represents an entire open area (otherwise the path optimization makes no sense) and the dark stuff are th

by kriro 14y ago

Question about the navigation mesh. I'm assuming that represents an entire open area (otherwise the path optimization makes no sense) and the dark stuff are the obstacles. In that case I'm wondering how the arrive at the actual grids and arrows (slide 12)

NickPollard 14y ago
Navigation meshes are commonly generated from actual collision geometry, i.e. as created by the art and design team.
gmaslov 14y ago
This link explains fairly well how a navigation mesh may be automatically generated from the level geometry: http://udn.epicgames.com/Three/NavigationMeshReference.html http://udn.epicgames.com/Three/NavigationMeshReference.html . I believe it's also a good practice for the level designer to examine it manually and make any necessary corrections for sharp corners, narrow corridors, etc. As for the path, A* search is usually the name of the game for any kind of 2D pathfinding. With the usual Euclidean distance heuristic it always returns the shortest path, but it's possible to use an "inadmissible" heuristic to make it run faster (and produce sub-optimal paths). The arrows shown on the slides are a little baffling; I can't imagine why those four vertically stacked boxes on the right-hand side would create a jagged path, for instance. It may just be exaggerated for effect.
- deleted 14y ago
  [deleted]
- kriro 14y ago
  Yeah I couldn't make sense of the arrows but I only know AI from 2d and have 0 clue about 3d game development. Most toy examples I know use an even square grid so I was wondering if I might be missing something there. Either way thanks for the answer (same goes for the other posters who provided links)
akx 14y ago
You might be interested in checking out https://code.google.com/p/recastnavigation/ https://code.google.com/p/recastnavigation/ (which, coincidentally, is what UDK/UE3 also uses nowadays (as a reference to the sibling comment))
winterismute 14y ago
Yes, navigation meshes can be created either automatically, by a designer, or through a mixture of the 2 (usually they are first computed and then adjusted by someone). Indeed, automatic and stable generation is essential in case of big, procedurally generated scenes, and it would be in general a nice achievement for the field. gmaslov provided links that explain some common ways of generating navigation meshes, that quickly looked to me like improved/refined application of the "flood filling" method. I just wanted to point out that there is a very interesting way (imho) of generating a 2D/multilayered navigation mesh, which is, by computing the Generalized Voronoi Diagram of the obstacles and then by annotating the vertices (and thus edges) of the graph with information about the closest obstacles' points. This way, we have both a "backbone graph" and a subdivision (a mesh). Here is a link to the related research of my Uni: http://www.staff.science.uu.nl/~gerae101/motion_planning/ecm.html http://www.staff.science.uu.nl/~gerae101/motion_planning/ecm... check it out if you are interested, there are also a couple of summarizing images and videos. The advantage is that such meshes are smoother, compact, yet they ensure very good coverage of the walkable space. Disclaimer: I am a MSc student working on the above method for my final thesis (involving GPGPU steps and a true multi-tiled approach).

by kriro 14y ago

NickPollard 14y ago

Navigation meshes are commonly generated from actual collision geometry, i.e. as created by the art and design team.

gmaslov 14y ago

This link explains fairly well how a navigation mesh may be automatically generated from the level geometry: http://udn.epicgames.com/Three/NavigationMeshReference.html http://udn.epicgames.com/Three/NavigationMeshReference.html . I believe it's also a good practice for the level designer to examine it manually and make any necessary corrections for sharp corners, narrow corridors, etc. As for the path, A* search is usually the name of the game for any kind of 2D pathfinding. With the usual Euclidean distance heuristic it always returns the shortest path, but it's possible to use an "inadmissible" heuristic to make it run faster (and produce sub-optimal paths). The arrows shown on the slides are a little baffling; I can't imagine why those four vertically stacked boxes on the right-hand side would create a jagged path, for instance. It may just be exaggerated for effect.

deleted 14y ago
[deleted]
kriro 14y ago
Yeah I couldn't make sense of the arrows but I only know AI from 2d and have 0 clue about 3d game development. Most toy examples I know use an even square grid so I was wondering if I might be missing something there. Either way thanks for the answer (same goes for the other posters who provided links)

akx 14y ago

You might be interested in checking out https://code.google.com/p/recastnavigation/ https://code.google.com/p/recastnavigation/ (which, coincidentally, is what UDK/UE3 also uses nowadays (as a reference to the sibling comment))

winterismute 14y ago

Yes, navigation meshes can be created either automatically, by a designer, or through a mixture of the 2 (usually they are first computed and then adjusted by someone). Indeed, automatic and stable generation is essential in case of big, procedurally generated scenes, and it would be in general a nice achievement for the field. gmaslov provided links that explain some common ways of generating navigation meshes, that quickly looked to me like improved/refined application of the "flood filling" method. I just wanted to point out that there is a very interesting way (imho) of generating a 2D/multilayered navigation mesh, which is, by computing the Generalized Voronoi Diagram of the obstacles and then by annotating the vertices (and thus edges) of the graph with information about the closest obstacles' points. This way, we have both a "backbone graph" and a subdivision (a mesh). Here is a link to the related research of my Uni: http://www.staff.science.uu.nl/~gerae101/motion_planning/ecm.html http://www.staff.science.uu.nl/~gerae101/motion_planning/ecm... check it out if you are interested, there are also a couple of summarizing images and videos. The advantage is that such meshes are smoother, compact, yet they ensure very good coverage of the walkable space. Disclaimer: I am a MSc student working on the above method for my final thesis (involving GPGPU steps and a true multi-tiled approach).