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:
- 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)
- Edges will NOT cross.
- 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)
- No star/point should have a multiplicity of more than 3.
- 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:
- Randomly generate a point in the neighboring vicinity of other stars that do not yet have a multiplicity of 3.
- Find the first star that does not yet have a multiplicity of 3 that will not generate edge conflict.
- 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.