I am working on a 2d spaceship game and want to implement a navigation mesh. Is there a method to automatically creating the navigation mesh based on some geography? I haven't had luck looking around for any material on the subject. Right now I am able to generate a grid with the walkable/unwalkable portions of the scenario, may that help? Any info is appreciated. Thanks.

Thats a start, you could use that grid and try to colapse (think thats the word) edges. if you have say 4 squards making up a larger square then you want to colapse them to one larger square.

Oh do you mean something like what's presented in this tutorial?
http://www.gamasutra.com/features/20020405/smith_01.htm

I thought that wasn't how a navigation mesh was constructed. Is that it?

One method of creating a navigation mesh (as opposed to a simple grid with passable and un-passable cells), is to decompose the 'open areas' in the environment into convex polygons. Using the image in your other thread as an example, the obstacle towards the top of the screen would be 'negative space' (i.e. impassable space), while the rest of the play area would be decomposed into triangles or convex n-gons.

As for the decomposition step itself, one approach is to build a constrained Delaunay triangulation from the obstacle geometry. This is the method I've been using, and I've been very happy with the results. (I use the Triangle library to perform the decomposition.)

Thanks for your two replies. I have already given pathfinding on a grid a try and it was okay. I've been obsessed with navigation meshes ever since I heard about them. Everyone seems to agree that they are great and they seem so intuitive aswell.

About Triangle, that would work aslong as I didn't want to sell games made with it. In that case I would be screwed wouldn't I?

Here's an update image just in case. Just now have I realized how little self-explanatory power the one I had uploaded before had. Green cells = walkable, red cells = unwalkable. Second image depicts the sectors built from the green cells.
http://img4.imageshack.us/img4/8913/playfieldt.jpg

Quote: About Triangle, that would work aslong as I didn't want to sell games made with it. In that case I would be screwed wouldn't I?

Your best bet there would be to contact the author regarding the exact licensing terms.

Quote: Here's an update image just in case. Just now have I realized how little self-explanatory power the one I had uploaded before had. Green cells = walkable, red cells = unwalkable. Second image depicts the sectors built from the green cells.
http://img4.imageshack.us/img4/8913/playfieldt.jpg

Yes, that makes more sense. As I said in the other thread, unless the grid will be significantly larger than in your example images, I wouldn't bother with the 'sectors and portals' approach (that's just me though).

[Edited by - jyk on September 4, 2009 6:55:24 AM]

Alright my second try at constructing a navigation mesh.

The red portions are the 'walls'/obstacles. Are the triangles too thin? If they aren't how should I procced to perform A* on a navigation mesh? How do you know which path is the shortest when the 'cells' don't have any definite shape?

http://yfrog.com/14secondtryp

Quote: Original post by Antonym
Alright my second try at constructing a navigation mesh.

The red portions are the 'walls'/obstacles. Are the triangles too thin? If they aren't how should I procced to perform A* on a navigation mesh? How do you know which path is the shortest when the 'cells' don't have any definite shape?

http://yfrog.com/14secondtryp

Only have time for a short reply at the moment, but based on the image, I would suggest using a simplified version of the obstacle geometry for the purpose of pathfinding. This will most likely drastically reduce the number of triangles in your navigation mesh, and get rid of most of the small and/or thin ones as well. (A fairly straightforward simplification method would be to collapse sequences of nearly colinear vertices into single line segments.)

As for finding the shortest path, finding the 'real' shortest path can be a little complicated, but here's one way to go about finding a 'reasonably short' path:

1. As a preprocessing step, build a graph, the nodes of which are the midpoints of unconstrained triangle edges, and the edges of which are weighted according to the Cartesian distance between the node points.

2. Run A* (or the search algorithm of your choice) to build a 'node-to-node' path. Note that you'll have to factor the start and end points in somehow.

3. Use line-of-sight smoothing (fairly simple) or the string-pulling or funnel algorithm (not as simple) to smooth out the path (otherwise it'll go directly from edge midpoint to edge midpoint, which won't look very natural).

Maybe this is useful to you?

http://code.google.com/p/recastnavigation/
http://www.codercorner.com/blog/?p=325

How can you test how collinear two segments are?

I've been playing with the switches in triangle and got this as my third try.
http://yfrog.com/10thirdtryp

Let's see. The graph would be a list of each triangle and the triangles each is connected to(Pointers to which ones it is connected)? The cost of the adjacent triangles would be the distance between both centers?

Gonna take a look into those algorithms you mentioned.

[Edited by - Antonym on September 12, 2009 6:33:45 AM]