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?
