From this point on the remaining lessons will focus on game programming techniques instead of being tutorial based. Lessons 1 through 14 introduced you to many of the commands needed to get a start in game programming with QB64. It's time to start putting those commands into usable code suitable for making games. The first and most basic concept that most games implement is collision detection. This lesson will investigate four different methods of collision detection; rectangular, circular, pixel perfect, and line intersection.

Rectangular Based Collision Detection

The simplest form of collision detection is if two rectangular areas are overlapping. Many of the earliest games purposely used sprite images that fit into rectangular areas such as 16x16, 32x32, 64x64, or a combination of these such as 32x64. Mario Brothers is a perfect example of this. All sprite images on the screen were created to fit within a 16x16 pixel area and the sprite images themselves were made to take up as much of that area as possible. Figure 1 below shows the Mario Brothers screen divided into a 16x16 grid allowing you to readily see how everything, including the pipe images, platforms, and even the score, fit neatly into this grid.

Note: The original Mario Brothers screen was 256x224 pixels. It has been resized 300% in Figure 1 for clarity.

Only three pieces of information are required from each rectangle to test for rectangular collision; the upper left x,y coordinate, the width, and the height. This made collision detection in early games such as Mario Brothers very easy to achieve. The following code illustrates the use of collision detection between two rectangular objects. Use the mouse to move the red box around on the screen. When it touches the green box a collision is registered.

( This code can be found at .\tutorial\Lesson15\CollisionDemo1.bas )

'** Rectangular Collision Demo

CONST RED = _RGB32(255, 0, 0) '     define colors
CONST GREEN = _RGB32(0, 255, 0)
CONST YELLOW = _RGB32(255, 255, 0)

DIM RedX%, RedY% '                  red box upper left coordinate
DIM GreenX%, GreenY% '              green box upper left coordinate
DIM RedWidth%, RedHeight% '         red box width and height
DIM GreenWidth%, GreenHeight% '     green box width and height
DIM BoxColor~& '                    color of green box

GreenX% = 294 '                     upper left X coordinate of green box
GreenY% = 214 '                     upper left Y coordinate of green box
RedWidth% = 25 '                    width of red box
RedHeight% = 25 '                   height of red box
GreenWidth% = 50 '                  width of green box
GreenHeight% = 50 '                 height of green box
SCREEN _NEWIMAGE(640, 480, 32) '    enter graphics screen
_MOUSEHIDE '                        hide the mouse pointer
DO '                                begin main program loop
   _LIMIT 30 '                      30 frames per second
   CLS '                            clear screen
   WHILE _MOUSEINPUT: WEND '        get latest mouse information
    RedX% = _MOUSEX '               record mouse X location
    RedY% = _MOUSEY '               record mouse Y location

    '** check for collision between two rectangular areas

   IF RectCollide(RedX%, RedY%, RedWidth%, RedHeight%, GreenX%, GreenY%, GreenWidth%, GreenHeight%) THEN
       LOCATE 2, 36 '               position text cursor
       PRINT "COLLISION!" '         report collision happening
        BoxColor~& = YELLOW '       green box will become yellow during collision
   ELSE '                           no collision
        BoxColor~& = GREEN '        green box will be green when no collision
   END IF

    '** draw the two rectangles to screen

   LINE (GreenX%, GreenY%)-(GreenX% + GreenWidth% - 1, GreenY% + GreenHeight% - 1), BoxColor~&, BF
   LINE (RedX%, RedY%)-(RedX% + RedWidth% - 1, RedY% + RedHeight% - 1), RED, BF
   _DISPLAY '                       update screen with changes
LOOP UNTIL _KEYDOWN(27) '           leave when ESC key pressed
SYSTEM '                            return to operating system

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

FUNCTION RectCollide (Rectangle1_x1%, Rectangle1_y1%, Rectangle1Width%, Rectangle1Height%,_
                      Rectangle2_x1%, Rectangle2_y1%, Rectangle2Width%, Rectangle2Height%)
    '--------------------------------------------------------------------------------------------------------
    '- Checks for the collision between two rectangular areas. -
    '- Returns -1 if in collision                              -
    '- Returns  0 if no collision                              -
    '-                                                         -
    '- Rectangle1_x1%    - rectangle 1 upper left X            -
    '- Rectangle1_y1%    - rectangle 1 upper left y            -
    '- Rectangle1Width%  - width  of rectangle 1               -
    '- Rectangle1Height% - height of rectangle 1               -
    '- Rectangle2_x1%    - rectangle 2 upper left X            -
    '- Rectangle2_y1%    - rectangle 2 upper left Y            -
    '- Rectangle2Width%  - width  of rectangle 2               -
    '- Rectangle2Height% - height of rectangle 2               -
    '-----------------------------------------------------------

    '** declare local variables

   DIM Rectangle1_x2% ' rectangle 1 lower right X
   DIM Rectangle1_y2% ' rectangle 1 lower right Y
   DIM Rectangle2_x2% ' rectangle 2 lower right X
   DIM Rectangle2_y2% ' rectangle 2 lower right Y

    '** calculate lower right X,Y coordinate for each rectangle

    Rectangle1_x2% = Rectangle1_x1% + Rectangle1Width% - 1 '  rectangle 1 lower right X
    Rectangle1_y2% = Rectangle1_y1% + Rectangle1Height% - 1 ' rectangle 1 lower right Y
    Rectangle2_x2% = Rectangle2_x1% + Rectangle2Width% - 1 '  rectangle 2 lower right X
    Rectangle2_y2% = Rectangle2_y1% + Rectangle2Height% - 1 ' rectangle 2 lower right Y

    '** test for collision

    RectCollide = 0 '                                     assume no collision
   IF Rectangle1_x2% >= Rectangle2_x1% THEN '             rect 1 lower right X >= rect 2 upper left  X ?
       IF Rectangle1_x1% <= Rectangle2_x2% THEN '         rect 1 upper left  X <= rect 2 lower right X ?
           IF Rectangle1_y2% >= Rectangle2_y1% THEN '     rect 1 lower right Y >= rect 2 upper left  Y ?
               IF Rectangle1_y1% <= Rectangle2_y2% THEN ' rect 1 upper left  Y <= rect 2 lower right Y ?
                    RectCollide = -1 '                    if all 4 IFs true then a collision must be happening
               END IF
           END IF
       END IF
   END IF

END FUNCTION

This example has been highly over coded for readability. Don't let its size intimidate you. The function RectCollide() accepts the upper left x,y coordinate of each rectangle as well the width and height of each one. From there it calculates the lower right x,y coordinate for each rectangle and then performs the collision check. Figures 3 and 4 below show a simplified version of how the collision check is performed using simple IF statements. If all of the IF statements equate to true then there must be a collision. If any of the IF statements equate to false then there can be no collision.

When writing a game you are going to be testing for collisions between multiple images flying around the screen. You are almost always going to use a function to accomplish this as the example above does. There are a number of different ways to achieve this. Using the upper left x,y coordinate, width, and height of each rectangular area, as shown in the previous example, is just one way to test for rectangular collision. Another method, as shown in the next example, is to pass the upper left x,y and lower right x,y coordinates of each rectangular area. With this method the function does not have to calculate the lower right x,y coordinates of each rectangle.

( This code can be found at .\tutorial\Lesson15\CollisionDemo2.bas )

'** Rectangular Collision Demo #2

CONST RED = _RGB32(255, 0, 0) '     define colors
CONST GREEN = _RGB32(0, 255, 0)
CONST YELLOW = _RGB32(255, 255, 0)

TYPE RECT '            rectangle definition
    x1 AS INTEGER '    upper left X
    y1 AS INTEGER '    upper left Y
    x2 AS INTEGER '    lower right X
    y2 AS INTEGER '    lower right Y
END TYPE

DIM RedBox AS RECT '   red rectangle coordinates
DIM GreenBox AS RECT ' green rectangle coordinates
DIM BoxColor~& '       color of green box

GreenBox.x1 = 294 '                         upper left X coordinate of green box
GreenBox.y1 = 214 '                         upper left Y coordinate of green box
GreenBox.x2 = 344 '                         lower right X coordinate of green box
GreenBox.y2 = 264 '                         lower right Y coordinate of green box

SCREEN _NEWIMAGE(640, 480, 32) '            enter graphics screen
_MOUSEHIDE '                                hide the mouse pointer
DO '                                        begin main program loop
   _LIMIT 30 '                              30 frames per second
   CLS '                                    clear screen
   WHILE _MOUSEINPUT: WEND '                get latest mouse information
    RedBox.x1 = _MOUSEX '                   record mouse X location
    RedBox.y1 = _MOUSEY '                   record mouse Y location
    RedBox.x2 = RedBox.x1 + 25 '            calculate lower right X
    RedBox.y2 = RedBox.y1 + 25 '            calculate lower right Y
   IF RectCollide(RedBox, GreenBox) THEN '  rectangle collision?
       LOCATE 2, 36 '                       yes, position text cursor
       PRINT "COLLISION!" '                 report collision happening
        BoxColor~& = YELLOW '               green box will become yellow during collision
   ELSE '                                   no collision
        BoxColor~& = GREEN '                green box will be green when no collision
   END IF
   LINE (GreenBox.x1, GreenBox.y1)-(GreenBox.x2, GreenBox.y2), BoxColor~&, BF ' draw green box
   LINE (RedBox.x1, RedBox.y1)-(RedBox.x2, RedBox.y2), RED, BF '                draw red box
   _DISPLAY '                               update screen with changes
LOOP UNTIL _KEYDOWN(27) '                   leave when ESC key pressed
SYSTEM '                                    return to operating system

'------------------------------------------------------------------------------------------------------------
FUNCTION RectCollide (Rect1 AS RECT, Rect2 AS RECT)
    '--------------------------------------------------------------------------------------------------------
    '- Checks for the collision between two rectangular areas. -
    '- Returns -1 if in collision                              -
    '- Returns  0 if no collision                              -
    '-                                                         -
    '- Rect1 - rectangle 1 coordinates                         -
    '- Rect2 - rectangle 2 coordinates                         -
    '-----------------------------------------------------------

    RectCollide = 0 '                         assume no collision
   IF Rect1.x2 >= Rect2.x1 THEN '             rect 1 lower right X >= rect 2 upper left  X ?
       IF Rect1.x1 <= Rect2.x2 THEN '         rect 1 upper left  X <= rect 2 lower right X ?
           IF Rect1.y2 >= Rect2.y1 THEN '     rect 1 lower right Y >= rect 2 upper left  Y ?
               IF Rect1.y1 <= Rect2.y2 THEN ' rect 1 upper left  Y <= rect 2 lower right Y ?
                    RectCollide = -1 '        if all 4 IFs true then a collision must be happening
               END IF
           END IF
       END IF
   END IF

END FUNCTION

In the second example a TYPE definition is used to define a rectangle structure and that TYPE is passed to the RectCollide() function. Since both the upper left x,y and lower right x,y coordinates are contained in the TYPE definition the function has no conversions to do first. The output of the second example is exactly the same as the first as seen in Figure 2 above.

Note: If the way TYPE definitions are being used here to transfer data between the main code body and function is not clear to you read the section on line intersection collision detection for a full explanation.

Circular Based Collision Detection

Games involving circular objects, such as pool balls or asteroids, will benefit from circular collision detection since rectangular detection would be woefully inadequate. Circular collision detection involves a bit of math, the Pythagorean Theorem to be exact, and because of this is a slightly slower method of collision detection. With circular collision detection two pieces of information are needed from the objects being tested; an x,y center point of the object and the radius to extend the detection out to. The following example program illustrates how circular detection is achieved. Use the mouse to move the red circle around on the screen.

( This code can be found at .\tutorial\Lesson15\CollisionDemo3.bas )

'** Circular Collision Demo #3

CONST RED = _RGB32(255, 0, 0) '     define colors
CONST GREEN = _RGB32(0, 255, 0)
CONST YELLOW = _RGB32(255, 255, 0)

TYPE CIRCLES '          circle definition
    x AS INTEGER '      center X of circle
    y AS INTEGER '      center Y of circle
    radius AS INTEGER ' circle radius
END TYPE

DIM RedCircle AS CIRCLES '   red circle properties
DIM GreenCircle AS CIRCLES ' green circle properties
DIM CircleColor~& '          color of green circle

GreenCircle.x = 319 '                               green circle center X
GreenCircle.y = 239 '                               green circle center Y
GreenCircle.radius = 50 '                           green circle radius
RedCircle.radius = 25 '                             red circle radius

SCREEN _NEWIMAGE(640, 480, 32) '                    enter graphics screen
_MOUSEHIDE '                                        hide the mouse pointer
DO '                                                begin main program loop
   _LIMIT 30 '                                      30 frames per second
   CLS '                                            clear screen
   WHILE _MOUSEINPUT: WEND '                        get latest mouse information
    RedCircle.x = _MOUSEX '                         record mouse X location
    RedCircle.y = _MOUSEY '                         record mouse Y location
   IF CircCollide(RedCircle, GreenCircle) THEN '    circle collision?
       LOCATE 2, 36 '                               yes, position text cursor
       PRINT "COLLISION!" '                         report collision happening
        CircleColor~& = YELLOW '                    green circle become yellow during collision
   ELSE '                                           no collision
        CircleColor~& = GREEN '                     green circle will be green when no collision
   END IF
   CIRCLE (GreenCircle.x, GreenCircle.y), GreenCircle.radius, CircleColor~& ' draw green circle
   PAINT (GreenCircle.x, GreenCircle.y), CircleColor~&, CircleColor~& '       paint green circle
   CIRCLE (RedCircle.x, RedCircle.y), RedCircle.radius, RED '                 draw red circle
   PAINT (RedCircle.x, RedCircle.y), RED, RED '                               paint red circle
   _DISPLAY '                                       update screen with changes
LOOP UNTIL _KEYDOWN(27) '                           leave when ESC key pressed
SYSTEM '                                            return to operating system

'------------------------------------------------------------------------------------------------------------
FUNCTION CircCollide (Circ1 AS CIRCLES, Circ2 AS CIRCLES)
    '--------------------------------------------------------------------------------------------------------
    '- Checks for the collision between two circular areas.            -
    '- Returns -1 if in collision                                      -
    '- Returns  0 if no collision                                      -
    '-                                                                 -
    '- Circ1 - circle 1 properties                                     -
    '- Circ2 - circle 2 properties                                     -
    '-                                                                 -
    '- Removal of square root by Brandon Ritchie for                   -
    '- more efficient and faster code. 05/10/20                        -
    '-                                                                 -
    '- original code read:                                             -
    '-                                                                 -
    '- Hypot% = INT(SQR(SideA% * SideA% + SideB% * SideB%))            -
    '- IF Hypot% <= Circ1.radius + Circ2.radius THEN CircCollide = -1  -
    '-                                                                 -
    '- Changed to current code below                                   -
    '-------------------------------------------------------------------

    '** declare local variables

   DIM SideA% ' side A length of right triangle
   DIM SideB% ' side B length of right triangle
   DIM Hypot& ' hypotenuse squared length of right triangle (side C)

    '** check for collision

    CircCollide = 0 '                                       assume no collision
    SideA% = Circ1.x - Circ2.x '                            calculate length of side A
    SideB% = Circ1.y - Circ2.y '                            calculate length of side B
    Hypot& = SideA% * SideA% + SideB% * SideB% '            calculate hypotenuse squared

    '** is hypotenuse squared <= the square of radii added together?
    '** if so then collision has occurred

   IF Hypot& <= (Circ1.radius + Circ2.radius) * (Circ1.radius + Circ2.radius) THEN CircCollide = -1

END FUNCTION

Collision detection is achieved by setting up a right triangle between the center point of the two objects. The Pythagorean Theorem  A2 + B2 = C2 can then be applied to determine the distance between the two object center points. Side A is the difference between x1 and x2 and side B is the difference between y1 and y2. Plugging the values for A and B into the equation yields the length of side C, or the distance between the two center points of the circles. If side C is less then or equal to the two radii of the objects added together then a collision must be occurring. Figure 6 below is a visual representation of this.

Because determining the square root of a number is labor intensive on the CPU many detection algorithms that require circular collision detection will first detect for a rectangular collision. Since rectangular collision requires only basic math and the use of IF statements it can be used first to test for two objects being in close proximity. Only when the objects are close enough does it warrant a circular collision detection check. The previous example has been modified to check for rectangular collision before determining if a circular collision has occurred.

Update: While updating the tutorial a few years back my son asked why I was using SQR in my circular collision detection routine. He reworked the math to remove the SQR statement all together which did in fact make the circular detection code faster. He's quite the coder himself and taught me something new!

( This code can be found at .\tutorial\Lesson15\CollisionDemo4.bas )

'** Circular Collision Demo #4
'** Rectangular Collision Checked First

CONST RED = _RGB32(255, 0, 0) '     define colors
CONST GREEN = _RGB32(0, 255, 0)
CONST YELLOW = _RGB32(255, 255, 0)
CONST DARKGREEN = _RGB32(0, 127, 0)

TYPE CIRCLES '               circle definition
    x AS INTEGER '           center X of circle
    y AS INTEGER '           center Y of circle
    radius AS INTEGER '      circle radius
END TYPE

TYPE RECT '                  rectangle definition
    x1 AS INTEGER '          upper left X
    y1 AS INTEGER '          upper left Y
    x2 AS INTEGER '          lower right X
    y2 AS INTEGER '          lower right Y
END TYPE

DIM RedCircle AS CIRCLES '   red circle properties
DIM GreenCircle AS CIRCLES ' green circle properties
DIM RedBox AS RECT '         rectangle coordinates of red circle
DIM GreenBox AS RECT '       rectangle coordinates of green circle
DIM CircleColor~& '          color of green circle

GreenCircle.x = 319 '                                 green circle center X
GreenCircle.y = 239 '                                 green circle center Y
GreenCircle.radius = 50 '                             green circle radius
RedCircle.radius = 25 '                               red circle radius

SCREEN _NEWIMAGE(640, 480, 32) '                      enter graphics screen
_MOUSEHIDE '                                          hide the mouse pointer
DO '                                                  begin main program loop
   _LIMIT 30 '                                        30 frames per second
   CLS '                                              clear screen
   WHILE _MOUSEINPUT: WEND '                          get latest mouse information
    RedCircle.x = _MOUSEX '                           record mouse X location
    RedCircle.y = _MOUSEY '                           record mouse Y location
    RedBox.x1 = RedCircle.x - RedCircle.radius '      calculate rectangular coordinates
    RedBox.y1 = RedCircle.y - RedCircle.radius '      for red and green circle
    RedBox.x2 = RedCircle.x + RedCircle.radius
    RedBox.y2 = RedCircle.y + RedCircle.radius
    GreenBox.x1 = GreenCircle.x - GreenCircle.radius
    GreenBox.y1 = GreenCircle.y - GreenCircle.radius
    GreenBox.x2 = GreenCircle.x + GreenCircle.radius
    GreenBox.y2 = GreenCircle.y + GreenCircle.radius
   IF RectCollide(RedBox, GreenBox) THEN '            rectangular collision?
       LOCATE 2, 33 '                                 yes, position text cursor
       PRINT "PROXIMITY ALERT!" '                     report the close proximity
        CircleColor~& = DARKGREEN '                   green circle become dark green during proximity
       IF CircCollide(RedCircle, GreenCircle) THEN '  circle collision?
           LOCATE 2, 33 '                             yes, position text cursor
           PRINT "   COLLISION!   " '                 report collision happening
            CircleColor~& = YELLOW '                  green circle become yellow during collision
       END IF
   ELSE '                                             no collision
        CircleColor~& = GREEN '                       green circle will be green when no collision
   END IF
   CIRCLE (GreenCircle.x, GreenCircle.y), GreenCircle.radius, CircleColor~& ' draw green circle
   PAINT (GreenCircle.x, GreenCircle.y), CircleColor~&, CircleColor~& '       paint green circle
   CIRCLE (RedCircle.x, RedCircle.y), RedCircle.radius, RED '                 draw red circle
   PAINT (RedCircle.x, RedCircle.y), RED, RED '                               paint red circle
   _DISPLAY '                                         update screen with changes
LOOP UNTIL _KEYDOWN(27) '                             leave when ESC key pressed
SYSTEM '                                              return to operating system

'------------------------------------------------------------------------------------------------------------
FUNCTION RectCollide (Rect1 AS RECT, Rect2 AS RECT)
    '--------------------------------------------------------------------------------------------------------
    '- Checks for the collision between two rectangular areas. -
    '- Returns -1 if in collision                              -
    '- Returns  0 if no collision                              -
    '-                                                         -
    '- Rect1 - rectangle 1 coordinates                         -
    '- Rect2 - rectangle 2 coordinates                         -
    '-----------------------------------------------------------

    RectCollide = 0 '                         assume no collision
   IF Rect1.x2 >= Rect2.x1 THEN '             rect 1 lower right X >= rect 2 upper left  X ?
       IF Rect1.x1 <= Rect2.x2 THEN '         rect 1 upper left  X <= rect 2 lower right X ?
           IF Rect1.y2 >= Rect2.y1 THEN '     rect 1 lower right Y >= rect 2 upper left  Y ?
               IF Rect1.y1 <= Rect2.y2 THEN ' rect 1 upper left  Y <= rect 2 lower right Y ?
                    RectCollide = -1 '        if all 4 IFs true then a collision must be happening
               END IF
           END IF
       END IF
   END IF

END FUNCTION

'------------------------------------------------------------------------------------------------------------
FUNCTION CircCollide (Circ1 AS CIRCLES, Circ2 AS CIRCLES)
    '--------------------------------------------------------------------------------------------------------
    '- Checks for the collision between two circular areas.            -
    '- Returns -1 if in collision                                      -
    '- Returns  0 if no collision                                      -
    '-                                                                 -
    '- Circ1 - circle 1 properties                                     -
    '- Circ2 - circle 2 properties                                     -
    '-                                                                 -
    '- Removal of square root by Brandon Ritchie for                   -
    '- more efficient and faster code. 05/10/20                        -
    '-                                                                 -
    '- original code read:                                             -
    '-                                                                 -
    '- Hypot% = INT(SQR(SideA% * SideA% + SideB% * SideB%))            -
    '- IF Hypot% <= Circ1.radius + Circ2.radius THEN CircCollide = -1  -
    '-                                                                 -
    '- Changed to current code below                                   -
    '-------------------------------------------------------------------

    '** declare local variables

   DIM SideA% ' side A length of right triangle
   DIM SideB% ' side B length of right triangle
   DIM Hypot& ' hypotenuse squared length of right triangle (side C)

    '** check for collision

    CircCollide = 0 '                                       assume no collision
    SideA% = Circ1.x - Circ2.x '                            calculate length of side A
    SideB% = Circ1.y - Circ2.y '                            calculate length of side B
    Hypot& = SideA% * SideA% + SideB% * SideB% '            calculate hypotenuse squared

    '** is hypotenuse squared <= the square of radii added together?
    '** if so then collison has occurred

   IF Hypot& <= (Circ1.radius + Circ2.radius) * (Circ1.radius + Circ2.radius) THEN CircCollide = -1

END FUNCTION

Pixel Perfect Based Collision Detection

When absolute accuracy is needed for collision detection nothing can beat pixel perfect collision detection. It's one of the most CPU labor intensive methods of collision detection available however. Pixel based collision works by first identifying if a rectangular collision has occurred then the overlapping areas of the two rectangles are checked pixel by pixel for any overlapping pixels. Depending on the size of the overlapping area and the location of the pixel collision this method can vary wildly from check to check in time taken to complete the test. Pixel detection should only be used on images that absolutely need to incorporate its accuracy. The following example program loads two oval images and then checks for pixel collision between them. Use the mouse to move the red oval to see just how accurate it is. You'll need to copy the code to your qb64 folder before executing.

( This code can be found at .\tutorial\Lesson15\CollisionDemo5.bas )

'** Pixel Perfect Collision Demo #5

TYPE SPRITE '             sprite definition
    image AS LONG '       sprite image
    mask AS LONG '        sprite mask image
    x1 AS INTEGER '       upper left X
    y1 AS INTEGER '       upper left Y
    x2 AS INTEGER '       lower right X
    y2 AS INTEGER '       lower right Y
END TYPE

DIM RedOval AS SPRITE '   red oval images
DIM GreenOval AS SPRITE ' green oval images

RedOval.image = _LOADIMAGE(".\tutorial\Lesson15\redoval.png", 32) '     load red oval image image
GreenOval.image = _LOADIMAGE(".\tutorial\Lesson15\greenoval.png", 32) ' load green oval image
MakeMask RedOval '                                                      create mask for red oval image
MakeMask GreenOval '                                                    create mask for green oval image
SCREEN _NEWIMAGE(640, 480, 32) '                                        enter graphics screen
_MOUSEHIDE '                                                            hide the mouse pointer
GreenOval.x1 = 294 '                                                    green oval upper left X
GreenOval.y1 = 165 '                                                    green oval upper left Y
DO '                                                                    begin main program loop
   _LIMIT 30 '                                                          30 frames per second
   CLS '                                                                clear screen
   WHILE _MOUSEINPUT: WEND '                                            get latest mouse information
   _PUTIMAGE (GreenOval.x1, GreenOval.y1), GreenOval.image '            display green oval
   _PUTIMAGE (RedOval.x1, RedOval.y1), RedOval.image '                  display red oval
    RedOval.x1 = _MOUSEX '                                              record mouse X location
    RedOval.y1 = _MOUSEY '                                              record mouse Y location
   IF PixelCollide(GreenOval, RedOval) THEN '                           pixel collision?
       LOCATE 2, 36 '                                                   yes, position text cursor
       PRINT "COLLISION!" '                                             report collision happening
   END IF
   _DISPLAY '                                                           update screen with changes
LOOP UNTIL _KEYDOWN(27) '                                               leave when ESC key pressed
SYSTEM '                                                                return to operating system

'------------------------------------------------------------------------------------------------------------
SUB MakeMask (Obj AS SPRITE)
    '--------------------------------------------------------------------------------------------------------
    '- Creates a negative mask of image for pixel collision detection. -
    '-                                                                 -
    '- Obj - object containing an image and mask image holder          -
    '-------------------------------------------------------------------

   DIM x%, y% '   image column and row counters
   DIM cc~& '     clear transparent color
   DIM Osource& ' original source image
   DIM Odest& '   original destination image

    Obj.mask = _NEWIMAGE(_WIDTH(Obj.image), _HEIGHT(Obj.image), 32) ' create mask image
    Osource& = _SOURCE '                              save source image
    Odest& = _DEST '                                  save destination image
   _SOURCE Obj.image '                                make object image the source
   _DEST Obj.mask '                                   make object mask image the destination
    cc~& = _RGB32(255, 0, 255) '                      set the color to be used as transparent
   FOR y% = 0 TO _HEIGHT(Obj.image) - 1 '             cycle through image rows
       FOR x% = 0 TO _WIDTH(Obj.image) - 1 '          cycle through image columns
           IF POINT(x%, y%) = cc~& THEN '             is image pixel the transparent color?
               PSET (x%, y%), _RGB32(0, 0, 0, 255) '  yes, set corresponding mask image to solid black
           ELSE '                                     no, pixel is part of actual image
               PSET (x%, y%), cc~& '                  set corresponding mask image to transparent color
           END IF
       NEXT x%
   NEXT y%
   _DEST Odest& '                                     restore original destination image
   _SOURCE Osource& '                                 restore original source image
   _SETALPHA 0, cc~&, Obj.image '                     set image transparent color
   _SETALPHA 0, cc~&, Obj.mask '                      set mask transparent color

END SUB

'------------------------------------------------------------------------------------------------------------
FUNCTION PixelCollide (Obj1 AS SPRITE, Obj2 AS SPRITE)
    '--------------------------------------------------------------------------------------------------------
    '- Checks for pixel perfect collision between two rectangular areas. -
    '- Returns -1 if in collision                                        -
    '- Returns  0 if no collision                                        -
    '-                                                                   -
    '- obj1 - rectangle 1 coordinates                                    -
    '- obj2 - rectangle 2 coordinates                                    -
    '---------------------------------------------------------------------

   DIM x1%, y1% ' upper left x,y coordinate of rectangular collision area
   DIM x2%, y2% ' lower right x,y coordinate of rectangular collision area
   DIM Test& '    overlap image to test for collision
   DIM Hit% '     -1 (TRUE) if a collision occurs, 0 (FALSE) otherwise
   DIM Osource& ' original source image handle
   DIM p~& '      pixel color being tested in overlap image

    Obj1.x2 = Obj1.x1 + _WIDTH(Obj1.image) - 1 '  calculate lower right x,y coordinates
    Obj1.y2 = Obj1.y1 + _HEIGHT(Obj1.image) - 1 ' of both objects
    Obj2.x2 = Obj2.x1 + _WIDTH(Obj2.image) - 1
    Obj2.y2 = Obj2.y1 + _HEIGHT(Obj2.image) - 1
    Hit% = 0 '                                    assume no collision

    '** perform rectangular collision check

   IF Obj1.x2 >= Obj2.x1 THEN '                  rect 1 lower right X >= rect 2 upper left  X ?
       IF Obj1.x1 <= Obj2.x2 THEN '              rect 1 upper left  X <= rect 2 lower right X ?
           IF Obj1.y2 >= Obj2.y1 THEN '          rect 1 lower right Y >= rect 2 upper left  Y ?
               IF Obj1.y1 <= Obj2.y2 THEN '      rect 1 upper left  Y <= rect 2 lower right Y ?

                    '** rectangular collision detected, perform pixel perfect collision check

                   IF Obj2.x1 <= Obj1.x1 THEN x1% = Obj1.x1 ELSE x1% = Obj2.x1 ' calculate overlapping
                   IF Obj2.y1 <= Obj1.y1 THEN y1% = Obj1.y1 ELSE y1% = Obj2.y1 ' square coordinates
                   IF Obj2.x2 <= Obj1.x2 THEN x2% = Obj2.x2 ELSE x2% = Obj1.x2
                   IF Obj2.y2 <= Obj1.y2 THEN y2% = Obj2.y2 ELSE y2% = Obj1.y2
                    Test& = _NEWIMAGE(x2% - x1% + 1, y2% - y1% + 1, 32) '               make overlap image
                   _PUTIMAGE (-(x1% - Obj1.x1), -(y1% - Obj1.y1)), Obj1.image, Test& ' place image 1
                   _PUTIMAGE (-(x1% - Obj2.x1), -(y1% - Obj2.y1)), Obj2.mask, Test& '  place image mask 2

                    '** enable the line below to see a visual representation of mask on image
                    '_PUTIMAGE (x1%, y1%), Test&

                    y1% = 0 '                                    reset row counter
                    Osource& = _SOURCE '                         record current source image
                   _SOURCE Test& '                               make test image the source
                   DO '                                          begin row (y) loop
                        x1% = 0 '                                reset column counter
                       DO '                                      begin column (x) loop
                            p~& = POINT(x1%, y1%) '              get color at current coordinate

                            '** if color from object 1 then a collision has occurred

                           IF p~& <> _RGB32(0, 0, 0, 255) AND p~& <> _RGB32(0, 0, 0, 0) THEN Hit% = -1
                            x1% = x1% + 1 '                      increment to next column
                       LOOP UNTIL x1% = _WIDTH(Test&) OR Hit% '  leave when column checked or collision
                        y1% = y1% + 1 '                          increment to next row
                   LOOP UNTIL y1% = _HEIGHT(Test&) OR Hit% '     leave when all rows checked or collision
                   _SOURCE Osource& '                            restore original destination
                   _FREEIMAGE Test& '                            test image no longer needed (free RAM)
               END IF
           END IF
       END IF
   END IF
    PixelCollide = Hit% '                                        return result of collision check

END FUNCTION

Pixel detection is achieved by using a negative image called an image mask. Every pixel in the original image that is not transparent is mirrored in the mask as a transparent pixel. Every pixel in the original image that is a transparent pixel is mirrored in the mask as a solid black pixel. When the mask is placed over a second image any pixels that show through indicate that a pixel collision must have occurred.  If you activate line 116 in the example code above you'll see the mask image being applied to the green oval. Only when the green pixels appear through the mask is a pixel collision detected. Figure 9 below describes the process.

The MakeMask() subroutine creates a mask image by scanning the original image from top to bottom one pixel at a time. The pixels are mirrored from the original image to the mask image but converted using the method described in Figure 9.

Lines 100 through 103 in the PixelCollide() function perform a standard rectangular collision check. If the rectangles have merged then that overlapping area is identified by lines 107 through 110. x1%, y1%, x2%, and y2% now contain the coordinates of the overlapping area. Line 111 then creates an image the same size as the overlapping area.

Lines 112 and 113 place the original image and the mask of the second image onto the newly created overlap image. The location of the images are calculated in these two lines so as to overlap in the same manner as they will on the screen.

Lines 121 through 132 then cycle through every pixel contained in the overlap image using the POINT statement to grab each pixel's color. If line 128 detects a pixel that is not solid black or transparent then it must be a pixel from the image underneath and a collision is recorded by setting the variable Hit% to -1 (true). DO...LOOP statements are used here so they can easily be exited as soon as a collision is detected. Once a collision is detected there is no reason to check the remainder of the overlap image.

Line Intersection Collision Detection

Line intersection collision detection is used to detect if two line segments are crossing paths. I find this type of collision detection useful for games that emulate vector graphics like Asteroids or Tempest. These vector based games used lines to draw objects on the screen instead of sprite images. My Widescreen Asteroids game built with QB64 is an example that uses line intersection collision detection for all of the objects seen on the screen.

Line intersection collision is also useful for small and fast bullet collision detection. Many times when bullets are flying around on the screen they can "skip" over an image from one frame to the next. By projecting an imaginary line from the current bullet coordinate to the next predicted coordinate that line can be used to see if it will intersect the object through its flight path.

The following example program illustrates the use of line intersection to achieve collision detection. Use the mouse to move the red line around on the screen to intercept the rotating green line.

Note: The following line collision routine is new and uses a completely different method of detection which is faster and more efficient. If you are using the previous method found from the old tutorial web site I highly encourage you to incorporate this new method.

( This code can be found at .\tutorial\Lesson15\CollisionDemo6.bas )

'* Line Intersection Collision Detection Demo #6
'*
'* Note: This is a completely new method of line intersection detection from the tutorial's
'*       previous code example. This detection algorithm is much smaller and more efficient.
'*
'* Updated 08/19/22
'*
'* Make note of the credit given in the LineCollide() subroutine.

CONST RED = _RGB32(255, 0, 0) '     define colors
CONST GREEN = _RGB32(0, 255, 0)
CONST YELLOW = _RGB32(255, 255, 0)

TYPE A_2D_POINT '                   X,Y point definition
    x AS INTEGER '                  X coordinate location
    y AS INTEGER '                  Y coordinate location
END TYPE

TYPE A_2D_LINE '                    line segment definition (notice a TYPE def can be used in another TYPE)
    s AS A_2D_POINT '               start of line
    e AS A_2D_POINT '               end of line
END TYPE

DIM Intersect AS A_2D_POINT '       X,Y line intersection coordinate identified by LineCollide()
DIM Line1 AS A_2D_LINE '            green line
DIM Line2 AS A_2D_LINE '            red line
DIM Plot(359) AS A_2D_POINT '       360 degree plotted coordinates
DIM c! '                            sine wave counter
DIM c1%, c2% '                      counters
DIM clr~& '                         green line color

FOR c1% = 0 TO 359 '                                           plot 360 points for spinning line
    Plot(c1%).x = 319 + 100 * COS(c!) '                        from screen center X radius 100
    Plot(c1%).y = 239 + 100 * -SIN(c!) '                       from screen center Y radius 100
    c! = c! + 6.2831852 / 360 '                                360 increments
NEXT c1%
SCREEN _NEWIMAGE(640, 480, 32) '                               enter graphics screen
_MOUSEHIDE '                                                   hide mouse pointer
c1% = 0 '                                                      set green line start counter
c2% = 179 '                                                    set green line end counter
DO '                                                           begin main loop
   _LIMIT 60 '                                                 30 frames per second
   CLS '                                                       clear the screen
   LINE (Line1.s.x, Line1.s.y)-(Line1.e.x, Line1.e.y), clr~& ' draw green line
   LINE (Line2.s.x, Line2.s.y)-(Line2.e.x, Line2.e.y), RED '   draw red line
   WHILE _MOUSEINPUT: WEND '                                   get latest mouse information
    Line2.s.x = _MOUSEX - 50 '                                 set red line coordinates
    Line2.e.x = Line2.s.x + 100
    Line2.s.y = _MOUSEY
    Line2.e.y = Line2.s.y
    Line1.s.x = Plot(c1%).x '                                  set green line coordinates
    Line1.s.y = Plot(c1%).y
    Line1.e.x = Plot(c2%).x
    Line1.e.y = Plot(c2%).y
   IF LineCollide%(Line2, Line1, Intersect) THEN '             line collision?
       LOCATE 2, 36 '                                          yes, locate cursor
       PRINT "COLLISION!" '                                    report collision
        clr~& = YELLOW '                                       green line becomes yellow
       CIRCLE (Intersect.x, Intersect.y), 4, GREEN
       PAINT (Intersect.x, Intersect.y), GREEN, GREEN
   ELSE '                                                      no collision
        clr~& = GREEN '                                        green line is green
   END IF
    c1% = c1% + 1 '                                            increment green line start counter
   IF c1% = 360 THEN c1% = 0 '                                 keep within limits
    c2% = c2% + 1 '                                            increment green line end counter
   IF c2% = 360 THEN c2% = 0 '                                 keep within limits
   _DISPLAY '                                                  update screen with changes
LOOP UNTIL _KEYDOWN(27) '                                      leave when ESC key pressed
SYSTEM '                                                       return to operating system

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

FUNCTION LineCollide% (L1 AS A_2D_LINE, L2 AS A_2D_LINE, Intersect AS A_2D_POINT)

    'Tests for 2 lines intersecting (in collision)
    'Returns: 0 if no collision, -1 if collision
    '       : Intersect.x, Intersect.y will contain the x,y coordinate of collision

    'L1.s.x start line 1 | L2.s.x start line 2 | Intersect.x line intersection coordinates
    '  .s.y              |   .s.y              |          .y
    '  .e.x end line 1   |   .e.x end line 2   |
    '  .e.y              |   .e.y              |

    'This function created from examples given at this discussion:
    'https://forum.unity.com/threads/line-intersection.17384/
    'Based on the "Faster Line Segment Intersection" code found in Graphics Gems III
    'pages 199-202 by Franklin Antonio (1992). ISBN 0-12-409672-7

   DIM Ax%, Bx%, Cx%, Ay%, By%, Cy%, d%, e%, f%
   DIM x1lo%, x1hi%, y1lo%, y1hi%

    Intersect.x = 0 '                             assume no collision
    Intersect.y = 0
    LineCollide% = 0
    Ax% = L1.e.x - L1.s.x '                       X bounding box test
    Bx% = L2.s.x - L2.e.x
   IF Ax% < 0 THEN
        x1lo% = L1.e.x
        x1hi% = L1.s.x
   ELSE
        x1hi% = L1.e.x
        x1lo% = L1.s.x
   END IF
   IF Bx% > 0 THEN
       IF x1hi% < L2.e.x OR L2.s.x < x1lo% THEN EXIT FUNCTION
   ELSE
       IF x1hi% < L2.s.x OR L2.e.x < x1lo% THEN EXIT FUNCTION
   END IF
    Ay% = L1.e.y - L1.s.y '                       Y bounding box test
    By% = L2.s.y - L2.e.y
   IF Ay% < 0 THEN
        y1lo% = L1.e.y
        y1hi% = L1.s.y
   ELSE
        y1hi% = L1.e.y
        y1lo% = L1.s.y
   END IF
   IF By% > 0 THEN
       IF y1hi% < L2.e.y OR L2.s.y < y1lo% THEN EXIT FUNCTION
   ELSE
       IF y1hi% < L2.s.y OR L2.e.y < y1lo% THEN EXIT FUNCTION
   END IF
    Cx% = L1.s.x - L2.s.x
    Cy% = L1.s.y - L2.s.y
    d% = By% * Cx% - Bx% * Cy% '                  alpha numerator
    f% = Ay% * Bx% - Ax% * By% '                  both denominators
   IF f% = 0 THEN EXIT FUNCTION '                 parallel line check
   IF f% > 0 THEN '                               alpha tests
       IF d% < 0 OR d% > f% THEN EXIT FUNCTION
   ELSE
       IF d% > 0 OR d% < f% THEN EXIT FUNCTION
   END IF
    e% = Ax% * Cy% - Ay% * Cx% '                  beta numerator
   IF f% > 0 THEN '                               beta tests
       IF e% < 0 OR e% > f% THEN EXIT FUNCTION
   ELSE
       IF e% > 0 OR e% < f% THEN EXIT FUNCTION
   END IF
    Intersect.x = L1.s.x + d% * Ax% / f% '        calculate intersect coordinate
    Intersect.y = L1.s.y + d% * Ay% / f%
    LineCollide% = -1 '                           report that collision occurred

END FUNCTION

I'm no mathematician and I'm sure line segment intersection was covered in the geometry class I took in the 10th grade back in 1983. The great thing about programming is somewhere, someone, has more than likely posted code or discussed the topic you are searching for. The code posted may even be in another programming language but the skills you learn in QB64 will help you to translate that code to your needs.

The LineCollide%() function above was translated from Unity source code I found on the Internet. The location of that code and any person(s) that need to be given credit are commented within the source code as well. When you use someone else's work you must ALWAYS give them credit where credit is due. Never use copyrighted code unless you have express permission to do so.

The LineCollide%() function above expects two line segments as input and another variable that will be modified when the function ends to contain the x,y coordinate of where the collision took place.

Hit% = LineCollide%(Line2, Line1, Intersect) ' true if the two segments intersect

Hit% will contain a value of -1 (true) if the line segments intersect or a value of 0 (false) if they do not. If there was a collision Intersect will contain the x,y coordinate where the collision occurred.

Using TYPE Defintions To Move Values

For clarity TYPE definitions have been used to hold values relating to x,y coordinates and line segments.

This TYPE definition sets up an x,y coordinate pair.

TYPE A_2D_POINT '                   X,Y point definition
    x AS INTEGER '                  X coordinate location
    y AS INTEGER '                  Y coordinate location
END TYPE

This TYPE definition then uses the A_2D_POINT definition twice to set up a start x,y coordinate and end x,y coordinate that defines the line segment.

TYPE A_2D_LINE '                    line segment definition (notice a TYPE def can be used in another TYPE)
    s AS A_2D_POINT '               start of line
    e AS A_2D_POINT '               end of line
END TYPE

TYPE definitions can be used within other TYPE definitions to define complex variables.

DIM Line1 AS A_2D_LINE ' a 2D line segment

Line1 is now a complex variable containing two TYPE definitions. To set the start x,y coordinate of this variable:

Line1.s.x = 10
Line1.s.y = 10

line 1's starting x coordinate is 10 and its starting y coordinate is 10. Likewise, to set the end x,y coordinate of this variable:

Line1.e.x = 50
Line1.e.y = 50

line 1's ending x coordinate is 50 and its ending y coordinate is 50.

Passing complex variables into subroutines and functions is simply done using the AS clause and the TYPE definition previously defined:

FUNCTION LineCollide% (L1 AS A_2D_LINE, L2 AS A_2D_LINE, Intersect AS A_2D_POINT)

When a complex variable such as Line1 is passed into the function the entire contents of the complex variable is transferred:

Hit% = LineCollide%(Line2, Line1, Intersect) ' true if the two segments intersect

The local variable L1 now contains the entire contents of Line1. In other words, this is going on in the background:

L1.s.x = Line1.s.x
L1.s.y = Line1.s.y
L1.e.x = Line1.e.x
L1.e.y = Line1.e.y

Since L1 and Line1 are of the same TYPE definition structure the contents are seamlessly moved between them. This behavior works anywhere within code:

Line2 = Line1

If Line2 is defined with the same TYPE definition structure as Line1 then entire contents of Line1 will be copied to Line2.

All of the previous collision demos use this method to pass information to their functions because it's an efficient way to move many values between the main body code and subroutines or functions.

Collision Routines With Intersect Reporting

The line segment collision routine above includes a method of determining where the collision took place. Included in your .\tutorial\Lesson15\ directory are circular, pixel, and rectangular collision routines that will report back collision points as well if you need this feature.

CircCollide.BAS will return the x,y coordinate of the collision location.

PixelCollide.BAS will return the x,y coordinate of the collision location.

RectCollide.BAS will return the rectangular overlapping area of the collision location as an x,y upper left coordinate and an x,y lower right coordinate of the overlapping area.

You can load each one into your IDE and see the change in action.