The last task in “phase one” of my galaxy generation process is to create links between the sectors.

Sectors are generated by taking a max X and max Y value and creating a “sector” at that grid location. Each [x,y] value has a random “sector ID” assignment so I don’t end up with [0,0] being sector 1, [1,0] being sector 2, and so on. While this sensibly creates a situation where, were I to look at the grid by sector ID, it would be impossible to tell which sector lies next to which, I still have the [x,y] coordinates to tell me where each ID falls in the grid.

I don’t want every sector to connect to every neighboring sector, so it should not be guaranteed that [0,0] connects to both [1,0] and [0,1]. More to the point, a sector at [25, 25] should not allow travel to all eight sectors surrounding it ([25+/-1, 25+/-1]). However, every sector should have at least one connection so none of the sectors defined in the Big Bang are wasted.

Since I am not well versed in maths, I have found a relatively simple brute force approach which works well, but not well enough.

The Procedure

A sector object looks like this (more or less)

{ 
   id: number, 
   x: number, 
   y: number, 
   name: string, 
   tag: string, 
   major: bool, 
   minor: bool, 
   status: string 
}

After “banging” the galaxy, I end up with an array of 100 of these objects.

Next, using the min and max [x,y] values (0 and 9 for testing) and a limited number of attempts (currently set to 100), I start picking random [x,y] values. Because my working grid and my galaxy generation grid use the same min and max values, I know that my random numbers will always be inside the grid. This was an issue in an earlier “walking” version in which I had to be careful not the generate X or Y values that lay outside of the grid.

Next, I gen two random numbers as “coin flips”. One will determine if we work with X or Y. The other is if we increment or decrement that value. Based on these outcomes, the random coordinate is shifted one cell in either the X or Y direction, positively or negatively.

Now I have two coordinates: a current, random grid position, and a next, randomly selected neighbor on the grid. With these coordinates in hand, I check against a tracking array which represents the current iteration of how I am storing the jump gate data. If the combo of current and next sectors exists in this array, then I simply don’t add it, otherwise I do. At this point I exit the function and loop back to start it over again.

The last step is to validate the connections. To do this, I check each sector sequentially by ID. Using the X and Y values in that sector object, I check the tracking array for those values as either the exit-to or entry-from values. If I find at least one entry, great! The sector is connected to at least one other sector. If the lookup comes up empty, though, then that sector is isolated.

The Results

I am getting these kinds of ratios pretty consistently. Paths Made and Failed Attempts are calculated when the path is stored and when a proposed path is found in the tracker array already, respectively. While I would expect a total of 100 attempts, I’m falling short at 98 consistently, which leads me to believe that some of my loops are using the wrong operators — not a difficult problem. But successes are always clocking in between high 70s and low 90s, with failures in the teens. While I haven’t broken out the actual values to examine, I realized in the writing of this post that my random +/- X/Y calculation could lead a connection outside of the usable space (if [0,1] attempted to connect to [-1,1] that’s a failure). So that’s a situation I’ll have to remedy.

The Good sectors and Bad sectors represent sectors which have at least one connection (good) versus those which don’t have any connections (bad). In repeated attempts, these numbers not only follow the same ratio as the paths made, but also fall very close to the actual values. This would make sense, although the determination of the numbers is approached slightly differently. Again, my suckage at maths probably means I am just calculating the same thing differently.

View it on Code Sandbox

If you’re interested in telling me where I’m going wrong, here’s the code from Code Sandbox. The output is printed to the console, so to see it you’ll have to visit the sandbox directly. I’m sure it’s not as elegant as it could or should be, but again, this is a brute force attempt and isn’t meant to be pretty.