Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Newcomers AppGameKit Corner / A fast Sprite Per Pixel Collision Function will be with you soon

Author
Message
damothegreat
2
Years of Service
User Offline
Joined: 18th Sep 2016
Location:
Posted: 3rd Apr 2017 21:52
Watch this space

Thanks
Damian
easter bunny
6
Years of Service
User Offline
Joined: 20th Nov 2012
Playing: Dota 2
Posted: 3rd Apr 2017 23:53
This will be awesome. Been wanting pixel perfect collision for agess

My Games - Latest WIP - My Website: Immortal.Digital - FB - Twitter
130,000 installs with AppGameKit and counting
damothegreat
2
Years of Service
User Offline
Joined: 18th Sep 2016
Location:
Posted: 4th Apr 2017 00:07
Your welcome,

It will helps lots of us for better percision
damothegreat
2
Years of Service
User Offline
Joined: 18th Sep 2016
Location:
Posted: 4th Apr 2017 00:17 Edited at: 4th Apr 2017 00:22
The algorithm is simply



This is work in progress and will be with us shortly, but this is the idea
blink0k
AGK Developer
Gold Codemaster
6
Years of Service
User Offline
Joined: 22nd Feb 2013
Location: the land of oz
Posted: 4th Apr 2017 02:02 Edited at: 4th Apr 2017 05:46
Just a suggestion but if you split the process in two where;

a) You can tag a sprite for pixel collision say SetPixelCollision(img)
This would encode the image into a matrix of bits (a 2D array of integers) 0=transparent 1=Non-transparent (So at 32bits you could encode a 256x256 sprite in an 8x8 array (Not much overhead at all)

b) Then when you check for collision you can;
1) Shift the bits in one of the arrays to accommodate the horizontal offset
2) ANDing the rows based on the vertical offset
3) When you get a 1 exit the loop

This should minimize your loop (Maximum 64 iterations for 256x256 sprites) and allow you to compare 32 pixels in one instruction

BatVink
Moderator
16
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 4th Apr 2017 08:29
I would look at BlnkOKs suggestion of storing data about the pixels and using this to check the collision.
But the one thing that you have to be wary of is rotated sprites, which change the rules.
Maybe have superfast collision for non-rotated sprites, and slower collision for rotated sprites.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Quidquid latine dictum sit, altum sonatur
TutCity is being rebuilt
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 4th Apr 2017 12:14 Edited at: 4th Apr 2017 16:26
If you have the transparency data stored, could you just multiply that by a transform matrix which contains rotation and scale data?

Elaborating on what Blink suggested, I typed this up. I'm not 100% certain on my bit setting math (at work, can't test it), but you get the idea. At this point, all you'd have to do is compare the overlapping areas, which should be quite small most of the time. This can also be expanded easily to support animated sprites.




This has me motivated to program, lol. Too bad all I can do is use Notepad right now (not even ++).

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
damothegreat
2
Years of Service
User Offline
Joined: 18th Sep 2016
Location:
Posted: 4th Apr 2017 17:50
Some cool options here - cheers

I'm going to get cracking on with this over next few days - hopefully by weekend will have something
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 4th Apr 2017 18:17
Ok, this is completely untested but should theoretically work.


"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
blink0k
AGK Developer
Gold Codemaster
6
Years of Service
User Offline
Joined: 22nd Feb 2013
Location: the land of oz
Posted: 5th Apr 2017 00:26 Edited at: 5th Apr 2017 02:23
WOW! Funky stuff Mr Phaelax. I will definitely test this.

I basically syntax checked it and plonked it in a project. It crashes and seeing as i understand very little of what is going on i cannot debug it unfortunately.

Attached is the project

Update:

Proggy crashes. I think there is a problem in addPixelCollision() the logic seems to suggest that each pixel in the memblock is a byte whereas each pixel is 4 bytes (At least that is what i think is happening)

Attachments

Login to view attachments
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 5th Apr 2017 02:53
Yea there's a few mistakes. I've fixed them now so it compiles, but it's returning true whenever the bounding boxes overlap. So I think I might be setting the bits incorrectly. Gimme a minute and I'll see if I can resolve that!

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 5th Apr 2017 04:06
Arghh, my rectangle function had a typo where I calculated [x4,y4]

I'm really close, arghhhh! Here's a screenshot of it drawing the alpha of each sprite, using the bitwise functions on the matrix array. So I know for sure the data is being written correctly. But the collision still isn't accurate. I think the problem lies in where I take the two overlapping parts for comparison.

A quick break down of going to the trouble of using bits instead of just comparing memblocks. A 64x64 image would take up 16,396 bytes (4 bytes per pixel plus 12byte header). Storing just the alpha channel and using only a single bit per pixel, that image's collision data can be store in only 512 bytes (64*64 / 8). That's 32x smaller!

There is another bug somewhere, and I don't know if it's my code or I'm hitting a limitation somewhere. But my sprites were 300 pixels wide before I shrunk them to 64. When I use the larger size, it crashes with index out of bounds. It's probably my program, I'm just confused as to why it only happens on large sprites and not small ones. Either way, the collision still isn't accurate yet.

Unfortunately, 4am comes quite quickly and, ah crap omg it's 11?! Yea I'm going to bed guys, I'll try again tomorrow. Here's my current code so far.


"I like offending people, because I think people who get offended should be offended." - Linus Torvalds

Attachments

Login to view attachments
CodeName
2
Years of Service
User Offline
Joined: 30th Dec 2016
Location:
Posted: 5th Apr 2017 05:02 Edited at: 5th Apr 2017 05:05
blink0k
AGK Developer
Gold Codemaster
6
Years of Service
User Offline
Joined: 22nd Feb 2013
Location: the land of oz
Posted: 5th Apr 2017 07:56
Looking very good.
When i move the sprite to collide from above, it registers a hit when the moving sprite touches the bounding box of the other sprite. When i move it from below it works perfectly!
Really enjoying watching the progress and trying to wrap my mind around it!

Attachments

Login to view attachments
damothegreat
2
Years of Service
User Offline
Joined: 18th Sep 2016
Location:
Posted: 5th Apr 2017 10:09
Ill send what I have "so far" tonight / tomorrow - just need to tweak a few coordinates to get it correct, its colliding perfectly on one side of the sprites and bombing out on the other side




Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 5th Apr 2017 13:16
Sorry Damo, didn't mean to hijack your thread.

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 5th Apr 2017 14:31 Edited at: 5th Apr 2017 14:54
I fixed the problem. It was a simple typo. If you look at this line:

                if getPixelMatrixValue(p[a], aPos)=1 and getPixelMatrixValue(p[a], bPos)=1 then exitfunction 1

I was comparing a bit to itself. One of those function calls should using p[b] but I used 'a' for both instead. Oops!

This code should work. I brought my laptop to work and it's running fine but I can't get it online so I'm just updating the text file here and posting it. So provided I didn't make any more dumb typos, this should be pixel perfect collision with low overhead. With the bug fixed, I'll have to see if it still crashes with large images or not.


I'm getting around 500 fps on my i7 laptop. It dips to 350 on an intersection, but the code has a lot of needless loops in it for drawing for demo purposes.

Ok, I took out all the needless stuff and it's twice as fast. About 1200 fps without collision, 600-900 once the sprites' bounding boxes overlap. Still seems like too large of a hit to me, maybe there's still room to optimize it.


"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
damothegreat
2
Years of Service
User Offline
Joined: 18th Sep 2016
Location:
Posted: 5th Apr 2017 15:28
Thanks Phealax - no no, its very much perfectly ok to bounce our code and ideas around.

This is something we all need in our games for perfect collisions - so the more the merrier coders to bring to my thread is all good

Its nice to see many of you having an interest in this topic too


Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 5th Apr 2017 16:21
I think this can also be useful to draw a pixel-perfect outline around a sprite, useful when showing your character behind objects.

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
damothegreat
2
Years of Service
User Offline
Joined: 18th Sep 2016
Location:
Posted: 5th Apr 2017 17:28
Yeah I think I know what you mean

A bit like Doom scenario, what you can have a specialised XRay vision camera, which if we add a dark gray on all the Alpha pixels which are >1, it will look like a ghost!!

Anyway

Back to my version

Damian
damothegreat
2
Years of Service
User Offline
Joined: 18th Sep 2016
Location:
Posted: 5th Apr 2017 18:29
Just tested your version Phealax and what an outstanding effort.

Indeed optimizing would be good, cause If have 50+ sprites on screen at same time all having collisins, it would just grind to a halt

I'm on with mine shortly after a break after a brain mush from work.


Damian
damothegreat
2
Years of Service
User Offline
Joined: 18th Sep 2016
Location:
Posted: 5th Apr 2017 20:44
Thanks Phealax , Batfink and Blink0K about the idea of heading towards putting the Alpha channel into its own data structure.

Bear with me, I'm trying to get to grips on how data structures work.

i.e.

I declare an array as [ ] as an empty structure I persume

can anyone advise at all what the .insert achieves and what parameters it requies

so, instead of saying

data[64,64] for a 64x64 image

I would like to add data to

data [ ]
then
datax
for x=1 to getspritewidth(img) * getspriteheight(img)
data.insert(1)
data[ x ] = AlphaValue
next

This is just foobarring me with invalid array length errors

Any takers to allow me to better understand how to build an empty data structure and add values into it

Cheers

damothegreat
2
Years of Service
User Offline
Joined: 18th Sep 2016
Location:
Posted: 5th Apr 2017 21:05
could go a step further.

how do we want to check alpha channel - 1's or 0's (binary), we all know that there is 8 bits to one integer, so reduce even further

so say a 8 x 8 image

1 0 1 1 1 0 1 0 = 1
1 1 1 0 0 1 1 1 = 2
1 1 1 0 0 1 1 0 = 3
1 0 1 0 0 1 1 1 = 4
0 1 1 0 0 1 1 0 =5
1 1 0 0 1 1 0 0 = 6
0 0 1 1 0 1 0 1 = 7
1 0 1 1 0 1 0 1 =8

8 x 8 x 4 image memblock = 256 + 12
= 8 bytes Alpha data


Unless that's how your function works Phealax, if yes - then ignore me lol
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 5th Apr 2017 22:54
Quote: "can anyone advise at all what the .insert achieves and what parameters it requies"

It inserts the item passed in the parameters to the array.


Quote: "This is just foobarring me with invalid array length errors"

When you initialize an empty array, the first item inserted into it will be at index 0, not 1.


Quote: " we all know that there is 8 bits to one integer"

There are 8 bits to a byte and 4 bytes to an integer. So an integer is 32 bits.

You're correct on calculating the memblock size of an image as well as the number of bytes needed to store the alpha data. Because we'll use each byte to store 8 pixels of alpha information. So it's the number of pixels in an image divided by 8.


I think I'll write a tutorial for the code as I think it covers a few interesting concepts that could really help folks. I may not have time tonight, I'm still stuck at work. My evening supervisor is in the hospital so I'm staying late (past my already 12hr day) until I can get the evening crew on their way. Short handed too, ugh.

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
damothegreat
2
Years of Service
User Offline
Joined: 18th Sep 2016
Location:
Posted: 5th Apr 2017 22:59
Thanks for that Phealax

Don't work too hard. and hope your colleague gets well soon
blink0k
AGK Developer
Gold Codemaster
6
Years of Service
User Offline
Joined: 22nd Feb 2013
Location: the land of oz
Posted: 6th Apr 2017 00:57
Hey Phelax, does that code accommodate rotation and scaling?
damothegreat
2
Years of Service
User Offline
Joined: 18th Sep 2016
Location:
Posted: 6th Apr 2017 01:04
it seems I'm non existent - ban me....I am not returning
blink0k
AGK Developer
Gold Codemaster
6
Years of Service
User Offline
Joined: 22nd Feb 2013
Location: the land of oz
Posted: 6th Apr 2017 01:20
Sorry about that damo. Didn't mean to offend. My apologies
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 6th Apr 2017 02:19 Edited at: 6th Apr 2017 02:58
Did I miss something? No idea what Damo is complaining about this time.

No it does not account for scaling or rotation. Scaling is likely possible by translating the bit array to match the sprite size, should be trivial. Rotation, though I'm sure is quite possible, requires me to go study up on some additional math.


Didn't have a chance to upload this til I got home. Here is my current code, polished up.

demo:



PixelMagic.agc



I've attached the project (source and images). The demo in the zip will show collision between a sprite controlled by your mouse and 100 other randomly placed sprites. I never dipped below 500fps during multiple intersections.

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds

Attachments

Login to view attachments
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 6th Apr 2017 04:29 Edited at: 6th Apr 2017 06:39
Unless I'm rereading my code incorrectly, I've made a big goof! Though the program works just fine, I'm using too much memory. All my bits are stored in integers, not bytes, and yet I've been treating each integer as a byte! In otherwords, I'm wasting 3 bytes for every integer in my bitmask array. Ughhh, I'll fix it tomorrow!


I get sidetracked to easily by programming topics! Here's that tutorial, I'm now going to bed.
http://purpletoken.com/pixelscollision.pdf

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
blink0k
AGK Developer
Gold Codemaster
6
Years of Service
User Offline
Joined: 22nd Feb 2013
Location: the land of oz
Posted: 7th Apr 2017 10:01
I just had an idea about this;
Maybe you could add a parameter to your CreatePixelSprite() which is the minimum angle that it will be rotated (zero if it won't be rotated). CreatePixelSprite() would then create a series of sprites to accommodate rotation through 360 degrees as well as collision data for each rotation
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 8th Apr 2017 01:57 Edited at: 8th Apr 2017 02:01
That sounds pretty inefficient to me. I should be able to just add a transform matrix to the data. I'm going to look into it, I just haven't had time the past few days.


Oh btw, I did fix the small bug I mentioned about I was only using a single byte out of each integer. In the pixelMagic_createPixelSprite function, divide the number of pixels by 32 instead of 8 for maskSize. And then change 8 to 32 in the two bitwise functions. That'll cut the memory currently used by each pixelSprite by 4X.

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds

Login to post a reply

Server time is: 2019-04-26 12:04:02
Your offset time is: 2019-04-26 12:04:02