We've all played the game 'Worms' or 'Worms: Armageddon' at one point. How is the collision detection done in that? With all the curves and even custom maps, how do they check and handle collision detection?

using pixels! this is the ultimate classic effect!.. and it's very easy to acheve.

to make it simple: you have a bitmap representing the map or playfield or whatever you want to call it.. then you just check the Yposition+1 of the player using if(getpixel(map, x, y) != (255,0,255)) to check for ground collision, for the x in worms they just checked if the wall the worm was walking against was low enough for the worm to clim (4 pixels or something) and stopped it there, they didn't alter the speed by checking if the worm was walking up or down hills but you can if you want. the best thing about using this approach is that you can easily edit the map during play with for example explosions and such!

Like i said, in worms(2) the collision detection was VERY simple. but if you want to make it more advanced nothing is stopping you except some work you have to overcome .

Probably split the map into smallish squares, 64x64 or so, and every time an object moves check its pixel mask against the current square. Since there aren't a ton of moving objects in the game at any one point this should work fairly well and scales to arbitrary map sizes.

I don't recommend checking with pmasks.. using one or two points for the collision detection is much easier and works much smoother. i remember someone posting an example of some advanced pmask routines, really cool except it wasn't! it was just unnecessary and flawed.

Trust me.. use one point for ground detection, one for over head, and use those two together against walls. pmasking isn't worth it.. try animating something and use pmask..

Sorry, but what's pmasking?

I'm not 100% sure, but i think it is when you have two bitmaps and check if the pixels which aren't transparent overlaps. If you think about it.. it sucks.
But I'm not that experienced, it would be great if some of the big guys would name ONE use of pmasking that one point checking can't do a million times better. except pmask..

Have you ever used pmask? It doesn't sound like you have. If you aren't doing that much checking then testing a 16x16 sprite vs a 64x64 square isn't that bad at all. pmask is pretty fast.

yeah, but lets say your animating a character which runs up a hill.. and how would we even use pmask to make this whole process smooth and painless? i can't name one good sidescroller which uses pmasking.. in fact i can't even name a game that uses pmasking.. except from some i made with games factory (ashamed) when i was little.

Sure, i would gladly think that it sucks because it think it sucks because my memory tells me it sucks... but no matter how i think about practical use of pmasking i can't make good use of it

(sorry for making this thread into a little discussion) If you need any help regarding the collision detection just post it here and i'll try to help, if that's what you want of course..

Sweet thanks for help..

Worms/worms armageddon consists of more than just hills... there are arbitrary sets of pixels floating about the map. How are you going to deal with that?

you don't.. the checking around the point is enough to stop the worm if it's hitting those little pixels. using the same checking routines as you do for the walls.. ok.. i call it one point but you check points around it, so it's kinda like pmask except the sprite doesn't effect the game and a million of unnecessary pixels isn't checked which you would have to deal with in some horrible ways too.

I suggest you try my game Lander and tell me that your idea is better. The pixel checking worked at an excellent speed on the 486 I originally wrote the game on.

I'm not sure if I'm just misunderstanding you. Is your entire argument that checking the pixels for overlaps is okay so long as you don't check the entire map at once? If this is so, then we are in agreement. You only need to check the pixels in the vicinity of the sprite you are checking for collisions with.

I only played the windows version (which seemed to be different) and all i have to say is: ok, good example of a game that has uses for pmask, but for a platformer like worms or castlevania or super mario, i don't think pmask is the right decision. i mean.. sure, pmask has it's uses.. but seriusly.. animation + pmask.. i just can't get those two together.

btw, i could not control the spacecraft , and here's a screenshot:
http://www.allegro.cc/files/attachment/593302

Yikes. I have no idea what's wrong with that. I must have put an older binary online by mistake. I'd check it but I'm not in Windows right now.

IIRC, worms doesn't really do a bitmap <-> bitmap check, but rather just a pixel <-> pixel check. The projectiles just check the pixels they go through, and the characters to the same thing with a pixel at the center of their baseline.
There's no need to subdivide the screen, really, since all you do is a single getpixel() on each check.

pmasking won't really work, since you'd basically have to recalculate the masks each time the terrain changes. OTOH, the terrain only changes once per move, and never while any movement occurs, so it might still be a good idea.

For those who don't know how pmasking works:
When checking for a collision between two sprites, you'd normally check each pixel from bitmap 1 against the corresponding pixel of bitmap 2. For a 16x16 overlap region, that's 256 checks, each involving a getpixel() and two comparisons - far from optimal.
So what you do is for each sprite, you calculate a "pmask" - two arrays of rectangles, each exactly 1 pixel wide cq. high. Once you have these, you can do a per-scanline / per-column bounding-box check on the two bitmaps. The effort is just 2 comparisons per scanline plus 2 per column. A 16x16 overlap area then requires only 64 comparisons. For larger overlaps, the difference is even more dramatic, since the brute-force approach is O(n²), while pmask is O(n).
The downside is that pmask is inaccurate for some concave shapes (which is why for a worms game, you'd want to split your area into smaller bits to minimize concaveness), and that it has some memory overhead. Also, generating the masks is O(n²), so if your sprites change on every frame, it's more costly than brute-force.

It was more complicated than you think in some ways, at least in Worms 2 onwards. Check out the way the Ninja Rope bends around the landscape.

If I think about it then: it registers an overlap exactly when the player sees an overlap.

I don't think I qualify as a big guy, but how about bullets in a shoot'em'up? Or just about anything on a high resolution screen? There's no way a pixel sized spot is going to cover much of a sprite.

I think that might be more because most games don't declare the nature of their collision detection routines.

If it helps the argument at all, all the console systems that follow the Texas Instruments TMS9918 line have the functional equivalent of pmask collision detection in hardware — every pixel overlap between sprites flags up as a collision. That means that you've almost certainly played side-scrollers with something the same as pmasking if you've ever played one on a Colecovision, Master System or Mega Drive. The Lynx also has equivalent functionality though it costs 8 kb of the total 64 kb RAM so may not be used so pervasively.

Based on the hardware, I think most 8bit platform games (i.e. the ones with an obviously grid based map) use a simple grid fitting collision detection for player/map collisions and a proper pixel check for player/shot/enemy collision detection.

I'd go for a check of the bounding box of moving things (worms, mines, projectiles) vs the pixel mask of the landscape.

I was thinking more about the worms but ok . although i don't think it would be too hard to create the rope effect.

And that's exactly why i think it's bad :/.

Ok, for non animating sprites pmask can be very effective, although i think pmasking the projectiles in shoot'em'up is more of a design decision that anything else, i like the way the projectile overlaps the enemy by one pixel before it collides. and aren't big enough to make point based collision detection irritating. and if you're using higher resolution you probably don't go with pixel collision detection anyway.

Hmm, that may be, but shouldn't pmasking be easy to spot? it's quite different to using one point or a box for collision detection.

Yes and no. Sure pmask is a lot more precise than a simple bounding box or bounding sphere, but there are other pixel-perfect (or near pixel perfect) algorithms:
- the brute-force method being one (though probably never used in anything commercial)
- brute-force on a low-res version of the sprite (e.g. an 8x8 collision box for a 32x32 sprite)
- polygonal vector-based: trace the outline, represent it as a polygon, and do vector-based collision detection on that
- multi-box, multi-sphere, and other related techniques: represent your object as a set of collision shapes which together resemble the outline of your sprite
Each of these, if done well, can look very convincing and be hard to distinguish from pmask. Also, pmask can be modified to look different: you can build the collision mask on a modified version of the sprite, giving you the extra pixel for example.

So how do they calculate the angle/surface normal of the surface in Worms? Like when 'nades and worms bounce off realistically..

I don't know exactly how they did it, but they probably checked for collision and if it's colliding they check the surrounding area and determine the(i don't know what it's called so we will just call it reflection plane..)

example:
XOOOOOOO
XXOOOOOO
XXXOOOOO
XXXXPOOO
XXXXXOOO
XXXXXXOO
XXXXXXXO
XXXXXXXX

P is the projectile, check the pixel that it's traveling to, if speed > 0 check posX+1 for example(i will call this Xpositive), in this case it going right down at that 45degree hill(we call it 45degree hill.. from where to count the angles ins't th eproblem right now), lets say the speed is Xnegative and Ypositive (in allegro Ypositive is not up it's down.. this gets really confusing when you switch to openGL) the reflection plane could be calculated like this(this is after we have confirmed a collision): since the collision point is Xnegative and Ypositive we should now check Xnegative (by itself) and Ypositive(by itself) and in this case we se that they are solid, this means that the original reflection plane stays as it is(45degrees), then check Xpositive and Ynegative, they're not solid, so it's still 45degrees.. then check Xpostitive&Ypostive vs Xnegative&Ynegative and they're also non-solid.. so where still at 45degrees.. (what i crappy example.. since i don't get to the point of what happens when two corresponding pixels are different..) I hoped you could figure that out yourself but since you asked you probably don't..
Anyway, we have a reflection plane, since we calculated the whole thing by starting with the incoming angle we won't have to take that into account..

and then just reflect the angle and slow down the grenade or whatever.

If you're still interested after this shitty and last post of help I'm going to give for the rest of the year(or so i say) i could make an example game for you.(maybe)

What?

yeah, figured that much..

So does anybody have a good explanation of angle/surface normal detection in 'Womrs'?

The simple version: look a few pixels to the left, look a few pixels (or just one pixel) to the right. Determine the height of the local area for the given x value. Use the pre-algebra slope formula . Now we know the slope of the ground. We can go anywhere from here.

I feel like I plug my (poopy) games too often. In my game Zonic the Hog, I do something similar to this to determine the slope of the ground, so that I can draw the pig at an angle so he looks like he is actually running along the ground.

My game Storm uses bitmask blocks to save memory and increase speed (some of the levels are pretty big as well). All collision detection and collision bouncing are done via these bitmasks. It works well..

The PMASK library uses 1-bit bitmasks. That is, each pixel is represented by a single bit, and 32 of them are packed into a single dword. Sideways movements can be achieved by shifting the dword left or right (or precalculating a mask for each of the 32 positions within a dword). Collisions of up to 32 pixels at once are checked by a single bitwise AND. If the result is nonzero, then the masks are colliding. This is much faster than checking each pixel individually with getpixel, but the speed-increase is linear at best. Pixel-masks for 32-bit RGBA bitmaps can take up to 1/32 of the memory of the equivalent bitmap.

Animation can be done by creating a pmask for each animation-frame of the sprite, but for dynamically generated content, the bitmasks will have to be updated as well.

One advantage that bitmasks have is that you can have precice control over what parts of the object are collidable. For example, you may want to give the player the benefit of the doubt and shave one pixel off the player's mask so that if a bullet comes close enough, they won't end up thinking it's unfair that they die because they scraped the edge of the bullett. Likewise, enemies' bitmasks can be grown by a pixel.

One way of optimising bitmasks is to map more than 1 bitmap-pixel to a bitmask pixel. For example, a 32x32 sprite could be represented by a 16x16 bitmask with each bit representing a 2x2 square of pixels. This reduces the time to check an individual sprite. Of course, don't forget to do higher-level optimisations to see if the collisions need checking in the first place (eg. dividing the world into a grid, quadtrees, etc.).

As for rope physics with bitmasks, if a surface is convex, the rope wraps round it. If it is concave, the rope will be stretched accross the start and end of the concave sections.

AE.

There's no evidence to be certain of how they do it. We can't actually rule out that a vector/CSG representation of the level is kept internally. It would be perfectly easy for the level randomiser to design it from vectors, and every subsequent modification can be expressed in vectors.

That's not really "rope physics with bitmasks", that's "rope physics" (kinematics really, but whatever). The problem is deciding what counts as a surface and then deciding whether it is convex or not.

The physics doesn't have to be exact in Worms (the original at least), so I think it's likely they used the bitmap (or bitmask data) directly for finding bounce vectors.

Oh, definitely not in the original — which is possibly why it was able to be so widely ported. It has many obvious collision detection flaws including the ninja rope just passing in front of all scenery and the worms themselves quite clearly having collisions based on a single pixel. But they seriously upped the physics game for Worms 2 and versions with the original gameplay complete weren't available for anything less sophisticated than a Playstation.

So how do you find bounce vectors using the bitmap (sprite)?