I believe that Scorched Earth and suchlike games store the landscape as an array of heights. When an explosion happens, te values nearby are changed as required, and posibly temporarily ome "in-the-air" dirt is created, which falls down , and is added to the height values.

More modern games, such as worms et-al probably use a similar method to yours, but may well actually erase/blank parts of a bitmapped/tiled landscape, instead of storing the holes, to make it a one-off calculation, rather than something that has to be continually kept in memory (e.g. if you have a lot of holes, you probbaly have to check many to see if a projectile is travelling through free space, or hitting the landscape, and that could become costly)

One of my bosses regularly uses the scenery as a collision map. Basically you can fall through png transparency, but not solid pixels which support you and push you up and out of the surface. A series of "pixel sniffers" manage this. Which is how she made this game with it's deformable landscape.

Levels were made in a custom, tile based level editor which she made and then when the game loads the XML for a level, it paints all of those tiles into a bitmap.

http://turpspages.freehostia.com/Dest_Terrain2

It looks and works way better than the other one, but there are a few problems:

-The applet is somewhat very laggy (the downloaded version doesnt lag at all)
-There are still a few bugs with the "makeahole"

Click to drop bomb, + - adjusts the size and any other key regenerates the terrain.

Only challenge remaining is "real" one where you remove a shape from a shape...

Yup, that demo is probably more in line with what Xeon is looking for (watch out though, it crashes if you bust through the bottom of the screen, I assume it needs a bounds check in the pixel test).  It really all depends how realistic you want to get - for gameplay purposes, a simple explosion without too much complication is probably quite enough.  You'd need springs and particle/particle (swept circle) collisions if you wanted to do something real serious, but it would be kind of involved.  The complicated algorithm I was envisioning would result in something along the lines of what I did a while ago at http://www.gamefight.org/liquid2/ (source available, though excruciatingly messy), though it would need to be pretty tuned to make something behave like dirt (probably a good bit of sliding friction would need to be added to the collision response to keep things from being "slippery").

Now to veer off topic: st33d, I've noticed several mentions of your using pixel based collision detection with a Verlet simulation.  Have you ever taken this "all the way," as in doing a full rigid body simulation with pixel by pixel detection?  I've always thought of that as sort of the holy grail of simple 2d physics libraries, since most of the libraries out there make you actually define the object in terms of the various pieces of simple geometry.  I was thinking it would be really nice to put together a Processing physics library where you would only need to supply a sprite and a mass and the library would handle the rest.  I've never dug into the pixel by pixel stuff, though, so I'm not sure how tricky it would be to pull off in a fast manner.  The real key would be to automatically set up a collision hierarchy so that you wouldn't have to test every single pixel every frame - I'm thinking that might be somewhat easy to accomplish by pre-caching alpha masks at halved resolutions all the way down to 1x1, but there are some details I haven't worked out.  But I like the pixel approach in that whereas in a normal broadphase collision algorithm you're essentially recreating from scratch a lot of geometrical information that's already been handled in rasterization.  Anyways, have you dealt with any of this stuff before, or do you have any thoughts on it?

>> Yes my demo breaks, but I already uploaded it
>> and my internet connection is useless.

Understood - during college I lived off campus and had nothing but dialup AOL, so I'm no stranger to the crappy connection.  Even just to download a PDF file for a class could take up to an hour, which made things quite difficult...in any case, don't worry about it, proof of concept demos are entirely exempt from any expectation of debugging, in my opinion.

>> Why the hell would you need springs? Why? Why? Why? Why?

True, I never did explain this...you need springs if you want to physically model dirt as opposed to sand.  A pile of sand is very well approximated (for the purposes of game physics, at least) by a whole bunch of spheres undergoing almost completely inelastic collisions (too much jitter if they are elastic).  If you hit a pile of spheres with a big heavy sphere, it will basically just spray everywhere, with no clumping or anything like that, just like real sand does when you kick it.  In contrast, if you play around with some actual dirt, it clumps together, and if you stick an M80 in a pile of it, you'll blow it up and get a lot of reasonably sized chunks flying through the air.  That's why you'd need springs, if you wanted to capture that clumping aspect of a ground explosion.  In reality, though, it's probably easier just to use a bunch of colliding spheres and attach clump-shaped graphics to them, since that will look almost as convincing.

Re: collisions against thin pixel walls.  My latest Verlet project was exclusively points and lines, so I've dealt a lot with "tunneling" issues, though not pixel based.  Since you've already got Bresenham's algorithm running, couldn't you do a rasterization from the last position to the current position and pick out a collision point that way rather than simply testing the current position for penetration distance?  This would require a Bresenham calc each time step rather than at each reported collision, which is slightly more computationally intensive than a single pixel check, but that's the price we pay for avoiding tunneling...anyhow, with today's computers you can do hundreds/thousands of lines with Bresenham without maxing out the processor, so it shouldn't be too much of an issue to do one for each particle (the mere drawing of the particle itself, if you're using circles, will outweigh the cost of the collision check).

Generally speaking a collision detector provides at least two things: 1) a collision point, and 2) a collision normal.  For the collision point, just run Bresenham from last->current and pick out the first occupied pixel.  For the normal things get a bit more complex, because the normal direction is not really specified from a pixel map - more thought would be required there, probably something along the lines of checking the neighborhood of the collision point and massaging that data somehow to come up with a normal direction.  It sounds like you're getting by without using normals anyhow, so you may not need to go there.

BTW, once I finish up the engine for the game I'm working on I'll post the source, where I have a lot of useful (and painfully debugged) code for doing Verlet collision resolution.  You might find some of it useful for your stuff.  At the moment I'm still tinkering, though, so I want to get it right before I put it online.

In any case, am I correct to assume that you've not tried to deal with bodies that have extent in this way? (as in full sprite-on-sprite collision)  At some point I might take a swing at that, P3D and P2D have some nice, fast triangle rasterization routines that could be modded to do overlap queries without too much trouble.  Even swept detection might not be too slow in such a scheme...would be interesting to try, at least.

Hm, I see, so the problem arises when both the beginning and end points are outside the occupied pixel because you have no control over the direction the algorithm goes in, so the algorithm will sometimes actually give you the exit point instead of the entry.  You could probably hack around this by forcing the algorithm to run to completion and return both the first and the last occupied pixel, then outside the algorithm determine which one is the entry pixel, right?

Anyhow, it's a very interesting approach to this problem, I'm very curious to see how it turns out - definitely post a link to the game when it's done!  I'm going to be away for a few days, but when I get back I may start experimenting with this method for rigid bodies, since if it worked for those, it would result in an extremely intuitive and beginner-friendly physics engine.  I'm sure even without rigid bodies built in it speeds level development for you quite considerably, turning any run of the mill paint program into a full featured level editor.  Having just spent three full weeks working on a custom level editor for the stuff I'm working on, I'm starting to wish I'd gone with your type of approach from the beginning!