The galaxy map is really slow at plotting routes over about 60-70LY. We know this. Why?
I've been taking a look at it's behaviour, and think I know why it takes ages. I wouldn't be suprised if the current algorithm looks similar to this:
1) Find all planets within a set range. Probably uses an octree to grab candidates very quickly. The procedural generation seems fairly swift, so I doubt that's a big hitter as we can see them very quickly.
2) Sort them by range, closest to furthest. Pretty standard stuff, and the list isn't going to be massive. Computers are good at sorting.
3) Starting at the start of the list, calculate the fastest/most economical route to that star.
Part 3) seems to be taking all the time. I can get routes to planets <50LY away instantly. Getting routes to 50-70LY out quickly depends on the star density, getting 80LY+ away takes a long while.
Now, star density varies. I'd guesstimate 5-6 stars per 1000 cubic lightyears (the grid lines on the galaxy map are 1LY), though this can obviously go up or down. This means within 100LY of me there are probably about 20,000 stars. Obviously some regions will have 100,000, some will have 5,000, but it's about right. Even very efficient pathfinding is going to take a while to find the shortest/fastest path to 20,000 stars, especially if you want the correct answer (you can do faster pathfinding if you're willing to accept sub-optimal paths).
So it's not suprising step 3) takes ages. It's going to need a change of method to be faster. Finding a path to that many stars is never going to be cheap. The solution then, is not to find a path to that many stars. I think there are two ways of doing this:
Method 1
Directional weighting. Is the user looking in particalar direction in the galaxy map? If so, prioritise stars in that direction. This can be fairly quickly implemented by adding a weighting factor to each star when sorting, repeating the sort step fairly frequently, and adding a check so as not to path to a star more than once. A stronger weighting factor could be used for selected or moused over stars.
Right now the problem scales with the distance cubed, strong directional weighting would scale with the distance. This is much much better, and I wouldn't be suprised if you could get something that would cut our candidate list from ~20,000 to ~1,000 quite easily, making the whole process an order of magnitude faster, and make plotting longer trips a lot less problematic.
Method 2
If I ask for a path to a system within, for example, 1,000 Ly, just generate a path for me. Maybe it'll be suboptimal, but it'll probably be pretty good. This would probably require more code to be written, as you'd have to be able to load systems into memory/remove them from memory on the fly based on the current trial path, which I guess is all done up front right now. Obviously, you'd need to keep the original method intact as well so I can have the pretty spiderweb of blue lines for local routes. Generating a path to one star, even if it's many LY away, should be a relatively quick process. Everybody and his frog knows that A*, even with a fairly trivial heursitci, should talkle this problem fairly promptly.
I think method 2 is better, to be honest, as often we know where we want to go, and don't need routes to places around it as well. Method 1 is perhaps more in keeping with the current implementation, but I'm not really sure what benifits the current system has, other than the blue spider web.
I've been taking a look at it's behaviour, and think I know why it takes ages. I wouldn't be suprised if the current algorithm looks similar to this:
1) Find all planets within a set range. Probably uses an octree to grab candidates very quickly. The procedural generation seems fairly swift, so I doubt that's a big hitter as we can see them very quickly.
2) Sort them by range, closest to furthest. Pretty standard stuff, and the list isn't going to be massive. Computers are good at sorting.
3) Starting at the start of the list, calculate the fastest/most economical route to that star.
Part 3) seems to be taking all the time. I can get routes to planets <50LY away instantly. Getting routes to 50-70LY out quickly depends on the star density, getting 80LY+ away takes a long while.
Now, star density varies. I'd guesstimate 5-6 stars per 1000 cubic lightyears (the grid lines on the galaxy map are 1LY), though this can obviously go up or down. This means within 100LY of me there are probably about 20,000 stars. Obviously some regions will have 100,000, some will have 5,000, but it's about right. Even very efficient pathfinding is going to take a while to find the shortest/fastest path to 20,000 stars, especially if you want the correct answer (you can do faster pathfinding if you're willing to accept sub-optimal paths).
So it's not suprising step 3) takes ages. It's going to need a change of method to be faster. Finding a path to that many stars is never going to be cheap. The solution then, is not to find a path to that many stars. I think there are two ways of doing this:
Method 1
Directional weighting. Is the user looking in particalar direction in the galaxy map? If so, prioritise stars in that direction. This can be fairly quickly implemented by adding a weighting factor to each star when sorting, repeating the sort step fairly frequently, and adding a check so as not to path to a star more than once. A stronger weighting factor could be used for selected or moused over stars.
Right now the problem scales with the distance cubed, strong directional weighting would scale with the distance. This is much much better, and I wouldn't be suprised if you could get something that would cut our candidate list from ~20,000 to ~1,000 quite easily, making the whole process an order of magnitude faster, and make plotting longer trips a lot less problematic.
Method 2
If I ask for a path to a system within, for example, 1,000 Ly, just generate a path for me. Maybe it'll be suboptimal, but it'll probably be pretty good. This would probably require more code to be written, as you'd have to be able to load systems into memory/remove them from memory on the fly based on the current trial path, which I guess is all done up front right now. Obviously, you'd need to keep the original method intact as well so I can have the pretty spiderweb of blue lines for local routes. Generating a path to one star, even if it's many LY away, should be a relatively quick process. Everybody and his frog knows that A*, even with a fairly trivial heursitci, should talkle this problem fairly promptly.
I think method 2 is better, to be honest, as often we know where we want to go, and don't need routes to places around it as well. Method 1 is perhaps more in keeping with the current implementation, but I'm not really sure what benifits the current system has, other than the blue spider web.
Last edited: