Collision Detection by zkman 07.10.99
Collision detection is a coding technique that you will use in many facets of your programming future. From the simplest of a side-scroller to a pixel-scrolling rpg to a G-Radius style shooter and on into 3d, you will need to know the basic fact of whether one object is intersecting with another. There are infinite ways of doing "approximatations" of whether objects are touching, which is what this article is about, since for qb's purposes, pixel-perfect collision is both extraneous and usually too slow for the average coder.

There are 4 common types of collision detection in 2 dimension that you will use in your coding:

  • Manhattan
  • Bounding Box
  • Radius
  • Pixel-perfect
Manhattan detection is formed by creating a "diamond" with equilateral sides around the center of a tile, and detecting if the other object's diamond intersects with yours. Radius works by forming a circle around an object, and detecting if another point is in the circle. Bounding Box is formed by checking two rectangles (or squares, obviously) for intersection, and is the most common one found in qb titles. Like we said earlier, pixel-perfect finds if even one pixel is intersecting and is the most exact, but is hard on the computer. It won't be covered indepth in this article, but Sonicblue's sidebar gives you the basics.

So, how do you do 'em

Manhattan

Manhattan detection essentially creates a "square diamond" around two objects, and checks to see if there is the distance from the center of one diamond to the edge of that diamond plus the distance from the center of diamond2 to the edge of that diamond is less than the "manhattan distance". It's very easy to do:

Distance = (ABS(Center1x - center2x) + ABS(center1y - center2y))

If Distance is less than the size of the tile, then it is a collision. For instance, if the tiles were 20 by 20, and Distance was less than 20, then the objects are colliding. This is the fastest method of detection (being only 3 calculations with no division or multiplication), but unfortunately, the "diamond" is not the shape of many tiles (such as a house).

Bounding Box
Bounding Box detection is the method most commonly found in both qbasic games and professional 2d games on older systems because it is both easy to understand, reasonably fast, and fairly sizable. This method creates a "box" or square around a tile (and because most tiles are fairly square, the detection is pretty accurate), and checks the corners of that box with the corners of the other tile's box. It works as below: 

IF obj1x > obj2x AND obj1y > obj2y THEN
  IF obj1x < obj2x + tilewidth AND obj1y < obj2y + tilelength THEN
    collision
In this example, obj1x is the x position of the first tile, obj2x is the x position of the second tile, obj1y and obj2y are the y positions of the tiles, and tilewidth and tileheight are the size of the tile (such as 16 by 16 or 20 by 20). This form allows for rectangles also by making tilewidth and tilelength different as per the size of your tile.

Radius
The Radius detection method will be familiar to anyone with basic geometry skills, as it is simply the distance formula applied to programming. The distance formula is, of course, SQR(((x - x2)^2) + ((y - y2)^2)). This formula is applied to code by using

Dist = SQR(((tilex - circenterx)^2) + ((tiley - circentery)^2)

tilex and tiley are the center of the tile you're checkin, and circenterx/y are the center of the tile where the circle should "originate" from. To see if they're colliding, simply Check to see if Dist < (CircleTileSize - tilesize / 2) where tilesize is from the "boxed" tile and circletilesize is from the circular tile. Because this method is extremely slow in qb compared to the other two (due to three square functions, which qb is notoriously bad at), use this only when absolutely necessary.

It could be that each of these routines could be sped up significantly, as they are all from my personal experience, but as they are, they represent the base from which you should be able to code any collision routines your game needs. The only time that pixelperfect routines would be necessary that I can think of, is if you need the direction of the impact vector of two objects (such as in SpaceARoo2). Later!

  Pixel Perfect
by Sonicblue

I wanted Space-a-Roo 2 to have pixel-perfect hit detection and this is the best way I could think of to get well-rounded results:

  1. Set up 2 screen pages, one for people to "ooo" and "aaah" over (known by me as the "visually appealing" (or pretty) layer), and one for the hit detection, which will not be looked upon except maybe by code-alterists or the author (him/her)self (known as "a-most-confusing-screenful-of-oddly-shaped-blobs" (or ugly) layer).
  2. Clear both layers with color 0.
  3. Place a sprite in full, gorgeous color using your unequally ingenious palette on your pretty layer.
  4. Convert that sprite completely, except for pixels that happen to be registered color 0, to color 1 and place it confidently on your ugly layer. Note that it doesn't matter what color 1 might happen to be because this layer should only be viewed by the tough-stomached.
  5. Pull up the data on your next sprite, and check to see, if placed, whether-or-not any of the pixels, except for those lucky color 0 pixels, are touching any other pixels that are not unfortunate to be color 0 .
  6. If a pixel that is not color 0 is found to be in a place where your 2nd sprite whould be if placed is found, the color number of the pixel is the number of the sprite that your 2nd graphic has collided with (which, at this point, can only be your 1st sprite).
  7. Do any data crunching that has to be done on the fact that you have or have not had a collision between your 2 sets of temporary, binary, graphic data.
  8. Place your 2nd victim....I mean SPRITE, on your pretty layer.
  9. Convert the data responsible for representing your 2nd sprite to color 2, leaving alone any pixels with the job of being color 0 and place the converted data on your ugly layer.
  10. Repeat steps 5 thru 8 with any more sets of data you wish to toil over but remember to convert, for the ugly layer, the data into a different color each time.
  11. Copy the pretty layer to the screen buffer for the admiration of the game's player. BE CAREFUL not to copy the ugly layer or be at risk of giving someone a heart attack at the sight of the unexlpainable ugliness that is portrayed by the ugly layer.
  12. Repeat steps 1-10 for each frame until your game is over!
That's all there is to it!

UPs to this method
It's pixel-perfect and it's FAST

DOWNs to this method
It pretty-much requires ASM if used in QBasic, only works for 255 sprites on screen 13 and requires 2 seperate layers unless you complete the ugly layer, erase it, then do the pretty layer.

What'd you think of this article? Let us know

(c) 1999 Grand Scimitar Studios.