Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

If I wanted to generate a universe/galaxy like that of Elite or Spore, what would be some good programming reference materials and algorithms to take into account?

share
    
I've un-deleted this post but left it locked. It's good to have for posterity and as a question to point to when others ask similarly broad questions. –  Byte56 Oct 2 '13 at 15:24
comments disabled on deleted / locked posts

migration rejected from stackoverflow.com Nov 13 '12 at 5:03

This question came from our site for professional and enthusiast programmers. Votes, comments, and answers are locked due to the question being closed here, but it may be eligible for editing and reopening on the site where it originated.

closed as not constructive by Nicol Bolas, Trevor Powell, Josh Petrie, Byte56, Jonathan Hobbs Nov 13 '12 at 5:03

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

14 Answers

You should read up on procedural content generation.

Idea 1

  1. Create a class to represent a PRNG in which you can control the seed. PRNGs always return the same sequence of numbers when given a duplicate seed.
  2. Create a universe seed number (you can use a PRNG seeded with the current time to do this).
  3. Save this seed.
  4. Use the PRNGs that you created to populate the universe with stars and planets. You will need to create at least five properties for each: X,Y,Z,Mass,Seed - add more as you see fit (e.g. Spore would have GroundColor, AtmosphereColor, Temperature, e.t.c.)
  5. When you draw near to a planet use its seed to create the heightmap and features on it.

Any changes that the player makes will need to be persisted somewhere. Basically you will need a transactional store (with CRUD operations) to indicate what the player has done.

Tree #44072:

  • Eaten
  • Deleted

Planet #14325:

  • Changed to blue

Idea 2

Instead of using a PNRG to create positions you could use perlin noise. If you create a few image filters (with deterministic outcomes) you could use the results as:

  • Star density maps
  • Planet seeds
  • Properties

By getting really clever you could even create specific filters that could:

  • Make stars in the center of galaxies hotter
  • Make different types of galaxies

The advantage of this is obviously the speed - you won't be creating or storing (in RAM) the whole universe in one shot (you simply work out the relevant 'quadrant' you are in).

You will obviously still need to store player modifications.

Hope this gives you a good head start!

share
locked by Community Nov 13 '12 at 5:03
3  
+1: Keeping the seed for an object constant after creation is important. An early JPL animation of a Saturn flyby had a sparkly moon in it because Jim Blinn forgot to reseed the PRNG before each animation frame was computed. Being on a deadline, it went out as it was, but IIRC he rerendered the frames later and used the mistake (as he often did, actually) as a kickoff point for a lecture. –  RBerteig May 6 '09 at 9:31
comments disabled on deleted / locked posts

Well, you can get the actual Elite's trading engine implemented in C. If I remember correctly it contains also the universe generation part minus the graphics part.

The basic idea is that you take a random number generator and seed it with fixed value. Then you build your galaxy/star system based on random values from the generator. After eight hyperspace jumps or so you reseed the generator with the original value.

share
locked by Community Nov 13 '12 at 5:03
comments disabled on deleted / locked posts

I would bet on L-Systems to be able to generate something like this.
Ofcourse saying this is like saying "you can write it in C++". L-Systems is a huge subject and you probably need to know what you're doing to get any result at all.

share
locked by Community Nov 13 '12 at 5:03
    
Yeah I was considering something like an Lsystem but most information is for plants, although I've also found city rules, but not space rules. –  Robert Gould May 6 '09 at 9:12
comments disabled on deleted / locked posts

You probably want to create only as much of your universe as you currently need. So I'd go for a generator that is able to generate a new element of the universe based on some rules and a randomized choice of parameters for these rules.

The generator should not need to examine the whole universe to generate a new element. Ideally only a small neighborhood should be sufficient.

Without more details what you wanna do, I don't think you can get much more detailed answers.

share
locked by Community Nov 13 '12 at 5:03
    
Well I'm not totally sure what I want yet :) doing preliminary investigation, but I was planning on using coordinates to seed random generation, so I can be sure to get the same results in the same location –  Robert Gould May 6 '09 at 9:15
    
You should add some randomness nevertheless to get some variance (of course this only applies if you don't depend on a repeatable identical generation of the universe) –  Patrick Cornelissen Mar 22 '10 at 7:57
comments disabled on deleted / locked posts

I think that the hardest part (and the one which requires most creativity) is likely to be generating interesting, uniquely recognisable names for all the places you will be creating.

share
locked by Community Nov 13 '12 at 5:03
    
Yeah naming is terrible, but I think I'll use mostly categoric names for most planets like (A321) and some markov algorithm for say 1% of the interesting areas –  Robert Gould May 6 '09 at 9:22
comments disabled on deleted / locked posts

All these other answers are boring. Why not copy the real thing? You can extract the data from DSS or SuperCOSMOS. Then just turn it into a cool space game. Simple.

share
locked by Community Nov 13 '12 at 5:03
    
Very interesting alternative. Need to evaluate datasize though, mmm –  Robert Gould May 6 '09 at 9:18
comments disabled on deleted / locked posts

Conway's Game of Life may be a good starting point.

share
locked by Community Nov 13 '12 at 5:03
comments disabled on deleted / locked posts

Most likely you'll have to generate some random numbers but wish to create the same universe from the same seed. See Jonathan C Dickinson answer for more on that.

The tough part though is to use those random numbers and generate a procedural environment that is looking like you wish. Perlin noise can be used to generate lanscapes and some textures but not all. Most texture will have to be generated vie other procedural algorithms. A good place for procedural worlds are very tiny sized demo from the demo scene (like the 1K demo on Pouet.net.

Spore had to focus on the 3-D textures and so on. Let's say you wish to create a universe and focus on the big picture instead. There's the easy way and the hard way:

  • Easiest: Random mass, size, color, texture among your gallery of textures, etc. plus a few ad-hoc checking that you don't create two planets at the same position. You won't get anything near realistic though.
  • Harder: Generate a star and a number of planets. Then for each generate a random mass and size wich will give you it position in the system and define it's composition (gaz, solid...). Do that at every level using existing knowledge. This gives something much more realistic.
  • Hardest: Use some physics. Create particles and laws that nearly follow those of the creation of stars and galaxies and planets. From the randoms particles should come all your universe. Once you have the rough universe generated, refine the details using another techique (after all you can't simulate an entire universe up to real details LOL - yet)

Those of the big pictures. If you wish to go in the details on the planet, you can follow a somewhat similar approach.

Last but not least, remember your focus. In Spore the focus was the game fun and not the scientific realism. Any mechanic that fits is good, and with random numbers there is already a lot of unpredictability.

share
locked by Community Nov 13 '12 at 5:03
comments disabled on deleted / locked posts

Are you trying to generate a new universe or a simulation of ours?

Re-imagining our universe with different fundamental constants would be interesting, but unless you're an astronomy or physics department of a major university, I would imagine it might be beyond most people's skillz.

share
locked by Community Nov 13 '12 at 5:03
    
Well my goal is an artificial universe similar to our own but not the same, however the idea to download it as 1800 suggests is interesting –  Robert Gould May 6 '09 at 9:16
    
I had thought that the Elite writers had open-sourced their code, but that would be a gravity engine rather than a universe simulator. –  Unsliced May 6 '09 at 9:59
    
and beyond computers' skills too. –  Alexandre C. Dec 4 '10 at 10:39
comments disabled on deleted / locked posts

I wouldn't take too much inspiration from the Elite universe. They were built with all the limitations of a 8-bit computer with tiny amounts of memory available. See Elite (particularly the section on technological limitations)

share
locked by Community Nov 13 '12 at 5:03
1  
Indeed now that you mention it Elite is probably terribly underpowered even for what a mobile phone can handle nowadays. –  Robert Gould May 6 '09 at 9:24
1  
Yes (not that I want to denigrate their achievement in any way!) –  Brian Agnew May 6 '09 at 9:27
    
ditto - a great achievement! –  divinci Jun 18 '09 at 14:01
comments disabled on deleted / locked posts

My first piece of advice for you on this is to recognize that we humans have a limited understanding of how astrophysics really works, because we have a limited amount of raw data we can collect due to our place and time within the cosmos, especially in areas such as the formation of galaxies and stellar accretion. I therefore don't recommend a pure hard science approach.

I have done a lot of research into existing hard science generators, and they are all more or less flawed due to the pace we are accelerating our actual knowledge in the field. Some of them like StarGen are quite old and skip over things like hot jupiters, for example. AstroSynthesis might be the best in this category. (Can't provide links due to lack of rep, sorry, just google for them)

Theorists have come up with all kinds of speculation on all of the various aspects of the creation of the universe, but they've hidden this knowledge from mere mortals inside academic papers. So taking a hard science approach to this problem will likely take you a lifetime (this is commonly called a career in Astrophysics research), and then you will only be certain on generalities based on speculation. The good news is that much work in Astrophysics is actually done via complex computer modeling, the same thing you are proposing, so it will be as realistic as a human can get it.

The approach of using real star map data is a good one, but fairly limiting. In particular, we don't have much raw data on terrestrial planets or brown dwarfs, because we can't really see them.

So my answer is to find someone that has distilled all of these theories down to a workable text, hopefully with actual percentages you can play with and hard rules about the consequences of choosing parameter A on parameter B and so forth.

The best one in this category I have found is GURPS Space 4th edition. It is an incredible resource for star / planet generation, and you can take it in any direction you wish, as far as you wish. Since it's GURPS, there are accompanying texts on anything you can think of, including pure fantasy (like Alien races). You can also check out the bibliography for additional resources. Most of the generation methods in this text are based on real-world science, but it is already 5 years old, so you have to take it with a grain of salt. All of the rules presented are explained with reasoning and then distilled down into simple 6-sided die rolls.

I would recommend pairing something like that with procedural content generation.

share
add comment

I would think that fractals would be a good start. So, maybe some sort of fractal algorithm with some random parameters thrown in for variety.

share
locked by Community Nov 13 '12 at 5:03
comments disabled on deleted / locked posts

It makes me giggle a bit that we think as human beings we are anywhere close to understanding what a universe IS to the point where we think we can start simulating one. I'm not saying It's bad to aim high and attempt to understand such higher level topics, it just makes me giggle

share
locked by Community Nov 13 '12 at 5:03
1  
Ok I should have said simulate a plae shadow of the universe then :) –  Robert Gould May 6 '09 at 9:19
comments disabled on deleted / locked posts
  1. Generate the positions of galaxies in the universe from some seed.
  2. For the currently "active" galaxy, use the current position of the galaxy to generate a seed, and use this seed to generate the positions of the stars in this galaxy.
  3. For the currently active star, use the position of the star to generate a seed, and use this seed to generate the positions of the planets in orbit around this star.
  4. Etc...

Of course, you need to use some other techniques to manage everything, you probably can't keep even just the positions for every galaxy in your universe in memory at the same time (if you're going for realistic amounts of galaxies). The same for stars in the currently active galaxy.

Precision is also going to be a problem. It's possible with some tricks to render an entire solar system to scale in the same scene, but you probably have to render the stars in the current galaxy and the other galaxies in the universe in separate scenes and blend them together (or render them each once to cube maps).

Anyway, that's a very simple explanation of how I did it.

share
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.