Task 17: Collision Detection  

CONTENTS

Rectangular Based Collision Detection
Circular Based Collision Detection
Pixel Based Collision Detection
Line Intersection Collision Detection



From this point on the remaining tasks will focus on game programming techniques instead of being tutorial based. Tasks 3 through 16 introduced you to most 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 task will investigate four different methods of collision detection; rectangular, circular, pixel, and line intersection.


Rectangular Based Collision Detection


The simplest form of collision detection is to detect if two rectangular objects are touching. 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. (The original Mario Brothers screen was 256x224 pixels. It has been resized 300% in Figure 1 for clarity.)


Figure 1 - Mario Brothers Screen Divided Into 16x16 Pixel Grid

Only three pieces of information are required from each rectangle to test for collision; the upper left x,y coordinate, width, and 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\task17\ directory.




Figure 2 - Colliding Rectangles

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.

 
Figures 3 and 4 - Detecting Collisions Between 2 Rectangular Areas

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\task17\ 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 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. BadBox is a simple game I wrote that uses rectangular collision that you can download and view the code.


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 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\task17\ directory. Use the mouse to move the red circle around on the screen.




Figure 5 - Colliding Circles

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


Figure 6 - Pythagoras to the Rescue

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\task17\ directory as CollisionDemo4.BAS. BadBox Revenge is an example game I wrote you can download that uses a combination of rectangular and circular based collision detection.




Figure 7 - Rectangular and Circular Collision Working Together


Pixel 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. If it has 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\task17\ directory.




Figure 8 - Pixel Collision Detection

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.


Figure 9 - Applying Masks to Test For Pixel Collision

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 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 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 intersects 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\task17\ directory. Use the mouse to move the red line around on the screen to intercept the rotating green line.





Figure 10 - Line Intersection Collision Detected

I'm no mathematician and I'm sure line intersection was covered in the geometry class I took in the 10th grade (back in 1983!). The great thing about programming is somewhere on the Internet someone has more than likely posted code for the task you are looking to do. It may not be written in the exact language you need but it will be close. The functions LineCollide(), Orientation(), and onSegment() were all created by modifying Python code I found on the Internet. The location of that code is noted within the functions themselves as comments. If you ever do use someone else's code ALWAYS give credit where credit is due and never use copyrighted code unless you have express permission to do so.

The five functions in this example, LineCollide(), Orientation(), onSegment(), Min(), and Max() are my goto functions when I need to implement line collision detection in my games. I may rewrite them a bit to suit the needs of the current project I'm working on but their basic core is always the same. Simply supply LineCollide() with the starting and ending coordinates of two line segments and it will return a -1 (true) if the line segments intersect and 0 (false) if they do not.

The code I have provided here is not the only method of line detection. In fact there is an entire thread on the QB64 forum devoted to this subject with many different examples available. Don't forget to ask for help and advice on the forum. Some of the forum members are gifted in all things math related.