|
|
|
This thread is locked; no one can reply to it.
|
| Bitmap on bitmap collision algorithms. |
|
Jorhlok
Member #12,490
January 2011
|
First off, are there any bits of libraries that do this for me that are allegro addon thingies? Anyways, here's what I'm thinking: //I load my PNG images at the beginning. //I prerender masks of the sprites that will have collisions. //create a bitmap surface for the mask in its own variable and whatever. //go through each pixel and load magic pink as is, anything else as a color //the colors will be the "teams" //a limitation, teammates can't detect collision, note that the game I'm writing this for will have 2 teams //keep track of how many pixels are colored //collision detection //first a quick bounding box check //make a bitmap that can contain all of the bitmaps //blit the first one on //blit the second one on //count the pixels of the color of the first one //if it is less than the mask had, then there is collision (the second one's color covered it up)
|
|
OnlineCop
Member #7,919
October 2006
 |
This is called pixel-perfect collision. First, test for "gross" collisions, where two objects are close enough that they even have a chance of colliding. If there's no chance they collide, do no more collision tests. Otherwise, test to see if the boxes themselves overlap. If the boxes don't overlap, no need to test each pixel. Then, test for pixel-perfect collisions. This has been asked before, and you can find some good resources on this, but you'll probably want to write this yourself.
|
|
Jorhlok
Member #12,490
January 2011
|
Also, I've forgotten my question. How does one access the bitmap pixel data? |
|
gnolam
Member #2,030
March 2002
 |
The fast way to go about the actual pixel-perfect test is to create bitmasks from your source sprites, where 1 represents a solid pixel and 0 a transparent pixel. You can then (after offsetting) use bitwise AND between two masks to check for collision: if any result is non-zero, there is a collision. -- |
|
Matthew Leverton
Supreme Loser
January 1999
 |
Jorhlok said: Also, I've forgotten my question. How does one access the bitmap pixel data? Use al_lock_bitmap() to lock the bitmap with a specified ALLEGRO_PIXEL_FORMAT. Then you can use the data parameter in the returned ALLEGRO_LOCKED_REGION struct. |
|
Jorhlok
Member #12,490
January 2011
|
I'll have to look into bitwise things. I've never had any use or understanding for them before. EDIT: okay, here's what I've gathered. Read the colors into a monochrome thing of bits for howover many bytes (char is eight bits, right?). Then "blit" each mask onto a blank space for each of them representing where they are. Then do a bitwise & with high level integers will yield a low level zero if there are no collisions. EDIT: Also, I'm using allegro 4.4 that I compiled. |
|
Tobias Dammers
Member #2,604
August 2002
 |
Just to avoid disappointment: Pixel-perfect collision detection done this way is horribly inefficient (O(n2) if that rings any bells), and it doesn't look / feel as good as you think. Most 2D games do NOT use it; instead, they represent the sprites as geometric shapes of some kind (rectangles, circles, polygons, or combinations of these) and perform collision detection on those, using the actual bitmaps for display only. If you look closely at, for example, classic Mario titles, you'll see that the Mario sprite often overlaps a bit with solid tiles, creating a more natural look & feel. If you insist on doing pixel-perfect, the best approach is to create a collision mask: Split your sprite into rows with a height of 1 pixel, find the first and last pixel on that row. Store these for every row of your sprite. Then do the same for columns. To check two such masks against each other, you need to first figure out which rows line up, and what their horizontal offset is. Using the min and max values from each, you can now check if the rows overlap. Do the same for the columns. If at least one pair of rows and one pair of columns overlap, you have a collision. This doesn't handle all shapes, but should be OK for most things you ever encounter in a 2D game, and it is far more efficient (O(n)), especially for larger sprites. It's still more wasteful than bounding boxes or bounding spheres (which are O(1)), so you should still do these to filter out the obvious non-collisions. It may also be a good idea to use a different sprite for the collision mask than the one you're actually displaying, so you can create the overlap effect I mentioned above. --- |
|
Jorhlok
Member #12,490
January 2011
|
http://wiki.allegro.cc/index.php?title=Collision_detection So on this, the Separating Axis Theorum? |
|
gnolam
Member #2,030
March 2002
|
SAT is for polygonal geometry, not for raster graphics. You could use it for the rough tests, but you would gain nothing. -- |
|
Jorhlok
Member #12,490
January 2011
|
Yes, but in general, I could pretty well approximate most sprites that need collisions with triangles and such. Thus making SAT a more viable and quick alternative to pixel perfect collisions. EDIT: I'm confused about this: http://www.allegro.cc/forums/thread/596552/752612 Is VECTOR defined somewhere? Is it just x and y? EDIT: Is this half C and half pseudocode? Anyways, I'm working on trying to define everything and then subsequently test it. EDIT: VECTOR *USCALE_VECTOR(VECTOR vec, double dbl); I think that's the prototype of a fuction that's missing. No idea what it's supposed to be. EDIT: I found other code here: http://gpwiki.org/index.php/VB:Tutorials:Building_A_Physics_Engine:Basic_Intersection_Detection This is a bit less explanatory, but has the complete code (Even if it is VB, it had a little C version, too). At any rate, I'm glad I've taken a look at that post. EDIT: I stuck the code in and made a couple polygon masks of two of my objects. I have confirmed they work. Thank you for all of your assistance in the way of dollision cetection. |
|
|
