Timeline for A* pathfinding takes too long, shortcuts needed
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 6, 2017 at 19:36 | comment | added | dpaz | I am not sure, and I do not have the code on hand at the moment. The path itself was probably around 400 nodes long, so that is an absolute minimum of 400 nodes processed in 1.5 ms. Based on what you are telling me, that seems quite acceptable for C# on an old i7 920. It makes me feel better about having spent all of my free time outside of work for two days getting it to where it's at. | |
| Dec 6, 2017 at 19:10 | comment | added | amitp | 300 nodes ÷ 30ms = 10 nodes / ms. I would expect somewhere between 100 nodes/ms and 1000 nodes/ms with a standard heap data structure and without hierarchies/waypoints. | |
| Dec 6, 2017 at 19:00 | comment | added | amitp | No, I can't be sure; it will depend on your requirements. But the original post here said it processed 300 nodes in 30 ms, which seems much slower than what you're talking about. For the 1.5ms (which seems good!), how many nodes did it explore in that time? | |
| Dec 5, 2017 at 6:20 | comment | added | dpaz | You mentioned that a 108x192 grid should not require hierarchies, waypoints, etc. Are you sure? I have been working on an A* algorithm for a few days, and I am pretty sure it is almost as fast as I can make it. I may be able to cut the times in half once more, but that does not feel like enough. In a 15x250 grid, it is taking about 1.5 ms to calculate a single path, on average. 1500 ms for 1000 iterations. Connectivity is only 4, and the path itself is not mazelike at all. Two straight shots. What kind of performance should I be expecting? | |
| Apr 13, 2017 at 12:18 | history | edited | CommunityBot |
replaced http://gamedev.stackexchange.com/ with https://gamedev.stackexchange.com/
|
|
| Apr 22, 2016 at 16:38 | history | answered | amitp | CC BY-SA 3.0 |