Stark Posted January 2, 2014 Author Posted January 2, 2014 Why Dijkstra? Using a heuristic based algorithm would likely be a lot faster. (A* might outperform Dijkstra quite a bit with an accurate heuristic) The complexity of the RS map means that any fast heuristic would be inaccurate most of the time, or if you did make an accurate heuristic it would be slow. I may be wrong, but that's how I interpreted it and decided to use Dijkstra.
FrostBug Posted January 2, 2014 Posted January 2, 2014 (edited) What kind of complexity are you referring to? Even if the map is weighted for stuff like doors, a heuristic will immensely improve the runtime, as long as you dont let it overestimate the heuristic distances. How is the graph built? If its a node-edge based graph where each node has like.. 1-3 neighbours and long/medium distance edges, then I see no issue with a heuristic.. Dijkstra is not much better than Breadth first search, with a runtime of O(n2) compared to A*'s potentially linear runtime. If the graph is how I imagine it, I would recommend Euclid heuristic Performing a large-scale pathfinding between 2 faraway points would be ridiculously time consuming without one Edited January 2, 2014 by FrostBug
Stark Posted January 2, 2014 Author Posted January 2, 2014 What kind of complexity are you referring to? Even if the map is weighted for stuff like doors, a heuristic will immensely improve the runtime, as long as you dont let it overestimate the heuristic distances. How is the graph built? If its a node-edge based graph where each node has like.. 1-3 neighbours and long/medium distance edges, then I see no issue with a heuristic.. Dijkstra is not much better than Breadth first search, with a runtime of O(n2) compared to A*'s potentially linear runtime. If the graph is how I imagine it, I would recommend Euclid heuristic Performing a large-scale pathfinding between 2 faraway points would be ridiculously time consuming without one I'll look into it. At the moment, I'm getting average ~15ms to calculate a path with ~1k nodes, with furthest apart nodes. Once I map out more, I'll see how it scales.
Stark Posted January 2, 2014 Author Posted January 2, 2014 Just did a bit of optimisation, and got the runtime down to 2ms to 4ms, without the use of any heuristic. I'll probably end up adding some sort of heuristic to it, if the runtime gets much higher as I add more nodes/edges.
FrostBug Posted January 2, 2014 Posted January 2, 2014 Just did a bit of optimisation, and got the runtime down to 2ms to 4ms, without the use of any heuristic. I'll probably end up adding some sort of heuristic to it, if the runtime gets much higher as I add more nodes/edges. Ah, that's quite a bit faster than I had expected o_O Gj on that ;), Guess a heuristic won't be necessary after all
Deffiliate Posted January 2, 2014 Posted January 2, 2014 Are you by any chance going to make this open source?
Stark Posted January 2, 2014 Author Posted January 2, 2014 Just mapped out Al-Kharid. I've also edited my webmaker so that it shows me the path it generates between two tiles I click on the map. I'll show a demo once I've mapped out a few more areas. It's awesome :P Are you by any chance going to make this open source? Not at first. I might consider releasing open source later on, though. If you have any questions about how it all works, feel free to PM me or add my skype: noble.stark1
Swaq Posted February 7, 2014 Posted February 7, 2014 Made by Stark, watch it be made and never to be updated again.
