Jump to content
  • Advertisement
  • 08/15/14 02:00 PM
    Sign in to follow this  

    Simple but Effective Collisions Part 1: Radial Collision Handling

    Math and Physics

    The illusion of smooth collision detection is paramount to a realistic gaming experience. Imagine if you were playing a horror game and you suddenly slipped through the dungeon walls, or you were driving a vehicle through a forest, only to crash into a tree with no effect or feedback. The facade of realism would instantly be broken. The horror game's environment would no longer be immersive, and driving your vehicle would simply feel like moving a camera through a world you cannot touch or feel. Of course, you probably already knew that. Anyhow, the purpose of this article is to present the first of two methods for modelling collisions in your own games. I'm hoping to release another article detailing the second method in the near future. The method described in this article, which I call 'radial' collision handling, can be used to model objects which can be enclosed by bounding cylinders. It is ideal for objects such as trees and poles, and can even be used to simulate collisions with small rectangular objects. I call the second method 'nodal' collision handling, and it can be used to provide bounding regions for a series of connected walls in any arrangement. It could be used to model the interior of a house or hut, or the walls of a maze. It will hopefully be discussed in a future article. I created these methods (or rather implemented them, as it's likely they've been used before) with two aims. First off, each method should allow me to detect collisions, which is an obvious requirement of collision detection! Second, each method should handle collisions in such a way as to 'slide' the player/object around the obstacle rather than bringing them to an awkward halt as soon as they touch it.

    Radial collision handling

    The Concept

    As mentioned, this system allows you to handle collisions with objects which can be enclosed by bounding cylinders. These cylinders can be defined by two numbers, or rather, a vector and a float - one containing a location, and the other containing a radius. Let's imagine we have a simple scenario with a triangle of trees placed on a simple flat plane:
    The player can move the camera around in a first person view, and is able to walk among the trees. We will use the 'radial' collision detection method to prevent the camera from passing through the trees. When the player attempts to walk through a tree, the algorithm will slide them smoothly around it, as seen in pretty much all current first person games. This process involves two steps, which are repeated every frame:
    1. If the camera has entered a tree's bounding cylinder, register a collision.
    2. Calculate a new location for the camera which puts it back outside the bounding cylinder.
    So, how do we do this in practice?

    The Implementation

    We'll start out by defining the location of each tree using an array of 2D vectors. We only need 2D vectors because the trees are not going to affect our motion in the up-down direction. If you wanted to use this algorithm for objects on 3D terrain rather than a 2D plane, it should work just as well with the same vector format because it's not possible for a walking person to collide with a tree from above or below, only from the side. Because of this, we only need to worry about the positions of the trees in the x-z plane, whether we have a flat terrain or not. As mentioned, we will use DirectX syntax and functions from here on in: //The array contains 3 vectors - one for each tree: D3DXVECTOR2 v_treePositions[3] = {D3DXVECTOR2(0, 1), D3DXVECTOR2(1, 0), D3DXVECTOR2(-1, 0)}; We will also define a variable to describe the radius of each tree trunk. We will assume they're all the same radius, but if you wanted to personalise each one, you could define an array of numbers, or add a third component to the vectors describing tree locations. //Each tree is 1m in radius: float f_treeRadius = 1.0f; ...and while we're at it, we will define a vector to hold the location of our first-person camera as it changes from frame to frame: //This is a global vector holding the camera's location. It starts at the centre of the world (0, 0, 0): D3DXVECTOR3 v_camPos(0, 0, 0); OK, now each tree has an entry in our program, and we know where our player's camera is from frame to frame. All that remains is to put this information to use! We will define a function which will be called every frame. This function will loop through the tree locations, comparing each one to the location of the camera for that frame. If it registers a collision (i.e. if the camera's location is closer to one of the trees than is permitted by the bounding radius), then we will push the camera back outside the bounding radius. The effect is cumulative, meaning that each tree makes its own contribution to the overall position change. This way, the algorithm also works for closely bound groups of trees where the camera could be in contact with more than one at once. Let's go through the function line by line: D3DXVECTOR2 handle_Collisions_Radial() { D3DXVECTOR2 v_deltaPos = D3DXVECTOR2(0, 0); for (int i = 0; i < 3, i++) { D3DXVECTOR2 v_vectorToCentre(v_camPos.x - v_treePositions.x, v_camPos.z - v_treePositions.z); if (D3DXVec2Length(&v_vectorToCentre) < f_treeRadius) { v_deltaPos += ((f_treeRadius / D3DXVec2Length(&v_vectorToCentre)) - 1) * v_vectorToCentre; } } return v_deltaPos; } First, we notice that the function returns a D3DXVECTOR2. This corresponds to the amount by which the camera needs to move to put it outside of the bounding cylinders of all the trees. It returns a D3DXVECTOR2 because the trees only affect the location of the camera in the x-z plane. Second, we create an inline vector called v_deltaPos which will be filled with the overall change in position required to put the camera outside the bounding radii of all the trees. This is the vector which the function will eventually return. Next, we enter a loop which will iterate through all the trees. Since we have three trees, we will have three iterations. Third, we create a temporary vector called v_vectorToCentre. This contains a directional vector between the location of the camera and the location of tree in the x-z plane. Fourth, we compare the length of this vector to the bounding radius. Note that the +y direction is up. Fifth and finally, if the camera is indeed within the bounding radius of the current tree, we will add on just enough of v_vectorToCentre to put it back outside the tree trunk. Once the loop is complete, we return the resulting position change. The process is fairly intuitive until the final step. This diagram explains the maths behind it a little clearer:
    As you can see, the location of the camera has moved within the bounding radius of tree . In order to put the camera back outside of the bounding radius while simultaneously making it slide smoothly around the edge, we need to add a certain amount of the vector v_vectorToCentre to the camera's position until it is once again outside the bounding radius, such that: CodeCogsEqn1.gif In this equation, |v_vectorToCentre| denotes the length of the vector between the camera position and the tree's centre. It is calculated using the D3DXVec2Length() function. We are looking for the value of k - that is, the linear multiple of v_vectorToCentre which we should add to our camera position in order to put it back outside the bounding radius. In order to find the value of k, we can first divide through by |v_vectorToCentre|. This gives us: CodeCogsEqn2.gif This can easily be rearranged to get: CodeCogsEqn3.gif We have now calculated our value of k. All that remains is to add this linear multiple of v_vectorToCentre to our overall change in location (v_deltaPos). If you review the fifth step in the function, you can see that this is exactly what is happening. If called every frame, this function will calculate a collision contribution for each tree in the loop. Once this contribution is acquired, it should be added to the camera position vector as follows: //Call the function to assess collisions: D3DXVECTOR2 v_camPosCollisionDelta = handle_Collisions_Radial(); //Since this function returns a D3DXVECTOR2 and our camera position is a D3DXVECTOR3, we //will need to create a dummy D3DXVECTOR3 with no y-component to add to v_camPos: D3DXVECTOR3 v_camPosCollisionDelta3D(v_camPosCollisionDelta.x, 0, v_camPosCollisionDelta.y); //Finally, we will move the camera according to our collison delta vector: v_camPos += v_camPosCollisionDelta3D; //Now that we have our new camera position, we can continue to render the frame as normal...


    That's it! You may be surprised at how well this simple method works. The effect is quite satisfying, and it certainly added an extra professional depth to my exploits in the first-person camera world. Of course, this method could be used to handle collisions involving objects other than a first-person camera, and subjects other than trees. This is also a bare-bones version of the algorithm, and it could easily be adapted to handle collisions in 2D games as well as collisions between circles and spheres and their environment (throughout, we assumed that the first person camera was a simple point rather than an object with dimensions). I intend to write another article describing another collision method which can be used to simulate walls and interiors/exteriors of buildings and things like hedges and maze walls. Until then, thanks for reading!

    Article Update Log

    19 May 2013: Initial release

      Report Article
    Sign in to follow this  

    User Feedback

    Well explained and simple. Though I can't see why a camera can be inside two trees at the same time. And should a tree be standing next to a wall, could this push the camera through that wall?


    Another "bug", might be if you come at an high speed and for the next frame, the camera has passed through the center and you are basically pushed out from the back of the tree.

    Share this comment

    Link to comment
    Share on other sites

    Hey, thanks for the comment,


    I found that I actually had to increase the size of the bounding radius beyond the physical radius of the tree, in order to make sure the near plane was always outside of the tree mesh, so in this case, it's possible that the 'corrected' bounding cylinders could overlap if two trees sit right next to eachother. This is determined by the preference of the user though - if the cylinders were kept right enough, then it shouldn't be a problem.


    Yes, it is possible that you could get errors if you have awkward setups with trees and walls, but I actually found that it's pretty difficult to get stuck - mainly because it pushes you out of the way before you can really get embedded in a tight corner. But yeah, it's not perfect!

    Share this comment

    Link to comment
    Share on other sites

    To fix your near plane problem, you should consider that the player himself has a radius :)

    following line:

    		if (D3DXVec2Length(&v_vectorToCentre) < f_treeRadius)

    Could be changed to

    		if (D3DXVec2Length(&v_vectorToCentre) < f_playerRadius + f_treeRadius)

    (with f_playerRadius defined elsewhere) and then the player wouldn't fit into gaps that were too small for them either.

    Share this comment

    Link to comment
    Share on other sites

    This article was a good read. Brief and concise. Nice work :)


    If you bring in a bit of recursion to keep moving away from the colliding objects with an increasing amount each time, I find it tends to be more robust when dealing with multiple collisions (i.e uncolliding with one tree thrusts you through another (or through a wall)).


    So rather than calculating and jumping to an uncolliding location, perhaps move in smaller increments towards that same location whilst also still checking against other objects (of course this may be slightly more cpu intensive).

    Share this comment

    Link to comment
    Share on other sites

    This article is okay. You're essentially talking about bounding sphere collision detection, but have a special case where it's appropriate to use a cylinder. A good collision detection system needs to be able to handle every possible collision case and be generalized enough to be broadly applicable. Here's an excellent MSDN article overviewing bounding volumes.

    As far as bounding spheres go, they should be able to intersect with the following:
    Bounding Frustums
    Bounding Boxes
    Bounding Spheres

    There are three collision states:
    1. Contains
    2. Intersects
    3. Disjoint


    Also, I don't know what you gain from just using 2D vectors. Why not go with 3D vectors? All it costs is an extra 4 bytes in memory and it gives you much more broad applicability. The math doesn't change.

    Lastly, there is a chance that a small object moving very fast could pass through a small bounding volume. Think of a fast ball vs. a baseball bat. Let's say the bat is a cylinder with radius 1 at X = 0. The ball is at position X = -2 with radius of 0.5f. If any point of the ball is between X = -1, and 1 at any time, we have a hit. But, the ball moves 5 units per frame. At frame 0, the ball is at X = -2. It's nearest point to the bat is at -1.5. No hits occur. Next frame, we now move the ball 5 units on the X axis so that it is now positioned at X = 3. Now, the balls nearest point to the bat is at X=2.5f. The ball passed through the bat completely between frame 0 and frame 1 and there was no collision! This is wrong. You need to find the point of impact which lies between frames, and a simple collision check doesn't account for this case.

    Share this comment

    Link to comment
    Share on other sites

    I wish you used pseudocode as the "shouting" D3DXVECTOR name and the unnecessarily type-prefixed camel case are somewhat distracting. As opposed to, say, `delta_pos += ((tree_radius / vec2_length(vector_to_center)) - 1) * vector_to_center;`


    But let me ask you something else:

    D3DXVECTOR2 v_vectorToCentre(v_camPos.x - v_treePositions[i].x, v_camPos.z - v_treePositions[i].z);
    D3DXVECTOR3 v_camPosCollisionDelta3D(v_camPosCollisionDelta.x, 0, v_camPosCollisionDelta.y); 

    - Are you enjoying this?


    Why subject people to the mind-boggling exercise of axis swapping when it's not only perfectly fine, but also clearer and easier, to simply use the same axes? Just like 2D X = 3D X, 2D Y could be 3D Y, and the code would then make a bit more sense.

    Share this comment

    Link to comment
    Share on other sites

    Good introduction. In your next article it would be nice if you describe common collision bugs, like floating point imprecision (you're moving the player to the surface of the sphere not completely outside and operator < could fail) or misprediction of where the collision will occur for moving objects

    Share this comment

    Link to comment
    Share on other sites

    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!