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).

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.

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 :)

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.