I have a potential field that updates periodically. It generates a short path to follow between (expensive) field/path updates. To generate the path, I'm just using a greedy best-first search that gives up when it hits the max path length (tick rate / path update rate) or a local maxima. Is there a smarter algorithm I should try? (eg one that keeps in mind the total potential of the path, instead of just the best neighbor?) My graph theory education ends at Dijkstra. EDIT: I should explain this better. The potential field is queried at certain points (places Entity can move to this tick). It searches all those places, adds the best one onto the path, searches again from there, etc. It doesn't know where it's pathing TO, it's just looking for the best available within x steps. I'm hoping to avoid most pathfinding issues by changing the potential field, rather than making the pathfinding more complicated. If you're stuck in a local maxima, for example, the field will change to get you out of it. I may not need a more advanced pathfinding solution, I'm just inquiring. [Edited by - CadetUmfer on April 28, 2010 9:54:27 AM]

The main benefit of potential fields is that you can just follow them reactively and not have to generate the whole path. For situations like horse shoes that you mentioned, you can get around that by grouping your obstacles into convex obstacles (circle is probably best) and applying a force around those. Are you sure what you're doing is necessary?

If you'd like to search over that map, and treat it as an influence map instead, then A* is still the most optimal way you can find a solution -- but because there are variable costs at each 2D point, it's going to be slow.

Did I miss anything?

Quote:Original post by alexjc
The main benefit of potential fields is that you can just follow them reactively and not have to generate the whole path.

I'm just trying to plan ahead a little bit, so that I can find the performance sweet spot. By adding a little bit of planning, I'm hoping to be able to slow down my potential fields.

For example, right now my potential fields update every 0.5 seconds, my physics every 0.05. So the PF generates a path of up to 10 steps describing how to move. This seems much quicker than trying to keep the PF up to date and just reacting (moving to best neighbor).

LPA* looks interesting. Not sure if I can use it in this case, since I have no idea which edge costs changed until I check them (the PF is lazy).

OK, I see.

I'd just use brute force local A* on a regular basis with a maximum search iteration set at a value that you pick based on performance. [EDIT] Your A* wouldn't have the usual heuristic since you don't have a goal, but the rest would be the same.

Quote:Original post by Sneftel
In that case you'll be interested in D* Lite, a variant of LPA* that does not require full prior knowledge of the state space or of changes to the edge costs.

The thing about either of these algorithms is that they're not as trivial to implement, and much harder to justify. Do you think it's worth it in this case?

It probably isn't justified yet--but I know where to look, thanks.