Destructible Terrain

[misiek]

no engine switch will happen - that would kill ufo - only replacing the underlying map structure

So it will be "quake" engine but with support for something else than bsp (it's quake format for maps, right)?

[Destructavator]

no engine switch will happen - that would kill ufo...

Very true, it would mean throwing out a good number of years of programming and hard work in favor of starting over with a totally different architecture.  In other words, project suicide.  I agree quite strongly with what Mattn says here, 100%.

For those who don't really program but dream of such a "suggestion," think of it this way:  You build a gigantic castle made of planks of wood, and then after a lot of hard work when much of it is complete someone suggests that you make the whole thing out of concrete instead - Just like that, you'd have to tear it all down, re-plan the design for different material and foundation, etc.

So it will be "quake" engine but with support for something else than bsp (it's quake format for maps, right)?

This - the solution to the issue - I don't know the answer to, I just know that it probably wouldn't be very easy to implement this, although not necessarily impossible.

[misiek]

This - the solution to the issue - I don't know the answer to, I just know that it probably wouldn't be very easy to implement this, although not necessarily impossible.

I'm afraid that it will be very hard. There are so many advanced "branches" of quake engines. But i don't know if at least one engine implement such functionality. On the other side those engines are mostly created for fps games, so maybe ppl just don't need such feature.

[Mattn]

define what you understand under the quake engine? - we've almost replaced everything or rewritten everything that was part of the quake engine. we are still using most of the utility functions and applications to create content for it. we are still using the formats the q2 engine introduced (though we advanced them a little bit here and there). so it's really only about replacing those formats - but the engine itself will not change.

[misiek]

define what you understand under the quake engine? - we've almost replaced everything or rewritten everything that was part of the quake engine. we are still using most of the utility functions and applications to create content for it. we are still using the formats the q2 engine introduced (though we advanced them a little bit here and there). so it's really only about replacing those formats - but the engine itself will not change.

That's what i've been asking. How much of quake2 is it Ufo: ai. I don't have experience in graphics engines, so that's why i'm asking.

So if i understand correctly it's problem of map format? Other things (like renderer) are capable of handling desctructible terrain?

[bayo]

map format (bsp) is optimised for fast rendering

[Destructavator]

BSP map sections also need to be compiled - That means either re-compiling parts of the map on-the-fly for damage, or dividing them into smaller sections and replacing them as needed, swapping out undamaged ones for damaged parts.

I don't know if the engine and most computers could handle the first case or not without slowing everything down, and for the second all the existing maps would have to be broken up and re-vamped.

The only case where I think this might work a little bit is base defense/assault - where if a building takes enough damage or a bomb is set that whole map tile (and that base facility) goes boom and is replaced with a destroyed, totaled mass of rubble.

[Mattn]

map format (bsp) is optimised for fast rendering

true but only for first person shooters with pvs and so on. there are other formats that are doing the same that would work better for us and are less static.

[Destructavator]

true but only for first person shooters with pvs and so on. there are other formats that are doing the same that would work better for us and are less static.

So does the game's modified engine support any of these other formats?  I've seen other games use tiles of OBJ meshes for maps instead, and some others still use other common formats such as .X, etc.  For one of my test projects I used a collection of B3D (Blitz3D, which IIRC is an open, free format) tiles to make a game map.

[ObLoM]

http://www.thermite3d.org/

Ok, well since the link I gave was broke (I've tried to repost it above), I'll paste a quick description from the site:

How Thermite Works
Most 3D game engines store their world as a collection of polygons, and in fact this is so common that you could be forgiven for thinking that this was the only way that a virtual world can be represented. For example, a simple room in a game world might be made up of six quadrilaterals, one for the floor and ceiling and one for each of the walls. In this representation we are essentially storing the surfaces which exist in the world because, most of the time, this is all we are interested in. We store the information that tells us what pattern is on the surface (texture), but we do not store any information about what is immediately behind that surface (brick, plasterboard, etc) or about what is in front of it (air).

For many purposes this surface representation is sufficient. It allows for detailed environments and efficient rendering by dedicated graphics hardware. However, its main drawback is that it is inherently rather difficult to modify at runtime. Imagine we wish to have an explosion blow a hole in one of our walls. This means we need to remove the polygon representing that wall and compute a new set of polygons in the shape of a hole. This process is known as Constructive Solid Geometry (CSG) and is a difficult thing to accomplish (though by no means impossible, as shown by the Red Faction 1&2).

Thermite3D does things very differently - instead of using polygons it uses a volumetric representation of the world (via the PolyVox library). This means it breaks the world into a 3D grid and, for each point on the grid, it stores what material exists there (rock, wood, air, etc). Each element on the grid is known as a 'volume element' or voxel. Figure (a) shows the idea:
 



The advantage of this representation is that it is very easy to modify at runtime. If you wish to destroy the world at a given point in space then you can simply change the material of all voxels within a given radius from being 'rock' to being 'air' and you have a hole. Of course, it's just as easy to go the other way and create material out of air, or even to just switch one material for another. There are no complex calculations and it is conceptually very simple. Figure (b) shows our room again, this time with a hole in it.

Of course, given this voxel world we still need some we of rendering it. There are a few options:
 
Use Raycasting: Raycasting is a computer graphics technique which involves tracing virtual 'rays' from the camera position into the scene. For each pixel on the screen, a ray is traced until it hits an object at which point lighting and shading calculations are performed to determine the pixel colour.
Render individual voxels: The voxels representing materials other than air can be rendered using graphics hardware. Each voxel could be displayed as a point sprite, or even as a cube mesh (though this would be costly).
Extract surface: An algorithm (known as Marching Cubes) is used to convert the volumetric representation into a conventional polygon mesh. This can then be rendered in the same way as any other geometry in the scene.

Needless to say, there are many trade offs to be considered when choosing one of these approaches. The underlying PolyVox library uses the surface extraction approach which allows it to integrate easily with existing 3D engines. When the world is first created PolyVox generates an initial mesh. When the world is then modified, the 3D engine simply requests new geometry for the appropriate region.

PolyVox is an Open Source (ZLib) library for storing volume data and for extracting isosurfaces for rendering. It is primarily designed to be integrated into a game engine as a method of providing fully dynamic geometry (this is how it is used in Thermite3D) but also has other applications in scientific and medical visualisation.

Its features include:

Storage:
Support for large volumes.
Memory efficient internal representation.
Fast read/write access to modify volume in memory.
Serialization routines provided.
Templatized on voxel type.
Surface extraction:
Fast implementation of the Marching Cubes algorithm.
Support for Level-Of-Detail meshes.
Allows different material types.
Automatic computation of surface normals.
Architecture:
Written in standard c++.
Cross platform (Windows and Linux).
No dependencies beyond standard library.
Bindings available to other languages.
Graphics API independent.

The PolyVox library's source is available, which should be all we need, unless I'm grossly mistaken. You don't need to replace your engine. That's what I'm trying to compile at the moment. Have been busy with work, but will actually look for a solution this weekend.

[Hertzila]

Just to clear things up, Red Faction did not actually remove any polygons while destroying walls IIRC but instead created an "emptyspace" object of the appropriate size when an explosive hit the ground or something else that was allowed to get destroyed. This was also used for other things: a bucket, for example, was a normal cylinder with an emptyspace object in the middle of it. Most of the time, however, the single player campaign did not allow the player to fully utilise this.

[Mattn]

might be worth a look, too: http://sauerbraten.org/

the cube (or sauberbraten) engine allows real time editing

[misiek]

I've also thought about about Cube 2: Sauerbraten. It's getting more popular in FOSS games, mainly thanks to:

http://sandboxgamemaker.com/

and

http://syntensity.blogspot.com/

Also someone suggested using Sauerbraten in project xenocide as battlescape engine.

[ObLoM]

The cube engine looks like an even better option simply because it's well documented and has a large community. What do you guys think? There is also an interesting paper on dynamic BSP trees:

http://www3.interscience.wiley.com/journal/120705748/abstract?CRETRY=1&SRETRY=0


I haven't read it yet, but will (again, this weekend...). It's old (2003) but may contain some useful info.

[Mattn]

again a deadlink