Sign in to follow this  

Navigation mesh

This topic is 3099 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi there, I'm making a relatively simple point and click adventure game, and could do with some help to get my navigation grid working well. To show an example of what is the problem, the example below shows a simple grid, and how my program plots the route (not sure how to make image URLs work on this). http://img221.imageshack.us/img221/1022/path.gif http://img196.imageshack.us/img196/4117/pathactual.gif The way it works is that the game knows A connects to B, and B connects to C. Its a simple node-graph, and the first stage of path finding is to plot the node path needed to reach the point. For example, the start point is on A, the end on C. Through a crude depth first search, it would know that the shortest route is A-B-C. From that, the actual coordinates are worked out. So, waypoint A is the nearest point on the line between A and B. From there, the nearest point on line B-C, and finally the endpoint itself. Whilst this approach does work, its not ideal, and can end up with some very daff routes coming out. The ideal approach would get this route: http://img268.imageshack.us/img268/7122/pathideal.gif Can anyone point me to an algorithm of sorts to plot a better route? Or alternatively, is there an efficient way of determining if a line remains within the mesh (i.e. a function that would return false for a line between the first and last point, but true for the second and last point).

Share this post


Link to post
Share on other sites
It sounds like you already know that there are more direct ways than a depth-first search to find the shortest path to the goal node, so I won't elaborate on that.

As for smoothing the path, there are a few options. One approach uses line-of-sight tests (this seems to be what you have in mind), which will often give decent (although not always optimal) results. How best to perform the line-of-sight tests depends on a few different factors, such as the size of the grid, and whether grid cells are always fully blocked or unblocked. (An approach that's quite efficient is 2DDDA. If your grid is relatively small though, you might be able to get away with multiple segment-box tests, perhaps accelerated by broad-phase culling.)

The most accurate path-smoothing algorithm that I'm aware of is the 'funnel' or 'string-pulling' algorithm. It's a bit tricky to implement (especially if you want to take the radius of the agent into account), but will always return the optimal path from one point to another.

Share this post


Link to post
Share on other sites
Thanks for the reply, I'll have a look at the algorithms you suggested, although I will point out that I'm not using a true grid, but a mesh of polygons - apologies as this definitely wasn't clear from the diagrams.

That said, I think your suggestions will be useful, thank you :)

Share this post


Link to post
Share on other sites
Quote:
Thanks for the reply, I'll have a look at the algorithms you suggested, although I will point out that I'm not using a true grid, but a mesh of polygons - apologies as this definitely wasn't clear from the diagrams.
Yes, what I posted earlier applies to navigation meshes as well, for the most part (except for the part about 2DDDA and segment-box tests).

I just finished implementing a navigation mesh-based pathfinding system with path smoothing, so if you need any more information or get stuck on anything, feel free to post back and I'll try to help further if I can.

Share this post


Link to post
Share on other sites

This topic is 3099 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this