Galaxy hyper lane generation

Keywords: star density, neighbor star, close neighbor, closest star, warp lane, origin star, distance, connection, mst, number, algorithm, generate, point. Powered by TextRank.

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 spacetime, they enable spaceships to travel through them and guide the spaceships to their destination. They are a cheap alternative to wormhole generators which bend spacetime to connect stars. Here are what they look like from a popular game

link

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

link

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 warp lanes 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

1. let S be a list star with random coordinates in a 1000x1000 plane
2. for each star in S
   1. if 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

link

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.

link

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

link

To address this issue a combination of an MST and the naive approach could work.

link

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.

link

Yet another way of connecting the stars would be to use Delaunay Triangulation. This also produces a very nice warp lane structure but still, has the cluttering problem due to the star layout.

Now let's address the clutter problem. It seem that the warp lanes look cluttered if there are neighboring stars too close to an existing warp lane.

link

the 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:

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

$$ \bigl|\frac{(y_2 - y_1) \times x_0 - (x_2 - x_1) \times y_0 + x_2 \times y_1 - y_2 \times x_1}{\sqrt{(y_2-y_1)^2 + (x_2-x_1)^2}}\bigr| $$

Here is the result of a relaxed threshold that will draw a lot of lanes

 [link](https://img.dendiz.xyz/image/55Lq)

here are the same results with a stricter threshold that has discarded the middle lane

 [link](https://img.dendiz.xyz/image/5sJo)

Metadata

Similar posts

• K Closest star selection
• Galaxy generation algorithm
• Using Kruskal's MST algorithm for warp lane generation

Powered by TF-IDF/Cosine similarity

First published on 2018-05-09

Generated on May 5, 2024, 8:48 PM

Index