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 is included as CollisionDemo1.BAS in your .\tutorial\Lesson15\ directory.

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. The following code is included as CollisionDemo2.BAS in your .\tutorial\Lesson15\ directory.

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. The program is included as CollisionDemo3.BAS in your .\tutorial\Lesson15\ directory. Use the mouse to move the red circle around on the screen.

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. This example is located in your .\tutorial\Lesson15\ directory as CollisionDemo4.BAS.

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!

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. This code is saved as CollisionDemo5.BAS in your .\tutorial\Lesson15\ directory. You'll need to copy the code to your qb64 folder before executing.

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. The program is included as CollisionDemo6.BAS in your .\tutorial\Lesson15\ directory. 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.

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%(Line1, Line2, 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
    s AS A_2D_POINT ' start of line segment
    e AS A_2D_POINT ' end of line segment
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%(Line1, Line2, 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

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.