Incremental improvement from A* to Dijkstra's

Sinus Pi · 2012-01-26T08:37:26

I'm looking for a way to smoothly present path improvement, starting from A* to a regular Dijkstra. I'm operating under an assumption that A* with its heuristics will find a path fast, while Dijkstra's will find the best path ever, though it might take significantly longer. Basically, I need my pathfinder to find (some) path immediately, with an option to improve it over the next second or two. Obviously gradual reducing the heuristic towards-the-target bias should do the trick, but at the unacceptable cost of recalculating every-damn-thing at each pass. I tried making A* not stop at a first found end node edge, and not putting the end node on the closed nodes list, but that resulted in the algorithm frantically hopping around the end node, trying to get at it from different angles. Also, nodes once visited in a seemingly good, but ultimately sub-optimal path (costly in terrain, but good in heuristics) were never visited again (closed list prevented that, naturally) even if backing away a bit from the proper direction resulted in finding a perfect shortcut path (very cheap terrain-wise, but not promising as far as heuristics go). So, here's my puzzle: is there a known combination of these algorithms, capable of somehow gradually reducing the use of heuristics? Perhaps by some clever "reviving" of closed nodes if they prove to be reachable faster (though when I tried it, it kept reviving all nodes around the goal, for some reason)..?

Artificial Intelligence Programming

Started by SinusPi January 24, 2012 03:18 AM

9 comments, last by wodinoneeye 12 years, 10 months ago

SinusPi

Author

102

January 25, 2012 10:04 PM

Well, without a node link to (next to) the target point the portals wouldn't be portals at all

Of course they have them. And the child node would have its heuristic show as very optimistic.

Hodgman

52,718

January 26, 2012 01:56 AM

[quote name='Hodgman' timestamp='1327379928' post='4905683']
A* will find the shortest path, assuming your heuristic is "admissible" (it never overestimates the minimal cost of reaching the goal).

Actually, I don't think it will: in a complex map where a direct portal (leading right next to the target point) lies just behind the starting point, no A* variant that I know of will ever knowingly move away from the target, unless it's stuck.[/quote]You missed the bold bit.

. 22 Racing Series .

wodinoneeye

1,691

January 26, 2012 08:37 AM

I would guess that a map problem which contains 'portals' would best be solved with a hierarchical AI where the portals (coarse level) search is based on a different distance system (and heuristic) and then with the fine level search being the more conventional cartesian heuristic.

--------------------------------------------[size="1"]Ratings are Opinion, not Fact

Incremental improvement from A* to Dijkstra's

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Incremental improvement from A* to Dijkstra's

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines