Timeline for How can I shorten the length of time spent on finding a path using my A* pathfinding code?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 15, 2022 at 12:30 | comment | added | Yakk | @AdamBarnes Also, barring really complex geometry, reducing the graph at longer distances means you can have local fine-grained paths, and looser paths at longer distances (shortest path to a zone instead of a square, where zones are closely connected), and keep using lookup tables. | |
| Jul 15, 2022 at 7:46 | comment | added | Adam Barnes | @ZizyArcher that's certainly correct if you naïvely apply the idea across the whole universe, but how likely is it the entire universe needs to be accurate at the same time? You don't need real behaviour, you just need behaviour that seems real to the player. Precompute stuff, compress it, and load localities to the player at runtime. | |
| Jul 15, 2022 at 1:02 | comment | added | Yakk | @ZizyArcher Yes, I assumed the OP described their problem. And yes, this is quadratic. There are O(n^(3/2)) fully calculated pathing solutions that lets you reach higher sizes (record distances to quadtree seams of self and adjacent; sum of seam distance quickly calculates 'midpoint'). And it also doesn't handle dynamic worlds as well as A star style can. | |
| Jul 14, 2022 at 7:47 | comment | added | Zizy Archer | Agreed, but this is probably just a small test map with the real one planned to be many times larger, making this approach unfeasible in practice. 20k spaces (200x100) is 100MB and probably the largest feasible. 100k (400x250) is 2.5GB already - people would complain about the game being a huge memory hog. | |
| Jul 14, 2022 at 2:42 | history | answered | Yakk | CC BY-SA 4.0 |