Jump to content

  • Log In with Google      Sign In   
  • Create Account

This article is under review by the community - Current moderation totals:
Mark as peer reviewed: 0 votes
Still needs work: 0 votes


Like
6Likes
Dislike

How the Procedural Map Generation Works in Reactor Heart UNDER REVIEW

By Néstor Viña León | Published Oct 18 2013 01:58 PM in Game Programming

random worlds tile engine Procedural Map performance procedural generation procedural map programming 2d

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.

PlanetWithMoon.gif Asteroid.gif AsteroidPlanet.gif


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.

 Generation.gif


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.

SectorSystem.gif


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.



License


GDOL (Gamedev.net Open License)




Comments

Interesting topic, I'll be sure to check out your game when I have the time to do so. <$0.02> Given the title of the article, I would have liked the explanation to be a bit more technical. </$0.02>

Interesting topic, I'll be sure to check out your game when I have the time to do so. <$0.02> Given the title of the article, I would have liked the explanation to be a bit more technical. </$0.02>

 

Thank you. I will make a more technical article about this topic in the future, for more low level details. But I'm still improving that low level details and I would like to publish the better information possible.

might just want to consider editing this one. I would be willing to reset the publication date

might just want to consider editing this one. I would be willing to reset the publication date

 

Sorry, I will wait for the publishing of the low-level version. :( I'm currently writing it and I think this one is a nice first approach for beginers.

Interesting

I think the article could be improved by clarifying the relationship between the different types of generation. I think that the last screenshot is the most zoomed-out (generated how?), and each circle represents a solar system (as shown in the previous screenshot), and each circle in that is a planet/planet with moons/asteroid field. Is that correct?


Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS