locked
In-Game Collision Detection RRS feed

  • Question

  • I'm quite curious about how some games allow you to slide along any walls if you try to walk through them, based on how you approach them, and also how certain vertical slopes cause the player to slide downwards. Is there anyway to do this with minimal code, because without this it's hard to make any games.

     

    One thing I do know is that for axis-aligned walls, it's easier to use BoundingBoxes, but what I want to know is how to test collision against any kind of wall, like a diagonal one.

    Wednesday, April 18, 2007 2:37 AM

Answers

  • What guile0 said... and some.

     

    Linear algebra is very helpful in games, especially the dot product. I think of the dot product as "how similar the direction of two vectors is". 1 = same direction, 0 = perpendicular, -1 = opposite direction. Remember this rule (where a and b are vectors and theta is the angle between them)

     

    Cos(theta) = a.b / |a||b|

     

    A simple process for handling collisions would be as follows:

    1. detect the collision
    2. modify the object's position so it is not (quite) currently colliding
    3. modify the object's velocity so it won't collide next frame

    Point 3 is what you want help with and this is one of the many areas where the dot product is invaluable. To make an object slide along a wall after a collision, you want it to keep it's velocity along the wall but lose it's velocity into the wall. So you really need to calculate how much velocity your object has, in the direction of the wall's normal.

     

    Trigonometry of right angle triangles to the rescue. V is the velocity of your object, W is the velocity along the wall (sliding), U is the component of V that is perpendicular to W (or along the wall's normal). If the angle between V and U is theta then Cos(theta) = adjacent / hypotenuse = |U| / |V|. Combine this with the dot product rule above and you can calculate the magnitude of velocity that is towards the wall. Since the "towards the wall" is known (it is the opposite of the wall's normal), we now know U. And using vector addition, V = U + W => W = V - U.

     

          W

         ____

         |      /

    U  |    /   V 

         |  /  

         |/       

     

    I have given all the basic maths, now it's down to you guys to implement it

     

    Hope this helps.

    Monday, April 30, 2007 7:57 AM

All replies

  • Check here.
    Wednesday, April 18, 2007 1:00 PM
  • I have seen this article before, as well as downloaded the source code for it, but this is only for 2D Sprite collision detection - what I need is 3D mathematical collision, such as when a BoundingSphere intersects a plane, but only within a certain triangle (the triangle collision is being tested against). And not only do I need to know whether or not there's a collision, I need to know specific angles so the player will 'slide' along the wall if approaching it at an angle - sort of like in Half-Life 2 for you Steam fans (I'm one too!).
    Wednesday, April 18, 2007 9:28 PM
  • You have to know the direction your player is trying to move and the wall normal. Figure out the angle in between and change the velocity to be perpendicular to the wall normal scaled by the angle between the wall normal and current intended velocity.
    Thursday, April 19, 2007 3:33 AM
  • While I seem to have forgotten about wall normals, how can I represent the wall with the Plane object? The Plane object extends a plane out to infinity, and I just need it to take the shape of the triangle I'm testing against.

     

    If I can get an exact point of collision on the plane, I can use back-face testing to see if it's in the triangle or not, but it needs to be a 2D point, where the 2D grid is the plane.

    Thursday, April 19, 2007 12:45 PM
  • In my simple (very very simple ) doom like game, i created that sliding along walls effect by testing for x plane and z plane (y is up) collision seperately.  I moved the player along the x axis, then tested for collision, stored this in a variable, did the same for the z axis  (these axis' are world space), and moved the player accordingly.  If the x axis was blocked then the player wouldn't move in that direction.  likewise for the z axis.

     

    If you need some source code to make this clear then let me know - but at 45 lines - it isn't short  !

    This is probably a slow way of testing for collision, and it only works (at least with this particular method) in games where the walls are grid aligned, but this method works for me.

    Friday, April 20, 2007 11:18 PM
  • Go ahead and give me the code (I can figure this out myself, but perhaps your code can be modified more easily), and I'll see if I can change it to support walls that aren't grid-aligned.
    Saturday, April 21, 2007 2:23 PM
  • My In Game Collision Detection

     

    Variables :

    • rot - the direction the player is facing - in degrees
    • speedmodify - the speed of the player 1.0 is normal speed, 1.5 is running, 0.5 is slow motion
    • temppos - the players location is copyed into this variable, moved then tested for collision
    • canx - if the movement along the x axis is collision free
    • cany - like canx, but for the y axis (z is upwards)
    • extradist - this is added to the players movement to stop the player from seeing through walls when they turn sideways
    • mapwidth - the width of the map in blocks
    • mapheight - the height of the map in blocks
    • tiletypes[] - an array of all the different types of terrain
    • tilemap[,] - a 2d array of the map
    • playerspeed - how fast the player can move
    • GetXYZ() - a function that returns the players position, transformed by a distance, in a certain direction (this uses Sine / Cosine)

    If i have missed a variable explaination of something is unclear then let me know

    Code Snippet

    private void MovePlayer(int rot, float speedmodify)

    {

          Vector3 temppos;

          bool canx = false;

          bool cany = false;

          float extradist = 0.3f;

          temppos = new Vector3(GetXYZ(PlayerPos, rot, PlayerSpeed * speedmodify).X,PlayerPos.Y,0);

          if (temppos.X - extradist > 0 && temppos.X + extradist < mapheight - 0.1f && temppos.Y - extradist > 0 && temppos.Y + extradist < mapwidth - 0.1f)

          {

                if (tilemap[(int)(temppos.X - extradist), (int)temppos.Y] > 0 && tilemap[(int)(temppos.X + extradist), (int)temppos.Y] > 0 && tilemap[(int)temppos.X, (int)(temppos.Y - extradist)] > 0 && tilemap[(int)temppos.X, (int)(temppos.Y + extradist)] > 0)

                {

                      if (tiletypes[tilemap[(int)temppos.X, (int)temppos.Y] - 1].passable == true)

                      {

                            canx = true;

                      }

                }

          }

          temppos = new Vector3(PlayerPos.X, GetXYZ(PlayerPos, rot, PlayerSpeed * speedmodify).Y, 0);

          if (temppos.X - extradist > 0 && temppos.X + extradist < mapheight - 0.1f && temppos.Y - extradist > 0 && temppos.Y + extradist < mapwidth - 0.1f)

          {

                if (tilemap[(int)(temppos.X - extradist), (int)temppos.Y] > 0 && tilemap[(int)(temppos.X + extradist), (int)temppos.Y] > 0 && tilemap[(int)temppos.X, (int)(temppos.Y - extradist)] > 0 && tilemap[(int)temppos.X, (int)(temppos.Y + extradist)] > 0)

                {

                if (tiletypes[tilemap[(int)temppos.X, (int)temppos.Y] - 1].passable == true)

                      {

                            cany = true;

                      }

                }

          }

          temppos = GetXYZ(PlayerPos, rot, PlayerSpeed * speedmodify);

          if (canx)

          {

                PlayerPos.X = temppos.X;

          }

          if (cany)

          {

                PlayerPos.Y = temppos.Y;

          }

    }

    Code Snippet

    private Vector3 GetXYZ(Vector3 start, int degrees, float dist)

    {

          float x;

          float y;

          x = (float)Math.Cos(degrees * 2 * Math.PI / 360) * dist;

          y = (float)Math.Sin(degrees * 2 * Math.PI / 360) * dist;

          return new Vector3(start.X + x, start.Y + y, start.Z);

    }

     

    Monday, April 23, 2007 7:16 AM
  • Oh, you use a grid of terrain blocks. I think I can apply the concept to BoundingBoxes as terrain blocks, then try to apply it to Planes. I will investigate Planes further and see if I can get something.

     

    Click here for the image.

     

    Basically, the player's location is projected onto the Plane via the Plane's normal, and backface culling can tell if the point is in the triangle or not. Also, the distance from the Plane to the player must be less than or equal to a certain value for it to test collision. Once it detects collision, it uses the direction the player is moving, and transforms it according to the direction of the Plane. Any help on coding this will be appreciated.

    Tuesday, April 24, 2007 2:57 AM
  • Good luck with the game - i hope my code is of some use.

    It sounds like some pretty tricky coding, so i don't think i'll be of any further help, but there should be someone who has employed this concept in one of their games

    Tuesday, April 24, 2007 7:38 AM
  • Heh, if only I could meet someone from a professional game company.
    Wednesday, April 25, 2007 2:41 AM
  • We can all hope

    Wednesday, April 25, 2007 7:46 AM
  • What guile0 said... and some.

     

    Linear algebra is very helpful in games, especially the dot product. I think of the dot product as "how similar the direction of two vectors is". 1 = same direction, 0 = perpendicular, -1 = opposite direction. Remember this rule (where a and b are vectors and theta is the angle between them)

     

    Cos(theta) = a.b / |a||b|

     

    A simple process for handling collisions would be as follows:

    1. detect the collision
    2. modify the object's position so it is not (quite) currently colliding
    3. modify the object's velocity so it won't collide next frame

    Point 3 is what you want help with and this is one of the many areas where the dot product is invaluable. To make an object slide along a wall after a collision, you want it to keep it's velocity along the wall but lose it's velocity into the wall. So you really need to calculate how much velocity your object has, in the direction of the wall's normal.

     

    Trigonometry of right angle triangles to the rescue. V is the velocity of your object, W is the velocity along the wall (sliding), U is the component of V that is perpendicular to W (or along the wall's normal). If the angle between V and U is theta then Cos(theta) = adjacent / hypotenuse = |U| / |V|. Combine this with the dot product rule above and you can calculate the magnitude of velocity that is towards the wall. Since the "towards the wall" is known (it is the opposite of the wall's normal), we now know U. And using vector addition, V = U + W => W = V - U.

     

          W

         ____

         |      /

    U  |    /   V 

         |  /  

         |/       

     

    I have given all the basic maths, now it's down to you guys to implement it

     

    Hope this helps.

    Monday, April 30, 2007 7:57 AM
  • That post you made makes me want to learn more about linear algebra and vector math (more than what I already know)!

     

    Anyway thanks for the help - I can probably use this idea for laser calculations, and even lighting!

     

    This method seems similar to a technique I learned about surface lighting, using simple trigonometry and dot products.

    Tuesday, May 1, 2007 1:15 AM
  • Here is a handy function I wrote that demonstrates the techniques I described above... so far I have used it in many places, especially handling collisions. It is not optimised yet.

     

    Code Snippet

    public static Vector3 ProjectPointOnPlane(Vector3 point, Plane plane)

    {

      // Plane's formula is A + B + C + D = 0 where (A, B, C) is the plane's normal

      // and D is distance to origin along plane's normal. Therefore, D * (A, B, C) is a point on the plane.

      Vector3 pointOnPlane = plane.Normal * plane.D / plane.Normal.Length();

     

      // Vector from some point on the plane to the passed in point.

      Vector3 testVector = pointOnPlane - point;

     

      // Cos(theta) = A.B / |A||B|

      float cosTheta = Vector3.Dot(Vector3.Normalize(testVector), Vector3.Normalize(-plane.Normal));

     

      // using Cos(theta) = Adjacent / Hypotenuse.

      // We know Hypotenuse = testVector and Adjacent = (projectedPoint - point).

      Vector3 projectedPoint = point - (testVector.Length() * cosTheta * plane.Normal);

      return projectedPoint;

    }

     

    Perhaps someone out there has a more efficient way of doing this? If so I am interested to hear it!

     

    Also Quantumdude, above you mentioned testing if a particular triangle has been collided. I had this same problem when colliding with my terrain. I really don't know if there is a better approach (you mention back face testing?) but I actually implemented a bool PointAbovePlane function (using Dot product), treated each edge of the triangle as a plane perpendicular to the triangle and tested that my point was "Above" each of these planes. This allowed me to ensure that I was colliding with part of the triangle rather than any old part of the triangle's plane. Note that the function below takes three points on the plane (ie the triangle vertices) rather than a Plane object.

    Code Snippet

    public static bool PointAbovePlane(Vector3 point, Vector3 v1, Vector3 v2, Vector3 v3)

    {

    Vector3 normal = Vector3.Cross((v2 - v1), (v3 - v1));

    float dotProduct = Vector3.Dot(v1 - point, -normal);

    return (dotProduct > 0);

    }

     

    Tuesday, May 1, 2007 1:56 AM