Thread: boolean algebra / memory manipulation / collision detection

  1. #1
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743

    Question boolean algebra / memory manipulation / collision detection

    Okay...I have a question that is mainly about bitwise comparisons of variables.

    I am working on collision detection in my game, and I figured out the way that I wanted to do it, so before I get into my question, let me explain the logic behind it.

    I have a couple bitmaps....one of a guy...and one of a map.

    When I load in my bitmaps, I have decided to immediately go through each pixel, and make a seperate matrix for collision detection purposes. For example, lets say I loaded a bitmap with these color values:

    0 0 5 7 0 0
    8 6 8 9 3 6
    0 0 4 4 0 0
    0 0 4 4 0 0
    0 5 0 0 7 0

    (I know those color values are not likely...they would most likely be in RGB format...but just go with me here...)

    Now, after loading in this BMP, I would automatically make a seperate matrix telling me which bits were colored, and which were not....the color value of 0 is my transparent color...so the seperate bit matrix would read as follows:

    0 0 1 1 0 0
    1 1 1 1 1 1
    0 0 1 1 0 0
    0 0 1 1 0 0
    0 1 0 0 1 0

    This matrix is used for collision detection purposes only. Now lets say I loaded in the map's BMP....and did the same process with it...and now I am checking a certain part of the map with the person's BMP that I have loaded to see if there is a collision. Lets say that this is that part of the map which we are checking for a collision in:

    0 0 0 0 0 1
    0 0 0 0 1 1
    0 0 0 0 1 1
    0 0 0 1 1 1
    1 1 1 1 1 1


    Now, the first matrix was my person, the second matrix was the part of the map where the person is located, so that is the part of the map where we need to check for a collision.

    Now, the easiest and quickest way to check for a collision is to use boolean algebra and AND these matrices together, so if we did:

    (assume the * is the AND operator)

    MatrixA * MatrixB = MatrixC

    MatrixC would result as:

    0 0 0 0 0 0
    0 0 0 0 1 1
    0 0 0 0 0 0
    0 0 0 1 0 0
    0 1 0 0 1 0

    The 1's are every place where MatrixA and MatrixB collided, or in other words, every place where both matrices had 1's.

    So then I would search MatrixC for any occurrences of a 1. If I found a 1, then I know I had a collision, and then I handle the collision.

    Now, after all that background explanation, it is time for my question!

    There are several bitwise operators in C++, such as the unary &, |, and ^.

    1 & 0 = 0 <-- the unary AND
    1 | 0 = 1 <-- the unary OR
    1 ^ 0 = 1 <-- the unary XOR

    However, these unary bitwise operators only work for variables of integral type...in other words....integers...

    Now my matrices use integers, so that is all fine and dandy if I wanted to use a nested loop and go through the matrices element by element, ANDing each one....but if you know anything about Big-O, that would be an N^2 algorithm....I want something faster than that....

    There must be some way to AND large chunks of memory together at a time. Boolean algebra is a primary principle of programming, after all. If I ANDed two integers together, it would AND every bit of them together, giving me a new integer as a result....so if the unary AND operator could operate on every bit of an integer, couldn't there be something to do it just the same way....only on a larger amount of bits?

    I was looking at the function memcmp(), but that just returns a true or false value telling you whether or not the two chunks of memory were equal or not....

    I need a function that would basically AND two matrices together....quick as a fly....there has to be some way to do it quickly, especially in assembler.

    I am sure there is a way to do it in inline assembler really quickly, or even in C++, but I cannot find any functions that would fulfill what I need to do....

    Does anybody know of anything?

    Also keep in mind that when you allocate a matrix, it is allocated linearly, even though we think of it as a box, ex:

    1 0
    1 0

    is this to the computer:

    1 0 1 0

    So it is all a linear chunk of memory that needs to be ANDed with another linear chunk of memory....

    Any ideas?
    My Website

    "Circular logic is good because it is."

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    As long as you manage to test a lot of bits (perhaps constaintly getting 32 everytime is impossible, if you consider the matricies sliding over each other.. I think you would need to bit shift to align them).with every AND you use, there is not going to be a much faster way to have pixel perfect collosion detection.

    Your algorithm is O(N) with respect to the total number of bits in the matrix, O(N^2) with respect to the number of bits in one row of a square matrix. I can't imagine anything better that is still pixel perfect.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  3. #3
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    Yeah, this method of collision detection is both very fast and very accurate...

    I just would rather be able to use some type of function that AND's a chunk of memory with another chunk in a quick manner rather than have to use a loop...

    although even when using a loop, this method should still be very fast...its just that when using a loop it would be 500 cycles in the loop per frame to check for collisions....assuming a 25x20 sprite...
    My Website

    "Circular logic is good because it is."

  4. #4
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    You could templatize the number of rows/cols, and do some recursively template inlining, but that is a lot of work.

    Something like this, in which the counting is done at compile time, could get rid of the loops..

    http://www.cprogramming.com/cboard/s...logCombination
    On the last post.

    Also, keeping the sizes of bitmaps as 32x32, 64x32, etc, means that you can completely pack the ints, which is nice.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  5. #5
    Has a Masters in B.S.
    Join Date
    Aug 2001
    Posts
    2,263
    ok i know you alread kinda said this, but im thinking this is about as fast as you can get.

    instead of using real matrices use a ~psuedo matrice of ints like

    int bitmap[32];

    muliply would be something like

    matrixC[i] = matrixA[i] & matrixB[i];

    detecting a collision would be as simple as seeing if a single int was true

    if(bitmap[i]) collision;

    just a suggestion...
    Last edited by no-one; 05-03-2002 at 09:49 PM.
    ADVISORY: This users posts are rated CP-MA, for Mature Audiences only.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple 2-D Collision Detection
    By Tonto in forum Game Programming
    Replies: 4
    Last Post: 10-14-2006, 06:54 PM
  2. Some per poly collision detection code
    By BobMcGee123 in forum Game Programming
    Replies: 0
    Last Post: 01-31-2006, 06:37 PM
  3. Manipulating the Windows Clipboard
    By Johno in forum Windows Programming
    Replies: 2
    Last Post: 10-01-2002, 09:37 AM
  4. Is it necessary to write a specific memory manager ?
    By Morglum in forum Game Programming
    Replies: 18
    Last Post: 07-01-2002, 01:41 PM
  5. Collision detection algorithm
    By Hannwaas in forum Game Programming
    Replies: 5
    Last Post: 11-30-2001, 01:27 PM