Stark Posted January 2, 2014 Author Share 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. Link to comment Share on other sites More sharing options...
FrostBug Posted January 2, 2014 Share 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 Link to comment Share on other sites More sharing options...
Stark Posted January 2, 2014 Author Share 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. Link to comment Share on other sites More sharing options...
Stark Posted January 2, 2014 Author Share 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. Link to comment Share on other sites More sharing options...
FrostBug Posted January 2, 2014 Share 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 Link to comment Share on other sites More sharing options...
Deffiliate Posted January 2, 2014 Share Posted January 2, 2014 Are you by any chance going to make this open source? Link to comment Share on other sites More sharing options...
Stark Posted January 2, 2014 Author Share 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 Link to comment Share on other sites More sharing options...
Stark Posted January 2, 2014 Author Share Posted January 2, 2014 Just mapped out Burthorpe and Taverly Link to comment Share on other sites More sharing options...
Swaq Posted February 7, 2014 Share Posted February 7, 2014 Made by Stark, watch it be made and never to be updated again. Link to comment Share on other sites More sharing options...
