## Warp lane generation

stuff about computer science and programming
dendiz
Posts: 114
Joined: Wed Oct 10, 2018 3:48 am

### Warp lane generation

Hyper lanes a.k.a Warp Lanes? What are those? They are a simple element of most space RTS/TBS games. They the lines that connect the stars. They are the highway lanes of space time, they enable spaceships to travel through them and guide the spaceships to their destination. They are a cheap alternative to wormhole generators which bend space time to connect stars. Here are what they look like from a popular game
15.png (68.42 KiB) Viewed 76 times
Technically speaking they are edges (the lines) between vertices (stars). What we need to do is generate these edges given a set of vertices and there a couple of methods for doing this. The first one that pops up is to generate a minimum spanning tree. But a minimum spanning tree would look this
16.png (7.29 KiB) Viewed 76 times
and this doesn't exactly look like a nice interstellar highway as we would like to be able to travel to a couple of nearby stars from our origin star. This way when we are trying to reach a distant star we have multiple options of getting to that star. Image that you did your warplanes using an MST and you want to get from star A to star D and the only path is A -> B -> C -> D. What do you do if there is an enemy fleet in the star C system and you don't want to engage that fleet with your science ship? Observe that the MST has only 1 connection between 2 neighboring stars so there is no way for you to do that.

So here is a naive algorithm I came up with

Code: Select all

``````1. let S be a list star with random coordinates in a 1000x1000 plane
2. for each star in S
1. if a star was visited before, skip it
2. get the N closest stars to this star
3. add a connection from this star to its neighbors
4. add a connection from each neighbor to this star
``````
the get closest star also needs some attention as we don't want to return a close neighbor if it already has a connection to the current star.

1. filter out all other stars except our current star
2. filter out all stars that already have a connection with the current star
3. map the remaining stars as a tuple of ( distance to source, this star)
4. sort by the distance
5. take N closest and return the stars from the tuple

The N parameter determines the number of max connections going out from a star. Here is an image of this algorithm with N=5
17.png (133.69 KiB) Viewed 76 times
This does look a bit better but there are too many cramped points where it's hard to tell what's going on. The stars are too close to each other so we need some kind of regulation when generating the random points for the stars. One way of doing this is checking the "star density" when generating the star and only placing the star if it's acceptable. This basically means not placing a star to close another and we can do this by checking if the generated star falls within a range of existing stars. That would be done by checking if it lies in a circle of radius R with the star at its origin.

1. let S be a list of stars initially empty
2. while S size < number of stars to generate
3. generate a random point in the plane
4. if this point satisfies the density condition add the star to S

One point to note about this algorithm is that it has the possibility of never terminating if the density conditions are too strict and it cannot find a good place for the next star. So it's a good idea to add a loop counter check that will terminate with an exception after a number of tries and tell the user to relax the number of stars and the radius R. The acceptable density function can be done as follows

1. let R be the minimum distance that two stars should be apart (which is the radius R)
2. for each star already generated check if (src.x - star.x)^2 - (src.y - star.y)^2 < R^2
3. if there are stars that satisfy this equation then the density condition is not satisfied.

After adding the density check and reducing N to 3 the lines look a bit clearer.
18.png (105.84 KiB) Viewed 76 times
There is a fundamental error in this approach. If you select a low N (connectivity value) then you sometimes will get disconnected stars like this
19.png (68.65 KiB) Viewed 76 times

To address this issue a combination of an MST and the naive approach could work.
20.png (58.74 KiB) Viewed 76 times
Now that the MST guarantees that all the graph will be connected we have addressed the issue but still, the layout doesn't look good for efficient traveling. We still could use more triangulation that is more lanes connecting nearby stars. Using the closest N method led to a cluttered layout. The cause of this clutter is that if 2 stars are almost in a straight line and are the 2 closest stars, there will 2 connections to these stars that overlap.
21.png (5.88 KiB) Viewed 76 times
Yet another way of connecting the stars would be to use Delaunay Triangulation. This also produces a very nice warplane structure but still, has the cluttering problem due to the star layout.
22.png (103.96 KiB) Viewed 76 times
Now let's address the clutter problem. It seems that the warplanes look cluttered if there are neighboring stars too close to an existing warplane.
23.png (10.38 KiB) Viewed 76 times
he green arrow shows a lane we could do better without. How can we detect these lanes? Just from the definition of the problem. If a neighbor star is too close to a lane, drop the existing lane so the closer lane to the a star will remain. Here is a simple outline for the algorithm that requires a bit of linear algebra:

Code: Select all

``````1. Sort all the neighbors for each star is descending order according to their distance from the origin star.
2. for each neighbor i to all neighbors - 1
1. for each neighbor j from i + 1 to all neighbors
2. if the distance of neighbor i from the lane between origin star and neighbor j < some threshold T discard the lane
``````
calculating the distance of a point P0 to a line given by P1 and P2 is

Math.abs( (y2-y1)*x0 - (x2-x1)*y0 + x2*y1 - y2*x1 ) / Math.sqrt( Math.pow(y2-y1,2) + Math.pow(x2-x1,2) )

Here is the result of a relaxed threshold that will draw a lot of lines
24.png (6.83 KiB) Viewed 76 times
here are the same results with a stricter threshold that has discarded the middle lane
25.png (6.72 KiB) Viewed 76 times