A fast Sprite Per Pixel Collision Function will be with you soon

Author

Message

damothegreat

User Banned

Posted: 3rd Apr 2017 21:52

Link

Watch this space

Thanks
Damian

Back to top

Profile

easter bunny

12

Years of Service

User Offline

Joined: 20th Nov 2012

Playing: Dota 2

Posted: 3rd Apr 2017 23:53

Link

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

Back to top

Profile PM Email

damothegreat

User Banned

Posted: 4th Apr 2017 00:07

Link

Your welcome,

It will helps lots of us for better percision

Back to top

Profile

damothegreat

User Banned

Posted: 4th Apr 2017 00:17 Edited at: 4th Apr 2017 00:22

Link

The algorithm is simply

// For speed first let AGK engine to check the first phase of the collision

if getspritecollision(img, img1)

// Find the intersection - as this is only checking a really small area each time, then speed performance wont be affected too much

imgtop = Min(getspritey(img), getspritey(img1))
		imgbottom = Max(getspritey(img)+GetSpriteHeight(img), getspritey(img1)+GetSpriteHeight(img1))
		imgleft = Max(GetSpriteX(img), getspritex(img1))
		imgright = Min(GetSpriteX(img)+GetSpriteWidth(img), getspritex(img1)+GetSpriteWidth(img1))
		
	
	DrawBox(imgtop, imgleft, imgbottom, imgright, c,c,c,c,1)
// Check every point within the intersection bounds
		for y = imgtop to imgbottom
			for x = imgleft to imgright
        
// Get the color of both pixels at this point
				Alpha1 = getpixelcolor(imgmem,  ((x - GetSpriteX(img ))-(x - GetSpriteX(img ))) + ((y - getspritey(img )) * GetSpriteWidth(img )-(y - getspritey(img )) * GetSpriteWidth(img )))
                Alpha2 = getpixelcolor(img1mem, ((x - GetSpriteX(img1))-(x - GetSpriteX(img1))) + ((y - getspritey(img1)) * GetSpriteWidth(img1)-(y - getspritey(img1)) * GetSpriteWidth(img1)))
                	//			print("Location: " + str((x - GetSpriteX(img)) + (y - getspritey(img)) * GetSpriteWidth(img)))
				collided=0
// If both pixels are not completely transparent,
				if Alpha1 <> 0 and Alpha2 <> 0 then collided=1

if collided=1 then print ("Collided with per pixel percision - YIPPEEE")
				
			next
		next
		
	endif
endif

+ Code Snippet

// For speed first let AGK engine to check the first phase of the collision

if getspritecollision(img, img1) 


// Find the intersection - as this is only checking a really small area each time, then speed performance wont be affected too much

		imgtop = Min(getspritey(img), getspritey(img1))
		imgbottom = Max(getspritey(img)+GetSpriteHeight(img), getspritey(img1)+GetSpriteHeight(img1))
		imgleft = Max(GetSpriteX(img), getspritex(img1))
		imgright = Min(GetSpriteX(img)+GetSpriteWidth(img), getspritex(img1)+GetSpriteWidth(img1))
		
	
	DrawBox(imgtop, imgleft, imgbottom, imgright, c,c,c,c,1)
// Check every point within the intersection bounds
		for y = imgtop to imgbottom
			for x = imgleft to imgright
        
// Get the color of both pixels at this point
				Alpha1 = getpixelcolor(imgmem,  ((x - GetSpriteX(img ))-(x - GetSpriteX(img ))) + ((y - getspritey(img )) * GetSpriteWidth(img )-(y - getspritey(img )) * GetSpriteWidth(img )))
                Alpha2 = getpixelcolor(img1mem, ((x - GetSpriteX(img1))-(x - GetSpriteX(img1))) + ((y - getspritey(img1)) * GetSpriteWidth(img1)-(y - getspritey(img1)) * GetSpriteWidth(img1)))
                	//			print("Location: " + str((x - GetSpriteX(img)) + (y - getspritey(img)) * GetSpriteWidth(img)))
				collided=0
// If both pixels are not completely transparent,
				if Alpha1 <> 0 and Alpha2 <> 0 then collided=1

	if collided=1 then print ("Collided with per pixel percision - YIPPEEE")
				
			next
		next
		
	endif
endif

This is work in progress and will be with us shortly, but this is the idea

Back to top

Profile

blink0k

Moderator

11

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

Link

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

Back to top

Profile PM

BatVink

Moderator

21

Years of Service

User Offline

Joined: 4th Apr 2003

Location: Gods own County, UK

Posted: 4th Apr 2017 08:29

Link

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

Back to top

Profile PM Email

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 4th Apr 2017 12:14 Edited at: 4th Apr 2017 16:26

Link

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.

Type Rectangle
	x as integer
	y as integer
	width as integer
	height as integer
EndType

Type PixelCollision
	spriteId as integer
	matrix as integer[]
EndType

pixelSprites as PixelCollision[]

dude = createSprite()
addPixelCollision(pixelSprites, dude)

function pixelCollide(p as PixelCollision[], a as integer, b as integer)
	x1 = getSpriteX(p[a].spriteId)
	y1 = getSpriteY(p[a].spriteId)
	x2 = x1 + getSpriteWidth(p[a].spriteId)
	y2 = y1 + getSpriteHeight(p[a].spriteId)

x3 = getSpriteX(p[b].spriteId)
	y3 = getSpriteY(p[b].spriteId)
	x4 = x2 + getSpriteWidth(p[b].spriteId)
	y4 = y2 + getSpriteHeight(p[b].spriteId)

// check bounding box overlap
	if x3 < x2 and x4 > x1 and y3 < y2 and y4 > y1
		// Get intersecting rectangle
		r as Rectangle
		r = getIntersection(x1,y1,x2,y2,x3,y3,x4,y4)

endif

endfunction 0

function getIntersection(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2)
	left   = max(ax1, bx1)
	top    = max(ay1, by1)
	right  = min(ax2, bx2)
	bottom = min(ay2, by2)

r as Rectangle

r.x = left
	r.y = top
	r.width = 0
	r.height = 0
	if right > left then r.width = right - left
	if bottom > top then r.height = bottom - top
	
endfunction r

function addPixelCollision(p ref as PixelCollision[], sprite as integer)
	
	img = getSpriteImage(sprite)

collisionMatrixSize = ceil((getImageWidth(img) * getImageHeight(img)) / 8)

x as PixelCollision
	x.spriteId = sprite
	x.matrix.length = collisionMatrixSize

m = makeMemblockFromImage(img)

for i = 12 to getMemblockSize(m)
		if getMemblockByte(i+3) > 0 then setPixelMatrixValue(x, i-12, 1)
	next i

deleteMemblock(m)

p.insert(x)
endfunction p.length

function setPixelMatrixValue(p ref as PixelCollision, bit, bool)

i = ceil(bit / 8)
	b = bit - i*8

p.matrix[i] = p.matrix[i] || bool << b
endfunction

function getPixelMatrixValue(p as PixelCollision, bit)
	i = ceil(bit / 8)
	b = bit - i*8
	value = (i >> b) && 1
endfunction value

+ Code Snippet


Type Rectangle
	x as integer
	y as integer
	width as integer
	height as integer
EndType


Type PixelCollision
	spriteId as integer
	matrix as integer[]
EndType


pixelSprites as PixelCollision[]



dude = createSprite()
addPixelCollision(pixelSprites, dude)




function pixelCollide(p as PixelCollision[], a as integer, b as integer)
	x1 = getSpriteX(p[a].spriteId)
	y1 = getSpriteY(p[a].spriteId)
	x2 = x1 + getSpriteWidth(p[a].spriteId)
	y2 = y1 + getSpriteHeight(p[a].spriteId)

	x3 = getSpriteX(p[b].spriteId)
	y3 = getSpriteY(p[b].spriteId)
	x4 = x2 + getSpriteWidth(p[b].spriteId)
	y4 = y2 + getSpriteHeight(p[b].spriteId)

	// check bounding box overlap
	if x3 < x2 and x4 > x1 and y3 < y2 and y4 > y1
		// Get intersecting rectangle
		r as Rectangle
		r = getIntersection(x1,y1,x2,y2,x3,y3,x4,y4)

	endif

endfunction 0


function getIntersection(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2)
	left   = max(ax1, bx1)
	top    = max(ay1, by1)
	right  = min(ax2, bx2)
	bottom = min(ay2, by2)

	r as Rectangle

	r.x = left
	r.y = top
	r.width = 0
	r.height = 0
	if right > left then r.width = right - left
	if bottom > top then r.height = bottom - top
	
endfunction r



function addPixelCollision(p ref as PixelCollision[], sprite as integer)
	
	img = getSpriteImage(sprite)

	collisionMatrixSize = ceil((getImageWidth(img) * getImageHeight(img)) / 8)

	x as PixelCollision
	x.spriteId = sprite
	x.matrix.length = collisionMatrixSize


	m = makeMemblockFromImage(img)

	for i = 12 to getMemblockSize(m)
		if getMemblockByte(i+3) > 0 then setPixelMatrixValue(x, i-12, 1)
	next i

	deleteMemblock(m)


	p.insert(x)
endfunction p.length





function setPixelMatrixValue(p ref as PixelCollision, bit, bool)

	i = ceil(bit / 8)
	b = bit - i*8

	p.matrix[i] = p.matrix[i] || bool << b
endfunction





function getPixelMatrixValue(p as PixelCollision, bit)
	i = ceil(bit / 8)
	b = bit - i*8
	value = (i >> b) && 1
endfunction value

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

Back to top

Profile PM Email Website

damothegreat

User Banned

Posted: 4th Apr 2017 17:50

Link

Some cool options here - cheers

I'm going to get cracking on with this over next few days - hopefully by weekend will have something

Back to top

Profile

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 4th Apr 2017 18:17

Link

Ok, this is completely untested but should theoretically work.

Type Rectangle
	x as integer
	y as integer
	width as integer
	height as integer
EndType

Type PixelCollision
	spriteId as integer
	matrix as integer[]
EndType

pixelSprites as PixelCollision[]

dude = createSprite()
addPixelCollision(pixelSprites, dude)

function pixelCollide(p as PixelCollision[], a as integer, b as integer)
	x1 = getSpriteX(p[a].spriteId)
	y1 = getSpriteY(p[a].spriteId)
	x2 = x1 + getSpriteWidth(p[a].spriteId)
	y2 = y1 + getSpriteHeight(p[a].spriteId)

x3 = getSpriteX(p[b].spriteId)
	y3 = getSpriteY(p[b].spriteId)
	x4 = x2 + getSpriteWidth(p[b].spriteId)
	y4 = y2 + getSpriteHeight(p[b].spriteId)

// check bounding box overlap
	if x3 < x2 and x4 > x1 and y3 < y2 and y4 > y1
		// Get intersecting rectangle
		r as Rectangle
		r = getIntersection(x1,y1,x2,y2,x3,y3,x4,y4)
		
		x1 = r.x-x1
		y1 = r.y-y1
		
		x3 = r.x - x3
		y3 = r.y - y3
		
		aWidth = getSpriteWidth(p[a].sprite)
		bWidth = getSpriteWidth(p[b].sprite)
		
		for y = 0 to r.height-1
			for x = 0 to r.width-1
				aPos = (y1+y)*aWidth + x1+x
				bPos = (y3+y)*bWidth + x3+x
				if getPixelMatrixValue(p[a], aPos)  && getPixelMatrixValue(p[a], bPos) then exitfunction 1
			next x
		next y
		
	endif

endfunction 0

function getIntersection(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2)
	left   = max(ax1, bx1)
	top    = max(ay1, by1)
	right  = min(ax2, bx2)
	bottom = min(ay2, by2)

r as Rectangle

r.x = left
	r.y = top
	r.width = 0
	r.height = 0
	if right > left then r.width = right - left
	if bottom > top then r.height = bottom - top
	
endfunction r

function addPixelCollision(p ref as PixelCollision[], sprite as integer)
	
	img = getSpriteImage(sprite)

collisionMatrixSize = ceil((getImageWidth(img) * getImageHeight(img)) / 8)

x as PixelCollision
	x.spriteId = sprite
	x.matrix.length = collisionMatrixSize

m = makeMemblockFromImage(img)

for i = 12 to getMemblockSize(m)
		if getMemblockByte(i+3) > 0 then setPixelMatrixValue(x, i-12, 1)
	next i

deleteMemblock(m)

p.insert(x)
endfunction p.length

function setPixelMatrixValue(p ref as PixelCollision, bit, bool)

i = ceil(bit / 8)
	b = bit - i*8

p.matrix[i] = p.matrix[i] || bool << b
endfunction

function getPixelMatrixValue(p as PixelCollision, bit)
	i = ceil(bit / 8)
	b = bit - i*8
	value = (i >> b) && 1
endfunction value

+ Code Snippet

Type Rectangle
	x as integer
	y as integer
	width as integer
	height as integer
EndType


Type PixelCollision
	spriteId as integer
	matrix as integer[]
EndType


pixelSprites as PixelCollision[]



dude = createSprite()
addPixelCollision(pixelSprites, dude)




function pixelCollide(p as PixelCollision[], a as integer, b as integer)
	x1 = getSpriteX(p[a].spriteId)
	y1 = getSpriteY(p[a].spriteId)
	x2 = x1 + getSpriteWidth(p[a].spriteId)
	y2 = y1 + getSpriteHeight(p[a].spriteId)

	x3 = getSpriteX(p[b].spriteId)
	y3 = getSpriteY(p[b].spriteId)
	x4 = x2 + getSpriteWidth(p[b].spriteId)
	y4 = y2 + getSpriteHeight(p[b].spriteId)

	// check bounding box overlap
	if x3 < x2 and x4 > x1 and y3 < y2 and y4 > y1
		// Get intersecting rectangle
		r as Rectangle
		r = getIntersection(x1,y1,x2,y2,x3,y3,x4,y4)
		
		x1 = r.x-x1
		y1 = r.y-y1
		
		x3 = r.x - x3
		y3 = r.y - y3
		
		aWidth = getSpriteWidth(p[a].sprite)
		bWidth = getSpriteWidth(p[b].sprite)
		
		for y = 0 to r.height-1
			for x = 0 to r.width-1
				aPos = (y1+y)*aWidth + x1+x
				bPos = (y3+y)*bWidth + x3+x
				if getPixelMatrixValue(p[a], aPos)  && getPixelMatrixValue(p[a], bPos) then exitfunction 1
			next x
		next y
		
	endif

endfunction 0


function getIntersection(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2)
	left   = max(ax1, bx1)
	top    = max(ay1, by1)
	right  = min(ax2, bx2)
	bottom = min(ay2, by2)

	r as Rectangle

	r.x = left
	r.y = top
	r.width = 0
	r.height = 0
	if right > left then r.width = right - left
	if bottom > top then r.height = bottom - top
	
endfunction r



function addPixelCollision(p ref as PixelCollision[], sprite as integer)
	
	img = getSpriteImage(sprite)

	collisionMatrixSize = ceil((getImageWidth(img) * getImageHeight(img)) / 8)

	x as PixelCollision
	x.spriteId = sprite
	x.matrix.length = collisionMatrixSize


	m = makeMemblockFromImage(img)

	for i = 12 to getMemblockSize(m)
		if getMemblockByte(i+3) > 0 then setPixelMatrixValue(x, i-12, 1)
	next i

	deleteMemblock(m)


	p.insert(x)
endfunction p.length





function setPixelMatrixValue(p ref as PixelCollision, bit, bool)

	i = ceil(bit / 8)
	b = bit - i*8

	p.matrix[i] = p.matrix[i] || bool << b
endfunction





function getPixelMatrixValue(p as PixelCollision, bit)
	i = ceil(bit / 8)
	b = bit - i*8
	value = (i >> b) && 1
endfunction value

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

Back to top

Profile PM Email Website

blink0k

Moderator

11

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

Link

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

Back to top

Profile PM

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 5th Apr 2017 02:53

Link

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

Back to top

Profile PM Email Website

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 5th Apr 2017 04:06

Link

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.

// Project: pixelCollision 
// Created: 2017-04-04

// show all errors
SetErrorMode(2)

// set window properties
SetWindowTitle( "pixelCollision" )
SetWindowSize( 1024, 768, 0 )
SetWindowAllowResize( 1 ) // allow the user to resize the window

// set display properties
SetVirtualResolution( 1024, 768 ) // doesn't have to match the window
SetOrientationAllowed( 1, 1, 1, 1 ) // allow both portrait and landscape on mobile devices
SetSyncRate( 30, 0 ) // 30fps instead of 60 to save battery
SetScissor( 0,0,0,0 ) // use the maximum available screen space, no black borders
UseNewDefaultFonts( 1 ) // since version 2.0.22 we can use nicer default fonts

Type Rectangle
    x as integer
    y as integer
    width as integer
    height as integer
EndType
 
 
Type PixelCollision
    spriteId as integer
    matrix as integer[]
    m as integer
EndType
 
 
pixelSprites as PixelCollision[]
 
 
 
dude1 = createSprite(loadImage("GameArtPartners_1_FeatureImage2.png"))
p1 = addPixelCollision(pixelSprites, dude1)
setSpritePosition(dude1, 300, 200)

dude2 = createSprite(loadImage("pirate-royalty-free-game-art2.png"))
p2 = addPixelCollision(pixelSprites, dude2)

c = 0xFFFFFF

do

setSpritePosition(dude2, getRawMouseX(), getRawMouseY())

bmax = pixelSprites[p1].matrix.length*8
	for i = 0 to bmax
		y = i / 64
		x = i - y*64
		
		`if getPixelMatrixValue(pixelSprites[p1], i) > 0 then drawBox(x+100, y+100, x+101, y+101,c,c,c,c,1)
	next i
	
	
	bmax = pixelSprites[p2].matrix.length*8
	for i = 0 to bmax
		y = i / 64
		x = i - y*64
		
		`if getPixelMatrixValue(pixelSprites[p2], i) > 0 then drawBox(x+200, y+100, x+201, y+101,c,c,c,c,1)
	next i
	
	
	
	result = pixelCollide(pixelSprites, p1, p2)
	print(result)

Print( ScreenFPS() )
    Sync()
loop

function pixelCollide(p as PixelCollision[], a as integer, b as integer)
    x1 = getSpriteX(p[a].spriteId)
    y1 = getSpriteY(p[a].spriteId)
    x2 = x1 + getSpriteWidth(p[a].spriteId)
    y2 = y1 + getSpriteHeight(p[a].spriteId)
 
    x3 = getSpriteX(p[b].spriteId)
    y3 = getSpriteY(p[b].spriteId)
    x4 = x3 + getSpriteWidth(p[b].spriteId)
    y4 = y3 + getSpriteHeight(p[b].spriteId)
    
    c = 0xFFFFFF
    drawBox(x1,y1,x2,y2,c,c,c,c,0)
    drawBox(x3,y3,x4,y4,c,c,c,c,0)
 
    // check bounding box overlap
    if x3 < x2 and x4 > x1 and y3 < y2 and y4 > y1
        // Get intersecting rectangle
        r as Rectangle
        r = getIntersection(x1,y1,x2,y2,x3,y3,x4,y4)
         
        x1 = r.x-x1
        y1 = r.y-y1
         
        x3 = r.x - x3
        y3 = r.y - y3
         
        aWidth = getSpriteWidth(p[a].spriteId)
        bWidth = getSpriteWidth(p[b].spriteId)
        
        
        c = 0xFFFF00
        drawBox(r.x, r.y, r.x+r.width, r.y+r.height,c,c,c,c,0)
        
        
        for y = 0 to r.height-1
            for x = 0 to r.width-1
                aPos = (y1+y)*aWidth + x1+x
                bPos = (y3+y)*bWidth + x3+x
                if getPixelMatrixValue(p[a], aPos)=1 and getPixelMatrixValue(p[a], bPos)=1 then exitfunction 1
            next x
        next y
         
    endif
 
endfunction 0

function getIntersection(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2)
    left   = max(ax1, bx1)
    top    = max(ay1, by1)
    right  = min(ax2, bx2)
    bottom = min(ay2, by2)

r as Rectangle
 
    r.x = left
    r.y = top
    r.width = 0
    r.height = 0
    if right > left then r.width = right - left
    if bottom > top then r.height = bottom - top
     
endfunction r
 
 
 
function addPixelCollision(p ref as PixelCollision[], sprite as integer)
     
    img = getSpriteImageID(sprite)
 
    collisionMatrixSize = ceil((getImageWidth(img) * getImageHeight(img)) / 8)
 
    x as PixelCollision
    x.spriteId = sprite
    x.matrix.length = collisionMatrixSize
 
 
    m = createMemblockFromImage(img)

bit = 0
    for i = 12 to getMemblockSize(m)-4 step 4
        if getMemblockByte(m, i+3) > 0
			setPixelMatrixValue(x, bit, 1)
		endif
        inc bit
    next i
 
	x.m = m
	
    `deleteMemblock(m)
 
 
    p.insert(x)
endfunction p.length
 
 
 
 
 
function setPixelMatrixValue(p ref as PixelCollision, bit, bool)
    i = floor(bit / 8)
    b = bit - i*8
 
    p.matrix[i] = p.matrix[i] || (1 << b)
endfunction
 
 
 
 
 
function getPixelMatrixValue(p as PixelCollision, bit)
    i = floor(bit / 8)
    b = bit - i*8
    value = (p.matrix[i] >> b) && 1
endfunction value

function max(a, b)
	if a > b then exitfunction a
endfunction b

function min(a, b)
	if a < b then exitfunction a
endfunction b

+ Code Snippet


// Project: pixelCollision 
// Created: 2017-04-04

// show all errors
SetErrorMode(2)

// set window properties
SetWindowTitle( "pixelCollision" )
SetWindowSize( 1024, 768, 0 )
SetWindowAllowResize( 1 ) // allow the user to resize the window

// set display properties
SetVirtualResolution( 1024, 768 ) // doesn't have to match the window
SetOrientationAllowed( 1, 1, 1, 1 ) // allow both portrait and landscape on mobile devices
SetSyncRate( 30, 0 ) // 30fps instead of 60 to save battery
SetScissor( 0,0,0,0 ) // use the maximum available screen space, no black borders
UseNewDefaultFonts( 1 ) // since version 2.0.22 we can use nicer default fonts



Type Rectangle
    x as integer
    y as integer
    width as integer
    height as integer
EndType
 
 
Type PixelCollision
    spriteId as integer
    matrix as integer[]
    m as integer
EndType
 
 
pixelSprites as PixelCollision[]
 
 
 
dude1 = createSprite(loadImage("GameArtPartners_1_FeatureImage2.png"))
p1 = addPixelCollision(pixelSprites, dude1)
setSpritePosition(dude1, 300, 200)

dude2 = createSprite(loadImage("pirate-royalty-free-game-art2.png"))
p2 = addPixelCollision(pixelSprites, dude2)



c = 0xFFFFFF



do
	
	

	
	
	setSpritePosition(dude2, getRawMouseX(), getRawMouseY())
	
	

	bmax = pixelSprites[p1].matrix.length*8
	for i = 0 to bmax
		y = i / 64
		x = i - y*64
		
		`if getPixelMatrixValue(pixelSprites[p1], i) > 0 then drawBox(x+100, y+100, x+101, y+101,c,c,c,c,1)
	next i
	
	
	bmax = pixelSprites[p2].matrix.length*8
	for i = 0 to bmax
		y = i / 64
		x = i - y*64
		
		`if getPixelMatrixValue(pixelSprites[p2], i) > 0 then drawBox(x+200, y+100, x+201, y+101,c,c,c,c,1)
	next i
	
	
	
	result = pixelCollide(pixelSprites, p1, p2)
	print(result)

    Print( ScreenFPS() )
    Sync()
loop





 
 
 
 
function pixelCollide(p as PixelCollision[], a as integer, b as integer)
    x1 = getSpriteX(p[a].spriteId)
    y1 = getSpriteY(p[a].spriteId)
    x2 = x1 + getSpriteWidth(p[a].spriteId)
    y2 = y1 + getSpriteHeight(p[a].spriteId)
 
    x3 = getSpriteX(p[b].spriteId)
    y3 = getSpriteY(p[b].spriteId)
    x4 = x3 + getSpriteWidth(p[b].spriteId)
    y4 = y3 + getSpriteHeight(p[b].spriteId)
    
    c = 0xFFFFFF
    drawBox(x1,y1,x2,y2,c,c,c,c,0)
    drawBox(x3,y3,x4,y4,c,c,c,c,0)
 
    // check bounding box overlap
    if x3 < x2 and x4 > x1 and y3 < y2 and y4 > y1
        // Get intersecting rectangle
        r as Rectangle
        r = getIntersection(x1,y1,x2,y2,x3,y3,x4,y4)
         
        x1 = r.x-x1
        y1 = r.y-y1
         
        x3 = r.x - x3
        y3 = r.y - y3
         
        aWidth = getSpriteWidth(p[a].spriteId)
        bWidth = getSpriteWidth(p[b].spriteId)
        
        
        c = 0xFFFF00
        drawBox(r.x, r.y, r.x+r.width, r.y+r.height,c,c,c,c,0)
        
        
        for y = 0 to r.height-1
            for x = 0 to r.width-1
                aPos = (y1+y)*aWidth + x1+x
                bPos = (y3+y)*bWidth + x3+x
                if getPixelMatrixValue(p[a], aPos)=1 and getPixelMatrixValue(p[a], bPos)=1 then exitfunction 1
            next x
        next y
         
    endif
 
endfunction 0


 
 
function getIntersection(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2)
    left   = max(ax1, bx1)
    top    = max(ay1, by1)
    right  = min(ax2, bx2)
    bottom = min(ay2, by2)
 

    r as Rectangle
 
    r.x = left
    r.y = top
    r.width = 0
    r.height = 0
    if right > left then r.width = right - left
    if bottom > top then r.height = bottom - top
     
endfunction r
 
 
 
function addPixelCollision(p ref as PixelCollision[], sprite as integer)
     
    img = getSpriteImageID(sprite)
 
    collisionMatrixSize = ceil((getImageWidth(img) * getImageHeight(img)) / 8)
 
    x as PixelCollision
    x.spriteId = sprite
    x.matrix.length = collisionMatrixSize
 
 
    m = createMemblockFromImage(img)
    
	
	

	
	bit = 0
    for i = 12 to getMemblockSize(m)-4 step 4
        if getMemblockByte(m, i+3) > 0
			setPixelMatrixValue(x, bit, 1)
		endif
        inc bit
    next i
 
	x.m = m
	
    `deleteMemblock(m)
 
 
    p.insert(x)
endfunction p.length
 
 
 
 
 
function setPixelMatrixValue(p ref as PixelCollision, bit, bool)
    i = floor(bit / 8)
    b = bit - i*8
 
    p.matrix[i] = p.matrix[i] || (1 << b)
endfunction
 
 
 
 
 
function getPixelMatrixValue(p as PixelCollision, bit)
    i = floor(bit / 8)
    b = bit - i*8
    value = (p.matrix[i] >> b) && 1
endfunction value



function max(a, b)
	if a > b then exitfunction a
endfunction b

function min(a, b)
	if a < b then exitfunction a
endfunction b

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

Attachments

Login to view attachments

Back to top

Profile PM Email Website

CodeName

7

Years of Service

User Offline

Joined: 30th Dec 2016

Location:

Posted: 5th Apr 2017 05:02 Edited at: 5th Apr 2017 05:05

Link

http://stackoverflow.com/questions/173199/can-someone-explain-per-pixel-collision-detection

I found this.. may help some.

Back to top

Profile PM

blink0k

Moderator

11

Years of Service

User Offline

Joined: 22nd Feb 2013

Location: the land of oz

Posted: 5th Apr 2017 07:56

Link

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

Back to top

Profile PM

damothegreat

User Banned

Posted: 5th Apr 2017 10:09

Link

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

Back to top

Profile

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 5th Apr 2017 13:16

Link

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

Back to top

Profile PM Email Website

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 5th Apr 2017 14:31 Edited at: 5th Apr 2017 14:54

Link

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.

// Project: pixelCollision 
// Created: 2017-04-04
 
// show all errors
SetErrorMode(2)
 
// set window properties
SetWindowTitle( "pixelCollision" )
SetWindowSize( 1024, 768, 0 )
SetWindowAllowResize( 1 ) // allow the user to resize the window
 
// set display properties
SetVirtualResolution( 1024, 768 ) // doesn't have to match the window
SetOrientationAllowed( 1, 1, 1, 1 ) // allow both portrait and landscape on mobile devices
SetSyncRate( 0, 0 ) // 30fps instead of 60 to save battery
SetScissor( 0,0,0,0 ) // use the maximum available screen space, no black borders
UseNewDefaultFonts( 1 ) // since version 2.0.22 we can use nicer default fonts
 
 
 
Type Rectangle
    x as integer
    y as integer
    width as integer
    height as integer
EndType
  
  
Type PixelCollision
    spriteId as integer
    matrix as integer[]
    m as integer
EndType
  
  
pixelSprites as PixelCollision[]
  
  
  
dude1 = createSprite(loadImage("GameArtPartners_1_FeatureImage2.png"))
p1 = addPixelCollision(pixelSprites, dude1)
setSpritePosition(dude1, 300, 200)
 
dude2 = createSprite(loadImage("pirate-royalty-free-game-art2.png"))
p2 = addPixelCollision(pixelSprites, dude2)
 
 
 
c = 0xFFFFFF
 
 
 
do
     
     
 
     
     
    setSpritePosition(dude2, getRawMouseX(), getRawMouseY())
     
     
 
    bmax = pixelSprites[p1].matrix.length*8
    for i = 0 to bmax
        y = i / 64
        x = i - y*64
         
        `if getPixelMatrixValue(pixelSprites[p1], i) > 0 then drawBox(x+100, y+100, x+101, y+101,c,c,c,c,1)
    next i
     
     
    bmax = pixelSprites[p2].matrix.length*8
    for i = 0 to bmax
        y = i / 64
        x = i - y*64
         
        `if getPixelMatrixValue(pixelSprites[p2], i) > 0 then drawBox(x+200, y+100, x+201, y+101,c,c,c,c,1)
    next i
     
     
     
    result = pixelCollide(pixelSprites, p1, p2)
    print(result)
 
    Print( ScreenFPS() )
    Sync()
loop
 
 
 
 
 
  
  
  
  
function pixelCollide(p as PixelCollision[], a as integer, b as integer)
    x1 = getSpriteX(p[a].spriteId)
    y1 = getSpriteY(p[a].spriteId)
    x2 = x1 + getSpriteWidth(p[a].spriteId)
    y2 = y1 + getSpriteHeight(p[a].spriteId)
  
    x3 = getSpriteX(p[b].spriteId)
    y3 = getSpriteY(p[b].spriteId)
    x4 = x3 + getSpriteWidth(p[b].spriteId)
    y4 = y3 + getSpriteHeight(p[b].spriteId)
     
    // bounding boxes around sprites
    c = 0xFFFFFF
    `drawBox(x1,y1,x2,y2,c,c,c,c,0)
    `drawBox(x3,y3,x4,y4,c,c,c,c,0)
  
    // check bounding box overlap
    if x3 < x2 and x4 > x1 and y3 < y2 and y4 > y1
        // Get intersecting rectangle
        r as Rectangle
        r = getIntersection(x1,y1,x2,y2,x3,y3,x4,y4)
          
        x1 = r.x-x1
        y1 = r.y-y1
          
        x3 = r.x - x3
        y3 = r.y - y3
          
        aWidth = getSpriteWidth(p[a].spriteId)
        bWidth = getSpriteWidth(p[b].spriteId)
         
        // show intersection box
        c = 0xFFFF00
        //drawBox(r.x, r.y, r.x+r.width, r.y+r.height,c,c,c,c,0)

c1 = 0xFFFFFF
	c2 = 0xFF0000
	c3 = 0x0000FF
	
	// Show what parts of the image are being checked
        for y = 0 to r.height-1
            for x = 0 to r.width-1
                aPos = (y1+y)*aWidth + x1+x
                bPos = (y3+y)*bWidth + x3+x
                if getPixelMatrixValue(p[a], aPos)=1 then drawBox(x+100, y+100, x+101, y+101,c1,c1,c1,c1,1)
		if getPixelMatrixValue(p[b], bPos)=1 then drawBox(x+100, y+100, x+101, y+101,c2,c2,c2,c2,1)

cx = r.x+x
		cy = r.y+y
		if getPixelMatrixValue(p[a], aPos)=1 and getPixelMatrixValue(p[b], bPos)=1 then drawBox(cx,cy,cx+1,cy+1,c3,c3,c3,c3,1)
            next x
        next y

// Check for overlapping collision 
        for y = 0 to r.height-1
            for x = 0 to r.width-1
                aPos = (y1+y)*aWidth + x1+x
                bPos = (y3+y)*bWidth + x3+x
                if getPixelMatrixValue(p[a], aPos)=1 and getPixelMatrixValue(p[b], bPos)=1 then exitfunction 1
            next x
        next y
          
    endif
  
endfunction 0
 
 
  
  
function getIntersection(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2)
    left   = max(ax1, bx1)
    top    = max(ay1, by1)
    right  = min(ax2, bx2)
    bottom = min(ay2, by2)
  
 
    r as Rectangle
  
    r.x = left
    r.y = top
    r.width = 0
    r.height = 0
    if right > left then r.width = right - left
    if bottom > top then r.height = bottom - top
      
endfunction r
  
  
  
function addPixelCollision(p ref as PixelCollision[], sprite as integer)
      
    img = getSpriteImageID(sprite)
  
    collisionMatrixSize = ceil((getImageWidth(img) * getImageHeight(img)) / 8)
  
    x as PixelCollision
    x.spriteId = sprite
    x.matrix.length = collisionMatrixSize
  
  
    m = createMemblockFromImage(img)
     
     
     
 
     
    bit = 0
    for i = 12 to getMemblockSize(m)-4 step 4
        if getMemblockByte(m, i+3) > 0
            setPixelMatrixValue(x, bit, 1)
        endif
        inc bit
    next i
  
    x.m = m
     
    `deleteMemblock(m)
  
  
    p.insert(x)
endfunction p.length
  
  
  
  
  
function setPixelMatrixValue(p ref as PixelCollision, bit, bool)
    i = floor(bit / 8)
    b = bit - i*8
  
    p.matrix[i] = p.matrix[i] || (1 << b)
endfunction
  
  
  
  
  
function getPixelMatrixValue(p as PixelCollision, bit)
    i = floor(bit / 8)
    b = bit - i*8
    value = (p.matrix[i] >> b) && 1
endfunction value
 
 
 
function max(a, b)
    if a > b then exitfunction a
endfunction b
 
function min(a, b)
    if a < b then exitfunction a
endfunction b

+ Code Snippet


// Project: pixelCollision 
// Created: 2017-04-04
 
// show all errors
SetErrorMode(2)
 
// set window properties
SetWindowTitle( "pixelCollision" )
SetWindowSize( 1024, 768, 0 )
SetWindowAllowResize( 1 ) // allow the user to resize the window
 
// set display properties
SetVirtualResolution( 1024, 768 ) // doesn't have to match the window
SetOrientationAllowed( 1, 1, 1, 1 ) // allow both portrait and landscape on mobile devices
SetSyncRate( 0, 0 ) // 30fps instead of 60 to save battery
SetScissor( 0,0,0,0 ) // use the maximum available screen space, no black borders
UseNewDefaultFonts( 1 ) // since version 2.0.22 we can use nicer default fonts
 
 
 
Type Rectangle
    x as integer
    y as integer
    width as integer
    height as integer
EndType
  
  
Type PixelCollision
    spriteId as integer
    matrix as integer[]
    m as integer
EndType
  
  
pixelSprites as PixelCollision[]
  
  
  
dude1 = createSprite(loadImage("GameArtPartners_1_FeatureImage2.png"))
p1 = addPixelCollision(pixelSprites, dude1)
setSpritePosition(dude1, 300, 200)
 
dude2 = createSprite(loadImage("pirate-royalty-free-game-art2.png"))
p2 = addPixelCollision(pixelSprites, dude2)
 
 
 
c = 0xFFFFFF
 
 
 
do
     
     
 
     
     
    setSpritePosition(dude2, getRawMouseX(), getRawMouseY())
     
     
 
    bmax = pixelSprites[p1].matrix.length*8
    for i = 0 to bmax
        y = i / 64
        x = i - y*64
         
        `if getPixelMatrixValue(pixelSprites[p1], i) > 0 then drawBox(x+100, y+100, x+101, y+101,c,c,c,c,1)
    next i
     
     
    bmax = pixelSprites[p2].matrix.length*8
    for i = 0 to bmax
        y = i / 64
        x = i - y*64
         
        `if getPixelMatrixValue(pixelSprites[p2], i) > 0 then drawBox(x+200, y+100, x+201, y+101,c,c,c,c,1)
    next i
     
     
     
    result = pixelCollide(pixelSprites, p1, p2)
    print(result)
 
    Print( ScreenFPS() )
    Sync()
loop
 
 
 
 
 
  
  
  
  
function pixelCollide(p as PixelCollision[], a as integer, b as integer)
    x1 = getSpriteX(p[a].spriteId)
    y1 = getSpriteY(p[a].spriteId)
    x2 = x1 + getSpriteWidth(p[a].spriteId)
    y2 = y1 + getSpriteHeight(p[a].spriteId)
  
    x3 = getSpriteX(p[b].spriteId)
    y3 = getSpriteY(p[b].spriteId)
    x4 = x3 + getSpriteWidth(p[b].spriteId)
    y4 = y3 + getSpriteHeight(p[b].spriteId)
     
    // bounding boxes around sprites
    c = 0xFFFFFF
    `drawBox(x1,y1,x2,y2,c,c,c,c,0)
    `drawBox(x3,y3,x4,y4,c,c,c,c,0)
  
    // check bounding box overlap
    if x3 < x2 and x4 > x1 and y3 < y2 and y4 > y1
        // Get intersecting rectangle
        r as Rectangle
        r = getIntersection(x1,y1,x2,y2,x3,y3,x4,y4)
          
        x1 = r.x-x1
        y1 = r.y-y1
          
        x3 = r.x - x3
        y3 = r.y - y3
          
        aWidth = getSpriteWidth(p[a].spriteId)
        bWidth = getSpriteWidth(p[b].spriteId)
         
        // show intersection box
        c = 0xFFFF00
        //drawBox(r.x, r.y, r.x+r.width, r.y+r.height,c,c,c,c,0)
        


	c1 = 0xFFFFFF
	c2 = 0xFF0000
	c3 = 0x0000FF
	
	// Show what parts of the image are being checked
        for y = 0 to r.height-1
            for x = 0 to r.width-1
                aPos = (y1+y)*aWidth + x1+x
                bPos = (y3+y)*bWidth + x3+x
                if getPixelMatrixValue(p[a], aPos)=1 then drawBox(x+100, y+100, x+101, y+101,c1,c1,c1,c1,1)
		if getPixelMatrixValue(p[b], bPos)=1 then drawBox(x+100, y+100, x+101, y+101,c2,c2,c2,c2,1)

		cx = r.x+x
		cy = r.y+y
		if getPixelMatrixValue(p[a], aPos)=1 and getPixelMatrixValue(p[b], bPos)=1 then drawBox(cx,cy,cx+1,cy+1,c3,c3,c3,c3,1)
            next x
        next y


        
	// Check for overlapping collision 
        for y = 0 to r.height-1
            for x = 0 to r.width-1
                aPos = (y1+y)*aWidth + x1+x
                bPos = (y3+y)*bWidth + x3+x
                if getPixelMatrixValue(p[a], aPos)=1 and getPixelMatrixValue(p[b], bPos)=1 then exitfunction 1
            next x
        next y
          
    endif
  
endfunction 0
 
 
  
  
function getIntersection(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2)
    left   = max(ax1, bx1)
    top    = max(ay1, by1)
    right  = min(ax2, bx2)
    bottom = min(ay2, by2)
  
 
    r as Rectangle
  
    r.x = left
    r.y = top
    r.width = 0
    r.height = 0
    if right > left then r.width = right - left
    if bottom > top then r.height = bottom - top
      
endfunction r
  
  
  
function addPixelCollision(p ref as PixelCollision[], sprite as integer)
      
    img = getSpriteImageID(sprite)
  
    collisionMatrixSize = ceil((getImageWidth(img) * getImageHeight(img)) / 8)
  
    x as PixelCollision
    x.spriteId = sprite
    x.matrix.length = collisionMatrixSize
  
  
    m = createMemblockFromImage(img)
     
     
     
 
     
    bit = 0
    for i = 12 to getMemblockSize(m)-4 step 4
        if getMemblockByte(m, i+3) > 0
            setPixelMatrixValue(x, bit, 1)
        endif
        inc bit
    next i
  
    x.m = m
     
    `deleteMemblock(m)
  
  
    p.insert(x)
endfunction p.length
  
  
  
  
  
function setPixelMatrixValue(p ref as PixelCollision, bit, bool)
    i = floor(bit / 8)
    b = bit - i*8
  
    p.matrix[i] = p.matrix[i] || (1 << b)
endfunction
  
  
  
  
  
function getPixelMatrixValue(p as PixelCollision, bit)
    i = floor(bit / 8)
    b = bit - i*8
    value = (p.matrix[i] >> b) && 1
endfunction value
 
 
 
function max(a, b)
    if a > b then exitfunction a
endfunction b
 
function min(a, b)
    if a < b then exitfunction a
endfunction b

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

Back to top

Profile PM Email Website

damothegreat

User Banned

Posted: 5th Apr 2017 15:28

Link

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

Back to top

Profile

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 5th Apr 2017 16:21

Link

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

Back to top

Profile PM Email Website

damothegreat

User Banned

Posted: 5th Apr 2017 17:28

Link

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

Back to top

Profile

damothegreat

User Banned

Posted: 5th Apr 2017 18:29

Link

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

Back to top

Profile

damothegreat

User Banned

Posted: 5th Apr 2017 20:44

Link

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

Back to top

Profile

damothegreat

User Banned

Posted: 5th Apr 2017 21:05

Link

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

Back to top

Profile

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 5th Apr 2017 22:54

Link

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

Back to top

Profile PM Email Website

damothegreat

User Banned

Posted: 5th Apr 2017 22:59

Link

Thanks for that Phealax

Don't work too hard. and hope your colleague gets well soon

Back to top

Profile

blink0k

Moderator

11

Years of Service

User Offline

Joined: 22nd Feb 2013

Location: the land of oz

Posted: 6th Apr 2017 00:57

Link

Hey Phelax, does that code accommodate rotation and scaling?

Back to top

Profile PM

damothegreat

User Banned

Posted: 6th Apr 2017 01:04

Link

it seems I'm non existent - ban me....I am not returning

Back to top

Profile

blink0k

Moderator

11

Years of Service

User Offline

Joined: 22nd Feb 2013

Location: the land of oz

Posted: 6th Apr 2017 01:20

Link

Sorry about that damo. Didn't mean to offend. My apologies

Back to top

Profile PM

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 6th Apr 2017 02:19 Edited at: 6th Apr 2017 02:58

Link

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:

+ Code Snippet


#include 'PixelMagic.agc'


dude1 as pixelMagic_PixelSprite 
dude2 as pixelMagic_PixelSprite 

dude1 = pixelMagic_createPixelSprite(createSprite(loadImage("dude1.png")))
dude2 = pixelMagic_createPixelSprite(createSprite(loadImage("dude2.png")))



setSpritePosition(dude1.spriteId, 300, 200)


setClearColor(92,92,92)



do



    setSpritePosition(dude2.spriteId, getRawMouseX(), getRawMouseY())
    
    result = pixelMagic_spriteHit(dude1, dude2)
    print(result)

    Print( ScreenFPS() )
    Sync()
loop

PixelMagic.agc

Type pixelMagic_Rectangle
    x as integer
    y as integer
    width as integer
    height as integer
EndType
 
 
 
Type pixelMagic_PixelSprite
    spriteId as integer
    mask as integer[]
EndType

function pixelMagic_spriteHit(a as pixelMagic_PixelSprite, b as pixelMagic_PixelSprite)
     
     
    x1 = getSpriteX(a.spriteId)
    y1 = getSpriteY(a.spriteId)
    x2 = x1 + getSpriteWidth(a.spriteId)
    y2 = y1 + getSpriteHeight(a.spriteId)
   
    x3 = getSpriteX(b.spriteId)
    y3 = getSpriteY(b.spriteId)
    x4 = x3 + getSpriteWidth(b.spriteId)
    y4 = y3 + getSpriteHeight(b.spriteId)
     
   
    // check bounding box overlap
    if x3 < x2 and x4 > x1 and y3 < y2 and y4 > y1
        // Get intersecting rectangle
        r as pixelMagic_Rectangle
        r = pixelMagic_getIntersection(x1,y1,x2,y2, x3,y3,x4,y4)
         
           
        x1 = r.x-x1
        y1 = r.y-y1
           
        x3 = r.x - x3
        y3 = r.y - y3
           
        aWidth = getSpriteWidth(a.spriteId)
        bWidth = getSpriteWidth(b.spriteId)
         
         // check for collision
        for y = 0 to r.height-1
            for x = 0 to r.width-1
                aPos = (y1+y)*aWidth + x1+x
                bPos = (y3+y)*bWidth + x3+x
 
                if pixelMagic_getPixelMaskValue(a, aPos)=1 and pixelMagic_getPixelMaskValue(b, bPos)=1 then exitfunction 1
            next x
        next y
           
    endif
   
endfunction 0
 
 
 
function pixelMagic_createPixelSprite(sprite as integer)
    p as pixelMagic_PixelSprite
    p.spriteId = sprite
     
    img = getSpriteImageID(sprite)
   
    maskSize = ceil((getImageWidth(img) * getImageHeight(img)) / 8)
   
    p.mask.length = maskSize
   
   
    m = createMemblockFromImage(img)
      
    bit = 0
    for i = 12 to getMemblockSize(m)-4 step 4
        if getMemblockByte(m, i+3) > 0
            pixelMagic_setPixelMaskValue(p, bit, 1)
        endif
        inc bit
    next i
      
    deleteMemblock(m)
   
endfunction p
 
 
 
function pixelMagic_setPixelMaskValue(p ref as pixelMagic_PixelSprite, bit, bool)
    i = floor(bit / 8)
    b = bit - i*8
   
    p.mask[i] = p.mask[i] || (1 << b)
endfunction
 
 
 
function pixelMagic_getPixelMaskValue(p as pixelMagic_PixelSprite, bit)
    i = floor(bit / 8)
    b = bit - i*8
    value = (p.mask[i] >> b) && 1
endfunction value
 
 
 
function pixelMagic_getIntersection(ax1 as integer, ay1 as integer, ax2 as integer, ay2 as integer, bx1 as integer, by1 as integer, bx2 as integer, by2 as integer)
    left   = pixelMagic_max(ax1, bx1)
    top    = pixelMagic_max(ay1, by1)
    right  = pixelMagic_min(ax2, bx2)
    bottom = pixelMagic_min(ay2, by2)
 
    r as pixelMagic_Rectangle
 
    r.x = left
    r.y = top
    r.width = 0
    r.height = 0
    if right > left then r.width = right - left
    if bottom > top then r.height = bottom - top
endfunction r
 
 
 
function pixelMagic_max(a as integer, b as integer)
    if a > b then exitfunction a
endfunction b
 
 
 
function pixelMagic_min(a as integer, b as integer)
    if a < b then exitfunction a
endfunction b

+ Code Snippet

Type pixelMagic_Rectangle
    x as integer
    y as integer
    width as integer
    height as integer
EndType
 
 
 
Type pixelMagic_PixelSprite
    spriteId as integer
    mask as integer[]
EndType


function pixelMagic_spriteHit(a as pixelMagic_PixelSprite, b as pixelMagic_PixelSprite)
     
     
    x1 = getSpriteX(a.spriteId)
    y1 = getSpriteY(a.spriteId)
    x2 = x1 + getSpriteWidth(a.spriteId)
    y2 = y1 + getSpriteHeight(a.spriteId)
   
    x3 = getSpriteX(b.spriteId)
    y3 = getSpriteY(b.spriteId)
    x4 = x3 + getSpriteWidth(b.spriteId)
    y4 = y3 + getSpriteHeight(b.spriteId)
     
   
    // check bounding box overlap
    if x3 < x2 and x4 > x1 and y3 < y2 and y4 > y1
        // Get intersecting rectangle
        r as pixelMagic_Rectangle
        r = pixelMagic_getIntersection(x1,y1,x2,y2, x3,y3,x4,y4)
         
           
        x1 = r.x-x1
        y1 = r.y-y1
           
        x3 = r.x - x3
        y3 = r.y - y3
           
        aWidth = getSpriteWidth(a.spriteId)
        bWidth = getSpriteWidth(b.spriteId)
         
         // check for collision
        for y = 0 to r.height-1
            for x = 0 to r.width-1
                aPos = (y1+y)*aWidth + x1+x
                bPos = (y3+y)*bWidth + x3+x
 
                if pixelMagic_getPixelMaskValue(a, aPos)=1 and pixelMagic_getPixelMaskValue(b, bPos)=1 then exitfunction 1
            next x
        next y
           
    endif
   
endfunction 0
 
 
 
function pixelMagic_createPixelSprite(sprite as integer)
    p as pixelMagic_PixelSprite
    p.spriteId = sprite
     
    img = getSpriteImageID(sprite)
   
    maskSize = ceil((getImageWidth(img) * getImageHeight(img)) / 8)
   
    p.mask.length = maskSize
   
   
    m = createMemblockFromImage(img)
      
    bit = 0
    for i = 12 to getMemblockSize(m)-4 step 4
        if getMemblockByte(m, i+3) > 0
            pixelMagic_setPixelMaskValue(p, bit, 1)
        endif
        inc bit
    next i
      
    deleteMemblock(m)
   
endfunction p
 
 
 
function pixelMagic_setPixelMaskValue(p ref as pixelMagic_PixelSprite, bit, bool)
    i = floor(bit / 8)
    b = bit - i*8
   
    p.mask[i] = p.mask[i] || (1 << b)
endfunction
 
 
 
function pixelMagic_getPixelMaskValue(p as pixelMagic_PixelSprite, bit)
    i = floor(bit / 8)
    b = bit - i*8
    value = (p.mask[i] >> b) && 1
endfunction value
 
 
 
function pixelMagic_getIntersection(ax1 as integer, ay1 as integer, ax2 as integer, ay2 as integer, bx1 as integer, by1 as integer, bx2 as integer, by2 as integer)
    left   = pixelMagic_max(ax1, bx1)
    top    = pixelMagic_max(ay1, by1)
    right  = pixelMagic_min(ax2, bx2)
    bottom = pixelMagic_min(ay2, by2)
 
    r as pixelMagic_Rectangle
 
    r.x = left
    r.y = top
    r.width = 0
    r.height = 0
    if right > left then r.width = right - left
    if bottom > top then r.height = bottom - top
endfunction r
 
 
 
function pixelMagic_max(a as integer, b as integer)
    if a > b then exitfunction a
endfunction b
 
 
 
function pixelMagic_min(a as integer, b as integer)
    if a < b then exitfunction a
endfunction b

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

Back to top

Profile PM Email Website

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 6th Apr 2017 04:29 Edited at: 6th Apr 2017 06:39

Link

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

Back to top

Profile PM Email Website

blink0k

Moderator

11

Years of Service

User Offline

Joined: 22nd Feb 2013

Location: the land of oz

Posted: 7th Apr 2017 10:01

Link

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

Back to top

Profile PM

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 8th Apr 2017 01:57 Edited at: 8th Apr 2017 02:01

Link

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

Back to top

Profile PM Email Website

Sorry your browser is not supported!

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

Attachments

Attachments

Attachments

Attachments