## Galaxy generation algorithm

*May 9, 2018*

an integral part of a 4x space game is the galaxy generation. Galaxy generation means speading out the stars in your galaxy in a way that looks good, should resemeble reality and must satisfy some constraints. If you take a look at the maps fom old 4x games you will see that the stars are laid out in a very linear fashion. The method used here is splitting the coordinate plane into sectors of a defined height/width and then randomly placing stars in side this satisfying a density constraint. You also have to check the neighboring sectors for stars that are near the border otherwise you might end up with star that are very close to each other. This is a tedious way of going about things and the end result isn’t that satisfactory.

Here is an example of the sector method

A better method is generating a spiral galaxy. I’ve being doing some research on the subject and there are various methods even some involving actual astro-physical calculations (simplified) but these are still to complicated and a better approximated result can be obtained will less hassle. Here is the version that I found which works quite well

Each black dot represents a star in the system. I think it looks nice and quasi realistic. The code to accomplish this layout is

```
public Galaxy generate(Galaxy galaxy) {
int NUMHUB = 20;
int NUMDISK = 5000;
double DISKRAD = 400;
double HUBRAD = 50;
int NUMARMS = 3;
double ARMROTS = 0.5;
double ARMWIDTH = 65.0;
double FUZZ = 25.0;
double omega = 360 / NUMARMS;
int i = 0;
while (i < NUMDISK) {
i++;
double dist = HUBRAD + RandomUtils.nextFloat(0, 1) * DISKRAD;
double theta = ((360.0 * ARMROTS * (dist / DISKRAD))) + RandomUtils.nextFloat(0, 1) * ARMWIDTH
+ omega * RandomUtils.nextInt(0, NUMARMS) + RandomUtils.nextFloat(0, 1) * FUZZ * 2.0 - FUZZ;
double x = Math.cos(theta * Math.PI / 180) * dist;
double y = Math.sin(theta * Math.PI / 180) * dist;
Star star = starService.create(x + galaxy.getSize().getWidth() /2 , y + galaxy.getSize().getHeight() / 2);
if (!isDensitySatisfied(galaxy, star)) { //make sure that the stars are not too close to eachother
LOGGER.info("density condition failed.");
continue;
}
galaxy.getStars().add(star);
}
i = 0;
while (i < NUMHUB) {
i++;
double dist = RandomUtils.nextFloat(0, 1) * HUBRAD;
double theta = RandomUtils.nextFloat(0, 1) * 360;
double x = Math.cos(theta * Math.PI / 180) * dist;
double y = Math.sin(theta * Math.PI / 180) * dist;
Star star = starService.create(x + 500, y + 500);
if (!isDensitySatisfied(galaxy, star)) {
LOGGER.info("density condition failed.");
continue;
}
galaxy.getStars().add(star);
}
return galaxy;
}
```

Here is a legend of what the knobs in the code actually tweak

The only gotcha here is that you may not get the number of stars that you requested if the density checking function returns false for some stars. But thats no big problem as you are requesting a constraint be satisfied. The algorithm used is by Ben Motz <motzb-at-hotmail.com> The original C source code for DOS (including a 3D viewer).

*Tags:
#gamedev
*