3 ms·
Looks similar to A* to my non-Clojure using eye. How has your performance been? If I use a 1000 x 1000 grid in my A* Python implementation I wrote last night it
by fuzz4lyfe 7y ago
Looks similar to A* to my non-Clojure using eye. How has your performance been? If I use a 1000 x 1000 grid in my A* Python implementation I wrote last night it takes forever.
[0]https://en.m.wikipedia.org/wiki/A*_search_algorithm https://en.m.wikipedia.org/wiki/A*_search_algorithm
- netb258 7y agoCool article. To tell you the truth I didn't really know about this algorithm. I just went at the problem function by function and this is what I ended up with.
- sdegutis 7y agoFor 20 years I couldn't make a Warcraft 2 clone because I just couldn't figure out A*. And now it turns out this Clojure program is probably doing just that! I can't wait to share this with my son. Having him help me port it to Lua might also end up teaching him a little Clojure too.
- valbaca 7y agoStay in school kids.
- thethirdone 7y agoI wouldn't expect performance to take forever (> 1 hr) for 1000x1000 in python. I know I have made not optimized path-finding that can solve 100x100 instantly (< 1 sec), and because the time complexity scales with # of vertices for planar networks that should mean that it would only take ~100 sec to solve 1000x1000.
- fuzz4lyfe 7y agoI was being hyperbolic, run time was more in the two minute range. Thank you for the numbers it seems my idea of thousands of units pathfinding over long distances isn't feasible in this way. My next idea is to "prerender" a series of interconnected waypoints across the map at the start and then pathfind to the nearest one before moving long distances using small bursts of pathfinding to move around obstacles and stay on track.