Timeline for Tweaking AStar to find closest location to unreachable destination
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 30, 2012 at 14:22 | comment | added | BlueRaja - Danny Pflughoeft | @Roy: A*, BFS, and all similar pathfinding algorithms will be exactly as slow as flood-fill, because they all need to inspect every connected node to make sure there is no path to the end. There are however ways to alleviate this issue; see here. | |
| Aug 30, 2012 at 13:45 | comment | added | snake5 | Yes, it could be slow. But the slowness would most probably come from having the nodes scattered throughout the memory; that can be easily fixed. Also, it's possible to speed it up by sacrificing some accuracy - just skip links that are too far or point in the wrong direction. | |
| Aug 30, 2012 at 13:35 | comment | added | Roy T. | Something like Flood Fill seems appropiate en.wikipedia.org/wiki/Flood_fill note that you still need to A* from the start node to the node with the lowest distance. Also note that this always involves inspecting all connected nodes and can thus be extremely slow. | |
| Aug 30, 2012 at 13:27 | history | answered | snake5 | CC BY-SA 3.0 |