error doing image collision detection with _MemGet

[madscijr]

The point of the method I used was that it doesn't loop pixel by pixel, doesn't use fancy math, and it works detecting pixel perfect collisions for 2 objects of the same color.

[bplus]

And just how does it detect "pixel perfect collisions" without testing pixel by pixel?

I am asssuming we are talking irregular shapes because circles and rectangles are a piece of cake for collision detection. If this is not the case then this topic is hardly interesting.

[SMcNeill]

' Steve's code appears to search whole screen pixel by pixel plus some??? 679?

For x = 0 To 799: For y = 0 To 679 'detect collisions

Hmm...looks to me like you are going the whole screen pixel by pixel for collisions and why, BTW, 679? typo?

I think checking for a box collision of images contained by rectangles before going pixel by pixel would save scads of time.  Box collisions are pretty easy to test and save you from searching the whole screen, brute force.
ie, if no box collision then no need to test a single pixel!!!

Aye, I was somehow thinking the screen was 680 when I hobbled this together.  (think 480 for a lot of junk, and 600 for this junk, and 2AM lack of coffee...) 

One advantage to doing something like this is you only need to read the screen once and you update it for all your objects.  Depending on the number of boxes you have, you may be running into a lot more comparisons than that.  10 boxes and you'd check box 1 against the other 9... then check box 2 against the other 8... then check box 3 against the other 7....    

With a screen that could have dozens of mobs (space invaders) and dozens of bullets (them shooting at you and you shooting back) and the shields you can hide behind and everything else, that could end up being a crapload of rectangles and such to check for possible collisions.  Doing as I did here, it's a non-scaling method which is great for keeping program FPS constant.  If you can read the screen with 1 enemy and keep the FPS you want, you can read it with 1000 enemies and keep the FPS you want.  (Well, unless something else affects the FPS such as draw times and such; the point is, your collision detection time would remain static for you.)

And remember, we're not really doing BOX collisions here.  We're doing full pixel-by-pixel collisions.  Whatever your sprite is, as long as it has a clear (0 alpha) background, you'll be able to detect a collision, whether it's shaped like a box or Clippy the Windows Assistant!   

[madscijr]

I'm not at the PC right now, but definitely will play with your example. I still don't see how it will work with 2 objects of the same color. I will reserve judgment. 

As for the scenario like Space Invaders, I would use a simple less accurate test first, to see if objects are near each other, then if they are, resort to checking for collisions with the memory compare intersect method. 

As a challenge, this just might inspire me to actually make a Super Invaders game, LoL!

Stay tuned!

[bplus]

' Steve's code appears to search whole screen pixel by pixel plus some??? 679?

For x = 0 To 799: For y = 0 To 679 'detect collisions

Hmm...looks to me like you are going the whole screen pixel by pixel for collisions and why, BTW, 679? typo?

I think checking for a box collision of images contained by rectangles before going pixel by pixel would save scads of time.  Box collisions are pretty easy to test and save you from searching the whole screen, brute force.
ie, if no box collision then no need to test a single pixel!!!

Aye, I was somehow thinking the screen was 680 when I hobbled this together.  (think 480 for a lot of junk, and 600 for this junk, and 2AM lack of coffee...) 

One advantage to doing something like this is you only need to read the screen once and you update it for all your objects.  Depending on the number of boxes you have, you may be running into a lot more comparisons than that.  10 boxes and you'd check box 1 against the other 9... then check box 2 against the other 8... then check box 3 against the other 7....    

With a screen that could have dozens of mobs (space invaders) and dozens of bullets (them shooting at you and you shooting back) and the shields you can hide behind and everything else, that could end up being a crapload of rectangles and such to check for possible collisions.  Doing as I did here, it's a non-scaling method which is great for keeping program FPS constant.  If you can read the screen with 1 enemy and keep the FPS you want, you can read it with 1000 enemies and keep the FPS you want.  (Well, unless something else affects the FPS such as draw times and such; the point is, your collision detection time would remain static for you.)

And remember, we're not really doing BOX collisions here.  We're doing full pixel-by-pixel collisions.  Whatever your sprite is, as long as it has a clear (0 alpha) background, you'll be able to detect a collision, whether it's shaped like a box or Clippy the Windows Assistant!   

OK I concede if you are checking collision of all sprites =n with each other the amount of checks becomes expodential as n inreases but if its just all sprites to the hero sprite then linear ie n-1 checks and would take a hell of allot other sprites to become less effiecient than pixel by pixel of whole screen. Also a likely positive the checking time remains constant for whole screen pixel by pixel method if you can stand the time of a single check of the screen  

For Star Invaders just use rectangular collisions or circle collision of centers of images, will be quite satisfactory if you ask me.

[SMcNeill]

I'm not at the PC right now, but definitely will play with your example. I still don't see how it will work with 2 objects of the same color. I will reserve judgment. 

As for the scenario like Space Invaders, I would use a simple less accurate test first, to see if objects are near each other, then if they are, resort to checking for collisions with the memory compare intersect method. 

As a challenge, this just might inspire me to actually make a Super Invaders game, LoL!

Stay tuned!

Two objects of the same color, and again this is not bound by rectangles, circles, polygon, or triangle checking:

Code: (Select All)

$Color:32

Screen _NewImage(800, 600, 32): collision = _NewImage(800, 600, 32)



box1 = _NewImage(100, 100, 32): box1mask = _NewImage(100, 100, 32)

box2 = _NewImage(100, 100, 32): box2mask = _NewImage(100, 100, 32)

Cls , Red, box1: Cls , _RGBA32(128, 0, 0, 128), box1mask

Cls , Red, box2: Cls , _RGBA32(0, 0, 128, 128), box2mask



bx(1) = 350: by(1) = 250 'one box stationary in the middle of the screen

_Source collision

Dim p As _Unsigned Long



Do

    Cls , 0: Cls , 0, collision

    If _KeyDown(19200) Then bx(0) = bx(0) - 1: If bx(0) < 0 Then bx(0) = 0

    If _KeyDown(19712) Then bx(0) = bx(0) + 1: If bx(0) > 700 Then bx(0) = 700

    If _KeyDown(18432) Then by(0) = by(0) - 1: If by(0) < 0 Then by(0) = 0

    If _KeyDown(20480) Then by(0) = by(0) + 1: If by(0) > 500 Then by(0) = 500



    _PutImage (bx(0), by(0)), box1: _PutImage (bx(0), by(0)), box1mask, collision

    _PutImage (bx(1), by(1)), box2: _PutImage (bx(1), by(1)), box2mask, collision

    crash = 0

    For x = bx(0) To bx(0) + 99: For y = by(0) To by(0) + 99

            p = Point(x, y): If _Red32(p) <> 0 And _Blue32(p) <> 0 Then crash = -1

    Next y, x

    If crash Then Print "COLLISON!"

    _Limit 60

    _Display

Loop

We have a red box, and we have a red box, and we're checking for collision using a simple color compare.  Quick and easy to implement and usually fast enough for most needs that I've seen with folks having here on the forums.

Are there better methods out there?  Sure, but look at the examples posted.  Unseen's demo was over 1000 lines of code, if I'm remembering correctly.  This is something like 30ish.  It's quick to write, easy to understand, and simple to maintain and update over time.  

Just like a BubbleSort is suitable and easily coded for most cases, this type of simple color detection will work in a ton of cases.  And who cares if the process takes 0.00001 second or 0.0001 second?  My guess is, if you THINK you're going to have trouble with runtime for collision detection, then you ARE going to have issues with display/rendering time of the graphics to begin with.  It takes much longer to draw and display the graphics than it does anything else.

[Unseen Machine]

Seems legit to me, same approach as bit masking but it still requires double rendering and POINT analysis..surely thats quite a performance hit when dealing with multiple objects? 

And yes, my code has grown a little, but its' very encompassing and to use it the user would only need 

Code: (Select All)

CONST GDK_SHAPE_CIRCLE = 1

CONST GDK_SHAPE_BOX = 2

CONST GDK_SHAPE_TRIANGLE = 3

CONST GDK_SHAPE_POLYGON = 4



CONST GDK_Vector_Size = 8

CONST GDK_TRUE = -1, GDK_FALSE = 0

SCREEN _NEWIMAGE(800, 600, 32)

_SCREENMOVE 0, 0

_DELAY 1



'///////////////////////////////////////////////////////////////////////////////////////////////////////////////



CONST MAX_SHAPES = 40

CONST FLASH_TIME = 0.25



DIM SHARED Shapes(MAX_SHAPES) AS GDK_Shape



DIM SHARED GT#, LastGT#

GT# = TIMER(.001): LastGT# = GT#



InitShapes '// Define youre collision shapes

'//////////////////////////////////////// Main Loop ////////////////////////////////////////////////////////////

DO

  _LIMIT 60

  _FPS 60



  GT# = TIMER(.001)

  dt = GT# - LastGT#

  UpdateShapes dt 

  HandleAllCollisions



  LINE (0, 0)-(_WIDTH, _HEIGHT), _RGBA32(0, 0, 0, 20), BF



  RenderShapes



  _DISPLAY

  LastGT# = GT#

LOOP UNTIL INKEY$ = CHR$(27)



SYSTEM

Happy coding folks.

Unseen

[madscijr]

And just how does it detect "pixel perfect collisions" without testing pixel by pixel?

I am asssuming we are talking irregular shapes because circles and rectangles are a piece of cake for collision detection. If this is not the case then this topic is hardly interesting.

Take a look at the code - we do a mem compare to see if the mask of sprite #1 (black pixels) differs in any way with the copy overlaid with any of the mask of sprite #2 (white pixels) layer overlaid over it.
No looping.
Note that we erase the background around sprite #1, so that only intersecting pixels at sprinte #1's location are possible to detect.

Two objects of the same color, and again this is not bound by rectangles, circles, polygon, or triangle checking:
...
Are there better methods out there?  Sure, but look at the examples posted.  Unseen's demo was over 1000 lines of code, if I'm remembering correctly.  This is something like 30ish.  It's quick to write, easy to understand, and simple to maintain and update over time.  
...
Just like a BubbleSort is suitable and easily coded for most cases, this type of simple color detection will work in a ton of cases.  And who cares if the process takes 0.00001 second or 0.0001 second?  My guess is, if you THINK you're going to have trouble with runtime for collision detection, then you ARE going to have issues with display/rendering time of the graphics to begin with.  It takes much longer to draw and display the graphics than it does anything else.

But see, you're looping and checking pixel by pixel. The whole point of this exercise is to leverage the power of direct memory compare, to avoid that, but still achieve pixel perfect collision detection, even between objects of the same color, of any size.

I do agree with the value of easy to maintain and update over time. I know my sloppy demo is not a model for that, but point well taken.

[Unseen Machine]

As youre going with simpler collision detection methods for now (wise idea in my box) I knocked this up for you...never know it might come in handy!

Code: (Select All)

'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

'// Radius and Non Rotated Rectangle collision detection Types, Subs and Functions \\

'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



RANDOMIZE TIMER

CONST NUM_OBJECTS = 10

SCREEN _NEWIMAGE(800, 600, 32)



DIM Entities(NUM_OBJECTS - 1) AS GameEntity

DIM Circles(NUM_OBJECTS - 1) AS Collision_Circle

DIM Boxes(NUM_OBJECTS - 1) AS Collision_Box



CreateObjects Entities(), Circles(), Boxes(), NUM_OBJECTS



DO

  _LIMIT 60

  CLS



  UpdateAndCollide Entities(), Circles(), Boxes(), NUM_OBJECTS

  RenderObjects Entities(), Circles(), Boxes(), NUM_OBJECTS



  _DISPLAY

LOOP



'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

'// This type is just to demo the usage, a simple representation of a generic game entity

'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



TYPE GameEntity

  X AS SINGLE

  Y AS SINGLE

  Rotation AS SINGLE

  Speed AS SINGLE

  IsColliding AS INTEGER

  EntityType AS INTEGER ' 0 = Circle, 1 = Box

END TYPE



'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



TYPE Collision_Box

  X AS SINGLE

  Y AS SINGLE

  W AS SINGLE

  H AS SINGLE

END TYPE



TYPE Collision_Circle

  X AS SINGLE

  Y AS SINGLE

  Radius AS SINGLE

END TYPE



'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



SUB Collision_Circle_New (Circ AS Collision_Circle, x, y, radius)

  Circ.X = x

  Circ.Y = y

  Circ.Radius = radius

END SUB



'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



FUNCTION Collision_Circle_Hit% (Circ1 AS Collision_Circle, Circ2 AS Collision_Circle)

  distSq = (Circ1.X - Circ2.X) ^ 2 + (Circ1.Y - Circ2.Y) ^ 2

  radiusSum = (Circ1.Radius + Circ2.Radius) ^ 2 ' Calculate the squared sum of the radii

  ' If the distance squared is less than or equal to the radii sum squared, they are colliding

  IF distSq <= radiusSum THEN Collision_Circle_Hit = -1 ELSE Collision_Circle_Hit = 0

END FUNCTION



'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



SUB Collision_Box_New (Box AS Collision_Box, x, y, w, h)

  Box.X = x

  Box.Y = y

  Box.W = w

  Box.H = h

END SUB



'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



FUNCTION Collision_Box_Hit% (Box1 AS Collision_Box, Box2 AS Collision_Box)

    IF Box1.X < Box2.X + Box2.W AND _

      Box1.X + Box1.W > Box2.X AND _

      Box1.Y < Box2.Y + Box2.H AND _

      Box1.Y + Box1.H > Box2.Y THEN

    Collision_Box_Hit = -1

  ELSE

    Collision_Box_Hit = 0

  END IF

END FUNCTION



'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



FUNCTION Collision_Circle_Box_Hit% (Circ AS Collision_Circle, Box AS Collision_Box)



  ' Find the closest point on the box to the circle's center

  ' Clamp the circle's center point to the box's dimensions

  testX = Circ.X

  testY = Circ.Y



  IF Circ.X < Box.X THEN

    testX = Box.X

  ELSEIF Circ.X > Box.X + Box.W THEN

    testX = Box.X + Box.W

  END IF



  IF Circ.Y < Box.Y THEN

    testY = Box.Y

  ELSEIF Circ.Y > Box.Y + Box.H THEN

    testY = Box.Y + Box.H

  END IF



  ' Calculate the squared distance from the closest point to the circle's center

  distSq = (Circ.X - testX) ^ 2 + (Circ.Y - testY) ^ 2



  ' Check if the squared distance is less than the squared radius

  IF distSq <= Circ.Radius ^ 2 THEN

    Collision_Circle_Box_Hit = -1

  ELSE

    Collision_Circle_Box_Hit = 0

  END IF

END FUNCTION



'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

'// The following is to demo usage...

'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



SUB CreateObjects (Entities() AS GameEntity, Circles() AS Collision_Circle, Boxes() AS Collision_Box, num)



  DIM i AS INTEGER

  FOR i = 0 TO num - 1

    ' Set entity's movement and collision status

    Entities(i).X = RND * 700 + 50

    Entities(i).Y = RND * 500 + 50

    Entities(i).Rotation = RND * (2 * _PI)

    Entities(i).Speed = RND * 2 + 1

    Entities(i).IsColliding = 0



    ' Randomly choose between a circle or a box

    IF RND > 0.5 THEN

      ' Create a circle entity

      Entities(i).EntityType = 0

      Circles(i).X = Entities(i).X

      Circles(i).Y = Entities(i).Y

      Circles(i).Radius = RND * 15 + 10

    ELSE

      ' Create a box entity

      Entities(i).EntityType = 1

      Boxes(i).X = Entities(i).X

      Boxes(i).Y = Entities(i).Y

      Boxes(i).W = RND * 20 + 20

      Boxes(i).H = RND * 20 + 20

    END IF

  NEXT i

END SUB



'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



SUB UpdateAndCollide (Entities() AS GameEntity, Circles() AS Collision_Circle, Boxes() AS Collision_Box, num)

  DIM i, j AS INTEGER

  DIM screenW AS LONG: screenW = _WIDTH

  DIM screenH AS LONG: screenH = _HEIGHT

  DIM dx AS SINGLE, dy AS SINGLE

  DIM hit AS INTEGER



  ' Reset collision flags

  FOR i = 0 TO num - 1

    Entities(i).IsColliding = 0

  NEXT i





  ' Update positions using vectors (speed and rotation)

  FOR i = 0 TO num - 1

    ' Convert rotation and speed to DX/DY vector components

    dx = COS(Entities(i).Rotation) * Entities(i).Speed

    dy = SIN(Entities(i).Rotation) * Entities(i).Speed



    ' Update position

    Entities(i).X = Entities(i).X + dx

    Entities(i).Y = Entities(i).Y + dy



    ' Update collision shape coordinates to match the entity

    IF Entities(i).EntityType = 0 THEN

      Circles(i).X = Entities(i).X

      Circles(i).Y = Entities(i).Y

    ELSE

      Boxes(i).X = Entities(i).X

      Boxes(i).Y = Entities(i).Y

    END IF



    ' Bounce off screen edges

    IF Entities(i).EntityType = 0 THEN ' Circle

      IF Entities(i).X - Circles(i).Radius < 0 OR Entities(i).X + Circles(i).Radius > screenW THEN

        Entities(i).Rotation = _PI - Entities(i).Rotation

      END IF

      IF Entities(i).Y - Circles(i).Radius < 0 OR Entities(i).Y + Circles(i).Radius > screenH THEN

        Entities(i).Rotation = _PI + _PI - Entities(i).Rotation

      END IF

    ELSE ' Box

      IF Entities(i).X < 0 OR Entities(i).X + Boxes(i).W > screenW THEN

        Entities(i).Rotation = _PI - Entities(i).Rotation

      END IF

      IF Entities(i).Y < 0 OR Entities(i).Y + Boxes(i).H > screenH THEN

        Entities(i).Rotation = _PI + _PI - Entities(i).Rotation

      END IF

    END IF

  NEXT i



  ' Check for object-to-object collisions

  FOR i = 0 TO num - 1

    FOR j = i + 1 TO num - 1



      hit = 0



      ' Case: Circle-Circle

      IF Entities(i).EntityType = 0 AND Entities(j).EntityType = 0 THEN

        IF Collision_Circle_Hit(Circles(i), Circles(j)) THEN hit = -1



        ' Case: Box-Box

      ELSEIF Entities(i).EntityType = 1 AND Entities(j).EntityType = 1 THEN

        IF Collision_Box_Hit(Boxes(i), Boxes(j)) THEN hit = -1



        ' Case: Circle-Box (i is circle, j is box)

      ELSEIF Entities(i).EntityType = 0 AND Entities(j).EntityType = 1 THEN

        IF Collision_Circle_Box_Hit(Circles(i), Boxes(j)) THEN hit = -1



        ' Case: Box-Circle (i is box, j is circle)

      ELSEIF Entities(i).EntityType = 1 AND Entities(j).EntityType = 0 THEN

        IF Collision_Circle_Box_Hit(Circles(j), Boxes(i)) THEN hit = -1

      END IF



      ' Handle collision

      IF hit THEN

        Entities(i).IsColliding = -1

        Entities(j).IsColliding = -1

        SWAP Entities(i).Rotation, Entities(j).Rotation ' Simple rotation swap

        ' Slightly displace the objects to prevent them from getting stuck

        Entities(i).X = Entities(i).X + (dx / 2)

        Entities(i).Y = Entities(i).Y + (dy / 2)

        Entities(j).X = Entities(j).X + (dx / 2)

        Entities(j).Y = Entities(j).Y + (dy / 2)



      END IF

    NEXT j

  NEXT i

END SUB





'///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



SUB RenderObjects (Entities() AS GameEntity, Circles() AS Collision_Circle, Boxes() AS Collision_Box, num)

  DIM i AS INTEGER, shapeColor AS _UNSIGNED LONG



  FOR i = 0 TO num - 1

    IF Entities(i).IsColliding THEN

      shapeColor = _RGB32(255, 0, 0) ' Red if colliding

    ELSE

      shapeColor = _RGB32(0, 255, 0) ' Green otherwise (circles)

    END IF



    IF Entities(i).EntityType = 0 THEN ' Draw Circle

      ' Use entity position for rendering

      cx = Entities(i).X

      cy = Entities(i).Y

      radius = Circles(i).Radius



      CIRCLE (cx, cy), radius, shapeColor

      PAINT (cx, cy), shapeColor, shapeColor

    ELSE ' Draw Box

      IF NOT Entities(i).IsColliding THEN shapeColor = _RGB32(0, 0, 255) ' Blue otherwise (boxes)



      ' Use entity position for rendering

      boxX = Entities(i).X

      boxY = Entities(i).Y

      boxW = Boxes(i).W

      boxH = Boxes(i).H



      LINE (boxX, boxY)-(boxX + boxW, boxY + boxH), shapeColor, BF

    END IF

  NEXT i

END SUB

Happy coding !
Unseen

[madscijr]

Thanks! I'll give it a spin. I do appreciate how helpful everyone has been (even though it may seem like I'm pushing back.)