TO LOAD THIS CART in immediate mode type:
load #ccm |
I have need of this function for a different game I'm working on - so you get a chance to enjoy and make use of it for your own projects.
Today most games in Pico-8 use what is called a HIT BOX to determine if there is a collision between two objects. And while it works fairly well it is not entirely accurate.
For instance, you could have a comparison between two completely different sprites and the hit box area would either be too big where a collision occurs even if they are not touching, or the hit box could be too small where you must run right up against the target and even though you are touching it, it does not register.
While this is good enough for most games, let's take a rare example of a game called VENTURE.
Venture was a challenging and interesting game in that the very pixels made it difficult to complete a level.
You would navigate WINKY your player around opponents and when you shot them while they did die, they also disappeared slowly one pixel at a time.
If the player were to touch any side of a live sprite or even a single dot of the dead one, comparing by pixels, that would defeat the player and they would have to start the level over.
And if you got yourself trapped in a narrow corridor waiting for an enemy's pixels to vanish enough so you could get around, this unstoppable skull comes after you - so it was the player's mission to grab the treasures from each room and leave as quickly as possible, trying not to shoot the opponents especially if they were blocking a door or exit.
Please enjoy this fairly complex function I wrote to do true pixel collisions.
To my knowledge no such routine exists for Pico-8 nor has anyone written one so it is indeed useful for pixel-accurate sprite collisions.
Two sprites are compared in the quickest way possible by determining both size and shape, including for instance a check between 15x4 and 20x18 if you so desire. Every pixel is checked and it does it the quickest way possible as well by determining which sprite is the smallest and largest.
The function itself uses several arguments:
-- sh1=spritesheet source x -- sv1=spritesheet source y -- sx1=spritesheet size x -- sy1=spritesheet size y -- ph1=screen position x -- pv1=screen position y -- sh2=spritesheet source x -- sv2=spritesheet source y -- sx2=spritesheet size x -- sy2=spritesheet size y -- ph2=screen position x -- pv2=screen position y |
In this demo code above, try going to the sprite sheet and changing the shapes of the sprites to see the collisions truly are being checked per pixel.
HOPE THIS HELPS !
This is far from ‘the quickest way possible’!
Look into how it was done in the 8/16 bits area with bitmasks.
Well by quickest I mean it determines the minimal area to scan, @freds72. You have a link to working 8/16 bitmask cart for speed comparison ? I'm always eager to learn new things. :)
« 8/16 area » refers to the Commodore/Atari days!
I am poking (!) at a prototype - should be able to test collision by group of 31 pixels...
Best wishes on it then. Would like to see that. Was already suitably impressed by your Sphere Stars.
This is what I was referring to, e.g. use bit operations to perform fast detection of collision.
Still work-in-progress (need a cleaner API to be released), but the gist is:
- create a bitmask (32bits) for each sprite row
- detect sprite collision as usual (aabox)
- detect overlaping region
- shift rightmost sprite bitmask using distance to leftmost sprite
- scan both bitmasks (virtually tests [/b]32 pixels[/b] with a single op)
- declare hit if any bitmask banding returns != 0
Known limit: works only for sprite up to 32 pixel wide (extension to more left to the reader :)
Okay, here's where it gets tricky, @freds72.
Your program which checks 2-colliding objects had a speed of according to inserting this line:
print(flr(stat(1)*100),64,0,8) |
right at the end of your _Draw() statement reveals a maximum of 16% CPU being used.
My program using the same exact PRINT statement checks 14-colliding objects at a time revealing a maximum of 21% CPU being used.
for i=0,6 do for j=0,1 do |
I modified my code also to see how well it handled one on one collisions as your code currently does and my CPU came out at maximum 3% - and that's even without changing the number of plotted and animated items despite not checking collisions for them.
I need you please to either increase your code efficiency at or less than 3% and/or beat my 21% by checking at least 14-different ways to collide sprites in your code of no smaller than 16x16 pixels per object checked.
Code available for either engine with CPU shown if you like so you can view the comparison yourself.
Color or B&W for your sprites are fine too. Currently my code treats only color 0 (zero) as transparent and any other color solid and valid for collision testing.
Hu... my checkboard drawing is taking most of the cpu.
If you take away that part, a single sprite-2-sprite (16x16) check is around 1.3% cpu (including cls + sprite display).
12 checks (without display) is 1.3 (not overlapping) to 3% (worst case)
Let's do this for verification, @freds72. Take a hold of my code if you will, REM out my collision routine, add your own.
Should be able to do that with one copy and paste. Or ... Modify my input parameters to match your own.
See if you can beat the 21% CPU mine uses. And please post it so can see the rockets and stars and collisions around them.
Note sure it was really necessary but ok - the key benefit of the bitmask is that check complexity is only dependent of the overlapping height. My version clocks at 2%, yours at 20%.
That said, looking at your collide function, it doesn't produce the smallest box possible.
In my previous sample, the red box shows the smallest area to test for - you can try to reuse that part. Given that collision is usually performed on small slices, both methods should end up a lot more closer (still, the iteration part is going to more costly than a band+shr call).
Note: I refactored a bit the player/stars tables to more easily switch between the 2 algorithms.
By smallest box I mean which of the two is the smaller sprite.
Oh I see what you're doing, @freds72. That's rather clever.
You're creating no box at all but a table of intersect points to begin with and then using those can cut down on the "search" for collision process considerably.
I see what you're doing but I certainly don't understand the code enough to really know what's going on.
Question, can this collision code of your as it is currently written check for a collision between two differently sized sprites, say 25x18 and 19x22 ?
The collide_aabox() function will handle any size - only the bitmask covers a max width of 32 pixels (but could be extended quite easily to arbitrary size)
Then well done. Let's hope in future Pico-8 @zep incorporates a by-pixel collision check routine and refers to this thread and others like it to do so.
Zep has already said he isn't going to implement any sort of built in collision, so i doubt it @dw817.
Well that's a shame, @ReeceGames. This =IS= a game programming language and I'm pretty sure other engines out there have that ability already.
Hmm ... I'm satisfied with the work that's been done though and - if someone needs a collision function can be found here.
@freds72 Thank you for that solution! I was vaguely aware that old games used bitmasks like this, but I'm unexperienced with bitwise operations and wasn't sure how to implement it.
I think I understand how your make_bitmask() function works, but the only thing I'm not clear on is the mask hex value of 0x1000.0000. My programming calculator shows me that in binary, this is 1 0000 0000 0000, so shouldn't the function accept a max sw arg of 12 pixels wide? How does it shift that 1 into place for the 20 0s that would be beyond that?
iirc there is a bug in that version - it should indeed be 0x8000 - can post a fix later
@freds72 No worries! I found the rest of the answer is that numbers are stored as 16.16 floating point under the hood and with it being 0x8000 I fully get it now. Thanks so much, I learned a ton from this example! 😃
[Please log in to post a comment]
