Search This Blog

30 April 2017

EndorRouting - pathfinding between planets in a solar system

I came across this interesting challenge 

It seems more of a Math Wars than Star Wars, than their previous one (solution for the Quest Wars I challenge - Store Locations), but here goes nothing :)


GitHub repository:
there you can find the source code for the Android application, as an Android Studio project.

As we have a solar system, we are using a polar coordinate system.
We can find the implementation of the routing algorithm in source file, method: getRouteMinimax

In the same source file we can also find other implementations of routing calculations, but as we have commented in the source, they are either not optimal; a lot less correct or both.

Of course the shortest path between two planets would be a straight line. In "figure 1" we see this route, but while we are traveling in our space ship, the planet keeps traveling on its orbit as well and by the time we reach the planet we see that it has moved and is no longer where we made our route - "figure 2".
We can constantly keep updating our route while we travel - "figure 3". But this means a bit longer path. Instead we calculate where would the planet be at the time that it takes us to cover the route and make our route to that location - "figure 4". We are calculating it to 1 kilometer, but we can calculate it to as much or as little as we need it.

 figure 1

figure 2

figure 3

figure 4

We have lavishly used floats and doubles, but if we want to speed things up we have to consider where we can sacrifice on precision and use integers instead.
The Minimax calculations are performed on a single thread and as we know most of the star citizens use multi-core mobile devices that have at least 2 or 4 cores and the marketing people sent on new market planets are bound to have the newest and flashiest CPUs with more than 8 cores, so updating that part of the calculations to take advantage of multi-threading would bring a big benefit.

Please do not install the software on your space ships yet, because it is not production ready. It has small pieces missing like validation of input and such. It is just a prototype.


 (Solar system -
The movement is updated only 4 times a second. If we want it to be smoother, we just need to update it more times per second)