matrixes for collision detection

Well, I am back to work on my game.

Xterria is probably shouting in his seat, "FINALLY! GET TO WORK!"

haha

anyways, I have encountered something that I could fix...but the only way I know how to fix it would be significantly slow...and I know there must be a faster way to do this...

Here is my problem:

Take blitting for example. I am using SDL by the way. Using blitting we can easily do a quick copy of one surface or even just a part of one surface to another surface or the screen. For example we could outline a rectangle using SDL_Rect and blit that specific part of a surface to another surface or the screen. Blitting is incredibly fast, and as far as I know I think it is just a quick memcpy(), right?

Well, my problem isnt with blitting, but it is similar to blitting.

I have 2 matrixes. Both matrixes only contain boolean values. Also, one is larger than the other.

The first matrix is a "bit matrix" of the entire map in my game. A 1 represents an obstacle, a 0 represents a clear path. For collision detection purposes, I only need a very small piece of this map's bit matrix at any one point in time.

I copy the part I need from the map's bit matrix into a smaller bit matrix which is then used for collision detection.

The problem I am having is when I copy part of the larger matrix to the smaller matrix being used for collision detection. I am using a slow nested loop (with a Big-O value of N^2) to move through every element in the section of the matrix that I need and copy it to the second matrix. That is slow.

Is there any way you can outline a specific rectangle of a matrix (or array even), almost like in blitting, and do a fast memcpy to another matrix (or array). It is like blitting. I dont want to "blit" the entire matrix to the other matrix. I just want to outline a rectangle of the matrix that I want to "blit", and then "blit" it to the other matrix, per se.

If this can be done with surfaces, surely it can be done with matrixes or arrays?

I do see possible obstacles in doing this with matrixes, but it should be able to be done with at least arrays, right?

Anybody have ideas?

You want to check if a rectangle overlaps any of your "obstacle bits", right?

There is no need to copy a smaller part of it, just do the checking directly in the big one instead.

First, calculate two points: The upper left (P1) and the lower right (P2) of the rectangle.
Divide the X and Y of these points with the dimension of the tiles (if you have 32x32 tiles, divide X by 32 and Y by 32) so you get the points expressed as elements in your array, rather than pixel coordinates.

Then do a nested for loop, one from P1.X to P2.X, and the other from P1.Y to P2.Y. If any element in your array at location (X, Y) contains an obstacle (the bit is set), then the rectangle overlaps an obstacle.

See this picture:

no no...dont think you completely understand my method...here, i will explain it a little bit more...

first of all, my collision detection is pixel perfect, so each little bit set on and off is one pixel on the screen, not a block of pixels.

http://www.geocities.com/theilkhan/c...ndetection.bmp

this is my pixel perfect collision detection.

i am also going to add a layer over it that is going to be bounding box collision detection, but i have not done that yet.

blah...the link doesnt work...just go to my webpage and go to the very bottom of the main page, the BMP is there...it will give u info...

http://www.geocities.com/theilkhan/index.html

That makes it even easier, no division with the dimension since they have the same scaling.

If you have two obstacle bit-maps (one background and one player), you also just need two nested for-loops basically the same as I showed above. Check if both maps have an obstacle on the same spot, the return Collision == true.

Also, you can upload images on this site when posting. Look at the bottom of the screen (when writing/posting a message).

thats what i am already doing. i have been doing that for several months now.

the point is that it is slow. nested for loops are slow. i am looking for speed here, and I am wondering if a memcpy could simplify things anywhere in this process...

I have been tinkering with my code a little bit, and this is what I have come up with. I am not quite sure if it is legal, but I hope it is.

In the code below, you will see a function called AND_DTP. It is simply a function that runs through two matrixes and AND's the bits of every corresponding element in each matrix together, and returns them in a variable called finalMatrix, which is a reference variable. It also physically returns (as a return statement), a value indicating whether or not any collision occurred at all. finalMatrix is for pinpointing the exact location of a collision, the returned value is for finding out whether there was a collision or not. Although finalMatrix does not play a big part in this function, it does play a big part in other functions.

I will show my old function first, and then my new function. The function isnt that long, so dont worry:

Code:

---


int PLAYER_DTP::CheckForCollision ( MAP_DTP *Map )
{
        int **finalMatrix, **mapMatrix;

        int cX = Map->GetX() + CurPlayerX; //get starting coords of rect
        int cY = Map->GetY() + CurPlayerY;
        int tempy = cY;

        //size the matrix
        mapMatrix = new int *[ MATRIX_WIDTH ];
        for ( int x = 0; x < MATRIX_WIDTH; x++, cX++ )
        {
                mapMatrix[x] = new int [ MATRIX_HEIGHT ];
                for ( int y = 0; y < MATRIX_HEIGHT; y++, cY++ )
                {
                        mapMatrix[x][y] = Map->ForegroundBitMatrix[cX][cY];                       
                }
                cY = tempy;
        }

                // AND the matrixes together:
        int isCollision = AND_DTP ( CharacterAnimation[CurAnimationIndex]->GetCurrentFrame()->bitMatrix,
                mapMatrix, finalMatrix );       

        delete [] mapMatrix;
        delete [] finalMatrix;       

        return isCollision;                       
}

---

that was my old function. Now I have changed it to the following function. Notice the memcpy statmenet. Check the legality of it for me.

Code:

---


int PLAYER_DTP::CheckForCollision ( MAP_DTP *Map )
{
        int **finalMatrix;
        int mapMatrix [ MATRIX_WIDTH ][ MATRIX_HEIGHT ];

        int cX = Map->GetX() + CurPlayerX; //get starting coords of rect
        int cY = Map->GetY() + CurPlayerY;
        int tempy = cY;

                //Since we are checking for a collision between the player and just a small piece of the map
        //We need to take a small part of the map, equal to the size of the player, that corresponds
        //to the position that the player is in, and put it in a seperate matrix.  We will then
        //do a boolean AND operation on the two matrixes that will return a final matrix which can
        //tell us whether a collision has occurred or not.

        //Size and fill the matrix containing the piece of the map:
        mapMatrix = new int *[ MATRIX_WIDTH ];
        for ( int x = 0; x < MATRIX_WIDTH; x++, cX++ )
        {
                mapMatrix[x] = new int [ MATRIX_HEIGHT ];
                memcpy ( mapMatrix[x], *(Map->ForegroundBitMatrix[cX] + 4), MATRIX_HEIGHT );
        }
       
        // AND the matrixes together:
        int isCollision = AND_DTP ( CharacterAnimation[CurAnimationIndex]->GetCurrentFrame()->bitMatrix,
                mapMatrix, finalMatrix );       

        delete [] mapMatrix;
        delete [] finalMatrix;       

        return isCollision;                       
}

---

blah, in my 2nd function, change this:

Code:

---


mapMatrix = new int *[ MATRIX_WIDTH ];
        for ( int x = 0; x < MATRIX_WIDTH; x++, cX++ )
        {
                mapMatrix[x] = new int [ MATRIX_HEIGHT ];
                memcpy ( mapMatrix[x], *(Map->ForegroundBitMatrix[cX] + 4), MATRIX_HEIGHT );
        }

---

to this:

Code:

---


for ( int x = 0; x < MATRIX_WIDTH; x++, cX++ )
        {               
                memcpy ( mapMatrix[x], *(Map->ForegroundBitMatrix[cX] + 4), MATRIX_HEIGHT );
        }

---

i think ;)

Then what? You still have to use loops to check the elements, since you can't compare two whole arrays with each other.
It seems to me that you gain nothing from this. Have you timed both functions?

And to answer your original question:
No, you can't copy it in 1 call. You have to memcpy each line in the matrix (like u did).

For most situations, checking only the border of the object frame would suffice.

Quote:

---

For most situations, checking only the border of the object frame would suffice.

---

for many games, yes...but unfortunately, not for this game...

its because it is very physics based and pixel perfect...if you have ever played Liero, you would understand...

probably the most evident reason that border checking wont work is because of gravity. because the player constantly accellerates due to gravity...for all i know he could pass completely through an object if all i did was border checking. for example, if gravity was to make his position directly in the place where an object was...and so it put him there...but the object did not extend to the player's surface's borders...then it would not catch the object....therefore he would fall straight through it. but what is supposed to happen is it is supposed to see the collision and handle it correctly so that he ends up on top of the object that he collides with, not in it or through it...

even with pixel perfect collision detection i am still facing problems...

because of gravity...a player could be falling so fast that instead of just being in the place of an object, he could go past an object that he was supposed to collide with...

for example, lets say an object is 10 pixels under the player. the accelleration due to gravity is, lets say for now, 2 pixels per frame^2 (that is actually a bit too much, but its just an example). lets say the player has already been falling for 10 frames of animation. that means he already has a velocity of 20 pixels per frame. therefore, he will be blitted from his last position to his next position, 20 pixels below him in just one frame of time (because of gravity). that would completely miss that object that was 10 pixels below him in the first place...

so therefore even with pixel perfect detection i have a couple bugs that i need to sort out....

and i am aware of the whole thing about the AND_DTP function, in which I am forced to use a nested loop there. I am looking for better options but it seems to be the only one.