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.

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(n²) 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, 201412 yr by FrostBug

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(n²) 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.

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.

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

Are you by any chance going to make this open source?

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

Just mapped out Burthorpe and Taverly

Made by Stark, watch it be made and never to be updated again.