# Destructible Terrain like worms

I have to develop a game with a dynamic destruction of the map, I searched the internet and even looked at some questions regarding this topic on this Website, but they did not help me much out.

I made the map with tiled and used box2d to make collision between the game objects. As a game engine we have to use Libgdx, but I dont know how to start as I had never develeped a game before, can someone give me any tipps how I could start?

with regards,

• Welcome, @Jizang. Keep in mind that when talking to experienced game developers, they're folks who haven't recently been beginners themselves. We're not the best audience to be able to tell you what tutorials available today are good, because they often weren't written yet when we were picking up those skills. Similarly, Q&A answers linking to tutorials don't age well — URLs change or they get outdated. So if you want the latest tutorials, a web search is a better bet. Can you edit your question to remove the request for tutorial links and instead describe the problem you need help solving? – DMGregory May 21 '18 at 12:18
• For example, can you clarify the type of destructible terrain you want? The Worms games, if I'm not mistaken, used bitmap collisions - where each pixel could be a solid obstacle or empty air. But you mention you're using Box2D, a library that uses geometric collision primitives, and Tiled, a tile-based level editing tool. Neither of these are a clear fit for pixel-granularity destruction. So, are you expecting to delete or modify square tiles of terrain to represent destruction, or do you have a different approach in mind? – DMGregory May 21 '18 at 14:08
• That is exactly what I need the terrain destruction in Worms, I have to ''Erase'' upon contact with a weapon but it still has to be an object. Which one would be better for an amateur trying to destroy the tiled maps or using bitmap? – Jizang May 21 '18 at 14:31
• This is a trade-off you'll need to decide for yourself: whether you can get an acceptable granularity of destruction from tile swaps, whether you're up to doing the work of procedurally chopping tiles into arbitrary polygons to support destruction of any shape, or whether you're willing to switch to a bitmap-based system and do the required physics calculations yourself. When you know what you want to do, we can help you solve the problems to make it work. – DMGregory May 21 '18 at 14:41
• The thing is I currently dont know about both methods much, I will look a few things up and try to learn the basics of both and then decide. Thanks I will be back when I need more help – Jizang May 22 '18 at 8:30

Okay, the naive approach is this: construct your terrain up of rectangles that are 1 pixel by 1 pixel (or, in the case of one of the 3D worms, of cubes). If you have a bullet, or an explosion, or any other source of destruction, then what you want to do is as simple as applying collision detection, and removing all of the rectangles/cubes that collide with the source of damage. The problem is, this is slow.

But, we can still use the idea behind this, if we're clever about it. The trick is: model the terrain as a larger rectangle. Then, when that rectangle collides with a source of damage, segment it into four smaller rectangles. And apply this recursively until you reach a necessary level of precision (i.e. 1 pixel, 2 pixels, 4 pixels, etc.) When you reach that level, remove all of the rectangles that are still in contact with your source of damage.

Here is an example of how it would look:

Note, that for more complex terrain, you could expand this into other polygonal shapes. However, consider also, that with some thought, you can model the shape of your 2D terrain using procedurally generated rectangles. But that would be a bit of a different discussion to have.

• Hi sry for the late answer. Thanks for ur explanation the graphics helped me, but my problem currently is I just dont know where to look at in order to learn. If I have understand you correctly, you want me to mark everything as objects in my tiledmap in tiled and than detect the collision and than set the tiles which collided to null right? – Jizang May 24 '18 at 7:48
• What you're looking for is an algorithm such as a Quadtree (or generally a K-Tree, or other O(log n) algorithms). A really great run down of how these are created was done by The Coding Train – Kira Sep 15 '18 at 11:51

Old Worm games did use the pixel by pixel approach, but this was a bit more understandable in that era. Pixels weren't as dense and per-pixel collision was easy and fast (you could check whether two sprites collided during drawing). Modern Worms actually use something called marching squares or marching cubes. Instead of actual pixels, the map is made out of values between 0 and 1 in a specific density, then the algorithms take this and convert it to a mesh.

• Not true, they didn't simply use a 2D pixel array. See my answer: They used RLE, which was a common approach to such problems at that time. – Engineer Feb 25 '19 at 15:45

You don't need quadtrees for this. If you're not used to recursion, I would suggest an RLE approach like Minecraft uses, because it's simpler to understand: for every vertical column of pixels, store ranges saying where that column starts and ends, in vertical pixel coordinates. Multiple ranges then allow for multiply-fragmented terrain, or what is known in voxel lingo as "overhangs". For example:

0-255

Assuming your space is 256 units high, this means this entire column is solid ground, from end to end. Other columns nearby might not be, such as:

0-115,121-167,170-255

which is a column that's been fragmented. We have a solid volume from the "sea level" 0 to 115, then there is a space of air between 115 and 121, then we have another solid range from 121-167, another air space, then we conclude the solid from 170 to the max height of 255.

Why use only values 0-255? Because that's the range a single 8-bit byte can support, making transfer of such information cheaper (across system bus, across network, etc.). You could also go for unsigned short int, @ 16 bits with range up to 0-16384. Bytes and shorts also make more efficient use of limited CPU cache / line space, meaning you can increase CPU throughput.

Your world consists of these columns, each of which are made up of the ranges described above.

struct World
{
List<RLEColumn> columns; //running left to right
}

struct RLEColumn
{
List<Range> ranges;
}

struct Range
{
byte min; //unsigned
byte max; //unsigned
}


or maybe, if you're willing to limit the amount of vertical fragmentation to make it more efficient:

struct RLEColumn
{
Range[] ranges; //could make this length 4, 8, 16 or what have you
}

• As a side note, RLE will also make things much easier if you plan to do things like falling dirt mechanics, napalm, roller bombs, etc. like you used see in the old scorched-earth games because you are just comparing adjacent columns for slopes and detecting for gaps for falling dirt. – Nosajimiki Feb 25 '19 at 19:54

By following the answer from Chris Qu, I've implemented a Phaser 3 + Typescript helper library for Destructible Terrain. Using Quad-Tree algorithm for creating/erasing terrain, collision detection and rendering.

Originally, I've tried using pixel by pixel approach, but it didn't get far until I found its limitations. Aside from performance, the approach seems to limit the bullet to be a point. (e.g. a line or a block shape bullet will be hard to achieve due to performance reasons).