Jump to content

  • Log In with Google      Sign In   
  • Create Account

Nick's Corner

Size does matter - and precision too.

Posted by , in Pigment, Game Programming 17 May 2012 - - - - - - · 986 views
ooh matron, double precision and 6 more...
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:

Use a Quad

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.

Use a combination of Single and Double precision.

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 distance 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

Posted by , in Pigment, Game Programming 15 May 2012 - - - - - - · 840 views
Pigment, description, procedural
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:

Attached Image

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...

Posted by , in Musings, Quick Bits, Pigment, Game Programming 09 May 2012 - - - - - - · 1,064 views
mygoditsfullofstars, 2001, space and 4 more...
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.