• ### Announcements

Followers 0
• entries
7
17
• views
9791

The journal of a graphics newbie trying to make his own procedural space game from scratch

## Quick Update - Texturing Sucks

Just a quick update to reassure you all that work is still progressing. Unfortunately I'm working on a lot of things at once right now which means very little in the way of screenshotable material has come out in the last week or two. I'm also working on a massive deadline for my PhD, so I've had less free time than usual.

What have I been working on?

Octree space representation and working around floating point inaccuracy

Brightness-based culling method

Combining deferred rendering with procedural textures in a (hopefully) efficient way

Parametric Planet Texture Generation.

But yeah, none of this is at a displayable stage, but expect a load of in-depth and wonderfully graphic dev journals over the next couple of months.

## Octrees are a dev's best friend

I've been using an octree system for space partitioning for a long time now, and a couple of the reasons I'm using one are:

• It can adapt well to any number of items in them
• It only really falls down as structures get very close together (and I'm dealing with celestial objects - which have a tendency to explode or absorb each other as they get too close)
• It can be built and rebuilt fairly quickly
• It's essential for Bayes-Hut

Now there's more than one way to skin a cat, apparently, and there's also more than one way to build an octree. Traditionally you build the hierarchy based on position, splitting a node into 8 smaller nodes as the number of items near each other reaches a pre-set threshold. This is how you should have it for Bayes-Hut to work as intended.

Alternatively however, (and useful for level of detailing in a space sim), you can build your octree hierarchy based on size, visibility, temperature or any other characterization.

Taking size as an example, let's say we want to render far away stars only if they're very large (why waste rendering calls on a star that's barely larger than a couple of pixels?). Normally we LOD to distance, but in this case a very, very large star or a very, very bright star can be seen from quite a distance compared to an asteroid. So we build an octree, with size, brightness, temperature, magnitude, etc as the function for calculating heirarchy. The giant items make up the first level of the tree, with maybe four or five of them in any one galaxy. Then, as the size gets smaller, we put them in finer and finer-grained octree nodes. This lets us operate by octree level, setting different view distances per size. Does this also work with Bayes-Hut? No.

Let's take a look at the Newtonian formula for pair-wise gravitational interactions:

F = (G*m1*m2 / r^2)

Here F is the force, G is the gravitational constant, m1 is the mass of the first body, m2 is the mass of the second body and r^2 is the distance between the two bodies squared.

You see, there are two important variables in the gravity calculation: mass and distance, but it's clearly seen that as distance increases, the force is reduced exponentially, so distance is more important in the long term. If you think about it, you'd want a planet that's orbiting a star to directly gravitate against that star instead of with every other planet in the galaxy. It just doesn't make sense otherwise.

So how do we cull the bodies that are far away and small, but keep the really big ones?

Well we build a formula for it.

There's a very complicated formula for what size an object will appear on the screen in pixels, but we don't actually need that and it makes me queasy just thinking about it. Astrophysics has our back. The visibility of a celestial object is described using its apparent magnitude.

## Size does matter - and precision too.

With Pigment, I hope to (for the computers that can handle it) offer an entire galaxy to explore. Most of the area will go unexplored, as the vast distance between stars alone is enough to make the heart jump, but I want the far away stars and black holes to still have their effect felt in across the galaxy.

This brings a problem of precision.

According to Wolfram Alpha, the rough width of our galaxy is approximately 9.5x10^20 meters. This is quite a lot, as you can imagine. Luckily, a double-precision floating point is more than capable of storing that number. What it cannot do, unfortunately, is store many numbers around that number.

The double precision floating point format has an 11 bit exponent and a 53-bit significand. The significand is essentially the number of bits of precision any number can use. This is approximately 15 decimal places. Any number that requires more than 15 significant digits will suffer from rounding errors. At the edge of the galaxy you would need a 70 bit significand (log2(9.5*10^20) = ~69.68) to represent a position at 1 meter accuracy. Ideally I would like centimeter accuracy to better deal with movement that takes place close to the camera and for that kind of accuracy I would need a 79 bit significand. With a double, the position would be rounded to the nearest 130,000 meters. That might be ok for large celestial bodies like the sun, but a 300x200 meter ship will have some considerable problems moving about.

So what can we do? There are a couple of options:

[font=arial,helvetica,sans-serif]

[/font]

A Quadruple precision floating point value is simply a turbo-charged double. It has a significand of 113 bits, which will give us a precision of around 114 femtometres at the edge of the universe. This seems like a bit of an overkill really. Each position value will take up 48 bytes with a quad. So a galaxy full of stars will be approximately 14.4GB of positions alone. On top of that, I would have to write my own implementation, as to my knowledge C# does not include its own native version, nor does HLSL - so I would have to add additional functions to my shaders for working with the larger data type, and I'm not even sure if it'll even accept a world coordinate that large. Additionally all of my code currently uses the SlimDX Vector3 class for position, as it's a handy tool for vector maths. I'm not adverse to writing my own implementation of those functions, but I'd rather not waste the time when there's a better solution.

[font=arial,helvetica,sans-serif]

# Use a combination of Single and Double precision.

[/font]

This is very similar to the Quad method, except instead of using a combination of 64bit and 32bit floating point values to give us a significand of 53 + 23 = 76 bits. An accuracy of 1.5cm at the edge of the galaxy. With this representation, a galaxy full of stars will have cut down to 10.8GB, which is not something to sneeze at, but I'll have to handle the math related to the compound values and I'm wasting the exponent bits in my single precision item.

# Use Integers

An odd decision for a system which wants decimal accuracy, but if I've decided the minimum acceptable positional change is 1cm then that can be represented as my minimum integral unit. I'd need an 80-bit integer (represented by a combination of a 64 bit integer and a 16-bit integer), which is still an ugly datatype, but it's precise and the accuracy is guaranteed to not change. Unfortunately I'd have to physically stop the player from exiting this range, and I thought we were passed the days of invisible barriers. I would need to pad data sent to the GPU to 128bits, but with this datatype the math will be slightly faster, and the overall size of a universe of stars would be 9GB.

# Shorten the maximum galaxy size

A double precision floating point will support a 1cm resolution

## up to a dis

tance of 9x10^13, or approximately 1/10,000,000th of our galaxy. Our galaxy has approximately 300,000,000 stars. 30 stars would fit in this restricted size, which isn't much for a space exploration game.

So what about integers? Using the same number of bits, an integer can represent 1.8x10^16 meters. This gives us 1/10,000th of a galaxy, and roughly 30,000 stars. This is much better for space exploration, and we can be fairly sure that a galaxy any larger has a very low chance of being explored. 30,000 stars with 64-bit integer positions would take up 720kb of memory.

But then there's still the problem of invisible barriers. It's very feasible that the player might hit 1.8x10^16 meters, which is only 1.9 lightyears, particularly since they'll start in the center.

# Offset from the player's location

If the precision of a floating point number reduces as the number increases, why not make that number the distance from the player? As the object is further and further from the player, its accuracy becomes less important, leaving an area of extremely high accuracy centred around the player, with lower accuracy reserved for the larger objects still being rendered, which are so far away that a 130km jump in position looks negligeable.

With this system you'd only really need the precision of a float, which would work wonderfully as I'm already using them. Fortunately the maximum size of a single-precision float is 3.4x10^38, due to the size of its exponent, which gives us plenty of room to play with. The accuracy at the edge of the galaxy (4.25x10^20) from the origin is 42,500,000,000,000m. This is a huge number, but remember we won't be rendering objects that far from the player, that's the maximum distance an item can be (roughly) from the player. Realistically, the most stars we would probably want to be rendering near the player would be ~2 (I intend to turn distant but bright celestial objects into a dynamically textured skybox). The 2nd closest star to the sun is Sirius, which is 8x10^16 metres away. At this distance, the accuracy will be ~800,000,000m, which is less than its radius (and at that distance I doubt that length would be much larger than one or two pixels).

The biggest downside from this system comes from the fact that you would periodically need to recalculate every celestial body's position from the player's by summing the difference between the player's current position and the position the player was at the last time the positions were recalculated, but that would only really need doing once a minute or so, depending on player speed. That's not too bad really, compared to 15GB galaxies or invisible walls or low-precision close to the player.

I haven't yet implemented it though, so it's still all pending. I want to re-evaluate how I use octrees so that instead of a spatial measure, they use the visibility of the celestial object to organise the objects (so using various "tiers" depending on visibility, allowing only a certain number of items in certain tiers), and this would be the perfect time to implement that.

## A Description Engine

Ok, so it's not the octree-based gravitation I promised you, but I came up with a very last-minute massive overhaul idea for aesthetics which has slightly broken the octree code. No biggie, but it's gonna take a bit longer to fix. On the plus side I am very excited indeed for the new look of the thing, which I'll show you at a later date. So this time I'm going to talk to you about descriptions.

Each one of my celestial bodies is based on a class which extends from a class, which in turn extends from more classes. In fact, if you want a look at the class tree at the moment for in-game objects, it's something like this:

So, as we can see, that's a lot of inheritence. I know you can't read the names properly here because it's so small, but the bottom-right block is where the stars, black holes and planets are. They inherit from things like mineable, dynamic, moving, massive, etc abstract classes. All designed to very easily encapsulate their own little pieces of functionality which has made crafting this game a hell of a lot easier.

An important part of Pigment will be exploration. I want it to be more meaningful than just zipping about, seeing what we can see. To start with I want to reward the player for finding new areas and I want the player to have to actively compete with other characters to be labelled the discoverer of that object (and be given the honour of naming it, of course). As such these things had better be a little more unique than "brown star", "dwarf planet", "moon". I need them to feel like they're individual, beautiful entities, born from the swirling fires of the galactic core and battered by the chaos around them. I took a big leaf from Dwarf Fortress here, which is probably the best case of procedurally generating attributes and descriptions there has ever been.

So how do I do it? Well, from every class, even right at the top, there is an overidden function Describe() which returns a string. The string it returns constitutes the current state of the description. So right at the top it will return "This object is a blue, supermassive star." and towards the end you might be getting a bit more detail. Each implementation of the function returns the parent class' string result combined with their own descriptive contribution in order to call the Describe() function on every class that is relevant.

So what does the code look like? Well here's the implementation for the Discoverable abstract class:

public virtual string Describe(){ if (Discovered) { return "It was discovered by " + Discoverer.Name + " in " + DiscoveryDate + base.Describe(); } return "It has not yet been discovered." + base.Describe();}

So here are a couple of descriptions that have been generated so far

This star has no name. It is unstable, with a temperature of 3574600C. It will likely collapse in 8000 million years. It can best be described as Yellow in colour. It is approximately 128 billion years old and it has a radius of 191AU. It has not yet been discovered.

This star has no name. It is unstable, with a temperature of 143400C. It will likely collapse in 1000 million years. It can best be described as Blue in colour. It is approximately 90 billion years old and it has a radius of 309AU. It has not yet been discovered.

This star has no name. It is unstable, with a temperature of 123130C. It will likely collapse in 1000 years. It can best be described as Dark Red in colour. It is approximately 100 billion years old and it has a radius of 252AU. It has not yet been discovered.

These are mostly randomized data in there, a lot of it just doesn't have the proper code to calculate things like size and colour so they're randomized, but later on this will give some highly scientific readings, and I hope to include orbit information and major events too.

In the future I hope to hook this description system up to some sort of text-to-speech engine and actually have the ship's computer read out data about it as you fly along. Space games always break with immersion as soon as you have to bring up a menu while you're flying along, because when that happens you're powerless to control your ship, so I want to have minimal reading and menu clicking where-ever possible.

## So I created a universe with 10,000,000 stars today...

Surprisingly it actually kept running interactively without stuttering for about five minutes before crashing. According to google our galaxy contains about 300,000,000,000 stars which is only 30,000 times more than what I've got! Not bad, if I do say so myself. Of course, really this is a limit on objects in general, as my universe won't just be made of stars. There'll be planets, asteroids, rings, nebulae, supernovae, etc.

Looking at the stats it took up approximately 12 gigabytes of RAM. I can probably optimize that later a little bit. Not to mention the fact that probably only 1/100,000 of that was on screen at any one time (draw distance was set to about 10,000km), so some sort of off-loading to disk would be best too. Maybe I'll work on that next, I've never done compression before - could be interesting. Anybody out there know any good articles on compression techniques?

Might publish a proper journal entry tomorrow about the gravitation system and the octree, if I have time. I'm also meant to be going to a ball with my girlfriend.

## And a video

This is a quick video I made of the spheres moving about and gravitating with each other.

I think in my next journal article (not tonight I'm afraid, I'm bogged down with tons of real-life work) I'll go into how I'm calculating them all. For the impatient I'm essentially using Barnes-Hut with my own implementation of an Octree. Each item performs pairwise gravity calculations which each other item in the octree node (each node has a capacity of items, I've set it to 3 currently) and then performs pairwise gravity calculations with the surrounding nodes themselves. The nodes accumulate the total mass of their children, so as to be a rough estimate for the amalgamation of gravitational forces in that region. This means that, roughly speaking, each item gravitates with every other item.

And lo and behold, the video:

[media]
[/media]

Bear in mind, I've artificially forced the spheres to be much closer together than they would be in real life (space, if you might know if you recall your Adams, is big. Really big), this is so that their motion is noticeable.

I'll talk about some of the issues present in the video (such as motion stuttering, a couple of LOD meshes with inverted normals and a bit of flickering here and there) in the next journal entry too, rest assured - I am aware of them.

## Hello Universe

I figured Hello World was a bit of a cliche these days, and since I'm working on a procedural space game, I figured Hello Universe would work better.

So I'll start by introducing you to my game. I call it Pigment.

Pigment is a game in which you fly among the stars, mining asteroids, trading, building factories, upgrading your ships and meeting interesting AI. I haven't gotten anywhere near AI yet (it's still a scary blob in the future), but I hope to make characters that you'll actually want to play with and keep alive. And I'm going to try to make those procedural. We'll see what happens along the way.

I'm also very new to games programming in general. I did a course on Graphics Programming two years ago as part of my BSc in Computer Science, but it was at an unfortunate time when everybody seemed to be translating from fixed-function to shaders, and we got taught the dying art. I have a long history of loving games, I used to make amateur levels for Unreal Tournament and UT 2003, and 2004 and did a bit of level design for the mod UnWheel (if there are any really ugly levels in there - you can bet I made them). Since then I've come to realize that design just isn't my thing, and so I've set out to create a graphically simplistic universe although it will be filled to the brim with pretty shaders because I love shiny things.

So, what's the story so far? I have a system which creates approximately 10,000 stars in random positions. I'm organizing them with an octree and I calculate gravity for each of them and move them all about in relation to each other using newtonian physics. In this game, there are no static objects.

I have just finished my post processing framework so I can add and remove shaders on the fly. It's based off of this, but a little more simplistic and specialized for my engine (although so far it works incredibly well, and is fantastically flexible).

And now that the framework is finished and working, I've begun writing some nice post-process effects. Currently I have bloom and depth of field blurring in there (although I want to modify the latter to use bokeh) and I have the following on my to do list:

Motion blur
Lens flare
Color aberration

Then after that I hope to put in fog volumes to simulate atmosphere and work out a better distribution algorithm for stars. Currently my stars are just placed randomly, I need them organised into galaxies.

So, what are my influences? Dwarf Fortress, Infinity: The Quest For Earth, the X series, Minecraft, Lego, Tribes: Ascend, Freelancer and, naturally, Elite.

So I present the culmination of approximately 1 year's worth of on-off work:

Pigment.

?
Followers 0