Haha, what a waste (collision detection)

Member
Posts: 161
Joined: 2005.07
Post: #1
I'm sure most of you guys have probably been through something similar at some point time time while developing your first engine:

Anyway, for the past few days I was trying to write down on paper a formal specification for how collision detection would be handled in my game. I covered one test case after another, constantly honing the algorithms accuracy and efficiency. Suddenly I noticed a test case I missed, and for the life of me could not wrap my brain around a solution.

Finally I gave up (about a half hour ago Wacko) and just wrote in a section about the standard "binary search" type algorithm that just subdivides the distance between the player's old and new positions a few times until there are no longer any collisions. With an effective culling algorithm the difference in execution time will be negligible, plus it automatically solves all the problems I was expecting with the old algorithm requiring the floats to be more precise than they are (it called for a lot of fudging the numbers by 0.0001, which is incredibly ugly and prone to errors).

Now I just need to rewrite the relevant parts of the algorithm to work with a subdivide function and I should be good to go... hopefully. Rolleyes
Quote this message in a reply
Member
Posts: 161
Joined: 2005.07
Post: #2
Heh, I just had another "duh" moment, although these things are never really obvious until after the fact.

I still had three nagging issues related to the collision detection, all of which were not-so-coincidentally centered on the cylinder-shaped bounding box I was designing the system around. The main issue is that when a collision takes place, I needed to generate the plane tangent to the surface of the bounding box, but the right angles at the top and bottom of the cylinder made this mathematically impossible.

After toying with a few ideas, I realized using an ellipsoid make a LOT more sense in terms of computation, plus it fixes all three issues in one fell swoop. I'm finally feeling confident about being able to cobble this thing together.
Quote this message in a reply
Member
Posts: 304
Joined: 2002.04
Post: #3
Cool! So what kind of game are you building with it?
Quote this message in a reply
Member
Posts: 26
Joined: 2006.09
Post: #4
(If this gets here twice, sorry... I think some error ate my first post, or if it gets here double then it's the noob-filter).

Cylinder is pretty complex collision primitive indeed. I would recommend a capsule instead of ellipsoid. If sphere is point with radius, the capsule is line segment with radius. It is really easy to check capsule-capsule and capsule triangle collisions. I have tried ellipsoids too, but since you need non-uniform scaling at some point sometimes it is not as straight forward. Especially the collision response part.

I one of my recent prototype projects' I used capsules againts tri-mesh collision detection. It was simple to implement. For the collision response I first tried the usual bounce vector calculation but that always failed in some cases. Could have been my epsilons and floating point precision, since the problems usually occured while sliding really slowly.

I finally settled to verlet integration. The character was simulated simply using one particle anyway. The cool thing about verlet integration is that you can just push the collider out of the object, and it will slide automatically. It also works nicely if the objects in the scene are moving.

I did not use binary search, but moved the capsule in small bits if the movement delta got big. I think I used 0.45*r as maximum step size. Worked really well, but it can miss a sharp corner (I never observed this problem).

I recommend Christer Ericson's book Realtime Collision detection. It helped me a lot. After reading that book I after implementing a simple AABB tree to speed up the collision i noticed that collision detection is not so much about calculating the collisions, but trying to avoid that calculation Smile For example my brute force code took around 7ms at start most time spent in tri-capsule tests, and the optimised version took less than 1ms 90% time spent on traversing the tree.
Quote this message in a reply
Member
Posts: 161
Joined: 2005.07
Post: #5
I chose an ellipsoid after working through some other designs and realizing that a simple matrix transform can turn the ellipsoid into a unit sphere, giving the equations some nice simplifications. I already worked through all the math for the collision detection and response, and it should work great. I don't even need a binary search for the ellipsis anymore, since I was planning that as a stop-gap measures for the problems associated with the cylinder collision response.

codemattic Wrote:Cool! So what kind of game are you building with it?
Platformer. The game engine originally started out very similar to Ninja Gaiden Black, but the more I work out the gameplay details, the more the engine starts to play like Donkey Kong 64. It turns out the Ninja Gaiden engine is perfect for hand-to-hand combat but not so good at general platforming. The engine will still have elements from NG, such as wall runs and wall jumps, but most of the engine will use elements from DK's gameplay style.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Optimize the collision detection alaslipknot 1 2,867 May 12, 2013 08:02 PM
Last Post: SethWillits
  Collision detection tutorial ThemsAllTook 7 22,911 Nov 5, 2011 05:20 PM
Last Post: SethWillits
  Help with Collision Detection..(i'm almost there) carmine 1 4,719 Jun 29, 2011 12:33 PM
Last Post: ThemsAllTook
  Time Delta, collision detection mk12 19 15,794 Sep 8, 2010 06:40 PM
Last Post: AnotherJake
  Collision detection for pinball game johncmurphy 0 4,828 Sep 6, 2009 02:46 PM
Last Post: johncmurphy