17

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?

9 accepted

You should read up on procedural content generation.

Idea 1

  1. Create a variety of PRNGs that always return the same sequence of numbers when given a duplicate seed.
  2. Create a universe seed number (you can use a standard (P)RNG 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 it's 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!

4

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.

3

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.

3

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.

3

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.

2

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.

2

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.

1

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)

0

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.

0

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

0

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

0

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.

-1

import universe