Improved route finding

[tuomount]

Improved route finding when starmap has been explored around the route. If starmap has explored are where route is being laid and there is blocked sector on way(Black hole, star or gas giant) A* pathing should be used to find best route around it. This is quite challening since it should not work on unexplored parts of star map or if there are cloaked enemy ships those should not be exposed when plotting the route.

[tuomount]

Moving this to 0.26.0

[mauof]

Hi, I am a CS university student and I would love to try working on this issue for one of my lecture. Would that be okay with you, do you think it this issue is suitable?

[tuomount]

Of course you can try. Does your course require that you need get it to main branch?

[mauof]

Thank you. While merge is not technically absolutely necessary, it would make the evaluation quite a bit easier. Of course, considering my contribution is actually working. Do you maybe have some pointers or tips where I should be looking in the code and what to be careful about?

[tuomount]

Project already has A* algorithm implemented but it never has been used for whole starmap. This would definitely get most optimal way, but it might be heavy on CPU. Specially if you think that player should be able to move mouse cursor quite fast, so calculating route should not take long.

My idea was something like this:

So there one wants to move from point A to point B. Direct line is blocked by a star. Algorithm would check route from up and down side of the star and either of those as new point. Then continue from there towards point B. If there is something blocking the way then again check from up or down which route to select.

Problem with this is that routes need to have more points, now they only have single target point. Currently starmap travel is done with org.openRealmOfStars.starMap.Route.java. So I would add array of intermediate points in route class and try to move from there. Calculating the route also requires starmap information and playerinfo in order to get what scanners can actually see while planning the route.

[tuomount]

What you also need is PlayerInfo.java getSectorVisiblity() method to resolve if sector has been charted or not. If it has been charted then you can StarMap.java isBlocked() method to check if sector is blocked. A* algorithm might not be that suitable also for reason that FTL drives use straight line instead of moving single sector at once.

And in my previous post that straight line from A to B going horizontally is a bit special case since checking the reroute is simply up and down, but I think it would be better to use trigonometry and take 90 degrees off from the original direction and check if reroute is possible on that line.