Timeline for How can I make A* finish faster when the destination is impassable?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 12, 2017 at 19:05 | comment | added | Harrichael | A practical solution is likely to be search forward and backward. Not only is this a fast search but in games, this will lead to the practical effect of early termination when destination is impassable, and fairly early termination when the destination is blocked off. | |
| Jan 23, 2015 at 8:41 | vote | accept | user2499946 | ||
| Jan 8, 2015 at 13:37 | comment | added | Zolomon | Another thing to do is to run it from both directions at the same time. Then the worst time scenario will be at the midpoint where the two paths would meet (at that time you can cancel either of the two algorithms and continue with the other). This way you basically half the time needed (tradeoff is utilizing more CPU & memory). | |
| Jan 5, 2015 at 6:34 | history | edited | Steven | CC BY-SA 3.0 |
added 50 characters in body
|
| Jan 4, 2015 at 18:07 | comment | added | Steven | @kasperd of course there is nothing preventing island ids being recalculated, merged at runtime. The point is that the island ids allow you to confirm if a path exists between two nodes quickly without doing astar search. | |
| Jan 4, 2015 at 17:55 | comment | added | kasperd | Island IDs don't need to be static. There is a simple algorithm which would be suitable in case there is a need to be able to join two separate islands, but it cannot split an island afterwards. Page 8 through 20 in these slides explain that particular algorithm: cs.columbia.edu/~bert/courses/3137/Lecture22.pdf | |
| Jan 4, 2015 at 0:02 | history | edited | Steven | CC BY-SA 3.0 |
More ideas, better formatting
|
| Jan 3, 2015 at 23:55 | history | edited | Steven | CC BY-SA 3.0 |
More ideas, better formatting
|
| Jan 3, 2015 at 14:32 | comment | added | AturSams | Flood fill or BFS each area. | |
| Jan 3, 2015 at 4:21 | comment | added | Slipp D. Thompson | +1 For recognizing that the issue is likely barriered-off areas (not just impassible tiles), and that this kind of problem can be solved easier with early load-time calculations. | |
| Jan 2, 2015 at 17:29 | comment | added | MSalters | If there are different agents with different rules, but not too many, this can still be generalized fairly efficiently by using a vector of IDs, one per agent class. | |
| Jan 1, 2015 at 17:10 | history | answered | Steven | CC BY-SA 3.0 |