Sign in to follow this  

Dealing with huge open spaces (universes)?

This topic is 3778 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello gamedevs, I'm currently working on my first rendering engine and got stuck on how to efficiently solve the problem given in thread title. Specifically here I'm wondering how to handle positioning, and rendering at those positions, in universes that span hundreds millions of kilometers yet to have good and preferably fixed precision at any point (I'm aiming between micrometer and millimeter precision here). I can't see how this can be done with a standard 32-bit float data type so the most straight-forward thing would be to switch from "floats" to "doubles" in order to use double's higher precision to alleviate the problem. However, this does not solve the problem completely as the double also has its limited range and, more importantly, there is still an issue of variable precision which will again cause problems at the "edges" of a universe which are now just further away than with a float. Some suggest switching to integer domain (64-bit or even 128-bit) to handle these problems like in the article here, "A matter of precision" on "http://home.comcast.net/~tom_forsyth/blog.wiki.html", which sounds reasonable to me. I can accept the idea to handle positions of a player/camera in large integers and do the movement deltas in floating point but what confuses me is that ultimately a scene at some point in universe has to be sent to graphic hardware as stream of vertices in floating point format but conversion from large 64-bit integer values even to doubles (space-to-space transformations) will have some serious rounding errors. I do not want to switch to doubles if there is any possibility to get away with integers+floats. Bottom line is I don't understand how to handle this problem, and have possibly misunderstood the proposed solution with integers, so if any of you good souls has any advice to give and point me in right direction, I'm all ears :) Thanks.

Share this post


Link to post
Share on other sites
Split up the whole place into grid regions? Each has a local position. I believe dungeon siege did something similar. I'd imagine you are limiting sight? Then again you'd run into a problem of grid regions with nothing. Not sure how memory friendly it would be.

Share this post


Link to post
Share on other sites
What exactly are you trying to pinpoint? That accuracy might be possible (though, I seriously doubt any modern computer could possibly store all that data), but utterly pointless. I did some research a while back for a science fiction story. If you're trying to draw even just every star in the universe, then you're drawing a good 100,000,000,000,000,000,000,000 stars (I can't remember the exact figures I used to get this estimate, but google search the number of stars in our galaxy and multiply it [ours is small] by some small number [1.x], then by the number of all the known galaxies, then round down). You can't possibly store all that information, let alone to the degree of accuracy you're seeking.

If you're on the galactic scale, a few light years wont make a difference, let alone micrometers. Even then there are an extreme amount.

You should note that there is no way to know the exact position of anything at any great distance in space (or anything, if you want to get much too technical), so no matter how accurate your scale is, it wont be "real." Also, one would not be able to tell if something were a number of kilometers off target at any great distance, let alone meters, so that scale is again unnecessary.

Honestly you need be no more accurate than astronomical units (AU), and even then you will be facing horribly complex methods of compressing locations in space.

Share this post


Link to post
Share on other sites
From a logical standpoint, and from that of making a game, trying to represent all at once an entire universe is completely unreasonable and unnecessary, but there are ways of doing it. The best approach would be procedural, which would allow you to generate static data on-the-fly and at a variety of scales. You could subdivide dynamic objects according to a variable-sized partitions. But, seriously, this is a waste of your time.

There is only one really viable alternative, and that's to individually design each significant region and ignore the space in between. Freelancer presents a very good example of this, with each star system being detailed down to the meteor level, while providing jump gates to speed travel between systems, thereby trimming all the boring, unnecessary parts. You still have to travel between planets and intra-system phenomena (like asteroid fields).

Consider that, as a practical matter, you would not be able to see anything more than a few hundred kilometers away at best, and it's likely you would see far less than that. Only planets, stars, and other massive cosmic features are visible from millions of kilometers; ships would be invisible at that distance, even with scanning devices (unless they are preternaturally accurate). A localized approach is probably your best bet from any standpoint. Seriously, who in his right mind would want to travel through all that empty space? Even Freelancer, with its hand-crafted star systems, jump lanes, and greatly exaggerated scale, bored me to death in its vastness.

Share this post


Link to post
Share on other sites
Just a principle that should work: Following the answers above, only a (more or less) small part of the universe should be rendered at a time. Then objects in the universe need not be given totally in the maimum numeric resolution. Instead, their position may need to be defined using that big integers, but perhaps their vertices don't need so. Now, after subtracting the (big integer) position of the cam from the (big integer) position of an object, and determining that the object is inside the (said more or less) near range of visibility, then the above subtraction has left a local co-ordinate system (i.e. camera CS) where e.g. float is sufficient. Since rendering is done in this local CS only, vertices with e.g. float resolution are sufficient. Things too far away may just be rendered using bill-boards or similar stuff.

(Since I haven't tried to implement such a thing yet, there may be pitfalls I've not seen from this theoretical point-of-view, of course.)

Share this post


Link to post
Share on other sites
You should never have to specify geometry at greater precision than that provided by floats (in video games, at least). Just make everything in a region keep track of its position relative to the origin of that region, which would be specified by a double or a long double or a big integer or whatever you want to use. The camera position is also specified relative to the region's origin.

Make the regions overlap a bit, and when an object passes completely into a different region, it becomes associated with that region and its position is recalculated. If parts of a region other than the one the camera is in need to be drawn, just compute the camera's position relative to that region.

Open space can be filled with a regular grid of regions, which only exist when they are needed. But space is a big place...

Share this post


Link to post
Share on other sites
I agree with Vorpy. To what end does so much precision become useful? If you're drawing a planet a million miles away, it isn't going to look any different if it is (imprecisely) a million and one miles away.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zipster
Check out The Continuous World of Dungeon Siege for some ideas.

Great, thanks. This article was right on the spot. The concept presented there, "there is no (unified) world space", is just about what I was thinking under "getting away with integers and floats".
While this does allow "endless" spaces with floating point precision issues constrained to only a single segment, it works well basically only with that type of game. Under this I mean:
- an environment that is not highly dynamic
- no need for high-velocity movements and fly-overs
- problems with "teleporting"
Second thing I noticed is that they use a fixed "up" direction meaning in fact that this system is not applicable, or perhaps with many difficulties, to planets (spheric worlds).
In general it is a really nice concept but with this implementation it's tailored for a different game genre than I'm aiming for.
Quote:
by Zouflain
If you're on the galactic scale, a few light years wont make a difference, let alone micrometers. Even then there are an extreme amount.

When looking at something from such a great distance, such fine precision really does not matter, you're correct. But, if I were to "fly" over to that distant place I would want to have the same (or very similar) precision as at the place that I started from.

From all your posts until now I can draw a conclusion that really the only reasonable way to handle this issue is to use segmented space. Haegarr summed this nicely. I could use integers to handle absolute universe coordinates and use floats in a single segment. Now, how big can this segment be? I'm thinking that if I am to accept 1mm precision at outer edges, this segment (box) could be 8km in each direction. With 1 cm it could be 80 km but this as far as I'm willing to accept. Discussion on units of measurement covered here.
Quote:
by Vorpy
Open space can be filled with a regular grid of regions, which only exist when they are needed. But space is a big place...

Indeed, it is big which leads to a problem Sirisian stated
Quote:
by Sirisian
Not sure how memory friendly it would be.
if such small segments are used. Left to be seen...
Quote:
by Tom
From a logical standpoint, and from that of making a game, trying to represent all at once an entire universe is completely unreasonable and unnecessary, but there are ways of doing it.

Exactly, and my goal was to find out what are possible solutions, both sane and insane ones. I am writing my final exam on the topic of 3D real-time renderers with support for open terrains/spaces and as one sub-topic I need to identify what would be theoretical and practical limitations if such renderer was to be taken to the extreme, meaning, "entire" universe and also what would be possible and eventually feasible solutions for it. I am also supposed to roughly calculate approximate memory/processing requirements for each solution and define its pros and cons.

For the practical part of this work I am to implement a relatively simple prototype, a showcase, for such a renderer which is required to cope with a plane with procedurally generated terrain (ultimate goal is 1000x1000 km). Solution for planets needs to be documented only, not implemented.
As a side question, does anyone have any idea how ROAM algorithm would be able to cope with a segmented space solution?. Since it works on the principle of triangle subdivisions, and two triangles make a quad which is after all the base for each segment, it should work in a single segment (lets say terrain patch for my prototype) but would it be able to cope with multiple segments (patches)? I guess some seam stitching will be required :-/.

Thanks for all your replies so far.

Share this post


Link to post
Share on other sites
Quote:
Original post by TomEven Freelancer, with its hand-crafted star systems, jump lanes, and greatly exaggerated scale, bored me to death in its vastness.


Maybe slightly off-topic, but how is that possible?!? IMO the Freelancer "universe" was far too small, rather than too vast.

Slightly more on-topic: It actually is possible to create a whole universe on a quite detailed scale, as long as it's done procedurally. for example look at this game: http://www.fl-tw.com/Infinity/

Share this post


Link to post
Share on other sites
The relevance of the Dungeon Siege system is in the idea of doing everything in a local coordinate system to avoid the floating point accuracy problems.

For example, you could make your universe out of, say, 1000km cubical sectors so your physics engine would only need to maintain accuracy with coordinates in the range between 0-1000km (each moving object runs physics within its local coordinate system). The size of the cube and how these cubes are arranged (e.g. as octree leaves) depends on the exact needs of the application.

When rendering, you render the sector the camera is in, then any neighboring sectors etc etc until you reach your maximum view distance. Float accuracy will affect the rendering of sectors far away from the camera, but the errors will not be visible due to the distance.

This doesn't scale to interstellar distances, but it doesn't need to. When traveling through interstellar space, you don't need much precision so using coarse "galactic coordinates" outside planetary space should be fine. Traveling to a (very) nearby star mere ten trillion km (~1 ly) away, taking (boring) half an hour of game time, running at 100fps... You're moving over 55 million km each frame! Even using integer kilometers would be total overkill for accuracy, while a resolution in the hundreds of thousands of km would be perfectly adequate.

In conclusion; a clever local coordinate system based space partitioning around stars/planets will allow "islands" of high precision where it matters (to allow slow-speed accurate maneuvering within star systems), while a much more coarse global grid should be good enough to allow traveling between them.

Share this post


Link to post
Share on other sites
Quote:
Original post by l0calh05t
Slightly more on-topic: It actually is possible to create a whole universe on a quite detailed scale, as long as it's done procedurally. for example look at this game: http://www.fl-tw.com/Infinity/

Yes, of course, I forgot to mention Infinity as an example closest to what I'm trying to achieve here. Some time ago I read through I believe entire journal of Infinity's developer here on Gamedev but do not remember to read anything on this issue. Now, motivated by your post, I visited the Infinity's homepage again and found this :). Answers the question in bigger part. Oh well, I should have looked harder in the first place.


Share this post


Link to post
Share on other sites
Quote:
Original post by Orcalib
Quote:
Original post by l0calh05t
Slightly more on-topic: It actually is possible to create a whole universe on a quite detailed scale, as long as it's done procedurally. for example look at this game: http://www.fl-tw.com/Infinity/

Yes, of course, I forgot to mention Infinity as an example closest to what I'm trying to achieve here. Some time ago I read through I believe entire journal of Infinity's developer here on Gamedev but do not remember to read anything on this issue. Now, motivated by your post, I visited the Infinity's homepage again and found this :). Answers the question in bigger part. Oh well, I should have looked harder in the first place.


I believe this is a similar problem to the one faced and dealt with here A Real-Time Procedural Universe, Part Three: Matters of Scale By Sean O'Neil.

You'll need to create an account on gamasutra to read it but it's well worth it there's always good solid articles on there. Several are linked too from GameDev itself. I don't have time now to find his personal website as am about to run out of the office but he's got lots of samples (including source code on the gamasutra article) that's worth taking a look at for reference purposes.

Andy

Share this post


Link to post
Share on other sites
(If you haven't already) you should check out how Freelancer and Eve Online handle space with a similar jump gate system. Eve Online has a 10 day free trial.

Also, I hear Battlecruiser has planets you can land on with seamless transitions from space. I believe it is the only relatively mainstream game to have implemented such a system? Never heard of any others personally.

Sounds like an interesting project though. Here's what I would do to keep it simple:

- I assume you want moving planets, stars, galaxies
- When drawing stars I assume you want to account for speed of light? (i.e. you see a star 7 light years away in the position it was 7 years ago)
- I think rendering all galaxies in the universe is doable if you do some simple LOD

Objects:

- all of space is the "Universe"
- a cluster of stars is a "Galaxy"
- a single star with orbiting planets is a "Solar System"
- a single planet with orbiting moons is "Planetary System"
- asteroid belts can optionally orbit any star or planet
- rings can optionally orbit any planet

Trajectories:

- define all trajectories by a) an elliptical orbit equation and, b) an axis, and c) an orbital period. You need all so you can know exactly where a given galaxy, star, planet, moon is at any time.

Movement of bodies (everything has an elliptical path):

- Moons/rings/asteroids orbit Planets
- Planets/asteroids orbit stars
- Stars orbit the center of a galaxy
- Galaxies orbit the center of the Universe

Time:

- When in a solar system time is "real time"
- When warping through freespace in light-years per second time is sped up.

Partitioning

- multiple-grid based scheme
- Universe divided by grid measured in light years
- each grid of the Universe divided into sub-grid measured in something smaller than light-years
- etc...

Updates:

- do a LOD-based update scheme
- In a "Universe Time Step" all Galaxies will be updated. When moving through freespace only Universe Time Steps occur.
- When in proximity of a Galaxy, "Galactic Time Steps" occur, in which stars are rotated around their galaxy center
- When in proximity of a star, "Solar System Time Steps" occurs
- etc...
- Thus, you only update objects that are near you adjusted for performance.

Drawing:

- Based on the same LOD system
- Galaxies >X light years away are represented as a single dot. When drawing them, subtract X years from their elliptical orbit calculation to show where they were X years ago from the viewers point.
- For Galaxies within X light years away draw each star, subtracting X from their elliptical
- Draw planets only within the local solar system
- Draw moons only when close to a planet

Using multiple grid resolutions solves your "extremely large number" issues. You can render far away galaxies using Universe Grid coordinates and render nearby object using finer grid coordinates.

The seamless transition from space to planetary atmosphere will be an extremely tough problem, I wouldn't worry about it until the end.

Share this post


Link to post
Share on other sites
Quote:
Original post by FippyDarkpaw
Also, I hear Battlecruiser has planets you can land on with seamless transitions from space. I believe it is the only relatively mainstream game to have implemented such a system? Never heard of any others personally.


This was also done by David Braben in Frontier: Elite II in 1993. Although a hyperspace system was in place there as well (as well as a method of speeding up time). I guess most players aren't all that interested in games that only get interesting when their great-grandchildren play it. ;)

Share this post


Link to post
Share on other sites
I only really see two main issues with space-based games:

1. Rendering and precisions. Easily solvable by floating-origin systems so that the objects being rendered are never sent to the graphics cards outside of 10k units or so. Planetary rendering and dynamic LOD has been covered many, many times just on this site alone.

2. Distances. Space is big. Really big. You just can't believe how mind-bogglingly big it is... and so on. This is a disaster waiting to happen in terms of gameplay. Most people do not like traveling for hours at a time and it really does not make a fun game, so you've got to keep a sense of scale. Freelancer basically threw away scaling and realistic positioning completely in order to make a fun game. As Freelancer is much more arcade shooter than space simulation, such a decision worked really, really well.

This is one issue I will be watching with Infinity pretty closely: how to keep the player occupied and not bore them to death with traveling massive distances. Freelancer did a good job, the X series did a good job, Eve Online maybe went a bit too far, but it is successful.

Good luck on your project!

Share this post


Link to post
Share on other sites

This topic is 3778 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this