There are a few really good pieces of advice you should always follow when developing your first computer game. Things like:
- Don't go it completely alone - always have at least one other person to work with and bounce ideas off
- Don't plan an MMO as your first game
- Don't start with crazily ambitious goals - always set a reasonable, contained scope for your first game
I am great at taking advice, and so last year when I set out to develop Ascent - The Space Game, I decided it would be an MMO, I'd work on it alone, and we would have the entire milky way modelled in the game, as closely as we could based on what present day science knows about star and planet formation, with earth sized rocky planets, Jupiter (and larger) gas giants, accurately scaled stars, full sized star systems and so on. I wanted to do that because I really felt the world needs a PvE MMO with truly open ended space exploration and scientifically plausible sci-fi.
There are a number of really big hurdles to overcome to achieve this - for example, having even an Earth sized planet in a game engine based on 32bit floating point vector coordinates is quite impossible without some extreme workarounds. Worse yet, an entire star system in actual scale is ridiculously large and no game engine written to date can cope with that either. Game engines (and video cards) are obsessed with 32 bit floating point numbers, and these aren't very accurate on scales of billions of kilometers. And don't get me started on 24bit z-buffers, those are really Fun. Then you've got the classic old chestnut of having to map your terrain engine to a sphere to make planets and moons.
These problems were great Fun to overcome and I may write about them another day.
Today I am just going to focus on how you fit more than 270 billion completely unique star systems into a web game that is an 18 megabyte download (and now a 31megabyte PC game!). Clearly, this involves significant Cheating, and as you might well guess, today's Cheat is pseudorandom generation.
Image courtesy NASA / JPL-Caltech / R.Hurt (SSC-Caltech)
So here's what NASA think the Milky Way looks like, if you take a photograph from about 100,000 light years "above" or "north" of it. It's believed to be about 100,000 light years across, 1,000 to 4,000 ly thick and to contain between 200 and 400 billion star systems.
After considerable internal debate (talking to yourself and/or your cat is the first direct result of solo game development, I've noticed) I decided to implement a completely three dimensional sector map rather than the essentially 2D one everyone does. Otherwise, how could I fit all the stars in? This involved the following
- Dividing this galaxy up into 10x10x10 light year cubes, and calling these cubes "sectors". This means the galaxy is 10,000 by 10,000 cubes wide and high, and usually between 100 and 400 cubes thick.
- Taking the image above, grey-scaling it and saving the data as "density map" - our sectors' number of stars (with a pseudoranom element) and the thickness (number of sectors "high" our galaxy is at given coordinates). This means we added NASA to the credits of the game as we're using their work above to build our density map, and so it needs to be attributed appropriately.
- Then, we get into psuedorandom generation.
If you're not familiar with pseudorandomness, translated into English it is simply "a process that appears to be random, but is not". This is useful for developing big games that don't take up much space because you can generate game levels on the fly rather than designing and storing them all somewhere.
You can give your players an open-ended experience, in this case being able to explore so many star systems that they can't possibly see them all in one human lifetime, but have that experience be the same every time, because the results of your generation code are not actually random at all.
So the first time I visit a system, it is generated, and I marvel at the generated star field and nebulae I see in the background, the crazily coloured generated gas giants, wacky generated 3d terrain (as far as the eye can see and beyond!) on the moons and rocky planets in the systems, and even the properties of these planets, the stars, the chemical composition of the gas giants etc. And the second time I visit that system, everything is exactly the same, down to the last dent in a mountain peak of the very last moon.
This planet's liquid methane sea and rocky coastline is identical the first, second, third, every time I visit it. This is handy for making the whole thing seem Real to a player. Real, and realistic. A persistent world, without the massive database overhead. This planet is the size of Earth, which required a lot of custom shaders, texture generation etc that I might post about another time.
So to get back to our generation process!
- For a given sector, we determine the base density (number of stars) based on the density map NASA published. We then build a random seed (an integer we use to initalise the random number generator to get the same results every time) from this sector's coordinates.
e.g., for sector 1, 1, 1, we might come up with a random seed like "1000100010001". 1 to designate which galaxy this is, and then the x,y,z coordinates of the sector, padded out to the full four digits so we don't get duplicates. Another thing we do is offset the base coordinates in the game, so we can show negative numbers to the players AND not give away where in the milky way they start, but that doesn't effect the overall method here, which as you can see is very simple.
Once you have a means of coming up with a unique random seed for each sector, you can quite literally generate anything you like.
What I'm doing is:
- Generate the number of stars in the sector - based on the base density and a random element
- For each star generate its mass. This ranges from a tiny red dwarf (0.08 times the mass of our sun) to a massive Wolf Rayet star or black hole (up to say 150 times the mass of our sun). A star's mass, combined with it's age actually determine things like its colour (spectral properties) and how much (and what kinds) of radiation it emits.
And we're done. That's all I'm doing to generate sectors. Seriously. I do _cache_ the generated sectors on the servers for 24 hours, but that's to save CPU time on the server when, for example, every player online opens the map at once...
When a player then VISITS a star system (players need a big enough hyperdrive for their ship and enough fuel to cover the distance), several things happen.
- We check to see if we have the system in the database.
- If we do, the system has things like a name and the user ID of the player who discovered it.
- If we don't, we create the record with those items. Congratulations, you've just discovered your first system.
- Next, we generate the system itself and send its data to the game client to render
When generating a system, we already have a bunch of data. We've figured out the mass and the spectral class of the primary star. As it happens, these impact things like how many other stars might be in the system (you can have two, three, up to five stars in a system, but most are one or two), and how much mass is left over for planets. The first system in sector 1,1,1 might have the random seed "100010001000101" - which is the sector seed plus a forced two-digit version of the system's ID for that sector. Two digits lets us have up to 99 star systems per sector, but you could have more if you were crazy. To generate a system we re-initialise our random number generator with the system's seed.
When generating planets, I try to follow what we know from science about planet generation. Which leaves a lot of room to make stuff up because we have a bunch of conflicting theories really. So, we take an arbitrary percentage of the star's mass (a small, pseudo-random arbitrary percentage) and use this as matter left over for planets. Then we generate planets, starting with the first gas giant just beyond the point where water would freeze, given the level of radiation the star(s) put out. Then we randomly generate the rest of the planets and moons until the "leftover star mass" runs out.
Each planet has its own seed. The first planet in the system 100010001000101 might have the seed "10001000100010101" giving us up to 99 planetary bodies in a system. You could have more by adding digits of course. To generate a planet, we re-initialise the random number generator with its seed and off we go.
For Gas giants, we generate a mass, calculate a size based on the mass, and a bunch of colour bands. These colours actually dictate what types of gas you can skim in A-TSG. E.g. the planet below has nice White bands which would let a newer player skim Hydrogen from it, whereas a player with a higher skill level can actually skim hydrogen from any part of any gas giant as they're better at filtering gases.
As you can see, another advantage to this sort of process is that someone like me, with the artistic capabilities of a dead moose, can somehow produce pretty looking scenes like the above. The A-TSG client takes the colour bands the server gives it, and generates a texture for the gas giant in another thread, as you are flying towards it. Threaded texture generation is something I might post about later!
Back to our planets - we can have our server generate everything - the mass, the soil composition, the minerals, whether it has an atmosphere or not, whether it has oceans, what the oceans are made of etc. To do this, we feed pseudorandom numbers into established rules about planets. Starting with the mineral composition, mass and level of geological activity. Geological activity might indicate magnetic activity, which helps us decide whether the planet can keep an atmosphere.
When a player lands, jumps out of their ship and takes a soil sample, the game client can ask the server about it and get the precise composition and its fertility (and toxicity) to the four major types of crops we have in game. Again, this is all pseudo-random generated information.
Here I am, standing ankle deep in some cold sludge on some desolate world. Isn't space exploration romantic?
Next, we generate how much of the basic fluid compounds the planet might have. Hydrogen, nitrogen, ammonia, carbon dioxide, methane etc. We determine their state (solid, liquid or gas) based on the amount of radiation the planet is receiving from its star(s) and a simplified formula for surface temperature. Then, some of these compounds are greenhouse gases so if they're in gas form we run the numbers again taking this into account (planet will be warmer, sometimes this means an ice might melt or a liquid might boil)
This gives us realistic atmosphere and oceans. In the right temperature range, for example, a planet might have an ammonia ocean and a nitrogen atmosphere if it has these compounds. I wouldn't recommend swimming there though.
The planet's seed can also feed straight into the terrain engine. How many impact craters it has will also depend on the geological activity (none means a lot, as volcanic and tectonic activity has never erased a single crater ever, and vice vesa) and things like the planet's mass and volume can inform the terrain engine of how mountainous it might be. If it has oceans and an atmosphere it will have more erosion than otherwise, etc.
However, spherical terrain engines are a matter for another post!