[Jihgfed Pumpkinhead]

I'm looking for a much better collision-detection algorithm; right now I'm just comparing the edges of bitmaps, which is pretty lame any way you slice it. I'm looking around at various algorithms, and am eager for recommendations, or better yet, functioning source I can steal.

Preferably it should be aimed at fairly large bitmaps, say as large as 200x200. I'm using Allegro right now but a bitmap's a bitmap, really, and I can probably deconstruct source using other libraries. C++ is preferable, C is fine, pseudo-code's good, anything else and I won't have any idea what's going on. But anyway I'm curious about both the theoretical and the practical side of this, so any comments are welcome.

Thanks a bundle.

[DrunkenCoder]

I don't have any source to give you but I can give you a the basic
ideas behind a pixel perfect collision system.

Any collision detection system should start with a fast test like the
bounding box test you're currently using because if this fails you won't
waste huge amounts of time doing something complicated.

Secondly basicly what you need todo for pixelperfect detection is
to figoureout where the bitmaps overlap (this can be done in your
first test) then basicly all you have todo is to and togheter the opacity
for the two bitmaps in those regions if any value turns out non zero
you know you've got a collision.
_________________
If there's life after death there is no death, if there's no death we never live. | ENTP

[BigManJones]

Basically, like D.C. said, in 2d you've got two options; 1. bounding rectangle/sphere/whatever and 2. pixel-to-pixel. The best way is to do bounding rectangle before you do pixel to pixel because it can be a bit slow.

Another option is to use a group of smaller bounding rectangles-using you contest entry for example if you have a 200x200 bmp with the character centered in it then instead of testing the bmp sides test a rectangle at x+50,y+100, ht=100, width=100:

[Adam]

In visual basic i reference a dll for the rectangle test

Declare Function IntersectRect Lib "user32" (lpDestRect As RECT, lpSrc1Rect As RECT, lpSrc2Rect As RECT) As Long

thats the VB declaration but you may want to find out the C++ equavilent cause people tell me its faster than doing it yourself.
_________________
https://numbatlogic.com

[Rainer Deyke]

In most rpgs, pixel-perfect collision detection is the wrong approach. This is because two sprites can overlap on the screen without actually overlapping in the game world. Play Ghost of the Haunted Grove to see what I mean: when the player stands directly behind a tree, the tree covers the player.

There are actually a number of different options in 2D. Feyna's Quest uses octagons. It's also possible to use arbitrary polygons or circles or any other 2D geometric shape. Remember that the bounding shape doesn't have to match the actual sprite bitmap exactly. You can have the top of the sprite stick out of the bounding shape top allow partial overlap.

In most rpgs, tile-based collision is the best and easiest approach. Each object occupies one (or more) tile(s). A collision occurs when one object attempts to move into a "wall" tile or a tile that is occupied by another object. This is what essentially all traditional SNES rpgs use.

[Jihgfed Pumpkinhead]

Pixel-perfect just seemed a little like overkill, as I don't really need that level of precision. But as it's a simple algorithm I could probably understand/implement myself, it might bear some looking into.

I'd already looked into the Allegro libs (trust me, I'm not going to do extra work if I don't have to), but all I got was broken links and some code which wouldn't compile.

I don't really see why I'd get better performance from a tile engine than from what I've got now. I'm not anti-tile-engine, or anything, it's just not quite what I want for this particular game.

What I'd actually intended to do to get the proper perspective look, with movement behind trees and such, was to make every image a composite of two images, a bottom and a top. The bottom is "there" and used to check for collisions: the top, so far as the engine is concerned, is just for show.

[Rainer Deyke]

[Bjorn]

[grenideer]

Pixel based collision is very accurate but it's also very slow. It may work in the game you're doing but I think most of us agree that it's overkill.

A few people mentioned using a hierarchial bounding box structure. This is a very common method and probably best for what you need. First check if two bitmaps are overlapping, if so, then check if smaller (could be multiple) more accurate boxes within the original are colliding.

Or you could make each 'object' just have a single collision rect that is checked for. No matter where the bitmap overlaps anything else, only that Rect contained within is a collision.
_________________
Diver Down

[Jihgfed Pumpkinhead]

It's true that pixel-perfect is not optimal for my game, and in a perfect world hierarchical bounding boxes is what I'd be using, if only because it's got a cool name. In a perfect world, though, someone would say to me "Here you go, you pumpkin-headed fool, I've finished your engine for you; now all you have to do is write the dialogue scripts" and I'd say "Gee, thanks, mister." Ah, but such is not life, and thankfully I've learnt to deal with the world's minor imperfections.

Well, the point of that was that for now I'm going to use pixel-perfect, because it's relatively simple. If I find it really lacking, I'll put the time into figuring out something more efficient and complex.

The problem with giving each object a single collision rectangle is that there's no guarantee that I won't have some really funky shapes; but again, I'll try that if pixel-perfect isn't too slow.

Incidentally, how would you recommend I store these bounding boxes, if I'm not extrapolating them from the bitmaps at run-time? Just text files?

Speaking of which, since I'm pretty much satisfied with collision detection right now, how do you all store game data? Personally, provided there's not too too much of it, I'm big on storing content in easily-editable text files, so that if the user finds something too difficult, say, or just wants to screw around, he can go in and change it himself. Don't tell me you've never wanted to change the main character's name to something obscene, because I know you have.
I forked this here //DrunkenCoder


[This is partly a chance to let DrunkenCoder flex his awesome might and split this part of my post off into another thread. I've seen one of the other moderators do in the main forum, at least... it was very impressive.][/url]

[DrunkenCoder]

Firstly I have to say that pixel perfect collision detection isn't *that* slow
if done right and secondly you should *always* use it togheter with some
bounding box scheme anyway.

And well, personally I would hack togheter a custom sprite format you can probably fool allegro to think that something is a bmp/pcx/<your fav format> and still save extra data somewhere in the file (I've done this with other apis) and when you have the bounding box if you really want pixel perfect collision detection (and yeah you do it's really one of those finishing touhces) you just create a collision mask from the bounding box
instead of the whole bitmap.

Oh, and about splitting the post, I *could* do that but I wouldn't end up the way I want :/ oh, well I'll do it anyway.
_________________
If there's life after death there is no death, if there's no death we never live. | ENTP

[DrunkenCoder]

Well, I split it and cross linked them, Im quite sure there's a better way (involving some hardcore topic moving editing and moving back the original but I don't want to use the board as a personal playground so what I did will have to do for now =) If Bjørn don't decide to clean it up proberly
_________________
If there's life after death there is no death, if there's no death we never live. | ENTP

[Jihgfed Pumpkinhead]

Ha! Very well handled, if I may say.

How would I go about doctoring my bitmaps? Just write a program to open them in "append" mode and tuck in the extra data at the end? Perhaps more importantly, how would I go about retrieving it?

I must admit, though, I still don't see the benefit of storing this extra information in this manner. Using two separate bitmaps seems easiest to me: if storing a bounding-box, I'd have to either a) create a "bounding-box editor" of some sort or b) have all sprites' bounding boxes be the same proportional size, regardless of the dimension of the thing its trying to represent. At least, that's as far as I see into it: I could not be seeing very far.

[Bjorn]

Regardless of whether you like to use it or not, the objects in Allegro datafiles can hold an arbitrary number of properties that can be configured in the grabber tool. So there's no need for any hackery. The property names have a maximum length of 4 characters though.

Oh and, the topic split is fine, I don't see any need for cleanup. :-)

[DrunkenCoder]

Well, having a bounding box editor is the simplest and where to store the data quite depends on both the reader and what format you have your graphics in. Since allegro usually don't use the alpha channel you could even use that to store aribitary data, or paint the collision mask there having special values for the extents of your bounding box.

Or use datafiles, I like to not commit resource handling to my graphics
api but that's just a matter of taste I guess.
_________________
If there's life after death there is no death, if there's no death we never live. | ENTP