As I start to program multiple objects on screen at once, it turns out we need a more robust movement system than merely relative to the ship.. Specifically, I need a way to pinpoint an object's location within the solar system, whether it be a planet, ship, or player. And, after some testing to determine the smallest change in location visible to the naked eye, I worked out that we need to do it to within a tenth of a millimeter.
To quote Douglas Adams' HitchHiker's Guide to the Galaxy, "Space is big. You just won't believe how vastly, hugely, mind- bogglingly big it is. I mean, you may think it's a long way down the road to the chemist's, but that's just peanuts to space."
For example, it's about 5,000 AU (747,989,353,500 or about 748 Billion kilometers) to the start of the oort cloud, and it finally peters out around 100,000 AU. If we do the math, that means the diameter of our solar system is roughly 600 quitillion tenths of a millimeter. 600,000,000,000,000,000,000. That's a lot of zeros.
This presents us with two big problems.
Problem One - Space is Big.
Accelerating at 3 G's (~30m/s/s, which may actually be too high to sustain ), covering that distance would take almost exactly one year of constant acceleration. We need travel times on the order of minutes, not years.
There are several solutions to this problem:
We could scale up our accelerations - But allowing humans to withstand 100's of G's of acceleration would wildly affect combat. We could make time go by faster or slower - But a multiplayer game demands all players be on the same time scale. We could introduce system-internal warp jumps - But this would make for a less fun game, where players had a difficult time interacting with one another, and the high speeds attainable would make combat much less realistic.
My favorite solution is simply to scale down the size of the solar system - Scaling it down by a factor of 100,000 turns a 120 AU Pluto-to-Pluto transit into a 40 minute epic quest, and places the close-in planets and asteroids mere minutes from each other. Keeping the ratios the same allows more accuracy than the other solutions, while ensuring that fun doesn't take a hit for it. It's worth noting that this solution is nearly the same thing as merely scaling everyone's time by a similar factor.
At the same time, let's chop off the oort cloud and restrict ourselves to the Kuiper belt - At 5,000-100,000 AU, there's no method of scaling that will allow the Oort cloud to be easily reachable without making the rest of the solar system absurdly close together, and we can still access Oort cloud objects through comets. So instead of 100,000 AU, we merely need around 60 AU to reach to the far edges of the Kuiper belt.
So from our original starting point of needing 100,000 AU (600 Quintillion tenths of a millimeter), we now only need about (60*2 AU)/100,000, or 1.8 Trillion tenths of a millimeter.
600,000,000,000,000,000,000
1,795,174,448,400
That's a significant reduction!
Problem Two - Computers are less Big.
The largest number I can easily represent in C is somewhere along the lines of 4.3 Billion (4,294,967,295). That's a far cry from 600 Quintillion OR 1.8 Trillion - We're not out of the woods yet!
The naive solution to this problem is to use a larger variable in a slightly different language - C99, for example, gives us access to a 64 bit number instead of a 32 bit number, expanding our range to
over 18 quintillion! (18,446,744,073,709,551,615) That's more than big enough.
However, this method has a problem - Namely, hit detection. If I were to lump all objects in the solar system together, I would need to check to see how close each one was to each other one. Since I need to do this about 30 times per second and there may be thousands or tens of thousands of objects, this solution is likely to eat up a ton of CPU time.
However, there's a better solution - Chop the system up into Sector, SuperSectors, and MegaSectors.
Each Sector is 10,000 kilometers (1 billion tenths of a millimeter) per side - For scale, Earth is 12,756 kilometers wide. This means that a straight line drawn through our shrunken solar system would cross about 1.8 million different sectors. I told you space was big.
By adding sectors to large structures (SuperSectors and MegaSectors) I can construct an easy method of having enough sectors to do the job. Now, instead of needing to check for collisions against all other objects, I merely need to check in the nearest sector or two!
I've already got this system partially implemented, and have had some success making the ship fly around independently of the human character. The next steps are bug fixing and implementation of multiple objects. (Such as the sun and planets)
Click here for demo and purchase info
Cheers,
-Dirk
P.S. This article contains a lot of math and sometimes I miss things. So let's have a contest: Whoever spots the first major math error (Anything besides a typo or rounding error.) in this article gets a free copy of ScrumbleShip!
I can't tell you how many times I've looked over this and haven't been able to find anything, although I'm betting that when you started this you didn't think that it'd be as complicated as its become.
You've got that right! I figured I'd just use a floating point number, which is a computer representation of numbers like 145.124. Unfortunately, as the bits on the left side of the decimal get bigger, the bits on the right get less precise, so by the time you're out past Earth's orbit (Random guess, it varies per computer) things start dancing in front of your eyes.
Cheers,
-Dirk
Curious on how you plan on implementing gravity into this, I guess you can implement it so sectors around a planet are effected by a certain degree of gravity, which would save you a bit of programming instead of playing with the whole gravity= G x m1 x m2 /r2 where G is the gravitational constant (Most accurate one I could find for earth was this lovely gem: (6.674 28 (+/- 0.000 67) x 10-11th m3 kg-1 s -2), and M1 and M2 are the masses of the objects in question, and R is the distance between them.
That would probably suck up alot of computing power having to run that calculation every second, play with percentages and distances could save you alot of space and power, like gravity=base gravity/distance, only real problem is that'd leave you affected by the gravity of every object in the solar system at the same time, although the farthest objects will effect you so minutely it probably won't matter.
But I may just be speaking to someone that already has this all planned out, so I'm going to apologize for the rant.
I suspect that I'll use the sector structures to limit gravity, only extending the gravity fields of very large objects. It's not a solved problem yet, but I'll be working on it.
Remember that gravity isn't limited to planets - I believe Insolent has actually made a ship massive enough to tug the player slightly towards its center. I still need to do some math there. The acceleration is very small, though.
-Dirk
I can't wait to see what you do with it, Till then I salute you and your efforts and hope you continued success.
For suns and planets, what about making them be rectangle shaped instead of spheres? Kind of like this:
I.imgur.com
It would not only be easier to code, but also look unique and cause less headaches when designing planetside gameplay.
Yup, it has a ton of advantages - Starmade, I believe, is going that route.
Sadly, my obsession with reality won't allow me to go that way. Hard to orbit a flat planet, and orbits are a HUGE part of space combat. I do have to solve the problem of curved surfaces for centrifugal gravity systems anyway, so I'll be able to re-use code for curved planet surfaces.
Also, that picture is the most awesome piece of art I've seen in months. Where did you get that?
Cheers,
-Dirk
What do you mean by "orbits being a huge part of space combat"?
Do you intend to have planetary gravitational forces affect ships or something? Atmospheric re-entry, have ships spin around the planet using its orbit and other stuff like that?
As for the picture, just found it through google image search with the keyword "minecraft planet". Kinda of anticlimactic, I know. :p
The whole idea of ScrumbleShip is to accurately simulate space combat in the near(ish) future - And planetary orbits being such a HUGE part of combat, I'd be failing at my job if I didn't include them.
I also intend heat from re-entry, eventually, but I don't intend to simulate the surfaces of planets in ScrumbleShip 1.0 - It's far future.
Cheers,
-Dirk
Okay, but what exactly do planetary orbits actually do ingame? Whats the big deal with planetary orbits?
Played games like Freelancer, so I'm not really getting whats so huge about planetary orbits and how exactly do they affect combat.
Look up at the night sky. EVERYTHING you can see (And everything you can't see) is in orbit around something. In ScrumbleShip, you yourself will always BE in orbit around something, whether it be a planet, a sun, or the galaxy itself.
By orbiting planets you can bring slingshot effects into battle, atmospheric braking, and just simply hiding behind the mass of the planet. Changing another craft's orbit through kinetic projectiles or strap-on-rockets can lead to them crashing and burning on the planet's surface. You have to lead shots in an unusual way to place kinetic projectiles in the path of a ship following a circular path.
-Dirk
Whoa, now I'm WAY more excited about this game than ever before! Being used to seeing very simplistic space games in terms of their mechanics, this is truly something interesting compared to anything I've seen so far.
I hope you'll have a good, streamlined interface to allow players to grasp the concept of orbital combat as well as have the necessary tools to properly determine the trajectory of weapons fire or ship course.
Anyway, this is totally cool. Looking forward to this game now more than ever.
As a developer who has made a 3d-cubes-in-space engine with planets, I recommend Cube-Mapped Spheres. It's is a very mathematically trivial way to map a hypercube to a sphere. The gist of it is this: for each 'shell' or layer of your sphere, create a cube of the same radius (its surface subdivided just like a voxel cube, depending on its radius, i.e. a cube of size 3 would have 9 squares on each face, etc). Create a ray from the center of the cube to each vertex on the surface of the cube. Normalize that ray and multiply it by the radius of this shell. Now you have 'inflated' your cube into a spheric shape.
- a-type
I would like to suggest something called octrees to you. I don't know if you've heard of them them or not, but they're a lot like your sectors/supersectors/megasectors, generalized to have an arbitrary number of levels. They're used in a lot of game engines - particularly the physicsy bit - to just this, keep hit detection efficient. If you have N objects, you can check that there are no hits in about log(N) computations. This number rises, of course, when there are lots and lots of collisions. Because there will be at least as many computations as there are collisions. But for the vast majority of the time, when you're just drifting, it's very efficient. You can have ten thousand objects and check each of them in just around 13 steps, for comparison. Considering that each object needs to be checked [unless your code gets very extra fancy], this comes out to about a hundred thousand computations, which is fine at 30fps.
Yup, we actually use an octree-like structure to hold the ship data. I've made them a little different than a standard octree - The base nodes divide down into 100x100x100 arrays of cubes. This does waste SOME memory, but it also allows me to speed up a ton of algorithms that check blocks next to them - Rather than going up and down in the octree, I can just +1 and -1 my way around, same as a normal array. The fact that ships are MOSTLY solid and I'm using ram efficiently means I don't need to worry too much about the wastage.
The problem with using a straight octree for space is that Space is Big. I haven't done the math, but /thousands/ of octree layers wouldn't surprise me at all.
All that said, I could easily be wrong - But the source is open to anyone that purchases the game, and I'll accept almost any patch that improves performance ;)
Cheers,
-Dirk
If you use a 64bit integer data type to represent your positions, then the maximum possible octree depth is 64.
Dirkson: This is so cool to see - you solving the problems that lay between your vision of the game and making it a reality. :) I love this kind of update, and I love the progress you're making.