Open world game strategy

[zingbat]

This is an idea i had to represent an open world like Morrowind, but without the problems of Morrowind.

Morrowind uses an terrain height map and divides the world in contiguous cells of a relatively small size (4000 x 4000 or something like that). In comparision a character is 256 units heigth so a cell has enough space for a small city quarter. Each cell places instances of game entities relative to its center so it works as a referential.

There is a library of unique game objects that are instantiated in the game. At any moment the world contains the terrain and content cell where the player is and the surrounding cells. If the player moves to another cell there is a cell cache that is update (loading cells from disk to memory) like this.

The current status:

VVV
VPV
VVV

V a visible cell arround the player
P the cell the player is on

When the player moves southwest for instance:

CCCC
LVVC
LPVC
LLLC

It keeps at trail of cached cells in memory just in case the player decides to sudenly step back.

C - a cell kept in cache
L - a recently loaded cell
P - the cell the player is on

I have detected the following problems with this solution. See the next post.

[zingbat]

The problems with this solution are enumerated bellow:

1- The library of unique game objects must be completely loaded into memory so that the game can instantiate game objects when a cell loads and has content that needs to be instantiated. The problem are textures, and dialog that grab a lot of main memory just for storage.

2- Morrowind isnt such a big game compared to its predecessor Daggerfall. The game itself takes place on a island called Vvanderfal that only ocupies a region similar to Betony island in Daggerfall. The size of Morrowind is comparable to a farm while the size of Daggerfall was comparable to Britain literally.

This is a problem because the 40x40 cell size of Morrowind takes something like 100Mb just to store height map data.
Using this solution to expand Morrowind map would be difficult and memory consuming.

It would be impossible for example for a game like starflight which has a map that spreads over several light-years distance on a section of our galaxy and has planets that can be landed and explored. Without breaking immersion or changing the world scale using this solution for an open world would be impossible.  

3- Another problem has to do with terrain recognition by the player. The player is only allowed to see what is just 1 or 2km in front of him. The player needs to look further and  recognize the shape of far away mountains to orient and guide himself in a big world.

There is a solution for this by using a plain map screen and fast travel like in Daggerfall and Fallout but this is not an immersive solution. The Player could enjoy walking and exploring the world without using fast travel.

My idea tries to solve these problems. See next topic.

[zingbat]

1- The first problem can be solved by using a database system like Berkley db2. There is a version of this database system that is completely made in java so its ideal for java games. The db2 also suports cached databases so this would allow a game to only load a part of the game objects library into memory saving lots of it.
The ideal would be to use zipped xml as the database format.

The cells would have to be loaded on demand and managed in a in memory database. Something that a database system can do very well too.

As for the size of textures and dialogs these can be keep in memory. Images compressed as jpgs and text using zip format. This would also save a lot of memory. The textures need only be decompressed when they are immideatly used.

3- The problem of terrain recognizion can be solved by working with 2 layers of tiles and a dynamic background. This works like shown bellow:

Layer 0: ..............................._._._._..................................
Layer 1: .____________.____________.____________.

The layer 1 tiles represent the world in a much larger scale: the surrounding mountains. Layer 0 tiles work just like Morrowind cells.

When the player moves inside layer 0 cells everything stays put.  When the player reaches the border of the center cells new cells are loaded and cached from cell DB and objects are linked from the game objects library.

At this moment the entire set of layer 0 cells shifts to the origin together with layer 1 cells. The layer 1 cells are then slighlty displaced to account for player movement, but notice that layer 1 cells may be smaller than the size they represent and the displacement too. The only thing that mater is the illusion of what the player sees.

In this way we can represent any world no mater what size it is in a snall region of the game engine 3d space. We are only restricted by hard disk storage capacity and not from main memory.

The dynamic bachground is placed at the limit of the far cliping plane. It represents far objects that are visible from the player point of view (like stars, the sun, moons) and is updated every N frames.

The only requirements for this is that layer 0 tiles must allways be placed above layer 1 tiles to avoid intersection.

2- Height maps take too much memory even if compression is applied. My solution is to have a mixture of procedural generated cells and hand made cells. Hand made cells as well as procedural generated  are true geometry. Terrain can have tunnels, archs, and be textured any way the artist wants. Something that doesnt work with heightmaps.

A new tool for creating the world would also be necessary. This tool would account for layer 0 and layer 1 tiles. The world designer would be able to set procedural properties for tile generation like vegetation, clima, terrain type, etc both for layer 1 and layer 0 tiles. The game creator could also edit a tile in layer 0 or layer 1 by hand. The precendence is handmade content is most important, then layer 0 procedural parameters then layer 1 procedural parameters then if nothing else is defined global procedural parameters.

Games published by our own members! Check 'em out!

[zingbat]

Any ideas, sugestions, rectifications, observations are welcome.

[t_larkworthy]

Procuderally generated geometries are really just a specialised form of compression really.
Err, I hope your layer 1 geomtry would be generated automatically as well.
But, thinking if you have a fast enough connection to a DB with all your geometry data, it should be possible to send queries to your map data.
So for your immidiate area you obviously need all the geometry data possible.
But as you get further away from the player, so you need less granularity. So you should be able to phrase a query that says if the distance is 1000 units away give me every 2nd tile data. Then more then more than 2000 everyy third et.c etc. and very continuously fade the resulution of the data proportionaly to the distance from one data source. (So not exactly how I just said it there, it would be a continuous function).
A good DB should be able to handle that I reakon.
When the player moves you need not run the whole thing again. Just add a little more detail to the map you have and lose a bit of deatial from the area around where you came from. The maths mof doing it would boggle my mind slightly, but it does not need even to be deterministic. You can imagine just sampling the data set around the player normalized on the player location. So point snear him are more likely to be picked to be added into main memory for drawing. And the same for removing points. MAke sure the immidiate area is certain to be picked.
I think thats a plausable method. I am not sure. I have jsut thought of it of the top of my head.
Further comments...

[dsellars]

Have you looked into somthing like ROAM for the terrain representation instead of tiles?

Dan.

[zingbat]

I think the Morrowind engine core, NetImmerse,  does a similar trick with the terrain. But its still an high-map. With an high-map we are limited by not being able to have holes and archs in the terrain. If we use tiles we can have any geometric shape for the terrain. Layer 1 is just for looks and orientation, it can be made of low-poly tiles (because of the distance) and have collision disable which spares a lot of cpu resources, and still have good background elements.

Imagine a tower 1km tall like in the Lord of the Rings movies. The player can see this tower far away in layer 1.

Another example is a sci-fi world like the prison planet in the movie Chronicles of Ridick. The walls are very tall and with a big inclination that usually cause problems on texturing height-map terrains. Rock cliffs are huge and its not possible to represent them with height-maps because they inclined to the side. All these aspects would be well represented on layer 1 with tiles.

[blahblahblahh]

With an high-map we are limited by not being able to have holes and archs in the terrain.

Not at all - you have plenty of research still to do in this area: games have been using "holey" heightmaps for many many years. The most common use is to allow caves and bridges, followed by modelling actual cities/buildings and things (which need rooms, archways, etc) directly in the heigtmap (although this is not done much these days since they can usually be more cheaply created using polygons - Max, Maya, etc are not traditionally great at city-scale modelling of heightmaps).

[zingbat]

How does that work ? Do you have more than one vertex defined per xy position ? In any case i think that algorithms similar to ROAM require a normal height-map to be able to LOD the terrain.

[blahblahblahh]

How does that work ? Do you have more than one vertex defined per xy position ?

I wasn't trying to be rude when I mentioned the need for more research - I was trying to gently point out the value of a quick google . You should very easily find lots of references to multi-valued heightmaps there.

IIRC there are 2 main techniques. One is to have multiple heightmaps layered on each other, each one being "solid" or "space" and then you simply make the area between the top of a solid and the top of a space == space, and the top of a space to the top of a solid == solid. The other is to parametrically define the HM, which is a lot better in some ways (makes it easy to encode entire map in a single number), and then you very very simply just use a multivalued function .

But...google it; it's been a very long time since I was doing HM's manually.