Create a Shortest Path (A*) route planner

[hastarin]

The current route planner makes a best effort to find a path with minimal jumps between the source and destination, but it's a greedy depth first search (if I understand the terminology correctly) and whilst it's damn fast the path found may not be the optimum one.

[hastarin]

There are a lot of explanations of the A* algorithm out there.

This is perhaps the one I've had the most chance of understanding so far: http://blog.nobel-joergensen.com/2011/02/26/a-path-finding-algorithm-in-unity/

[stringandstickytape]

I remember I once pulled together an A* implementation, I was getting nowhere until I saw this illustration on Wikipedia... => http://upload.wikimedia.org/wikipedia/commons/5/5d/Astar_progress_animation.gif

[hastarin]

My problem is two fold.

1. I'm an engineer and not a computer scientist, so I don't understand all the terminology used.
2. The examples I've found (like the one you linked) are mostly in 2D and involve finding their way around obstacles.

That's why I chose to just implement something for now and improve upon it later. ;)

[hastarin]

I've started working on this, but either I still don't understand the algorithm, or there is something wrong with my implementation because it's on average no better than what I'd already done.

Ie it sometimes find a better route, but often finds routes that are longer and/or have more jumps.

See commit 71d791a3636372464d0a0844f5f5c11690bc2fe3 for Unit Tests comparing algorithms.

It might be a case of getting the correct heuristic.

[stringandstickytape]

Hm. From what I remember of A* it shouldn't matter if the map is 2d or 3d - all A* needs to know is a) how many points (systems) you've got, b) which systems are "linked" (can be travelled directly between) and c) the length of the paths linking them. So 3d maths comes in (pythagoras) in c) where you need to work out the distance between system a and system b, but 3d shouldn't be relevant after that. To be clear, A* doesn't need to know the locations of the systems - just how they join together and the lengths of the paths that join them.

I was at one point writing a Sim City-style game in C#, it had a working A* implementation in it. I'll see if I can dig it out at some point. I remember finding that artificially increasing the length of a path between two points made the algorithm favour other routes, which was quite useful when simulating traffic levels (not an issue in ED of course).

Will try to take a look at your code in the next couple of days - pushed for time at the moment. I see you have gone MVVM! I've spent 7.5hrs a day for the last three years writing MVVM code, and I still can't decide if it's a good model or not... although doubtless better than the "I'm allergic to objects" approach I took on day one of this project! :)

[hastarin]

Yeah, I found a version from UnityUtils that I adapted. Like I said, I'm not sure what's wrong. I think it may be that the algorithm may discard points too early to find the true optimal path. Ie when it takes the cost + heuristic into account it may replace a node early on that would have actually worked out better in the long run because it lead onto other shorter options.

I'll tackle it again down the track.

On the bright side. I've now compared my algorithm to this and two other route planner websites, and it stacks up reasonably.

And yeah, when I first started with MVVM I wasn't sold on it, but it's grown on me. Particularly when aided by custom templates in Resharper, and using libraries like MVVMLight.

[stringandstickytape]

algorithm may discard points too early to find the true optimal path

When I did that SimCity style game, I found that for even as many as 50,000 nodes ( = 50,000 systems in the ED metaphor), it was faster and better overall, and used relatively-negligible memory, to calculate the whole A* table once. Which is to say, work out the shortest path from every node to every node, and then never recalculate it. Might be worth a try.

We could even consider pre-calculating this for the systems we know the location of, using a standalone utility, and then distributing the completed data with the release as an XML (or whatever).

These are just ideas though :)

[hastarin]

It turns out I needed to use actual distance, not distance squared! That finds the shortest path with the A* algorithm I have. Of course the downside compared to the algorithm I'm currently using is then time (though still under 1 second on my PC) and the fact you end up making more jumps.

I now need to try and find what I can use for a heuristic and a cost function so that it minimizes jumps whilst staying as close as possible to the shortest path. Perhaps a tall order, but I'll give it a go.

[hastarin]

Actually that was simple enough.

Cost is 1 h = Ceiling(Distance/JumpRange)

The end result though is relatively slow (up to 2 secs in my unit tests) and of course whilst it minimizes jumps may increase the actual distance travelled.

That said, it's still a LOT faster than the game itself and with the two sets of costs/heuristics I can calculate the equivalent (assuming we have all the stars mapped) of the economical and fastest routes.

I may have to give the user the choice of algorithms to use...

[hastarin]

And as done as I'm going to be with this. :D abfdda5cf5f204be2383b24ad9e8f4a1223afbce