I've been following this tutorial. http://www.gamasutra.com/features/20020405/smith_01.htm And already have my sectors and their portals however how do I know if I want to go from one sector to another which portal do I have to take? And how to find the sector path that is the quickest? Any info is appreciated. Also at what point to cross the sector(Without bumping with the edges or corners). Thanks.

Quote:

Original post by Antonym And already have my sectors and their portals however how do I know if I want to go from one sector to another which portal do I have to take? And how to find the sector path that is the quickest?

For your second question, A* (pronounced and googled A-Star) search is the most common technique for pathfinding of all sorts. Your first question, assuming the use of A*, is backwards: The search algorithm tries a portal to see where they end up, rather than deciding where they want to go and then picking the appropriate portal.

Quote:

Also at what point to cross the sector(Without bumping with the edges or corners).

Since all your sectors are convex, you can go from any point on one portal on a sector to any point on any other portal in the same sector and be guaranteed not to hit anything on your way there. So bumping into things is not the problem.

But how do I have to change the implementation of A* in this case? Since sectors vary in area.

What I meant is, say I am in sector A and want to go to sector B through the portal that connects both(Where their edges meet).

For example, the ship could crash with the corner while going through the portal it needed to make a sharp turn and/or if it were larger.
http://img527.imageshack.us/i/cornera.jpg/%5D%5BIMG%5Dhttp://img527.imageshack.us/img527/9381/cornera.th.jpg

It's not clear to me what that picture is showing. What is red? What is yellow? In any case, that picture does not show a navigation mesh.

The red are the sectors, the yellow are the sector edges. Whatever edges that meet would be the portals.

Quote:

Original post by Antonym The red are the sectors, the yellow are the sector edges. Whatever edges that meet would be the portals.

Then what's the deal with the spaceship? Is the green line a path for it? What is the red X? Why is the path going through an obstacle?

The green path is the a path the ship could take, it's not going through an obstacle but if it were wider it could bump with the corner of an obstacle. The edges where two sectors meet would be the portals. The tutorial I read wasn't explaining navigation meshes although I thought it was.

I skimmed the article, and as far as I can tell it doesn't discuss navigation meshes per se, but rather a discretized representation based on a regular grid (where multiple contiguous open grid cells are combined into 'sectors' to save memory and accelerate pathfinding queries).

Here's my (unsolicited) advice. I'm sure the method described in the article is perfectly sound, but I think it might be unnecessarily complex for what you're wanting to do. Also, since pathfinding is kind of a tricky topic (IMO), you might have better luck using a simpler and more straightforward approach (especially if you're new to the subject).

If I were you, I'd go one of two ways:

1. Use a 'real' navigation mesh.
2. Use a regular grid (uniformly subdivided, with no 'sectors' or other irregularities).

Of these two, the latter would probably be easier to implement. It looks like you already have code in place to identify what grid cells contain an obstacle or part of an obstacle, so it would probably be pretty easy to build a grid representation of the search space. From there, you would use an algorithm such as A* to build the actual paths.

The navigation mesh approach is a little more complex, IMO, but can yield very good results (since the paths that are built will reflect the actual obstacle geometry, rather than an approximation thereof).

There's also the issue of object size to consider. There are ways to address this issue with both navigation meshes and regular grids, but again, grids will probably be a little easier to work with in this respect.