Some time ago I had a project where I wanted generate a lot of random planets in (2D) space that each had it’s own statistics (resources available, size, etc). Two of the things I wanted to learn were how to generate random planet names and how to actually generate a field of planets without them colliding.

For the names I used a technique called the Markov Chain. In my case I analyzed an input set of English words (58000+). Using this technique and my input set I could created random and (mostly) English pronounceable words for my planets. I even added a random chance for a roman numeral. Some examples names from my set could be:

For the generation of the planets I researched a bunch about spatial indexing. I wanted to generate a set of planets at random locations that would not collide, be a minimal distance apart from each other and would be efficiently searchable. The reason I wanted a spatial index for each planet was because each planet had a “sphere of influence” that would grow over time. This means I had to know which planets were close by. My first attempt was to simply use brute force to generate all planets without them colliding and then use a KD-tree for the lookup.

After that I did more research about what technique I could use for the distribution of the planets without brute force. The techniques I tried were: spatial hash grid, quad trees and Poisson distribution. The Poisson distribution simply didn’t fit my needs as the distribution looked too uniform. The quad tree worked really well, but since my planets weren’t going to move at all, I thought the spatial hash grid was a better and simpler solution. Unfortunately I never finished this project.

  • Languages used XNA (C#), Unity C#