Click here to Skip to main content
Click here to Skip to main content

My first collision algorithm

, 18 Jul 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
Collission algorithms aren't rocket science and this article proves this idea.

Introduction

When I started 3D programming I soon realized that a lot of things I gave 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 give 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. Been this demo 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 the 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 find it out.

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 it’s 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 2 functions trying to find the intersection point
  3. When you find the intersection point there are 3 choices:

     

    1. Intersection point is contained in the line segment.

    2. Intersection point is not contained on the line segment and is near of one extreme of the line segment.
    3. Intersection point is not contained on the line segment and is near of 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 less of the 3. The distance is calculated by the Euclidian method, try this link if you don’t know 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 articles 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 thing 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. If you like this article you can visit my blog for more stuff like this.

History

  • 25 Aug 2013: Initial release.
  • 30 Aug 2013 Fixed blog link , image order and changed cover image(now it has codeproject logo)
  • 18 Jul 2014 Uploaded source code to Codeproject, instead of external server

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Vasily Tserekh
Software Developer
United States United States
born on 86, had my first computer at the age of 8, wrote my first code at the age of 15(pascal), began to study informatic engineering at 2005 and graduated in 2010, now I am currently working on a software development department in my company. Working with extjs mysql and php. I have a dev blog www.vasilydev.blogspot.com. My real pasion is 3D game programming and playing guitar. Ive programmed stuff in C#, python, Delphi, PHP, C++, JS, QT and others...
Follow on   LinkedIn

Comments and Discussions

 
GeneralMy vote of 5 PinmemberAmir Jalilifard3-Sep-13 23:18 
QuestionWhat is updated? Pinmembernewton.saber30-Aug-13 4:31 
AnswerRe: What is updated? PinmemberVasily Tserekh30-Aug-13 4:33 
GeneralMy vote of 5 PinmemberVolynsky Alex30-Aug-13 1:24 
AnswerMy vote of 5 PinmemberDaniel Chernenkov29-Aug-13 9:00 
GeneralMy vote of 5 PinmemberSouthmountain28-Aug-13 15:31 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.1411023.1 | Last Updated 18 Jul 2014
Article Copyright 2013 by Vasily Tserekh
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid