How the Procedural Map Generation Works in Reactor Heart

How to proceduraly generate a huge 2D universe in real time.

October 18, 2013 17.5k views

This article sums up what I've learnt so far developing the procedural map generation system of Reactor Heart. What I expose here should not be considered the last word on the topic since I'm still looking for the way to enhance the system. In the beginning, I made lots of rookie-mistakes and learnt a lot overcoming them; I hope it proves useful for you and If anyone knows, I'll gladly accept any suggestion to make my system better. When I started developing Reactor Heart I realised immediately that I had to create an infinite universe able to automatically expand itself. With a Restricted world I wouldn't have made so far so I started my research gathering information on many articles and white papers about procedural generation. The first idea I came up with was create a giant sector generator to allocate planetary systems, asteroids, and many other things. So I began to code function to create the planetary system basic elements: planets, asteroids, moons, minor satellites, etc. The planets were circles with a variable length ratio, the moons were the same but much smaller and for the asteroids I used an algorithm to create an outline with a logical and more or less round shape.

With those elements I defined the soon to be planetary system generation in which planets were located in determined orbits round a centre (where I'd set a Star). They were defined with a random angle and distance from the center, restricted within reasonable ranges to set them coherently.

The generation system worked as expected with the exception of four issues:

The whole process lasted 15 seconds
The shapes of the asteriods didn't match what I had in mind.
The generation of each asteroid took a lot of time using the algorithm I designed.
Due to the random location of the asteroid, lots of blank spaces might occur.

For a limited map, 15 seconds are trifle since the generation is done once. For limitless universe where the users are expected to travel for hours that's unacceptable. Moreover, the asteroid's shape was kind of rhomboid and the system needed a lot of time to generate them. The first issue I mended was the asteroids, which was the most obvious one. I created an asteroids editor in which I could pre-design a set of asteroids and save them to load them later in the game. Without the asteroids generation equation, the loading time improved enormously. It did even better when I added pre-processing while exporting the files in the editor. In addition, the asteroids shape were more coherent and, when combined, bigger asteroids with cool shapes were generated. Despite fixing the asteroids issue, the loading time was still not good so I had two possibilities:

Work on revamping the algorithm by means of parallelism.
Lessen the generation system complexity.

In systems where Real Time generation was mandatory, they reduced the "unit" size and hence, reducing the amount time necessary for the generation. At first, my "unit" was the sector size and to follow this philosophy I decided to make it smaller. The sector would be an area of space defined by 6x6 chunks (the planetary system was 50x50) that might be occupied by a planet, a planet with some moons or asteroids, a cloud of asteroids, a nebula, a Star, etc. The system worked wonderfully and I managed to reduce the generation time to a mean of 0.007-0.1 seconds using this new method (and with some low-level optimizations in the process ). Tip: The use of profiling tools like gprof is very helpful to seek those functions that do most of the calls and see which part of the code you should try to optimize.

I haven't parallelized the system yet though I've designed it with an eye to the future to make it easier for subsequent versions to integrate it. And that has been my experience so far.