Hi, I'm currently messing around with the idea of a 2D lemmings/worms style of game and I am wondering how to go about doing the terrain. I want the terrain to be fully deformable, also allowing tunnels to be dug underneath the terrain like you can in Lemmings. I'm not 100% certain about how to use the vertex buffers and index buffers correctly for this but I have a couple of ideas of how I think I might go about it. The terrain would be made up of quads, and the more complex the terrain the more quads would be required. The incredible ascii diagram below might help. Now for the deformation. The first way I was thinking was just constantly unlocking the vertex buffer and changing the number/positions of vertices whenever a deformation happened. I'm guessing this would be slow, and complex to implement? The next way was to have a constant vertex buffer with a fairly high-res grid of vertices. Then whenever a deformation on the terrain happens I would just edit the index buffer to match the new terrain. This would require a fair bit of memory for storing all the vertices though right, but would it be just as slow as editing the vertex buffer on the fly? I'm not sure how I'd go about dealing with polygons which become seperated from the rest of the terrain either. I'm probably missing something here, and I have a feeling that this is going to be hard work. I'd just like to know if I'm on the right lines, or if there are better ways I should go about this (using the polygon approach)? Also, any tutorials or related links would excellent. I'll be doing this in Direct3D. Any help is much appreciated. Thanks.

Google for a project named 2Oreil, or search for it in the gaming universe forums under Liero sequels/clones/remakes. I'll see if I can find a link.

Edit: The site seems to be down. :( It did however have some pretty deformable polygon based terrain. No idea how it was done, but perhaps you can contact the author to find some info or something.

You may want to look into CSG for this kind of operation.

Lemmings 2D, almost the firsts versions, use bitmap based map : when a lemming dig : it remove a piece of pixels ( to transparent color/alpha chanel )

I dont think you need polygon/geometric based operations to do that for a 2d lemming-like game.

For a 3D lemming-like game, if i have got good memory :) , maps in first lemming 3D was like big lego blocks : when a lemming dig something it juste remove a block... but i may be wrong... ( that was long years agos ;) )

You can store an array for the game field containing booleans for "full" or "empty". Whenever a collision/digging happens, set the appropriate array fields to "empty". On the GPU, you store a texture in RGBA format for the game field. This one contains more info than the RAM memory game field, as it must also keep track of which color each pixel has. Clear it to (0,0,0,1) at the beginning of the game (don't clear it each frame!). Every time a collision/digging happens, you render a circle with alpha 0 to this texture, with color mask set to (0,0,0,1). OpenGL allows you to set the color mask in the output by glColorMask(0,0,0,1).

This is non-polygon based, but the original worms wasn't polygon-based either.

Another way is to use a 3d array (voxel grid), and generate polygons from it in realtime. Unfortunately, the most intuitive and simple algorithm of doing this process, happens to be patented.

I've attempted to create a very similar project about 5 years ago. It was supposed to be a 2D Liero (ie. real-time worms) clone, using polygonal terrain. It was called "war worms" but I doubt you can find any info on it now.

After reading your original post, I see you're not very familiar with CSG yet. Definitely look into that, because what you're describing is exactly what CSG is. It's a very huge and complex topic; you wouldn't want to be reinventing the wheel in this case if you want to have a finished game as a result.

There are quite a few libraries that can help you out with this (in 2D), some are really good. I recommend you look into Alan Murta's gpc (general polygon clipping) library and PolyBoolean (use google to find them). From my research, those two are some of the fastest 2D CSG libraries avaliable.

That should give you a lot to think about and experiment. If you want, feel free to contact me and I can tell you about my experience of creating that project, and what went right/wrong.

Thanks for the responses, lots of useful information.

I'm realising I've got a lot of learning to do with this. I'm going to do some reading on CSG and look at the libraries suggested, and see where to go.

Cheers for the offer aswell shurcool, much appreciated. I might take you up on that if I get stuck.