# Algorithm to generate Edges and Vertexes outwards from origin with max multiplicity of 3

I am creating a 2d game for a website where the universe can grow extremely large (basically infinitely large). Initially, the universe is composed of 6 stars that are an equal distance from the origin (0, 0). My task is to be able to generate more stars that will have "paths" (edges) that connect to each other. How can I design an algorithm that meets these restrictions:

1. Stars are randomly generated outward. (e.g. (x, y) coordinates for new stars will slowly go outwards from (0, 0) in all directions, preferably in spiral format)
2. Edges will NOT cross.
3. Although there should be some variance, new stars should not be too far or too close to other stars. (E.g. there must be a minimum radius)
4. No star/point should have a multiplicity of more than 3.
5. Given that all of this will be stored in a Database, the algorithm cannot be too costly. In other words, I would love to achieve something of O(n) complexity (I don't know if this is feasible).

Essentially, what I am going for is a spiral looking galaxy where the stars are points on the graph and travel between stars is depicted by edges between those stars.

The particular steps I need to solve are:

1. Randomly generate a point in the neighboring vicinity of other stars that do not yet have a multiplicity of 3.
2. Find the first star that does not yet have a multiplicity of 3 that will not generate edge conflict.
3. If the star is a minimum distance of x units away then create an edge between the two points.

I tried looking for solutions, but my math skills (and knowledge on Graph Theory) need a lot of work. Also, any resources/links on this matter would be greatly appreciated.

Here is some pseudo-code I was thinking of, but I'm not sure if this would even work and i'm sure it would not perform terribly well after a few 10,000, etc stars.

newStar = randomly generated (x, y) within radius of last star from origin
while(newStar has not been connected):
for (star in the known universe):
if(distance between newStar and star > x units):
if(star has < 3 multiplicity):
if(path from newStar to star does not intersect another path):
connect the star to the other star
break;

newStar = new random (x, y) coordinate


Also, if anyone has any advice on how I should store this on a MySQL database, I would also appreciate that.

Finally, in case nothing makes sense above, I have included an image of what I would like to achieve below:

• A traveler of this universe would likely move in one direction, meaning if you run out of stars, you'd have to generate stars in all directions from origin. One bored user could break your database, in other words. Have you considered this possibility (assuming it may be an issue)?
– Neil
Jan 12, 2016 at 7:31
• Also another thought, the placement of the stars needs not be remembered. If you use a reproduceable generation of stars, then you could generate the stars that the user could see in such a way that those stars will be generated in the same way in the future. Meaning, your database only needs to save info on stars. Its position is its identity.
– Neil
Jan 12, 2016 at 7:53
• What will you do if each generated star has exactly a multiplicity of 3, so step 1 will fail? Any why is in your picture one point with a multiplicity of 4, is that an error? Jan 12, 2016 at 8:16
• No. If you can generate stars in a predictable way, then it will be as if they had always been there if you leave and then return. It is only the algorithm and the seed which don't change.
– Neil
Jan 12, 2016 at 8:19
• @J.F. See No Man's Sky. The guy literally generates a universe. He saves only planets that have been visited by players, and yet the existing planets remain in their same respective spots. It is all based on using the proper seed used to generate random numbers.
– Neil
Jan 13, 2016 at 7:32

## 1 Answer

Suggestion: Keep the internal universe network perfectly ordered, algorithmic, and relatively simple. You only need the universe to look random when it's displayed on the user screen. Only apply random offsets to the star positions for user display.

Problem: The most obvious approach of calculating a random offset for each star won't do a very good job of hiding the underlying true structure. You can only randomize stars by a small amount before they risk colliding with each other or crossing paths.

Solution: You can apply large random distortions and get a much more random and interesting looking universe if you apply coordinated non-local randomness. Imagine placing the stars on a rubber sheet, and imagine randomly stretching and squishing different parts of the sheet. That can shift an entire groups of stars by a long distance. They will never collide or cross because nearby stars stretch and squish in relation to each other.

How to do it: Look up fractal terrain generators. There's plenty of free and open code for it. You only need basic code that generates a height value for each point on a map. We're going to use it in a different way. Use that code to generate TWO independent terrain-height maps. Start with the star's true X,Y position, look at that location on each map, use one map value to offset the star's X display position and use the other map value to offset the star's Y display position. You'll have to play with some of the scaling factors, but that can give you the randomly warped rubber sheet effect. The large variations in star position should completely hide the underlying ordered positions. The fractal nature of the randomness will give a very natural-looking effect, with visually-interesting things apparently going on in different regions of the universe.