Polar Collision Module

magic

Active Member
3rd Party Module Dev
3rd Party Tool Dev
Joined
Mar 5, 2018
This is a collision detection module that I created long time ago. The idea come from a question post by someone at stackoverflow.com answer by @Blindman67 about the idea of having fast but almost pixel perfect collision using Polar coordinate.
https://stackoverflow.com/questions/36012563/how-to-do-pixel-perfect-collision-detection-of-two-partially-transparent-images

651


The concept:

Fast almost pixel perfect collision can be achieved by defining the shape of each sprite with a set of polar coordinated. Each coordinate describes the distance from the center (the center is arbitrary but must be inside the sprite) and direction from the center of the furthest most pixel from the center along that direction. The number of coordinates (n) is determined by the circumference of the outermost pixel.

652


Base on the answer by @Blindman67 ,I code this CX module here: https://github.com/zomagic/cerberus_magic/tree/master/magic
Feel free to optimize it :)
 

magic

Active Member
3rd Party Module Dev
3rd Party Tool Dev
Joined
Mar 5, 2018
I tough the the concept is interesting (semi/almost pixel perfect collision). So I coded into CX. Try to see how fast it do the job.
 

MikeHart

Administrator
Staff member
Joined
Jun 19, 2017
Location
Germany
Interesting concept for sure. With your examples, I get a lot of collisions where none should appear or opposite. Is there a function where it renders the collision shape for debugging purposes?

And I understood, that it is also creating sprites to draw the images, right?
 

Rich

Active Member
3rd Party Module Dev
Joined
Sep 9, 2017
I really like optimisations like this.
Cant wait to have a look when i get home
 

magic

Active Member
3rd Party Module Dev
3rd Party Tool Dev
Joined
Mar 5, 2018
I get a lot of collisions where none should appear or opposite
Its not accurate but faster than doing pixel perfect collisions. It suitable for fast game where player can barely discern a pixel.

Good thing is.. it can support transform (scale and rotation) and animated image

Is there a function where it renders the collision
No. But probably can create a sprite during CreatePolarData() for the purpose of debugging.
 

SLotman

Member
Joined
Jul 3, 2017
I once wrote a routine to test if a point was inside a polygon. But it didn't handle scaling or rotation.

Does this generate the polygon automatically from an image? And it handles real time scaling/rotating? If so, this is very interesting, and can have many applications indeed :)
 

magic

Active Member
3rd Party Module Dev
3rd Party Tool Dev
Joined
Mar 5, 2018
Does this generate the polygon automatically from an image?
No. Its generate polar coordinates from the image automatically. It do that in function CreatePolarData(). This function only call once but must be done inside OnRender() due to using ReadPixel(). The function task is to get polar data of all image (every frames if animation) and store in array.
653

It is actually an array of distance (from center).

And it handles real time scaling/rotating?
Yes.

This is how collision is check:
1. First it check normal box collide
2. If true then do a polar checking
a. get distance of both image from centre
654

b. get which polar coordinate to be use (after consider rotation of image above)
655

b. Then get average distances to be use
656

c. Finally add both distance (cyan+magenta) and compare with real distance(yellow)
If more meaning a collision
657


To be able to consider scaling, it just multiply polar length with current scale.
 

SLotman

Member
Joined
Jul 3, 2017
Well, in those images you can see there is a collision and it isn't registered... maybe instead of comparing distances/real distance would be better to just do a line intersection and see where they hit each other and then compare it to the lines 'distance'?

To get the intersection point seems really easy: http://www.pdas.com/lineint.html
 

SLotman

Member
Joined
Jul 3, 2017
If I'm not mistaken, I think that code on that page would translate to something like this:

Code:
Global LineIntersectionX:Float
Global LineIntersectionY:Float

Function LinesIntersectionPoint:Bool(x1:Int, y1:Int, x2:Int, y2:Int, x3:Int, y3:Int, x4:Int, y4:Int)

    Local a1:Int, a2:Int, b1:Int, b2:Int, c1:Int, c2:Int ' Coefficients of line eqns.
    Local denom:Int

    a1 = y2-y1
    b1 = x1-x2
    c1 = x2*y1 - x1*y2  '{ a1*x + b1*y + c1 = 0 is line 1 }
    a2 = y4-y3
    b2 = x3-x4
    c2 = x4*y3 - x3*y4  '{ a2*x + b2*y + c2 = 0 is line 2 }

    denom = a1*b2 - a2*b1
    If denom = 0 Then Return False

    LineIntersectionX = (b1*c2 - b2*c1) / denom
    LineIntersectionY = (a2*c1 - a1*c2) / denom
End Function
So what am I thinking? Get 2 lines, one from each image. Get the intersection point between those. Get distance from intersection point to center of image 1. Get distance of the line from image 1. If distance_line <= distance_intersection, we have a colision.
 

magic

Active Member
3rd Party Module Dev
3rd Party Tool Dev
Joined
Mar 5, 2018
Well, in those images you can see there is a collision and it isn't registered
Yes, I am aware of this problem from the beginning.

658


This method produce good and fast solution on scenario A and B

On case C it fail to recognize a collide. May be we can improve by do a line intersection checking like you suggested
We can check only few line that 90 degree facing the other sprite.
659

In the above image show only 4 set of line to be test.
 
Top Bottom