#30057 - wiz - Sun Nov 28, 2004 1:35 am
This is probably the 100th post on collision questions?
I have ideas on how this is done, and actually made games in the past with detection using pixels.
For the most recent pixel / map detection method on the pc I used a 2d array which put all the pixels from the background layer where the player sprite was stood, then applied an outline to the array which set 0's of the outline border of the sprite. A bit like a cookie cutter effect.
Anything that was not a 0 left in the array was a collision, not the best method but it worked, flawless too.
Now I tried something like this for the GBA except (obviously) it ran too slow and even at that I couldnt really get it working.
What really winds me up is the 2 pixel per 16bits, it drives me mad! :(
I can think of methods using a binary mask (?) checking bits with pixels but my code turns very ugly/confusing/useless within seconds because of this accessing 16bits at a time business. Surely it cant be that hard to do pixel perfect collisions on the gba? =/
tile collisions wont cut it either, I already have that working as a tempoary measure..
Anyone have some advice on the subject?
Thanks kindly
#30063 - sajiimori - Sun Nov 28, 2004 1:59 am
Code doesn't become ugly because of the kind of work being done. It becomes ugly due to bad factoring. Make sure you're writing short functions that do one thing well, rather than long ones that try to do everything.
I tend to write lots of small utility functions that have no side effects and only compute values based on their arguments. It makes things easier to understand, because you don't have to hold many things in your head at once.
#30117 - Lupin - Sun Nov 28, 2004 3:01 pm
sajiimori i think this topic is about collision detection, not coding style :P
Well, i would not use pixel perfect collision detection on a GBA because it is just too slow, you have to abstract the object that you want to colide with...
_________________
Team Pokeme
My blog and PM ASM tutorials
#30134 - sajiimori - Sun Nov 28, 2004 7:27 pm
If he is only avoiding fast techniques because they make his code ugly, then it is about coding style because the answer he seeks is to write better code.
Be careful claiming that the GBA is too slow for pixel-perfect collision. Star Control II used it on 16MHz 80386 PCs.
#30244 - wiz - Mon Nov 29, 2004 8:16 pm
Hi guys,
I didnt mean to claim the GBA is slow for pixel perfect collisions, I was just commenting on the same technique I had used on the PC would be too slow to convert.
sajiimori thanks for the tips, I dont try to avoid fast techniques but its true I do need to write better code. I was wondering if using functions (small utilities) would slow things down (if called heaps of times during a frame loop)? Or do function calls not cost anything at all?
Lupin, cheers for writing - tile collisions are very easy to handle and usually the way to go but for a game like, lets say, pinball you would want non-square collision detection for the corners etc.
Is bitmask the way to go with pixel perfect collisions?
Thanks for your time :)
#30257 - R0d Longfella - Mon Nov 29, 2004 10:15 pm
Perhaps it's dumb to mention this, but
You could test for collisions using a bounding box, and then if you find a collision you could test if the objects actually collide using the pixel perfect approach. This way you would save cycles by only using the expensive pixel perfect detection when two objects are in eachothers vicinity.
Goodluck!
#30258 - R0d Longfella - Mon Nov 29, 2004 10:25 pm
By the way, pixel perfect detection shouldn't be so expensive.
Using some optimization you only need (worst case) to use 32 checks for detecting a collision between 2 sprites which are 32 by 32 pixels.
Assuming that both sprites almost completely overlap, you'll need to check each row (32 times) and you can check every 32 pixels on each row by comparing two unsigned 32 bit masks (int). You'll need to create the masks using shifts and AND's, but that wouldn't take too much to calculate. And if you precisely wanted to know where both sprites collided, you could calculate the precise coordinates when two rows match.
Provided that each sprite comes with a bitmask for collision detection, it shouldn't be too hard.
Again, goodluck!
#30263 - keldon - Mon Nov 29, 2004 10:51 pm
I'm not sure how you do it but here's a basic algorithm that outlines the a process I would use for perfect pixel collision.
| Code: |
struct Rect {
int x;
int y;
int width;
int height;
}
boolean collides ( map1, x1, x2, map2, x2, y2 ) {
Rect overlap;
int jointCollisionMap[maxMapSize];
bool overLapped = getOverlapRegion ( x1, y1, x2, y2, &overlap );
if ( !overLapped ) return false;
copy map1 to jointCollisionMap with overlap region
copy map2 to jointCollisionMap with overlap region returning true where there's a collision
otherwise return false;
}
// returns whether regions overlap, and copied data into &overLap
void boolean getOverlapRegion ( int x1, int y1, int x2, int y2, Rect *overlap ) {
if ( x1 > x2 ) {
return getOverLaplegion ( x2, y2, x1, y1, &overlap );
}
Assert ( x1 <= x2 );
if ( x1 < x2 - spriteWidth ) return false;
overlap.x = x2;
overlap.width = (x1+spriteWidth) - x2;
if ( overLap.width <= 0 ) return false;
if ( y1 < y2 ) {
overlap.y = y2;
overlap.width = (y1+spriteHeight) - y2;
else {
overlap.y = y1;
overlap.width = (y2+spriteHeight) - y1;
}
if ( overlap.width <= 0 ) return false;
return true;
}
|
This of course doesn't work if the two objects are going past each other too fast to catch them overlapping within one frame; but that's only important to worry about if that can happen.
#30277 - sajiimori - Tue Nov 30, 2004 1:03 am
| Quote: |
| I was wondering if using functions (small utilities) would slow things down (if called heaps of times during a frame loop)? Or do function calls not cost anything at all? |
If your utilities are in the same file (or a header), the compiler will inline them when appropriate. Use the -O3 option on GCC to enable this behavior.
Non-inlinable (e.g. extern) function calls are costly in inner loops, so if you're having speed problems, check the compiler's output to make sure it's inlining everything it should.
#30305 - tepples - Tue Nov 30, 2004 5:39 am
| wiz wrote: |
| tile collisions are very easy to handle and usually the way to go but for a game like, lets say, pinball you would want non-square collision detection for the corners etc. |
For pinball, you'd want exact-geometry collision: circles with line segments.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#30311 - Marill - Tue Nov 30, 2004 6:14 am
I wouldn't want to tie my collision data with my graphics data anyways, and abstract shaped (spheres, boxes, line) collision may be good enough for most uses.
I would see 2D pixel perfect collision solution something like a brute-force volume collision (testing every unit point in the volume) in 3D, which is pretty much overkill in most applications of it... if the you can do abstract shaped collisions in the game then go with it, unless the game really needs pixel perfect tests, or you're just coding one for the heck of it without any game in mind, then well, go for it :)
#30322 - keldon - Tue Nov 30, 2004 8:21 am
| tepples wrote: |
| wiz wrote: | | tile collisions are very easy to handle and usually the way to go but for a game like, lets say, pinball you would want non-square collision detection for the corners etc. |
For pinball, you'd want exact-geometry collision: circles with line segments. |
=D I didn't know it was a pinball game. To be honest I hadn't completely read the post, it was formatted too badly so I skimmed it poorly.
Yeah, well if it's a geometric shape it's easier. You just calculate when the two paths will cross using line gradients. Because it's a circle you'll have to include a bit of sin/cos for alterations to the path's collision. This is based on the angle of the ball against the surface it is colliding with.
Also when you're doing it, instead of checking with every line filter out all lines clearly behind its path.
A little more on how you do collision detection from the ground up here.
http://forum.gbadev.org/viewtopic.php?p=30221#30221
It's really simple when you think of 1d collision where two trains collide.