My First Collision Algorithm

• Download demo - 12.5 MB

Introduction

When I started 3D programming, I soon realized that a lot of things I took for granted on all the games I played, weren’t so. For example, in a 3D world, there are only textures and triangles to be drawn. Collisions and a lot of things alike have to be created on your own. That means that if you want the camera not to pass through a wall, you have to create an internal geometric representation of the wall and manage the logic yourself. I want to point out that there are many approaches for handling collisions. I am only showing my approach, I think that everything should be from simple to complex. I have seen so many people trying to enter the 3D programming world but most of them back out because a lot of tutorials demand previous background of so many areas of knowledge that people usually get overwhelmed. About the math used in this article, I studied it at school when I was about 12 years old, so I guess you don’t need to have a solid background to understand this and it won’t be rocket science. I say again this algorithm is only my approach, I think there are far more better ones on the web but this one is pretty simple and it puts you on the right way.

Background

First of all, I assume I am handling 2D collisions. I am on a 3D environment but the floor is a flat surface. It’s like looking at a maze from above, the walls can be considered line segments and the camera can be considered a point. If I plot those line segments into a coordinate axis I can make use of analytic geometry to perform some collision calculations. So if say I don’t want my camera to get near a wall (in this case a wall is a line segment) no more than 1 unit; then every time I move my camera I check the distance to all those line segments and if one distance is less than 1 unit, then there is a collision and the camera won’t move to that direction. Of course, the new position has to be checked before moving the camera.

This image gives you an overview of my method:

This has a drawback. You have to create your line segments on your own. That means that if you have a room, then you have to create 4 line segments. That does bring another complication because you don’t get to know the coordinates of the points. As this demo is only for educational purposes, I have created in the scene a code that displays on the left top side of the screen the current position of the camera. You go into one corner, write down the coordinates, then go to the other corner of the wall and write down to other coordinate. In this way, you have the 2 points needed to create a line segment. I know you have to work a lot to create all the collisions for a simple scene but this goes in order to gain in understanding. Later on, if you want to simplify, you can make dummy points on the 3D object and interpret them on the code later.

Steps to Determine a Collision

The main objective of this demonstration is finding out the distance between a point (camera) and a line segment (wall). Here are the steps to do it.

Y = MX + N where M is the pendent of the equation and N is where it intersects the Y axis. The first step is finding out that equation. M can be found using the 2 points of the line segment and its equation is M = (Y1 – Y2)/(X1 - X2); to avoid division by zero I add a very small number if (X1 - X2) leads to zero.

1. A line segment is defined by 2 points and is contained in a linear function of the type:

M1X + N1 = M2X + N2
X = (N2 – N1)/ (M1 – M2)

Y is found replacing X in any of the two equations.

1. Later, you try to find out the equation of the linear function perpendicular to that equation. For that, you know that the pendent of that equation is M2 = - 1/M1.
   
   
    
2. Then you Equals the two functions trying to find the intersection point.
3. When you find the intersection point, there are three choices:

   

   

   1. Intersection point is contained in the line segment.

      

   2. Intersection point is not contained on the line segment and is near one extreme of the line segment.
   3. Intersection point is not contained on the line segment and is near the other extreme of the line segment.

This is the main reason why I calculate the distance between the intersection point and the two extremes, and then the real distance is the least of the three. The distance is calculated by the Euclidian method, try this link if you don’t know it. It is very simple.

Note that in this example, the intersection point is not contained in the line segment.

Using the Code

In this demo, I used a small engine that I developed to simplify other stuff such as texture loading, drawing, and others. Here is a brief look at the classes it contains.

House.cs

This class contains the methods to draw the house seen on the demo. Here is the code where I create all the collisions:

public void CreateCollisions()
{
 Collision.AddCollisionSegment(new Vector2F(-24.4f, -14.1f), new Vector2F(18.9f, -14.1f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(-24.4f, -14.1f), new Vector2F(-24.4f, 13.2f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(-20.2f, -0.1f), new Vector2F(-4.8f, -0.1f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(-0.5f, 0.7f), new Vector2F(-0.5f, -8.7f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(19.4f, 14.4f), new Vector2F(-24.4f, 14.4f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(19.4f, 14.4f), new Vector2F(19.4f, -14.4f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(-17.5f, 0.5f), new Vector2F(-17.5f, 11), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(13.4f, -0.15f), new Vector2F(18.74f, -0.15f), 0.5f);
 Collision.AddCollisionSegment(new Vector2F(-0.43f, -9.1f), new Vector2F(12.4f, -9.1f), 0.5f);
 //Collision.GhostMode = true;   
}

Note the third parameter is the distance in which a collision will be valid. I mean if the distance of the camera to that line segment is less than that parameter, a collision event will be triggered.

Camera.cs

This class handles camera movements. If you take a look at the code, you will see how collision is managed:

if (pressedButton == 1) // forward button is pressed
{
    if (!Collision.CheckCollision(new Vector3(eyex - (float)i * 
            forwardSpeed, eyez - (float)k * forwardSpeed, 0)))
    {
       eyex -= (float)i * forwardSpeed;
       eyez -= (float)k * forwardSpeed;
    }   
}

Note that current X and Z position will only be updated if there is no camera collision. Also note that the floor is located on the XZ plane.

Collision.cs

This is the class that handles collisions; note the code that checks for a collision.

public static bool CheckCollision(Vector3 camaraPos)
{
    if (!ghostMode) //if collisions are not disabled
    {
       foreach (var item in colitionSegments)
       {
           if (item.segment.DistToSegment(camaraPos) < item.ColitionDistance)
           {
              return true; 
            }
       }               
     }
     return false; 
}

Segment Struct

This struct holds all the calculations explained at the bottom of this article. First, it finds the segment linear equation on the constructor and it has the method to calculate the distance between a point and a line segment.

public float DistToSegment(Vector3 other)
{
    //calculate the two linear functions
    float n2 = other.Y - m2 * other.X;   //y = m2x + n   m2 = -1/m1

    //calculate the intersection point(i.p.)
    Vector3 intersectionPoint = new Vector3();
    intersectionPoint.X = (n2 - n1) / (m1 - m2);
    intersectionPoint.Y = m1 * intersectionPoint.X + n1;
    float d = Vector3.DistPointToPoint(intersectionPoint, other);

    float dist1 = Point3D.DistPointToPoint(other, first);
    float dist2 = Point3D.DistPointToPoint(other, second);


    //if the i.p. is contained in the rect segment, return d else 
    //the minimun value between dist1 and dist2
    if ((intersectionPoint.X < first.X && intersectionPoint.X > second.X) ||
        (intersectionPoint.X > first.X && intersectionPoint.X < second.X))
        return d;
    else
        return Math.Min(dist1, dist2);   
}

Controller.cs

This is the controller class; the most important part relative to this tutorial is the Draw method:

public void DrawScene()
{    
   house.Draw();
   sky.Draw();  
   //DebugMode.WriteCamaraPos(200, 200);
   //Collision.DrawColissions();
}

The function WriteCamaraPos outputs to the screen the current coordinates of the camera; this is how I find out the coordinates of both extremes of a wall to define it as a line segment. The other commented function draws all the lines representing collisions on the scene. This is how I see if everything is going ok. Sometimes, if you want to see them, you have to comment the code that draws the house into the screen in order to see them.

Points of Interest

You will find out that all collisions for the house on the demo have not been implemented, only a few. If you want to learn how I did it, give it a shot and try to complete the collisions on the scene. This approach will place you on the right track if you want to learn this side of 3D programming. I think this article proves that implementing your own collisions in a game doesn't always to have to be difficult. Also, it proves that if you really want to learn 3D programming, you have to make a lot of things by yourself rather than relying on a complex engine. In this way, you will be your own God and you will go as far as your mind takes you. 

History

• 25^th August, 2013: Initial release
• 30^th August, 2013: Fixed blog link, image order and changed cover image (now it has Code Project logo)
• 18^th July, 2014: Uploaded source code to Code Project, instead of external server