Can I create 2D destructible terrain like Worms / Scorched Earth

#1 Tile Maps: The problem with tile maps is the difficulty with preserving the edges of decay without modifying the bitmaps/tiles at the destructed tile locations. This creates problems because the entire map is sharing the tiles and I don't think you want to be creating new tiles on the fly for every shot. Tile maps would be fast and easy to implement unless you wanted something that looks more exact. Damage tiles would smooth the transition of the terrain destruction.

Quad maps: I would dynamically generate the terrain and use quad maps for collision and geometry. The actual background would be one giant image (or a collection of compatible pow^2 textures). Any damage to the terrain would be drawn directly on the bitmap (burn marks, magma, particle effects fire/snow). The quad map would need to be regenerated in the area that recieves damage, but that should be very fast. Though I haven't used the TBX tile maps yet, I would imagine it be easier to store user data in the quad maps since you would have to create them from scratch. The user data could store elements that define what type of materials or the collision responses (empty space, impactable, sink like a rock, tunnelling factors). This would allow you to more easily do things like snow drifts, glaciers, rocks, water, mossy mountains or tree tops.

Either way I can also imagine a system that records the weight of segments and controls landslides or cave ins from stressed areas. I can also imagine this would be easier with quad maps because the child data for every node can be aggregated in it's parent which should speed up certain types of algorithims.

Lastly, quad maps can be extended to octal trees for 3d representation.

-Stu

#2 Thanks for the replies!

@Stuart: Can you give me more details on the quad maps? How would you get use one imagine for the entire background instead of individual textures for each quad?

I'm also unsure of what you mean by using the user data to store snow drifts, glaciers, etc.

Any more help you can give me would be greatly appriciated!

Thanks,
John

#3 I immagine collision would be a huge pain for something like that without convex polys. If you plan on colliding with the terrain you might wind up needing a custom solution. Post back with what you find, if you don't mind. I'm curious to see what you come up with for this.

#4 @John: What kind of quad map detail are you looking for? Are you familiar with oct trees and quad tress and would like some direction on implementation tactics, or would you like something that includes the definition of the quad structure as well? The latter would take me longer to discuss and I would need to make some pictures for visual aids.

I haven't rolled it into Torque yet, but I have an XNA demo that creates a quad map for collision detection based on an input bitmap. I use the non-alpha areas to represent the solid sections of the map. It's more than fast enough, but it news/deletes a lot so it needs some optimization before making itself useful (there's occasional jitter from GC). As a demonstration for per-pixel collision detection against swept spheres it's awesome, but now that I'm using Torque it's not as sexy as it was 10 mins ago. The main reason I wrote it was to avoid writing the more robust/complicated system that GG has already created. I didn't want to update my collision zones every time I tweaked the stadium boundaries because before Torque I would've had to do it in code and buy hand. Hail Torque! Since it's a hockey game demo, I wanted the curves of the wall to be simulated really nice. This translates to requiring no push out code so I never experience any sprite jitter on the edges or anywhere.

I'm thinking of integrating a hybrid quad scheme that uses the swept poly collision code already in Torque but setting it up in XML as part of the content pipeline. Why? Because its less work in content maintenance over the life of the project. I think I could also generate light/shadow maps using this approach in semi real-time (not every frame, but fast enough for level updates) for more interesting grand theft auto style game play (Think GTA 1 or 2, before the 3D). I'm also a bug fan of Syndicate's isometric lighted environments. I think the quads would make it pretty simple to use streaming/LOD techniques for huge environments akin to some kind of cheesy ROAM algorithm.

As for snow drifts, water, ice, etc..... When a projectile enters a section of the quad/tile map you can change the physics that interact with it. For snow drift you could allow the projectile to tunnel in for a bit before impacting. When it reaches zero within the drift it blows up. This makes it possible to smack a snow drift on the top of a mountain and pop out the other side, albeit at vastly reduced speeds. Dirt/rock can work the same way but with much higher friction values. That section of the map would hold values such as the friction of the material or the percentage of rocks hidden within. When projectiles explode in snow you could create water and let that flow/pool up in the low areas. Projectiles that hit water could bounce at high enough speeds and shallow angles, or sink like a rock with a big splash on top and an explosion at the bottom of the water where a bunch of steam and bubbles come up. Your map tiles could represent more than just the solid parts of the level. You could simulate forces such as wind and gravity or repulse fields. Depending on how many forces you wish to simulate a quad map could greatly help in calculating the 'force map' so that the game doesn't chug with a few hundred forces going on.

It really depends on what you have in mind. I have no idea if any of these ides would make your game fun but I could go on like this for decades.

-Stu

#5 Those are ideas are PERFECT for the game I'm thinking of... (eg. different terrain types [snow, dirt, water] and tunneling inside the ground before creating an explosion is another great idea)

I'm familar with the Quad structure and I know that in my original version (that Michael Worister created for me), that tons of quads were used (each 1 pixel wide by the current terrain height). However his version didn't allow for tunneling (eg. digging a tunnel through the landscape and having dirt above and below you).

I don't know how a Quad Tree is, but I'll do some searching (Wikipedia has some information, but no nice pictures or the like). Although if you feel like explaining it better that would be excellent :)

It sounds like you have a perfect idea of what I'd like for the game... (although I hope you know I'm talking about 2D only and not 3D [eg. so I don't need "octrees", right?])

Whatever information you can help me with would be VERY greatly appriciated. However, if you don't have time to explain any of this, that's OK.

Thanks!

- John

#6 Also, could you use quad trees with TorqueX and/or Torque Game Builder, or does it require custom programming? (eg. modifying the engine)

Modifying the engine is OK (obviously harder), but I'm really determined to get this project working...

#7 >> Also, could you use quad trees with TorqueX and/or Torque Game Builder, or does it require
> custom programming? (eg. modifying the engine)
>

I know I'll get my quads working with Torque X. What I don't know is how I'll place them into the TGB as visual components. For the time being the Quad Maps will have to be hooked up by hand in code.

>> although I hope you know I'm talking about 2D only and
> not 3D [eg. so I don't need "octrees", right?])
>

Quad Maps are simplified octrees but the principles are exactly the same. I don't have the time to explain QM now but I'll have the opportunity tonight and I would love to talk about QMs and how they may apply to the game you're making. You've got me hyped on your project and I relish the chance to give advice and ideas.

More news at 11:00.

-Stu

#8 After reading an article over at (http://www.heroicvirtuecreations.com/QuadTree.html), I understand the basic idea. I can also sort-of see how this can apply to a terrain landscape in the very broad-sense (eg. my terrain would be a quad tree and when an projectile hits the ground it will sub-divide if necessary). However I don't understand how I would use the quad trees to accomplish this.

I look forward to hearing your explanation!

Thank you very, very much!

- John

#9 I'll need to make this quick as work keeps coming up.

Since you're familiar with what QM's essentially are I'll talk about their usage. To use a quad map, you'll need to create one. So that's the first step. The second is to run your calculation in your game loop through the QM.

Creating the QM
I usually start by creating one giant quad that's a power of 2 that'll cover my map/boundaries. If the quad fails to satisfy 'done' conditions I break the quad into 4 pieces if possible (For example, a 2x1 quad will not be broken down further). If you really want 1x1 granularities you'll need the width and height to be the same size and powers of 2 so that the splitting works out.

What satisfies the quad condition is entirely up to what you're using it for. For a brute force collision detection scheme, I used the pixels in the bitmap that the quad area represented. For example: If the quad was Min(128, 128) - Max(256, 256) I would read that area of the source bitmap. If the pixels are all black the quad is marked 'solid'. If the quad has no black pixels then it's marked 'empty'. If it has white and black pixels it's marked mixed and 4 new quads are created and added as children to the mixed quad. The children each do their own test and so and so until no more children are created. You only want to do this once.

In the picture below the pink represents solid quads. The red are the quad boundaries. The green is just hideous.

Using the QM
If you don't already know the position of the object in your world you should start with a function that returns the quads that the object rests in. Since I'm playing with circles, mine tells me what quads an object straddles given its position and radius. This function always returns leaf nodes! That's important. The yellow in the picture below are the areas that the puck is touching.

When my object moves across the landscape I run a circle sweep test from the quads that the object rests in. In the picture the large blue line represents how far the object can travel before it hits something. The little blue line represents the normal of the surface it's hitting to the center of the circle. Normally you run an intersection test in the quad that the object is in. If it penetrates the boundaries of the quad, you get the neighbor of the quad and find the leaf node that contains the intersection. You start the test over from their. At some point the neighboring quad will be 'solid' or different in some way that you change the behavior of the projectile. If it's 'thicker' than air you alter the bitmap and the physics operating on the projectile. If it's rock you blow it up and edit the bitmap. Keep changing the behavior of the projectile depending on the properties of the quad that it says it's in. In my demonstration I always calculate the distance to the first edge which is why you see blue line go to the edge. Normally you just calculate enough to know you haven't 'hit' anything.

Because the map is changing you want to restructure the quads, but never the whole tree! To make it work quickly you'll have to work the tree backwards. Take all effected nodes and run an update test. If the quad is different you add or removing children and run the same test on the parent. I haven't done any update quads so the exact implementation will probably vary a bit.

I hope that helps at least somewhat. I would start with creating a quad tree and writing a function to find the leaf quad the object is in.

#10 Great explanation Stuart!

#11 Thanks for the explanation!

How can I create a quad map with TGX/TGB?

I'm thinking that I will start with a one very large bitmap (2000x1000 or something) that will contain a rectangle-shaped landscape.

Next I will create a random set of points to create a random terrain (eg. hills, slopes, etc).

Finally, I will need to create a quad tree of the terrain using the points that were randomly generated.

What kind of structure exists in TGX/TGB to let me store a quad tree? Also, how would I map specific parts of my large bitmap to each quad tree leaf?

(Does this sound like the correct approach?)

I'm trying to learn how to map quad trees using OpenGL (in Delphi since thats what we use at work), but it looks like using OpenGL is not very easy... (compared to normal Delphi stuff)

#12 I believe that you will have to create your own quadtree functionality for TXE/TGB. I could be wrong, but I do not think it is implemented (and hence the need for Stuart to create an implementation for his work).

#13 I found a resource link in the 'resources' section of this site on quadtrees: www.gamedev.net/reference/programming/features/quadtrees/

It has pictures and example source which should be very useful to starting out with quad trees. I know of no support within TGX/TGB that'll help with building the tree so you'll have to roll your own. I would start with a bitmap drawn by hand that represents my terrain, unless you already have a random map generator. From there I would work on an algorithm to sub-divide the terrain into the smallets quads, which is covered on page 2 of the tutorial. It's all C++ code so you'll need to convet over to managed.

#14 Ok, I'm beginning to understand more...

Quick question:

In your picture above, you seem to have different sized quads. Some of the large white areas are one big quad and the more detailed areas are several smaller quads.

From what I've read it seems like all quads are the same size (eg. when you first create the quad tree, you keep sub-dividing until you reach the smallest size you allow [eg. 2x2, 1x2, 1x1, etc]). However your picture seems to contradict my understanding (so my understanding is probably incorrect :)).

Also, would I need two quad trees? One for the image and one for a collision map?

Thanks,
John

#15 If there are large "empty" areas, then you do not need to subdivide them or you will begin diminishing your returns. The importance is first finding where things are and then subdividing to find the boundaries of where they are. Then, as things move through the various quadrants, you can an accurate way of determining where they are and whether they have come into contact with something else. You can subdivide the empty spaces, but you will begin to spend more time processing empty space and you will filled space in the setup of a hockey ring above. In your scorched earth clone, depending on the level, the reverse may be true since a goodly amount of the space will be filled rather than empty and therefore have more need of subdivision to track changes.

I don't think I'm making any sense.

One of the keys to tree algorithms is to only branch or subdivide when necessary (ie. when there is more to process). If you subdivide when its not necessary, you eat up any efficiency that the algorithm provides.

I'm still not making sense. I think I need an Excedrin to clear my thoughts.

#16 Imagine that you are the puck. Be the ball. For a hockey game all you really care about is if you are running into something. To figure that out you take a look around you and check for stuff. For simplicity sake, let's say that we are completely contained in one of the Quads. The puck is currently in an empty quad (and unless something breaks, this will always be true). The puck knows its safe until it 'leaves' this quad. As long as it stays where it is nothing will happen to it. The bigger the quad the more unrestricted room the puck has.

That's essentially the strategy. The reason the quads are so big over the empty areas is the way I wrote my divide and conquer function. I only care about the 'solid' space. If a quad is found to be empty, then I need to find its neighbors and check to see if any of them are solid. If I sub-divide the empty space all the way down to the pixel level then I lose the speed the quads give me, I'll come back to this. The goal isn't to go all the way down to the pixel for the sake of going to the pixel level. The goal is represent as much data as possible with as little memory as possible. The larger the quad the less work the will computer do.

When testing the quads I quite often go from one quad to the next looking for a 'solid' node. If a quad represents an area of 128x128, then I only need 1 check to cover the entire surface area of 16384 pixels! If I sub-divide that quad into 1x1s I'll have to test at least 128 quads (or pixels) to cover the same space where I used just 1 test previously. Realistically, if the quad goes all the way down to the pixel level every time then you wouldn't actually need to make the quad tree to represent the map. You would just use pixmap directly instead.

There are a number of cases where binary trees (another spatial algorithm) vs. sorted arrays are pretty much the same thing (such as log 2n searches). This is the same with quad maps vs. pixel maps and the same techniques could be applied to the pixel map as to the quad map. However, you'll still lose the convenience of having a quad represent an area much larger than 1 pixel. Larger quads will be the bread and butter of your performance. A useful tactic when creating quad trees is to limit their depth. For example, If I specify a depth of 3 for my map (currently it is set to 9) the min quad sizes are much larger, but it's also a massive performance increase.

#17 Sorry for all of the questions but this concept is completely new to me...

Would it make sense for me to start my game with one giant quad and then as a projectile is moving each quad it interacts with would be split to ensure to collisions are happening? Doing this would start the game with a tiny quad tree, but as the game is played the quad tree would grow bigger and bigger.

My other idea is to mark each quad tree node as empty, solid, or "unknown". Nodes would start off as "unknown" and then the first time it needs to be checked (eg. a projectile is passing through the quad), it would be checked and assigned a more specific type (eg. empty or solid).

Would you suggest I checked collisions on a per-pixel level against the bitmap of the terrain? Each quad would contain a small bitmap (or so I'm thinking) that is actually copied from the large terrain bitmap. When it needs to be checked for collisions then each pixel of that bitmap would be checked for color (to see if it's empty, etc...)

Thanks again for all of your help!

#18 You could start the game with one giant quad, in fact that may be a great way to start so you can 'see' how the quads are borken down and how they interact with your projectiles and physics. Instead, I reccomend that you start with one quad but you break it down into pieces before the action starts. Otherwise the first projectiles will probably stutter as your code creates the new quads.

Marking your nodes type is a good way to quickly identify what's contained without having to scan the pixel data. If it's empty or completely solid that should save you some update calculations. If it's mixed and has no children then a pixel read could be used. If you consider that a node can only be solid/empty then you'll never have to cast against the pixel data. There's no right or wrong way, it really depends on what you're after and what kind speeds or accuracy you want the game to have.

Instead of copying a bitmap from the background into the quad consider this: The quad's coordinates already correspond to the positions of the bitmap. Let's say for the sake of debugging you draw the bitmap data that corresponds to the leaf nodes of you're quad.

QuadNode DrawBakground(LevelRenderer renderer)
{
if(hasChildren)
{
foreach(QuadNode child in children)
child.DrawBackGround(renderer);
}
else
{
renderer.Draw(QuadNode.Min, QuadNode.Max);
}
}

The QuadNode Min and Max functions define the extents of this quad. The level renderer is a class that I made up with access to the screen device (SpriteBatch, GraphicsDevice, TorqueX, etc...). The quad passes the coordinates to be drawn into the LevelRenderer which contains the original bitmap. More advanced code would probably allow you to ask the LevelRenderer for it's pixel data for the quad extents. This would certainly take less memory than saving a bitmap in each quad.

#19 @Stuart: Can you re-post the picture from the beginning of this thread? I'm re-reading this and noticed that picture is no longer available...

Also, one quick question about quad trees... I'm pretty sure I understand them completely, but just have this one question:

Will the quad tree be subdivided until each quad contains a single "ground type"? (eg. solid, liquid, etc)

This would mean that the edges of my terrain would have LOTS of small quads, right? There would also be lots of small quads where the ground-type changed, right?

Thanks Stuart!!!

#20 No picture! Forgot to reenable access to my web server after I had a power failure, I'll fix that sometime today.

>> Will the quad tree be subdivided until each quad contains a single "ground type"?
>

I believe the easiest implementation would be to subdivide until each quad is just one type of terrain. You could implement mixed quads but then you'd have to implement another layer of collision detection routines on top of the quad tree. I would start with the simlpest approach, gauge that approaches ability to meet my requirements and work from that point.

>> This would mean that the edges of my terrain would have LOTS of small quads,
> right? There would also be lots of small quads where the ground-type changed, right?
>

Yes, usually there is a lot more quads on the edges of the terrains.

-Stu