LegacyWorlds Beta 6

The previous posts in this series discussed generalities, stellar systems and special objects such as nebulae. The last element that needs to be considered to describe travel in the Legacy Worlds universe is actual interstellar travel.

Because of the structure of the universe in the new version, it is impossible to describe interstellar travel as simply as it was in Beta 5. It is impossible to fly through some of the map’s areas, while Beta 5 made sure that it was always possible to get from one point to another without passing through something that wasn’t reachable. In addition, the new version will allow players to use waypoints when determining a fleet’s trajectory; because that is possible, it is only logical that the game can propose optimal trajectories to the player. Finally, a lot of computations depend on the distance between two points – these computations should always use the best possible route.

As implied by the introduction above, there are at least two different modes which can be used when computing interstellar travel routes: direct paths (flying in a straight line) and indirect, optimal paths. However, players in Beta 6 will not always know the whole map of a layer; it would therefore be illogical for their fleets to use the optimal paths when they do not know these paths. This fact adds a third trajectory computation mode, which is the “best known route”. We will examine all 3 modes.

Direct paths

While direct paths seem easy (they are, after all, a straight line between two points) at first glance, it gets much more complicated than that due to the fact that the trajectory has to be split in order to know the distance traveled at each location. This computation is made necessary by the fact that different areas of the map have different multipliers (for example nebulae or areas near a black hole).

The graph below illustrates the problem:

On this graph, we can clearly see that the direct path between the two areas noted by a black spot intersects different areas (the cyan areas); however, it is also clear that the distance traveled in each area is different.

In order to solve this, we start by computing the raw Euclidean distance between the two points and multiplying it by 1000; this is the total length of the path. We then use a parametric representation of the line to compute transitions from an area to the next:

x( distance ) = X1 + distance * ( X2 - X1 ) / total_distance
y( distance ) = Y1 + distance * ( Y2 - Y1 ) / total_distance

The results are then rounded to integer values; while this causes a few errors (some paths end up being asymmetrical when they shouldn’t), the error is always 1 distance unit, which can safely be ignored at this scale.

In the case of the trajectory presented on the graph above, the resulting path is:

Applying this algorithm to our example results in the following list of transitions and distances:

• At (-1;2) : 625 distance units
• At (-1;1) : 208 distance units
• At (0;1) : 1042 distance units
• At (0;0) : 625 distance units
• At (1;0) : 625 distance units
• At (1;-1) : 1041 distance units
• At (2;-1) : 209 distance units
• At (2;-2) : 625 distance units

Indirect paths

In some cases, it is impossible to go from a point to another directly because of a black hole sitting in the middle of the trajectory. In other cases, the direct paths would take the ships through very slow areas of the map and there is a much more efficient trajectory that goes around these areas. However, the best path is not always known. Two different algorithms will be used for these two types of indirect trajectories.

The classic Djikstra algorithm will be used to compute optimal paths; since it is very slow, the optimal trajectories will be pre-computed when the layer is created, and partially re-computed in case the space-time drilling ability is used (which shouldn’t happen too often, hopefully). Using the pre-computed results, it is easy to determine whether a player has all of the data required to compute the optimal trajectory or if a sub-optimal indirect path has to be used.

Sub-optimal indirect paths are impossible to pre-compute, as it would require computing the set of indirect paths for each possible combination of known/unknown map areas. Therefore, the A* algorithm (classically used for pathfinding in real-time strategy games) will be used on a per-request basis.

The examples below show the difference between direct and optimal indirect paths. The image on the left is the direct path, which requires 41,565 distance units; the image on the right is the indirect path, “measuring” only 15,889 distance units.

Next time, on the LWB6 blog…

Now that we’ve seen the different parts needed for distance and trajectory computation, the only thing left is to explain how these different parts will be put together to actually compute distances and trajectories as required.