error doing image collision detection with _MemGet

[Herve]

Oh no — it’s not just tinkering, it’s also an attempt to improve performance. 

Your approach of searching for common pixels in the intersection of bounding boxes is effective, but I face a rapid drop in FPS (17 fps / 40 spiders). 
In the program from post #21 it’s an equivalent technique plus a zoning system to avoid testing all pairs of bounding boxes. FPS is a bit better (from 60 fps / 40 shapes to 17 fps / 130 shapes) but I don’t find that satisfactory. 
In the program from post #29 I abandon the search for common pixels but keep the zoning technique and add polygon intersection testing. It’s much more complicated to set up, but we get much better FPS (60 fps / 120 shapes), although a few detection bugs remain. 

In any case, there’s one thing I completely agree with you on: DIY is fun and I’m not about to stop 

[madscijr]

I know I kind of started this craziness asking questions and trying some crazy methods, but it turns out I got nice fast and accurate detection by pre-populating a 2D bitmask for each object using a basic 2D boolean (_BYTE) array, and checking for simple bounding box overlap, and if yes, find pixel overlap by comparing the bitmask arrays. You can avoid having to check blank rows/columns around the edges by doing a simple edge detect and saving offsets for top / bottom / left / right. I had a demo in the works which turned into a game, which delayed my posting the demo. Things got hella busy, so I haven't had a chance to try these demos y'all have posted. I should get around to running your code and also have something to share in the next couple of days.

[madscijr]

Here's my collision code - see attached "MultiCustomFontsAndCollisions131.bas" for the full working program. 

To run around and shoot things, use the cursor keys and the right Ctrl key. Also it breaks if you choose both the max robots AND max big robots. If you want to see a lot of things moving and colliding, choose 127 robots and 3 or 4 big robots. 

First I'll explain that the graphics / sprites / etc. are all done with custom fixed-width fonts, drawn to the screen with _PrintString. It's possible to do "multicolor" sprites by layering 2 or more characters, so you will see the sprite type has members fgChar, bgChar, fgColor, bgColor, although this demo only really uses fgChar for single color "sprites". All graphics (fonts) are defined in text (makes it easy to edit without ever leaving the code) and are used to generate BDF font files on the fly everytime the program runs (this can be easily changed to only create the files if they're not found in the program folder, but I've been constantly editing and adding graphics so it's just easier to have it regenerate them, and it's fast enough that it doesn't cause any noticeable extra delay when the program starts).

To see the actual graphic definitons for the fonts, search in the code for these routines:

Code: (Select All)

' The base 8x8 font:

Sub GetTileText8x8 (arrTileText() As String)

...

' The special 8x8 character definitionss specific to this program:

Sub GetTileText8x8_Override (arrTileText() As String)

...

' The base 16x16 font:

Sub GetTileText16x16 (arrTileText() As String)

...

' The special 16x16 character definitionss specific to this program:

Sub GetTileText16x16_Override (arrTileText() As String)

...

' The base 32x32 font:

Sub GetTileText32x32 (arrTileText() As String)

...

' The special 32x32 character definitionss specific to this program:

Sub GetTileText32x32_Override (arrTileText() As String)

...

' The base 64x64 font:

Sub GetTileText64x64 (arrTileText() As String)

...

' The special 64x64 character definitionss specific to this program:

Sub GetTileText64x64_Override (arrTileText() As String)

Next, here are a couple UDTs and array definitions the collision detection uses:

Code: (Select All)

' USED BY PlayGame

Type MyFontType

    FontHandle As Long

    Height As Integer

    Width As Integer

    MaxRow As Integer

    MaxCol As Integer

End Type



' USED BY PlayGame

Type PixelInfoType

    pxCount As Long ' pixel count

    x1 As Long ' column first pixel is at

    x2 As Long ' column last pixel is at

    y1 As Long ' row first pixel is at

    y2 As Long ' row last pixel is at

End Type



    ReDim arrFont(0 To 3) As MyFontType '  arrFont(FontIndex) holds font handle, character dimensions, etc., for a custom fixed-width font

    ReDim arrPxInfo(0 To 3, 0 To 255) As PixelInfoType ' arrPxInfo(FontIndex, ChrCode), holds pixel count and edge info for each character 0-255 for 1 or more fonts

    ReDim arrBitMask(0 To 3, 0 To 255, 0 To 63, 0 To 63) As _Byte ' arrBitMask(FontIndex, ChrCode, LocalY, LocalX), holds true/false bitmask array for each character 0-255 for 1 or more fonts

This routine pre-populates the bit mask array for all characters/fonts that gets compared to detect overlapping pixels:

Code: (Select All)

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

' GET PIXEL COUNT + POPULATE BIT MASK ARRAY



' RECEIVES

' FontIndex as Integer = which font (index for arrFont, arrBitMask, arrPxInfo) to populate arrPxInfo & arrBitMask for

' arrFont(0 To 3) As MyFontType ' arrFont(FontIndex) holds font handle, character dimensions, etc., for a custom fixed-width font

' arrPxInfo(0 To 3, 0 To 255) As PixelInfoType ' arrPxInfo(FontIndex, ChrCode), holds pixel count and edge info for each character 0-255 for 1 or more fonts

' arrBitMask(0 To 3, 0 To 255, 0 To 63, 0 To 63) As _Byte ' arrBitMask(FontIndex, ChrCode, LocalY, LocalX), holds true/false bitmask array for each character 0-255 for 1 or more fonts



' FOR EACH CHARACTER:

' IMAGE IS BLANK IF: arrPxInfo(FontIndex, iChar).pxCount = 0

' LEFT-MOST   PIXEL: arrPxInfo(FontIndex, iChar).x1 ' NONE = _Width(MyImage)

' RIGHT-MOST  PIXEL: arrPxInfo(FontIndex, iChar).x2 ' NONE = -1

' TOP-MOST    PIXEL: arrPxInfo(FontIndex, iChar).y1 ' NONE = _Height(MyImage)

' BOTTOM-MOST PIXEL: arrPxInfo(FontIndex, iChar).y2 ' NONE = -1



Sub GetBitMask (FontIndex As Integer, arrFont() As MyFontType, arrPxInfo() As PixelInfoType, arrBitMask() As _Byte)

    Dim MyImage As Long

    Dim iChar As Integer

    Dim y As Integer

    Dim x As Integer

    Dim p1 As _Unsigned Long

    

    ' CREATE TEMP IMAGE

    InitImage MyImage, arrFont(FontIndex).Width, arrFont(FontIndex).Height, _RGBA32(0, 0, 0, 0)

    _Font arrFont(FontIndex).FontHandle ' SWITCH FONT

    _MapUnicode 32 To 32 ' FIX CHAR MAPPING (I WAS GETTING WEIRD CHARACTERS FOR SPACE)

    _MapUnicode 255 To 255 ' FIX CHAR MAPPING SO WE GET CHR$(255)



    ' GET BIT MASK ARRAY + PIXEL COUNT FOR ALL CHARACTER CODES 0-255 FOR THIS FONT

    For iChar = 0 To 255

        _Dest MyImage: Cls , _RGBA32(0, 0, 0, 0)

        Color _RGB32(0, 0, 0), _RGBA32(0, 0, 0, 0)

        _PrintString (0, 0), Chr$(iChar), MyImage



        ' INITIALIZE

        arrPxInfo(FontIndex, iChar).pxCount = 0

        arrPxInfo(FontIndex, iChar).x1 = _Width(MyImage)

        arrPxInfo(FontIndex, iChar).x2 = -1

        arrPxInfo(FontIndex, iChar).y1 = _Height(MyImage)

        arrPxInfo(FontIndex, iChar).y2 = -1

        For y = LBound(arrBitMask, 3) To UBound(arrBitMask, 3)

            For x = LBound(arrBitMask, 4) To UBound(arrBitMask, 4)

                arrBitMask(FontIndex, iChar, y, x) = _FALSE

            Next x

        Next y



        ' COUNT PIXELS + POPULATE BITMASK

        _Source MyImage

        For y = 0 To _Height(MyImage) - 1

            For x = 0 To _Width(MyImage) - 1

                p1 = Point(x, y)

                If _Alpha32(p1) > 0 Then

                    ' FIND EDGES (FIRST PIXEL ALONG TOP+LEFT EDGES + LAST PIXEL AT BOTTOM+RIGHT EDGES)

                    If y < arrPxInfo(FontIndex, iChar).y1 Then arrPxInfo(FontIndex, iChar).y1 = y

                    If y > arrPxInfo(FontIndex, iChar).y2 Then arrPxInfo(FontIndex, iChar).y2 = y

                    If x < arrPxInfo(FontIndex, iChar).x1 Then arrPxInfo(FontIndex, iChar).x1 = x

                    If x > arrPxInfo(FontIndex, iChar).x2 Then arrPxInfo(FontIndex, iChar).x2 = x

                    

                    ' COUNT PIXELS

                    arrPxInfo(FontIndex, iChar).pxCount = arrPxInfo(FontIndex, iChar).pxCount + 1

                    

                    ' MARK LOCATION IN BIT MASK ARRAY

                    arrBitMask(FontIndex, iChar, y, x) = _TRUE

                End If

            Next x

        Next y



    Next iChar



    ' FREE MEMORY

    FreeImage MyImage

End Sub ' GetBitMask

And finally, the collision detection routine:

Code: (Select All)

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

' Detect collision (regular bounding box test + bit mask overlap)



' Checks if the iSprite1's and iSprite2's bounding boxes overlap,

' if they do, compares bitmask arrays to determine if any pixels overlap,

' and returns _TRUE if collision detected or _FALSE if not.



' RECEIVES:

' iSprite1     = index in arrSprite of object #1 to check for collision

' iSprite2     = index in arrSprite of object #2 to check for collision

' arrSprite()  = array of type SpriteType containing the sprite details

' arrBitMask() = byte array containing _TRUE/_FALSE

'                for all pixels of all characters for all fonts

'                (used to check for pixel-perfect collision)



Function ShapesCollided% (iSprite1 As Integer, iSprite2 As Integer, arrSprite() As SpriteType, arrBitMask() As _Byte)

    Dim bCollision As Integer

    Dim iOverlapLeft As Long

    Dim iOverlapTop As Long

    Dim iOverlapRight As Long

    Dim iOverlapBottom As Long

    Dim iX As Long

    Dim iY As Long

    Dim iLocalX1 As Long

    Dim iLocalY1 As Long

    Dim iLocalX2 As Long

    Dim iLocalY2 As Long



    bCollision = _FALSE



    ' =============================================================================

    ' BEGIN CHECK BOUNDARY OVERLAP

    ' =============================================================================

    if ( _

        ((arrSprite(iSprite1).x1 + arrSprite(iSprite1).width) < arrSprite(iSprite2).x1) or _

        ((arrSprite(iSprite2).x1 + arrSprite(iSprite2).width) < arrSprite(iSprite1).x1) or _

        ((arrSprite(iSprite1).y1 + arrSprite(iSprite1).height) < arrSprite(iSprite2).y1) or _

        ((arrSprite(iSprite2).y1 + arrSprite(iSprite2).height) < arrSprite(iSprite1).y1) _

        ) = _FALSE then



        ' -----------------------------------------------------------------------------

        ' BEGIN SEE IF PIXELS OVERLAP

        ' -----------------------------------------------------------------------------

        ' Calculate the overlapping region

        iOverlapLeft = _Max(arrSprite(iSprite1).x1, arrSprite(iSprite2).x1)

        iOverlapTop = _Max(arrSprite(iSprite1).y1, arrSprite(iSprite2).y1)

        iOverlapRight = _Min(arrSprite(iSprite1).x1 + arrSprite(iSprite1).width, arrSprite(iSprite2).x1 + arrSprite(iSprite2).width)

        iOverlapBottom = _Min(arrSprite(iSprite1).y1 + arrSprite(iSprite1).height, arrSprite(iSprite2).y1 + arrSprite(iSprite2).height)



        ' Loop through the overlapping area

        For iY = iOverlapTop To iOverlapBottom - 1

            For iX = iOverlapLeft To iOverlapRight - 1

                ' Get local coordinates for each sprite

                iLocalX1 = iX - arrSprite(iSprite1).x1

                iLocalY1 = iY - arrSprite(iSprite1).y1

                iLocalX2 = iX - arrSprite(iSprite2).x1

                iLocalY2 = iY - arrSprite(iSprite2).y1

                

                ' Check if pixels are opaque in both masks

                If _ 

                    ( _

                        arrBitMask(arrSprite(iSprite1).FontIndex, arrSprite(iSprite1).fgChar, iLocalY1, iLocalX1) = _TRUE _

                        or _

                        arrBitMask(arrSprite(iSprite1).FontIndex, arrSprite(iSprite1).bgChar, iLocalY1, iLocalX1) = _TRUE _

                    ) _

                    And _ 

                    ( _

                        arrBitMask(arrSprite(iSprite2).FontIndex, arrSprite(iSprite2).fgChar, iLocalY2, iLocalX2) = _TRUE _

                        or _

                        arrBitMask(arrSprite(iSprite2).FontIndex, arrSprite(iSprite2).bgChar, iLocalY2, iLocalX2) = _TRUE _ 

                    ) _

                Then

                    

                    ' Collision detected

                    bCollision = _TRUE

                    Exit For

                End If

            Next iX

            If bCollision = _TRUE Then Exit For

        Next iY

        ' -----------------------------------------------------------------------------

        ' END SEE IF PIXELS OVERLAP

        ' -----------------------------------------------------------------------------

    End If

    ' =============================================================================

    ' END CHECK BOUNDARY OVERLAP

    ' =============================================================================



    ShapesCollided% = bCollision

End Function ' ShapesCollided%

Note that I also started playing with shrinking the boundary box by storing the edges for each character (see Sub FindEdges) but I realized it was redundant as GetBitMask was already storing them in x1, x2, y1, y2, and I saw it would be unwieldy to have to keep recalculating, so in the next version I started developing a 2nd version of GetBitMask that generates the bit mask and finds edges for each unique fgChar / bgChar combination. But I didn't need it for this game, and so it's neither here nor there. The point is that when I get to it, it will use the precalculated edges for each character, for the boundary boxes, and thus avoid having to compare empty rows / columns.

Anyway, I had this checking collisions for a few hundred sprites ranging in size from 8x8 upto 64x64 and it was plenty fast.

Attached also is "MultiCustomFontsAndCollisions144.bas" which is the updated version with more developed logic for shooting and players/robots/bullets being shot, and upto 16 players on the screen, where I started adding the updated "find edges" and collision routines for sprites using both fgChar and bgChar. The current part I'm stuck at is that when a robot gets shot, it's supposed to explode, but that animation isn't displaying. I have similar animation when the player gets shot, and that's visible, so I'm not sure what's going on. Also there's a weird bug that happens every so often, where if a player gets shot by another player's bullet, ALL the players die. Very weird.

Try running it and let me know what you think.

[madscijr]

And here are some screenshots...

"MultiCustomFontsAndCollisions131.bas" selecting options:









"MultiCustomFontsAndCollisions131.bas" in action. Currently it draws each sprite's array index next to the given sprite, and a red box appears around any that are colliding.



""MultiCustomFontsAndCollisions144.bas" has simplified options (the robot size is now selected at random, everything from 8x8 upto 64x64 robots):





Currently it reminds me of Robotron:2084 meets Berzerk, but eventually we'll have walls / mazes / etc. once I add any collision with background logic ... 

"MultiCustomFontsAndCollisions144.bas" in action - currently the cursor keys (movement) & right ctrl key (fire) control all the players, players' speeds are chosen at random:

[Herve]

Wow man, amazing work! Redefining the characters must have taken you a long time — I’m impressed!

My Linux setup doesn’t recognize the _button instruction to read the keyboard, so I couldn’t move the player or make them shoot.
Everything else works well: rendering, robot movement, and collision detection are fine.

To gauge performance I added an FPS counter. All tests were done with the default size 3 for the player and robots. I also varied the resolution to see the performance impact (the higher the resolution, the fewer collisions). Results:

• 127 robots and 0 large robots: 38 FPS at 640×480.
  
• 42 FPS at 1024×768.
  
• Lowering to 320×240, it’s impossible to run with 127 robots — the initial placement algorithm loops because it can’t find non-colliding spots for all robots; at that resolution a placement of 100 robots succeeds and gives 40 FPS.
  
• With 0 robots and 100 large robots, performance drops — at 1024×768 we fall to 12 FPS.
  

Finally, to confirm performance depended on the pixel-overlap detection technique, I disabled it and kept only bounding-box detection: at 1024×768 with 127 robots we get 47 FPS, and with 127 large robots 20 FPS. Pixel-perfect detection has a significant cost. It’s fun to dig into, but if your goal is a game with many sprites you should prefer other, more performant techniques.

[madscijr]

Wow man, amazing work! Redefining the characters must have taken you a long time — I’m impressed!

It took some work to initially figure out how to generate BDF files, but I've been building on earlier code and this system has gradually evolved, so at this point it's very little work, which was kind of the goal - to arrive at a simple system that could be used for lots of different projects.

My Linux setup doesn’t recognize the _button instruction to read the keyboard,

Hmm, so _button doesn't work in Linux for the keyboard? I wonder if that's the case for Mac as well?

To gauge performance I added an FPS counter.
...
Finally, to confirm performance depended on the pixel-overlap detection technique, I disabled it and kept only bounding-box detection: at 1024×768 with 127 robots we get 47 FPS, and with 127 large robots 20 FPS.

That sounds really slow for just using bounding box - then again, I'm not known as the most efficient or skilled programmer (there's a reason I call my programs Softintheheadware! LoL) so there could be a million things that could be improved in my code.

Pixel-perfect detection has a significant cost. It’s fun to dig into, but if your goal is a game with many sprites you should prefer other, more performant techniques.

Well, my ultimate goal is just to turn some of my crazy ideas into fun or interesting old school type games that people can enjoy or be inspired by.

I would like to figure out how to improve performance, which I hope the smaller bounding boxes (using the edge detection) will help with.

I'm going to study the examples you and others have left and see if any of that can be applied.

For the collisions I really would prefer a general reusable pixel-perfect technique that works with any characters in those fixed-width fonts, that can be called with a simple function call. Any suggestions?

Also, I realize my code is all over the place and will give Steve and BPlus a headache. Hopefully I'll be able to clean it up & simplify it as time goes on, to make it more maintainable and easier for others to understand & modify.

Anyway, thanks for giving it a try!

[madscijr]

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 \\

...

Pixel-perfect collision detection demo; it was fun to create. There's definitely room for performance improvements.

[qb]' This program demonstrates the application of a collision detection algorithm in 3 steps:
'
' Step 1. Inspecting areas to identify where at least 2 shapes are in.
' Step 2. For each area, checking the distance between the present shapes to determine
'        if they could potentially be in contact.
' Step 3. Testing for overlap in each area where the shapes are potentially in contact
'        using semi-transparent shape masks.
...


Here’s the new program that performs pixel‑perfect detection without using mask techniques; it’s based on polygon intersection calculations.

It handles shapes that are longer than they are wide well. Performance is pretty good (60 FPS for 128 objects on a Raspberry Pi 500). 

There are definitely optimizations to be found. And also need more comments to explain how it works. This could become a library — what do you think?
...
[/qb]

I ran Unseen's program, and Herve's first and second programs (VERY nice work, BTW!)
and have a question for all 3.

They work for these vector shapes - even irregular shapes, in Herve's case - but how would you use these to detect collisions between the raster characters my program is using? Would each characters need to mapped to an equivalent vector shape?

(At some point I think I wrote some code that may have done that, but it's been a couple years, and I don't recall how well it worked...)

Thanks again for sharing these fascinating demos.

[madscijr]

+1 Thankyou @madscijr of reminding me of this delightful little piece of code. As I recall @TerryRitchie got us started on this topic of collision with irregular objects. Thankyou Terry, where the heck are you anyway?

To save people from having to dig this up, here it is AGAIN!

Code: (Select All)

Option _Explicit
_Title "Spiders with Box and Pixel Collisions Experiment 3" 'b+ 2023-01-30/31
' 2023-02-08 Another experiment in handling Spider collisions,
' At collision, explosion!
...

I don't know PixelCollision& looks pretty straight forward. Why get _Mem stuff involved? For speed of course but the above code does work pretty darn good in real time!

+1 @Unseen Machine has an interesting idea how to approach this problem worth investigating, if you can draw a line between two objects without touching either then no collision. But you can draw infinite amounts of lines between 2 objects, not sure how you can narrow it down? Needs study.

BPlus, thanks for sharing this (again), it's very impressive, but I have one major problem - it's way too advanced and/or cryptic.
I can't even see where those spider shapes are defined, how would I modify it to use my own shapes, such as the robots in my demo?

Thanks again

[bplus]

BPlus, thanks for sharing this (again), it's very impressive, but I have one major problem - it's way too advanced and/or cryptic.
I can't even see where those spider shapes are defined, how would I modify it to use my own shapes, such as the robots in my demo?

Honestly I don't remember what I did except carry forward Terry's idea into my own coded app.

Checking if the image boxes intersect is the crucial first step for saving time as opposed to looking for intersects over the whole scren for each image. If two images are going to intersect then certainly their image boxes will. 

OK I will assume you know how to do box or rectangular intersects. 

Now what did we do next?   ...stay tuned for bplus to reread his code.

[madscijr]

Yes, my prog first checks for boundary overlap, then if those intersect, it compared the bitmask arrays of the overlapping areas for overlapping pixels, comparing 2 precalculated 2D boolean (_BYTE) arrays. It's fast enough on my PC but @Herve was citing some low FPS performance testing on their machine (not sure what hardware Herve is running or how they're measuring FPS, plus they're on Linux & I'm on Windows. How fast or slow is my prog on your computer?)

Anyway, I was just curious about the other methods you all use & how those might be applied to my use case. I'm sure my code can also be made faster by updating the test to use the real edges of each shape (which I'm already finding & storing), simplifying the variables instead of using UDTs, using more global vars & less parameter passing, and generally simplifying & cleaning up the logic, which is kinda convoluted.