# Planet-sized level format?

## Recommended Posts

Mobile    100
I'm trying to gather ideas for a system to create a large terrain "world." The requirements are that it needs to feel like you're on a planet (e.g. you can start at one end and walk for a long time and end up back where you started), and there must be only a single "noticable" loading time. I was thinking maybe a streaming system could eliminate the noticable loading by loading level "patches" in the background as you travel. Anyone have any ideas or are there any papers coving this? Thanks

##### Share on other sites
MatrixCubed    199
Games did this 20 years ago. Ultima games used a system of realtime loading of groups of tiles to maintain a veil that the world was endless, with little to no load time. In 1999, Ultima IX did this in a 3D setting; the player could walk from one side of the world to the other, take hours to do so, and parts of the map would load dynamically with no visible performance hit. I don't think the world was continual in a spherical sense, but it's just a planned feature I guess; not impossible.

I'd be happy to discuss this in detail; let me know, as I have loads of ideas.

Cheers,

##### Share on other sites
Mobile    100
I wonder how well this would work out...

The map is made out of 9 patches of terrain (the patches are rather large) in a grid. Let's say you're standing in grid 1 and go directly to your left. As you walk, grid 2 will load and eventually grid 3. After grid 3, grid 1 will load again. At least I think that's how it would work. Let's say you're in grid 3 on the same path as described earlier... taking a sharp left from there would take you to grid 9... but what about diagnially from 3? Hmm... Let me draw a grid.

------------------------||     |     |     |     ||  7  |  8  |  9  |  ?  ||     |     |     |     |------------------------||     |     |     |     ||  1  |  2  |  3  |  1  ||     |     |     |     |------------------------||     |     |     |     ||  4  |  5  |  6  |  4  ||     |     |     |     |------------------------||     |     |     |     ||  7  |  8  |  9  |  7  ||     |     |     |     |------------------------|

Does that make any sense? Perhaps a grid is not the best way to represent a globe o_O

##### Share on other sites
Guest Anonymous Poster
As long as the size or location of any "zone" isn't larger than the effective floating point precision. That entails changing the local reference frame continually. I think this may have been what happened with Serious Sam if you walked too far off the beaten path.

##### Share on other sites
Mobile    100
Quote:
 Original post by MatrixCubedI'd be happy to discuss this in detail; let me know, as I have loads of ideas.

Yes, please :) I'm eager to discuss this!

edit: Also, technically, the world of course never has to actually be spherical at all. It just has to seem like what you're on is a planet.

##### Share on other sites
Yohumbus    152
Well that kind of top to bottom/left to right movement emulates a sphere well enough that users probably wont know or wont care but it is actually a torus. If you would like to read up I would suggest a great article on how these topologies work at everything2.com which can be located at http://www.everything2.com/index.pl?node_id=746760&lastnode_id=1140332 . Another thought is to use a lahey space which is just like the wraparound effect you see in most games but whenever you wrap your direction is taken into effect and you are made to end up where you started. There arnt too many sources over that topology so I will point you to where I heard of it in the funge-98 code specification (funge-98 is a whole different beast, interesting none the less). go here for that and search for lahey space and how it wraps around http://catseye.mine.nu:8080/projects/funge98/doc/funge98.html

##### Share on other sites
jflanglois    1020
You should probably take a look at The Continuous World of Dungeon Siege. It deals with just what you are describing.

jfl.

##### Share on other sites
hplus0603    11356
If you need a REAL planet that's sized like a REAL world (and round), then this is slightly harder. For example, the amount of data you need to store would be huge, unless you store it at very coarse grain, and let some procedural algorithm fill in the blanks.

For There, we made the world approximately earth sized. This means that you can get in a car and drive (our cars are amphibious), and it'll take three weeks of continual driving to circumnavigate the globe. A member did it (by taping down the "gas" key) just to see whether it'd work. It did :-)

##### Share on other sites
Mobile    100
Quote:
 Original post by Anonymous PosterAs long as the size or location of any "zone" isn't larger than the effective floating point precision. That entails changing the local reference frame continually. I think this may have been what happened with Serious Sam if you walked too far off the beaten path.

Can anyone elaborate a little more on what the AP said? I read in the Dungeon Seige paper that they had problems with the FPU as well. Perhaps I'm just undereducated in this area of 3D programming? ;)

Thanks

##### Share on other sites
Guest Anonymous Poster
Quote:
 Original post by Mobiletaking a sharp left from there would take you to grid 9... but what about diagnially from 3? Hmm... Let me draw a grid.------------------------|| | | | || 7 | 8 | 9 | ? || | | | |------------------------|| | | | || 1 | 2 | 3 | 1 || | | | |------------------------|| | | | || 4 | 5 | 6 | 4 || | | | |------------------------|| | | | || 7 | 8 | 9 | 7 || | | | |------------------------|

7

##### Share on other sites
tolaris    288
Quote:
 Original post by MobileCan anyone elaborate a little more on what the AP said? I read in the Dungeon Seige paper that they had problems with the FPU as well. Perhaps I'm just undereducated in this area of 3D programming? ;)

IIRC it's similar to the issue with z-buffer precision, i.e. 'resolution' of floats is not linear. If you move far enough from the centre of your world to the point where coordinates become 'large enough', you'll start noticing distortions in geometry caused by vertices veering off their expected positions. In order to fix this the origin of coordinate system needs to be relocated so what was too far from it now becomes sufficiently close to maintain desired precision. o.O;

##### Share on other sites
Mobile    100
Thanks for confirming that AP

##### Share on other sites
Mobile    100
Quote:
 Original post by tolarisIn order to fix this the origin of coordinate system needs to be relocated so what was too far from it now becomes sufficiently close to maintain desired precision. o.O;

How is this done? I didn't know you could relocate the origin...

##### Share on other sites
tolaris    288
Well technically, you can't. In practice, i figure moving coordinates of your object say, 50 units towards the origin ... is about the same as moving the origin 50 units towards the object? ^^; (since the coordinate values shrink by the same either way)

##### Share on other sites
Mobile    100
Well, let's use my grid technique for an example...

Let's say a grid is 100 "units" tall and wide and the origin starts at the upper left corner of the grid (see my grid for reference).

I am in grid 1 and I am facing grid 2. I walk through grid 1 to grid 2 and then onto grid 3. Past grid 3 is grid 1 again, but AFAIK I'm still actually 400 (or so) units from the origin, correct?

With that in mind, what should I be doing in order to prevent horrible z-buffer issues as I move further and further? Sorry if this question was answered and I just didn't get it ^_^

##### Share on other sites
Fingers_    410
Quote:
Original post by Mobile
Quote:
 Original post by tolarisIn order to fix this the origin of coordinate system needs to be relocated so what was too far from it now becomes sufficiently close to maintain desired precision. o.O;

How is this done? I didn't know you could relocate the origin...

You should read about the Dungeon Siege engine... The idea is that the contents of each "sector" of the world are stored in a coordinate system relative to the sector's origin so their coordinates are kept small. Each sector also contains a list of other sectors that connect to it, and where they are located relative to this sector's origin. When rendering, you start with the sector the camera is in, then draw the neighboring sectors (translated to where they connect to the current sector) and then their neighbors etc until you reach the maximum view distance.

As long as your maximum view distance is reasonable, you'll never run into floating point precision problems and the world can be infinitely large. The disadvantage is that the concept of a global coordinate system doesn't exist and you can't conveniently go to "location xyz". Creating a world map is also going to be difficult, as the system doesn't automatically result in a continuous non-overlapping world.

##### Share on other sites
Synex    170
Most of it all comes down to coordinate systems in the end. If you have enough coord-systems running at one you could pretty much simulate anything.

Trouble is getting your head around all the math involved in translating stuff all over the place through the coord-systems.

##### Share on other sites
So how big do you have to go before floating point precision kicks in? (roughly).

##### Share on other sites
Fingers_    410
Depends on a lot of things, like how much precision you need. For example, if your physics code uses small time steps and there are objects moving at a slow speed they will move very little during each step and require good precision.

An object moving at 1m/s (slow walking speed) in a simulation running at 100fps moves 0.01m per frame. To make it possible to move smoothly in all directions, you need a precision of 0.0002m or so (moving in a direction one degree off north, you move +0.01 in Y and 0.0002 in X). When a floating point number gets big enough, adding 0.0002 to it ceases to have an effect and that's when you start running into problems... The object will move directly north instead of north-northeast.

32-bit floats have 6-7 digits of precision, so the maximum magnitude of a coordinate should be no more than 1-10 million times greater than the smallest movement step that has to be reliable. Given the smallest step of 0.0002m, the maximum size of a continuous coordinate system is 400-4000m... Which is where the world sizes of most shooter games end up.

##### Share on other sites
Guest Anonymous Poster
I'm dealing with similar idea but what I want achieve is procedural generated endless terrain. My heightmapping unit uses Perlin algorithm. When we generate heightmap first thing is to get a bunch of random numbers. To achieve this we must use srand() routine. But when we use srand with constant number (f.e. 100) generated heightmap will be identical each time we create it.
So, my idea is based on kind of grid with seed numbers. With small bunch of these numbers we will be able to generate huge world. But there is also a dark side of this concept. We need algorithm which can fit edges of generated terrain patches. And unfortunately I don't have idea for this algo. It must be extremly efficient to fit terrain edges on fly.
Anyone of You have some ideas ? I'll be grateful for any help.

Regards,
Holrin.

Sorry for my weak english :)

##### Share on other sites
Ezbez    1164
Going back up to the grid that Mobile posted, if you change it to look like this...

------------------------|

| | | | |

| 7 | 8 | 7 | 8 |

| | | | |

------------------------|

| | | | |

| 1 | 2 | 3 | 1 |

| | | | |

------------------------|

| | | | |

| 4 | 5 | 6 | 4 |

| | | | |

------------------------|

| | | | |

| 10 | 9 | 10 | 9 |

| | | | |

------------------------|

...then it will create a shpere(a demented sphere becuase its made out of squres, but thats no less demented than the torus would be) instead of a torus. This way is just like a map. When you come off the top of a map, you come back facing downwards at a different point on the top of the map. The edges are left and right sides are still the same(again, just like a map). Note that if you move off a corner square to either the left or the right, you will come out on the other corner square in the same row.

Sorry that the grid didn't come out very well. It should still give you the idea.

[Edited by - Ezbez on June 15, 2005 2:55:04 PM]

##### Share on other sites
kosmon_x    205
I was actually thinking about this the other day, and here is the grid I came up with :

------------------------------||   / |   / |   / |   / |   / ||  9  |  7  |  8  |  9  |  7  || /   | /   | /   | /   | /   |------------------------------||   / |     |     |     |   / ||  3  |  1  |  2  |  3  |  1  || /   |     |     |     | /   |------------------------|-----||   / |     |     |     |   / ||  6  |  4  |  5  |  6  |  4  || /   |     |     |     | /   |------------------------|-----||   / |     |     |     |   / ||  9  |  7  |  8  |  9  |  7  || /   |     |     |     | /   |------------------------|-----||   / |   / |   / |   / |   / ||  3  |  1  |  2  |  3  |  1  ||/    |/    | /   | /   | /   |------------------------------|

The 9 locations in the center are the only locations that would actually 'exist'. All of the locations around the perimeter would only be fake 'pointers' to real locations in the middle -- you can't actually exist in these locations, but you can 'see' them. My idea was that as you start in square 5 and travel east, you will enter square 6. From there, you may be able to see square 4 on the horizon ( wrapping around ). So, you just draw square 4 where it looks like it should be (the fake square 4). If you keep heading east in square 6, you just warp the player or whatever back into the actual square 4, and then square 5 is on the horizon again to the east. Then it seems like a wrap-around world.

Similarily, if youre in square 4 heading west, you see the fake 6 on the horizon. As soon as you leave the edge of square 4, instead of entering the fake square 6, you are warped back to the 'real' square 6 on the other side of the map. The warping would be simple: if the left edge of the actual square4 has an X coordinate of 0, and the right edge of square 6 has an X coord of 600 (for example), as soon as your position gets > 600, subtract 600 from it. The player should pop back to square4, however the visuals shouldnt change at all since they've been looking at the fake square4 the entire time. (This only works if multiple squares aren't visible straight ahead from the left edge of a square.. otherwise you'd need a thicker fake border around the middle)

Anyone think this would work?

[Edited by - kosmon_x on June 15, 2005 11:38:03 AM]

##### Share on other sites
Ezbez    1164
That sounds like it would work, Modile. Of course, its still a torus, but that is no biggie. The only other thing that I can think that might go wrong, is that when you get moved to another square, it could be alot of sudden loading, which is not wanted.

##### Share on other sites
c0mas    107
Just an ideea, why use a full grid ? There may be some cases where a square in your grid is never visible and you can use that memory for other square and to enlarge your world. I think it's easy to modify the algorithm to allow nonsquare grid with empty places.

##### Share on other sites
Guest Anonymous Poster
Quote:
 Original post by c0masJust an ideea, why use a full grid ? There may be some cases where a square in your grid is never visible and you can use that memory for other square and to enlarge your world. I think it's easy to modify the algorithm to allow nonsquare grid with empty places.

Sure, but unless the basic square-grid algorithm for generating a torus that fakes a sphere works in the first place, this won't work..