# 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
Commented 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
Commented 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? Commented 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
Commented 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
Commented Jan 13, 2016 at 7:32