Navigation Mesh & Cost Function

There is a better solution -- basically, performing A* over incomplete funnels -- but it is rather involved to code up correctly. The simpler (and standard) solution is just to decompose long map-edges into shorter ones. That is, there are (say) five nodes along the map-edge connecting A and H, not just one node at the center of the map-edge. This can lead to dramatic slow-downs in certain contrived situations, but it'd do fine here.

Thanks for your reply. I "played" around with the multiple-nodes per edge solution, but my coworkers were not very pleased with it. There were still situations where the calculated path was a not "realistic enough" (as they say). *AllDesignersShouldBurnInHell* (just kidding). :-)

I admit, that I don't have THAT much experience in the pathfinding area, but somehow the desired "fast AND accurate AND realistic" path seems a bit illusional. This is my personal impression after reading some papers and postings. Correct me if I'm wrong.

But your tip about the "incomplete funnel search" just gave me the proper keywords to google for. Should have searched the forum, but sometimes you just don't know the right terms ;)
I will implement the funnel algorithm side-by-side with the existing navigation mesh and we will see.

Thanks again,
Markus

Valve has a power-point (pdf format) here on the AI in Left 4 Dead. After slide 11, it talks about their navigation mesh based system in some detail. While they don't give anything to solve the red path vs. yellow path problem, they do have some tricks for finding more optimal and more realistic paths.

Problems "solved" ;)

I added an incomplete funnel search into the A* pathfinder for distance calculation and it looks beautiful so far. I took the code from Modified Funnel Algorithm, refactored it a bit to suit my data-structures and needs and it works like a charm. The time spent in the actual pathfinding went up a bit, but not that much.
There are still some areas to improve performance, but right now, there are other tasks on the list :)


@Sneftel: Thanks again for pointing me in the right direction.

@Ezbez: Nice read, thank you, but I haven't found time so far to test some of these things out.

Nice to see that code finding good use!

In my experience, the occurrence of occasional suboptimal paths is not a big enough problem to warrant the time spent running the funnel on all nodes as A* progresses. In your diagram, both actual paths (hugging corners) are of similar enough length to look 'correct' during game play. I found that this is usually the case, unless you have created some pretty unusual world geometry.

If you are only using intersections in the A* search, ie nodes with three or more branches, it becomes even less practical to try to funnel along the way, as most distances will be precomputed. However, there are some simple 'cheats' that you can do to get more realistic estimates of pre-calculated distances.

My point is that I think the practicality of exact cost evaluation verses estimation would depend on the application. If you need very fast pathfinding for a large number of agents, then it's probably not worth it. If, on the other hand, speed is not the biggest issue, and exactly correct paths are (ie, the agent is following mouse clicks) then by all means take those extra steps to make it bulletproof.

In any case, good luck with your project!

Quote:

Original post by jack_1313 Nice to see that code finding good use!

I am Jack's increased rating, I give Jack a sense of well-being. :)

Quote:

Nice to see that code finding good use!

It was nice to find some actual code that isn't written in pseudo-language or described by mathematical equations that I can't understand :)

Quote:

If, on the other hand, speed is not the biggest issue, and exactly correct paths are (ie, the agent is following mouse clicks) then by all means take those extra steps to make it bulletproof.

That was exactly my problem. It just looked weird when the agent was running around a small obstacle in the opposite direction as you would have anticipated. As the gameplay relies on "predictable" movement of the NPCs, this wasn't acceptable, e.g. trying to lure some enemies around and they would walk the other way -> bang ! ;)
My first attempt was to smooth and straighten the path after it was found, but the problem from my opening post came up. And I asked myself: hmm, I can only smooth the path after it was found, but to calculate the movement-cost I need to KNOW that path before... aaaargh - total brain freeze at this time. AI/Pathfinding is still pretty new to me, even after 10 years of coding *g*

Quote:

In any case, good luck with your project!

Thank you :)