Xbox LIVE Indie Games
Sort Discussions: Previous Discussion Next Discussion
Page 1 of 2 (28 posts) 1 2 Next >

Collision Detection - How?n00b time

Last post 10/24/2008 7:55 AM by matieman. 27 replies.
  • 10/21/2007 11:01 AM

    Collision Detection - How?n00b time

    Hey all,

    First off, I'm an artist, not a good programmer, but I'm learning. I'm trying to create a very very basic engine to test out stuff I create in XNA. Here's the basis for my engine: A guy walks around on terrain. Not too hard, right? I can get my models into XNA, I can animate them, normal map them, anything the samples show me how(copy-paste coding basically :\). All I need is to be able to do some collision detection with something other than collision spheres. something that will detect where my player collides with the terrain (terrain will be modeled, not height map, It's complex map geometry). Any suggestions?

    *I've heard of some Dx stuff with triangle collision detection, but never found many articles on it, is this worth looking into? also newton physics?

    thx ahead of time,
    -Chris
  • 10/21/2007 1:24 PM In reply to

    Re: Collision Detection - How?n00b time

    there are 2 classes in xna that help you in collision detection BoundngBox and BoundingSphere.
    in the bounding box class you define 2 vectors one is the minimum and one is the maximum then an invisible box is created between them you can use the .intersect method to determine if another box or sphere is collided with it.the bounding sphere you only define one vector the center of the sphere then you define a float value that is the radius of the sphere. the sphere class also has a intersect method. i prefer to use spheres beacuse they are easier to handle.in your case you'd defne the center of the sphere the models current position. i use a good way for collision detection that is i store the position of the model before actually calling the move function then if it collides then i make the current position equal to the previous position.

    here is some code

     // at the beggining of the game class
    BoundingSphere BSphere;
    BoundingBox BBox;//the other box that is going to be collided with


    //define a new method
    private void CheckCollision()
    {
    if (BSphere.Intersects(BSphere))
    {
    //the two spheres collided what to do
    currentMeshPosition = PreviousMeshPosition;
    }
    }

    I hope that helped

  • 10/21/2007 2:05 PM In reply to

    Re: Collision Detection - How?n00b time

    He needs collision detection with complex terrain! Well, I guess you could use Newton, like I am trying now, but it has no samples for XNA that demonstrate how to use it properly :(
  • 10/21/2007 3:15 PM In reply to

    Re: Collision Detection - How?n00b time

    if what you are searching for is using terrain colision detection there s a custom content processor that makes you able to extract the vertex data i think its in ziggyware so you could use the Y component of the position as the height data then make the height of the camera equal to the Y of the vertex.
  • 10/22/2007 3:26 PM In reply to

    Re: Collision Detection - How?n00b time

    This may be a little more advanced than you are hoping for, but there is an article out there called the Plane-Sphere Sweep Test Algorithm.  Here is the link to the actual paper written in 2003.  It may seem complicated, but if you carefully read the article, it all makes quite logical sense.  There is even C++ code at the end of the article to help you out.  Here is another, more recent powerpoint presentation on the same topic.

    A while back I implemented this algorithm with success.  It works quite well and should allow you to traverse over complex geometry.  If it can help you at all, I wrote a small demo a while back (A tribute to Rainbow Six).  It can be found on my site here:

    Source:  http://users.accesscomm.ca/xnagaming/files/r6_tribute/Source.zip
    Exe:  http://users.accesscomm.ca/xnagaming/files/r6_tribute/Exe.zip


    If you have any questions, I may be able to help you with some of the understanding.  Feel free to e-mail me at:
    signot [at] gmail.com

    Good luck!


  • 10/22/2007 7:33 PM In reply to

    Re: Collision Detection - How?n00b time

    what about the XNA sample that has the ball rolling around on a mesh? I believe it simply sticks the mesh to the ground, no gravity or anything special.
  • 10/23/2007 9:18 AM In reply to

    Re: Collision Detection - How?n00b time

    I don't quite think that's what he's looking for, Ikon. He has a plain old mesh that needs collision detection.

    I've been having the same problem, and I've just given up on it. I have a large, varied terrain mesh, and I have no clue how to implement collision detection with it. So I've just restarted with a heightmap.
  • 10/23/2007 10:01 AM In reply to

    Re: Collision Detection - How?n00b time

    Ohhh. I actually spoke about the same thing with one of the guys on my engine project and he said you would need to have convex physics setup, and you'd need a way to cull out parts of the model that the entities are not close to. Basically it is very difficult to get a setup like that running....

  • 10/26/2007 10:19 AM In reply to

    Re: Collision Detection - How?n00b time

    Why is collision detection so unintuitive without BoundingBoxes/Spheres?
  • 10/26/2007 11:01 AM In reply to

    Re: Collision Detection - How?n00b time

    @Signot: The paper you linked is very helpful, I'm currently working on implementing collision detection in a game of mine and it cleared up several of my questions.  Hopefully your example code will clear up some more :).

    I have a question though, and I'm hoping you or someone else on the forum can answer it.  How would one handle the need for the different collision "responses" that can arise in a game when you start moving geometry itself?  Ideally, I would like my collision detection to work like this:

    Situation 1) Player runs into wall, is stopped.  "Regular" response.

    Situation 2) Player runs into some stairs, moves up the stairs.  Handled in the article.

    Situation 3) Player is standing still on top of an "elevator" tile.  Elevator starts moving upward.  I'm assuming that I would then be testing a swept box against a stationary ellipsoid, but I want any collisions to result in "fixing" the position of the player, not the elevator.  Perhaps measuring the distance between the collision and the end position of the elevator, and applying that same translation to the player?

    Situation 4) Let's say there's a "crushing wall" mesh.  If the wall is moving horizontally, and the player is in front of it, it should push the player in the direction it is moving, similar to the elevator.  However, if a second player is standing in the way, the first player should also push the second player - a chain reaction.

    To handle this, I'd probably have to have multiple passes - Pass 1 would be movement of all player- and AI-controlled actors, Pass 2 would apply gravity to all applicable objects, and Pass 3 would move geometry objects.  Pass 1 & 2 responses involve adjusting or stopping the movement of the actor against geometry, whereas Pass 3 assumes geometry is completely unyielding - if something gets in the way during that pass, you move the thing in the way instead of changing the geometry's vector.  And, if you can't move the things in the way because of other geometry (e.g. the space between the crushing wall and opposing wall is smaller than the player) you "destroy" the thing that doesn't fit, or simply stop, depending on context.

    It would also be nice if when one actor runs into another, you apply a small amount of your velocity into the other actor, giving the "running in place against another player slowly moves them out of the way" feel, which feels more natural than other players being immovable objects.

    Has anyone put any thought into a system like this for a game they've designed, or seen an article that goes into some of the details of keeping track of what "kind" of velocity an object has, whether it's more or less immoveable than the thing it ran into, etc.?
  • 10/26/2007 12:13 PM In reply to

    Re: Collision Detection - How?n00b time

    Matt Sayar:
    Why is collision detection so hard without BoundingBoxes/Spheres, seriously? I'm trying to add collision detection to some rocky terrain of mine, and it's really frustrating me.

    It isn't difficult against a heightmap terrain. You simply check the bottom of the box or sphere against the height of the terrain. Click the link to the template or engine in my signiture if you'd like some examples of this.

    However, collision against models is a whole different story. Models can overlap, and rotate, and are dynamic. That is when you need a physics component to your game. That is when it becomes more difficult.

  • 10/29/2007 8:04 PM In reply to

    Re: Collision Detection - How?n00b time

    hey guys, thanks for all the replies!

    All of your replies were very good, but I think Opelions hit the nail on the head, the only question I would have though, is what about bridges and such?

    I've heard of raycasting collision detection, but I don't think that will work either, that's why I suggested newton, which, if anyone has any good tutorials/source code, please put it up, that would be nice.

    thanks again,
    -Chris
  • 10/29/2007 8:25 PM In reply to

    Re: Collision Detection - How?n00b time

    So basically, exactly what I said above.....

    You can't have bridges or tunnels or caves, etc...., unless you implement a physics component. And then you may not end up with a heightmap at all, or you would have a heightmap and meshes, and the meshes would require the special physics checks.

  • 10/30/2007 1:43 PM In reply to

    Re: Collision Detection - How?n00b time

    I am very interested in this also. If I was to have an animated character model, for instance a goalkeeper, how would I go about applying collision detection with a ball? Obviously bounding boxes would need to be moved/rotated in accordance with the animation, is this actually feasible or should there be another way?

    It is slightly different but along the same lines.

  • 10/30/2007 2:36 PM In reply to

    Re: Collision Detection - How?n00b time

    Unless you do the math yourself, you cannot rotate bounding boxes. You would likely want a physics component setup that could detect the collision of a mesh of the player with the ball to get a semi-accurate bounce off of it, however I'm sure there are ways to cheat.
  • 10/30/2007 3:59 PM In reply to

    Re: Collision Detection - How?n00b time

    Lord Ikon,

    I use bounding box's a lot on 3D models, and I don't have to do any extra calculation to get it to rotate, it rotates with the model and I don't use a third party physics component either.

    It may be we are going about generating the boundingbox in different ways. I was going to put some screen shots up, but have decided that this will now be my next blog post, give me a day or two and I will have an example project up for you to down load.

  • 10/30/2007 4:37 PM In reply to

    Re: Collision Detection - How?n00b time

    It would have to be your own calculated bounding box, the XNA BoundingBox is always axis aligned. There was actually a thread on how to use that bounding box and then create your own rotated one.
  • 10/30/2007 4:49 PM In reply to

    Re: Collision Detection - How?n00b time

    Ah! Yes I see what you mean now, I am indeed building the bounding box myself in a custom model content pipeline. I will be posting the code any how.
  • 10/30/2007 4:53 PM In reply to

    Re: Collision Detection - How?n00b time

    Sounds good, might come in handy.
  • 10/30/2007 6:36 PM In reply to

    Re: Collision Detection - How?n00b time

    For those interested, I'm adding collision support for heightmaps and rays to my 3D physics component within the next couple of weeks (http://www.codeplex.com/OopsFramework).  This, along with other static collision shapes (boxes, spheres, wedges and planes are all implemented) could probably define a fairly complex world with somewhat accurate collision response.  If you make the playable character's collision shape a sphere, the collision responses should naturally occur as usual.  Take a look at the example application included with the source code to get an idea. 

    Ayatollah: Your example (soccerball and goalie) sounds like a physics problem as Lord Ikon has stated (at least when in 3D) .  You could probably set this up with the 3D physics component as well, matching the collision shapes of the goalie to the animation as you mentioned.  The only collision response would be that of the soccerball, represented by a collision sphere, off of the collision shape(s) of the goalie.

    Good luck!

  • 10/30/2007 7:10 PM In reply to

    Re: Collision Detection - How?n00b time

    Having played with this I now see what you are getting at, the Intersects method does not take the position of the corners into account, rather it just uses the distance the edge of the box is from the center of the model and so you lose the rotation.

    I got the impression that the bounding box was rotating as I draw my box's in debug and as these appear in world space it rotates, but the Intersect method does not take this transformation into account :( and so they stay flat.

    So you could get the corners from the bounding box and transform them and then use those positions against the transformed corners of the target intersecting bounding box and check for collision that way. I might be talking pants here, but will try and get this working :) Nothing like a new project eh...

  • 10/30/2007 7:52 PM In reply to

    Re: Collision Detection - How?n00b time

    You might do a search in the forums, someone posted the code to calculate a rotated bounding box from the XNA bounding box type.
  • 10/30/2007 7:59 PM In reply to

    Re: Collision Detection - How?n00b time

    FretboardOfFury:
    Ayatollah: Your example (soccerball and goalie) sounds like a physics problem as Lord Ikon has stated (at least when in 3D) .  You could probably set this up with the 3D physics component as well, matching the collision shapes of the goalie to the animation as you mentioned.  The only collision response would be that of the soccerball, represented by a collision sphere, off of the collision shape(s) of the goalie.

    Good luck!

    Total noob at 3D models et al. Is there any good places to look at for this information? You say the 3D physics component, was that a figure of speech or were you referencing a physics component that is out there?

  • 10/30/2007 8:17 PM In reply to

    Re: Collision Detection - How?n00b time

    In his post there is a link to a physics project/engine he is working on. I assume he was talking about a 3D physics component inside his project.
  • 11/1/2007 10:59 AM In reply to

    Re: Collision Detection - How?n00b time

    Hey Nelson,

    Glad the paper helped, and hopefully I can try and answer a few questions for you too.  Don't take my word on this, I am only vaguely remebering reading some of these solutions or techniques a while back.

    1)  Regular response, should be handle by the paper.  If the player is running straight into the wall, the sliding vector will cause the player to stop at the wall.  If there is an angle in the direction of collision, then it will cause the player to slide.  Depending on the angle, this could be large or small.
    2) Running up some stairs - as you said is handled by the paper.
    3) Elevators - are a little more tricky.  From what I remember a while back (and this may have changed with newer techniques), but the player physics object is "linked" to the elevator physics object.  In this sense, the player's physics object has become a "child" of the elevators physical object.  When the eleveator moves, all it's children will move.  This would have to be part of the physics library that you create.
    4) Crushing wall - this would involve applying momentum.  Again, this adds a new layer of complexity to the physics engine.  Before we were dealing with simple collisions and their responses.  This extra step would involve calculating the forces of each movment, and applying intertia and momentum.  Think of a pool table.  If you were to write a physics library dealing with pool balls, you would have to handle collisions by applying momentum to each ball that took part in the collision.  I am pretty sure there are lots of tutorials/articles out there dealing with this problem.  It is simply a matter of applying those techniques.

    Not sure about the passes, but it would be something similar to how the Farseer physics enigne works.  It implements a pass solution like the one you are describing.  It is an impulse based method with multiple passes.  I think this is the most common way of implementing a momentum physics engine.

    here is a site that may help you:  http://www.harveycartel.org/metanet/tutorials/tutorialA.html
    As well here:  http://www.cs.brown.edu/courses/gs007/lect/sim/web/murat.html

    http://www.impulse-based.de/

    If you want more, look up I-Collide or Impulse Based Dynamic Simulations.  There are a lot of papers out there.  Good luck.
Page 1 of 2 (28 posts) 1 2 Next > Previous Discussion Next Discussion