Polygonal Pathfinding with Incremental Funnel - how!?

I've not implemented the kind of solution you describe, i.e. using the funnel algorithm within A*. The more "traditional" approach would be to try to generate a better navmesh with polygon sizes that suit your pathfinder. This will not only be much faster, but you won't have to solve uncommon problems like this one...

Quote:

Original post by alexjc I've not implemented the kind of solution you describe, i.e. using the funnel algorithm within A*. The more "traditional" approach would be to try to generate a better navmesh with polygon sizes that suit your pathfinder. This will not only be much faster, but you won't have to solve uncommon problems like this one...

Certainly trying to find find better polygon sizes would be the one solution, but I'm not sure it is every going to ultimately solve the problem.

At the moment the navigation mesh generation is somewhat out of my hands, so I was hoping to find a solution on the pathfinding side, instead.

OK. There are two quick ways to solve this:

1. Recalculate your funnel from scratch everytime you need to calculate the heuristic. This is going to be expensive, but your A* datastructure will remain lightweight.

2. Store the information about the current funnel in each A* node on the stack, and add to it incrementally as you expand new nodes. This will be more efficient but take up loads more memory.


The ideal solution (once it works) is to try to find a compromise, what's the minimal amount of information that you need to store per A* node that will allow you an efficient representation and fast heuristic calculation.

I'd advice trying the super slow version first, to see if it gives you good results.

Quote:

Original post by alexjc 1. Recalculate your funnel from scratch everytime you need to calculate the heuristic. This is going to be expensive, but your A* datastructure will remain lightweight. 2. Store the information about the current funnel in each A* node on the stack, and add to it incrementally as you expand new nodes. This will be more efficient but take up loads more memory.

I'm confused - in both of these cases, don't I cause my cost-per-node to change during the calculation of the cost (i assume you meant cost, not heuristic)? And doesn't this change cause problems in the cost of the other child nodes?

Is the node cost calculate by the funnel-path's intersection with each node edge?

Yes, I meant cost and not heuristic. Your cost is going to change based on the way you arrive into a node, but that shouldn't be a problem. Some A* implementations have the ability to check if a node is already in the open list, and update that value. I wouldn't worry too much about the child nodes also changing, A* will expand your nodes in a sensible order, so it should look OK even if it is theoretically not accurate. You'll have to try it for your problem.

Alternatively, you can treat the whole search space as one large tree (instead of a graph) and have each position+path as a unique node within A* -- but it's much slower. We do this for animation/motion planning.

Anyway, just try it out! If you have everything in place it won't take you long to experiment.

Quote:

Original post by alexjc Yes, I meant cost and not heuristic. Your cost is going to change based on the way you arrive into a node, but that shouldn't be a problem. Some A* implementations have the ability to check if a node is already in the open list, and update that value. I wouldn't worry too much about the child nodes also changing, A* will expand your nodes in a sensible order, so it should look OK even if it is theoretically not accurate. You'll have to try it for your problem. Alternatively, you can treat the whole search space as one large tree (instead of a graph) and have each position+path as a unique node within A* -- but it's much slower. We do this for animation/motion planning. Anyway, just try it out! If you have everything in place it won't take you long to experiment.

Thanks for the push. I realized that some optimizations I had made to my A* were causing me the grief:

I assumed that, because circular loops would yield more expensive paths, I never had to consider if a new node I was adding to the open list was already in my path or not - it would always be more expensive to visit it twice. Using the string pull distance as my cost, instead of the sum of my parent's cost and my local 'parent-to-me' cost, was yielding circular loops because sometimes costs seemed artificially smaller, causing infinite recursion.

Now, every time I consider a new node for addition to the open list, I confirm it isn't in my list of ancestor nodes at all before proceeding. I'm not sure if this is an appropriate addition, but it was necessary to solve the cases where sometimes a child node's 'total cost' was lower than it's parent's cost as a result of its orientation relative to a vertex causing a lower cost from the string pull distance.

Hope that makes sense.

update: actually, not so fast ... it seems like this solution doesn't give me the best path in all cases - in fact, where it solves one set of problems, it introduces another. My strategy as a test was to recalculate a string-pulled distance for every new node added to the open list, and set the 'cost' to be the Euclidean distance between each point in the string-pulled path. For some cases, this works, but for others it seems to never investigate the best-path case. ... more puzzling to be done.

double-actually: looked like some bugs in some code crept in with my change over here, so things are looking like they might be working at the end of the work week.

I'll do some profiling and see how it performs on the consoles.

[Edited by - Sphet on May 7, 2010 8:27:45 PM]

I thought I would update this in case anyone searches for the topic.

While I did end up getting the funnel algorithm to run on incomplete costs, I achieved almost the same results by subdividing long edges into three nodes: both end points, and a midpoint. It increased the number of nodes potentially searched but was ultimately faster than performing the funnel at every step.