11

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:and etc, alot of stars...

John F.
  • 111
  • 4
  • 1
    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 '16 at 07:31
  • 2
    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 '16 at 07:53
  • In this case, the stars are not generated based on where the user has traveled but instead on how many users are registered online. I like the idea of not having to remember stars but wouldn't that become a problem if there was say 500000 stars? – John F. Jan 12 '16 at 08:09
  • 1
    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? – Doc Brown Jan 12 '16 at 08:16
  • 1
    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 '16 at 08:19
  • @Neil I must investigate this further then; in that case I'll just have the algorithm client side and remember the connections via the database. – John F. Jan 12 '16 at 08:25
  • 1
    @Doc Brown, there will always be atleast one star that doesn't have a multiplicity of 3. I guess I better explain that part better. Every time a user creates an account on the website 1 star will be created. That star would then connect randomly to a star that doesn't have a multiplicity of 3. Also, I don't see any with multiplicity of 4, it must be the coordinate system that makes it look that way. Please excuse my terrible drawing skills. – John F. Jan 12 '16 at 08:25
  • 1
    @J.F.: in your picture, it is the point in the upper left quadrant, next to the origin. It has four connections to other points. – Doc Brown Jan 12 '16 at 10:27
  • 1
    @Doc Brown oh ok yea, that is an error – John F. Jan 12 '16 at 14:31
  • 2
    @J.F. See [No Man's Sky](https://en.wikipedia.org/wiki/No_Man%27s_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 '16 at 07:32
  • Correction to the above comment. Apparently everything *on* the planet is randomly generated as well, meaning the server only has to keep track of resources, currency, and player stats. I assume landing on the same planet won't retain the changes made by other players. – Neil Jan 13 '16 at 08:09
  • @Neil I've been looking at the game, and I am seriously impressed. It looks like these guys really know their stuff. Time to learn about procedural generation haha – John F. Jan 13 '16 at 08:21

1 Answers1

2

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.

Alsee
  • 141
  • 2