matrixes for collision detection

This is a discussion on matrixes for collision detection within the Game Programming forums, part of the General Programming Boards category; Well, I am back to work on my game. Xterria is probably shouting in his seat, "FINALLY! GET TO WORK!" ...

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

    Question 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?
    My Website

    "Circular logic is good because it is."

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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:
    Attached Images Attached Images  
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    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.
    My Website

    "Circular logic is good because it is."

  4. #4
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    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
    My Website

    "Circular logic is good because it is."

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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.

  6. #6
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Also, you can upload images on this site when posting. Look at the bottom of the screen (when writing/posting a message).
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  7. #7
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    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;			
    }
    My Website

    "Circular logic is good because it is."

  8. #8
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    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
    My Website

    "Circular logic is good because it is."

  9. #9
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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).
    Last edited by Magos; 11-09-2002 at 06:27 PM.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  10. #10
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    For most situations, checking only the border of the object frame would suffice.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  11. #11
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    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.
    My Website

    "Circular logic is good because it is."

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Collision Detection
    By Grantyt3 in forum C++ Programming
    Replies: 3
    Last Post: 09-30-2005, 04:21 PM
  2. multiply 2 matrixes
    By BianConiglio in forum C Programming
    Replies: 2
    Last Post: 04-14-2005, 02:52 AM
  3. bounding box collision detection
    By DavidP in forum Game Programming
    Replies: 7
    Last Post: 07-08-2002, 12:43 AM
  4. collision detection
    By DavidP in forum Game Programming
    Replies: 2
    Last Post: 05-11-2002, 02:31 PM
  5. Replies: 4
    Last Post: 05-03-2002, 10:40 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21