Qbasicnews.com

*binary pathfinding
*binary data trees
*binary 2D collision detection (and 3D?)
*binary Machine Learning (AI)
*binary __________________

How Collision Detection is Binary

*As I explained at qbnews, 2D collision happens when one object touches another.

Let's first set up my regular algorithm:
1) Convert each object into a binary array of 0 (transparent) and 1 (solid) and keep in mind the object's index. Also get the x and y sizes of each object, and current positions, for bounding rectangle search.

2) Using bounding rectangles of each object to figure out if one object has *possibly* hit another object.

3) Paste objects onto a screen-wide array.

3) Use the bounding rectangles to test for possible object-object collision. (well I am not so sure how to do this efficiently, but there is a way)

4) Use point collision detection to test each object collision pair (it's only 0 and 1, so it's faster than checking each pixel color and then testing)

5) Return object collision pairs in an array [collision(integer1) = integer2, collision(0) = integer being the collision.amount]

----------------------------------------------------------

You can further optimize this algorithm by making each object hollow inside, since objects can only move one pixel for every collision detection frame. You could also convert each pixel to a line so that the transparent parts are skipped much faster. (for instance, 00011 becomes 3 0 2 1 which becomes 11001001.. bad example)

----------------------------------------------------------

To employ a recursive scheme, we do this:

1) Convert each object into binary, just like last time, and with an index.
2) Now reduce the object size by 2 and do the same thing.
3) Keep reducing until you can't divide evenly anymore. (for this to work, each object must have the same number of binary layers)

1b) Now, make a screen with the last (least detailed) binary layer.

2b) Then run the pixel collision check for that layer.

3b) For any object pair that has possibly collided, check again, using a higher resolution layer. Continue until highest resolution layer has been reached.

-----------------------------------------------------------

At the max limit, this algorithm runs as slowly as the previous algorithm.
(1/2+1/4+1/8+1/16+1/32.. approaches 1 but never reaches it..)
At the min limit, it runs as fast as the smallest resolution (or worst resolution), whether 1/64x, 1/32x, 1/16x, etc.

Space:
It does use as a maximum a little more than twice as much memory for each binary object, but it uses much less memory for the screen test, so it is possibly much more space efficient.

-----------------------------------------------------------

Now, someone code it in ASM and make a QB interface. Yeah..

<-- Is throughly confused. :o

Add this stuff to the FAQ

Would be nice if someone could make a working example, though.

(preferrably with UGL)

I might, later..

binary collision detection in 2D

1) Choose a minimum resolution N starting at a minimum of 1. Each object must be divisible by 2^(N-1). Choose vertical sector amount and horizontal sector amount Vs and Hs.

2) For each object, transform the object into 0 and 1 bits, with the first 32 bits (4 bytes) used as X and Y coordinates and filler bits if the whole thing is not divisible by 8. 0 means transparent, 1 means solid.

3)
For each object,
For n-1 steps,
create another object array with the same characteristics as (1). This time, however, use the following algorithm for every 2x2 block:
If majority 1, set current block to 1 else set current block to 0

4) For n-1 steps,

A) Sort each remaining object's pixels into squares. Each square receives information about what objects are inside it.

B) For each object, pass through each square that contains it and determine whether the object shared a square with any other object. If not, remove that object from the square info and from the collision routine.

C) update remaining objects by increasing their resolution

5) Pass through each object once more and collect an array on which other objects collided with it.