It is currently Fri Dec 06, 2013 7:14 pm

 All times are UTC

 Page 1 of 1 [ 8 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Collision Detection?Posted: Wed Nov 30, 2011 6:35 am
 Rookie

Joined: Wed Nov 30, 2011 4:47 am
Posts: 2
Hi.
I figure there must be a few well established ways to go about this, but some research turned up nothing that I needed. I'm trying to make a game in c# using XNA, but this part is generic enough to be the same in just about any language, and I want to make collision detection work so that an Actor (class with a Rectangle for it's collision box and a Vector2 for it's velocity) can't pass through a block that is kept in a 2d array.
So I looked up how to do this, and it seemed simple enough. Ended up with the following code.

Code:
internal virtual void Collide(Actor actor, int x, int y)
{
Rectangle collideBox = new Rectangle(x * GameConstants.BlockSize, y * GameConstants.BlockSize, GameConstants.BlockSize, GameConstants.BlockSize);
if (actor.FutureLocation.Intersects(collideBox))
{
if (actor.Location.Right <= collideBox.Left)
{
leftCollide(actor, collideBox);
}
if (actor.Location.Left >= collideBox.Right)
{
rightCollide(actor, collideBox);
}

if (actor.Location.Bottom <= collideBox.Top)
{
topCollide(actor, collideBox);
}
if (actor.Location.Top >= collideBox.Bottom)
{
bottemCollide(actor, collideBox);
}
}
}

protected virtual void leftCollide(Actor actor, Rectangle collideBox)
{
actor.SpeedX = collideBox.Left - actor.Location.Right;
}
protected virtual void rightCollide(Actor actor, Rectangle collideBox)
{
actor.SpeedX = collideBox.Right - actor.Location.Left;
}
protected virtual void topCollide(Actor actor, Rectangle collideBox)
{
actor.SpeedY = collideBox.Top - actor.Location.Bottom;
}
protected virtual void bottemCollide(Actor actor, Rectangle collideBox)
{
actor.SpeedY = collideBox.Bottom - actor.Location.Top;
}

The block needs an x and y coord because its location is dictated by it's index in the array held by a level, unlike an actor that stores it's own location.
actor.Location is an XNA rectangle that represents the actors collision box.
actor.FutureLocationis an XNA rectangle that represents where the actor is trying to move to.
If there is anything else that needs to be cleared up, just ask.

I made separate functions for each type of collision (Top, bottom, left and right) so that other classes that extend block can override these functions for other effects, E.G. if I made a class called platform that overrides leftCollide, rightCollide and bottemCollide with empty functions, then you would be able to jump through platforms and then land on them.

Now the problem here is that although the actor will collide with a box, it can not 'slide' along the side of one. If you are trying to go left, the gravity is pulling you down, then the future location will be down and to the left, and collides with a box, so you will collide with the ground and not be able to move left, when it should only be blocked going down.

I think that to solve this problem, I need to figure out what the actor collides with first, the top/bottem or the sides. Right now it knows if there is a collision, but doesn't know the cause. For example.

Red square: The actor's location.
Pink square: The actor's future location.
Blue Square: The block that the actor is colliding with.
Green Square: Where the actor should be if it hits the top first.
Orange square: Where the actor would be if it hit the left side first.

So in the above example, because it collides with the top (As shown by the black arrow intersecting the top) Velocity initial Y (ViY should be set to Velocity final Y (VfY) and Velocity initial X should remain unchanged.\
Instead, it is doing both collisions for green and orange and setting both ViY and ViX to VfY and VfX respectively.

Anybody have any idea how I would fix this? I need to find what side the actor collides with, but don't know how to do that.

Code dump would be truly awesome, but an explanation or link to an article would be legendary.

Top

 Post subject: Re: Collision Detection?Posted: Wed Nov 30, 2011 1:19 pm
 Funky Monkey

Joined: Thu Sep 09, 2004 1:17 pm
Posts: 1642
Location: burrowed
I would advise implementing a physics engine (except you want to really lern the stuff, then i'd suggest a math university )

Jitter Physics for example is a great engine in .net and is easily set up and implemented.
Since you're using XNA you might also consider JigLibXalthough i'm not sure about it's current development process.

If you want strictly 2D physics, you could take a look at Farseer.

You probably realised that collision detection and response is a pain in the butt, and having a working physics environment helps tremendously when trying different things, speeding up the prototyping process or even coming up with new ideas

_________________
Long pork is people!

wzl's burrow

Top

 Post subject: Re: Collision Detection?Posted: Wed Nov 30, 2011 5:20 pm
 Super-dooper pooper scooper

Joined: Tue Oct 11, 2011 8:08 pm
Posts: 170
I actually have been having major trouble finding a good engine that works in C#/XNA/.NET. Thanks!

Top

 Post subject: Re: Collision Detection?Posted: Wed Nov 30, 2011 10:57 pm
 Rookie

Joined: Wed Nov 30, 2011 4:47 am
Posts: 2
Thanks for the reply, but physics engines tend to be all broad sword and no scalpel. Much too powerful for what I need without the specific functionality that I want. Jitter Physics, for example, seems to be built with 3d processing in mind, while I only want a 2d side scroller.
The vast majority of engines I have seen for 2d are for advanced physics games with polygons that rotate and liquids that act under pressure and so on, yet they don't really help me delegate separate functions to each different side. All I need is something that Super Mario Bros. had, working collision detection between rectangles on a 2d grid, so I don't think it is the kind of thing that will require a collage level understanding of maths to do.
I'm willing to bet there is a well known and easy way to do this, but any attempts to find an article always lead to colliding circles and other thrills that I don't need.

Still, thanks for the help this far.

Top

 Post subject: Re: Collision Detection?Posted: Thu Dec 01, 2011 7:03 pm
 Obfuscation Ogre

Joined: Sun Oct 16, 2011 3:09 pm
Posts: 298
Location: Here (where else?)
I'd do it by math. From the right bottom corner of the red box, construct a line in the direction of the movement, something like (CX + p * VX, CY + p * VY) where (CX, CY) is the position of the corner of the box, and (CX, CY) is your speed vector. p is unknown, by changing it, you can reach any point at the line (if you don't see this, compute points for some values of p, and draw them).

To collide with the top of the blue box your y must be some value TB (Top of Blue box), that is CY + p * VY = TB, thus p = (TB - CY) / VY. Obviously, VY must be non-zero :p Use the computed p to compute x from CX + p * VX, et voila, your x/y coordinate of the collision with the horizontal line. Note that this does not know that x must be bigger then LB (Left of Blue box), so you need to check that afterwards.
The same can be done with the vertical edge at LB.

Another approach is to do it using bisection. If your red box intersects with the blue box after the move, you have hit a wall :p
If it does not intersect, you are not far enough. Since each step reduces the interval by 1/2, you find the edge very quickly.

Top

 Post subject: Re: Collision Detection?Posted: Fri Dec 02, 2011 1:38 pm
Mauris wrote:
Hi.
I figure there must be a few well established ways to go about this, but some research turned up nothing that I needed. I'm trying to make a game in c# using XNA, but this part is generic enough to be the same in just about any language, and I want to make collision detection work so that an Actor (class with a Rectangle for it's collision box and a Vector2 for it's velocity) can't pass through a block that is kept in a 2d array.
So I looked up how to do this, and it seemed simple enough. Ended up with the following code.

Code:
internal virtual void Collide(Actor actor, int x, int y)
{
Rectangle collideBox = new Rectangle(x * GameConstants.BlockSize, y * GameConstants.BlockSize, GameConstants.BlockSize, GameConstants.BlockSize);
if (actor.FutureLocation.Intersects(collideBox))
{
if (actor.Location.Right <= collideBox.Left)
{
leftCollide(actor, collideBox);
}
if (actor.Location.Left >= collideBox.Right)
{
rightCollide(actor, collideBox);
}

if (actor.Location.Bottom <= collideBox.Top)
{
topCollide(actor, collideBox);
}
if (actor.Location.Top >= collideBox.Bottom)
{
bottemCollide(actor, collideBox);
}
}
}

protected virtual void leftCollide(Actor actor, Rectangle collideBox)
{
actor.SpeedX = collideBox.Left - actor.Location.Right;
}
protected virtual void rightCollide(Actor actor, Rectangle collideBox)
{
actor.SpeedX = collideBox.Right - actor.Location.Left;
}
protected virtual void topCollide(Actor actor, Rectangle collideBox)
{
actor.SpeedY = collideBox.Top - actor.Location.Bottom;
}
protected virtual void bottemCollide(Actor actor, Rectangle collideBox)
{
actor.SpeedY = collideBox.Bottom - actor.Location.Top;
}

The block needs an x and y coord because its location is dictated by it's index in the array held by a level, unlike an actor that stores it's own location.
actor.Location is an XNA rectangle that represents the actors collision box.
actor.FutureLocationis an XNA rectangle that represents where the actor is trying to move to.
If there is anything else that needs to be cleared up, just ask.

I made separate functions for each type of collision (Top, bottom, left and right) so that other classes that extend block can override these functions for other effects, E.G. if I made a class called platform that overrides leftCollide, rightCollide and bottemCollide with empty functions, then you would be able to jump through platforms and then land on them.

Now the problem here is that although the actor will collide with a box, it can not 'slide' along the side of one. If you are trying to go left, the gravity is pulling you down, then the future location will be down and to the left, and collides with a box, so you will collide with the ground and not be able to move left, when it should only be blocked going down.

I think that to solve this problem, I need to figure out what the actor collides with first, the top/bottem or the sides. Right now it knows if there is a collision, but doesn't know the cause. For example.

Red square: The actor's location.
Pink square: The actor's future location.
Blue Square: The block that the actor is colliding with.
Green Square: Where the actor should be if it hits the top first.
Orange square: Where the actor would be if it hit the left side first.

So in the above example, because it collides with the top (As shown by the black arrow intersecting the top) Velocity initial Y (ViY should be set to Velocity final Y (VfY) and Velocity initial X should remain unchanged.\
Instead, it is doing both collisions for green and orange and setting both ViY and ViX to VfY and VfX respectively.

Anybody have any idea how I would fix this? I need to find what side the actor collides with, but don't know how to do that.

Code dump would be truly awesome, but an explanation or link to an article would be legendary.

Top

 Post subject: Re: Collision Detection?Posted: Fri Dec 02, 2011 3:03 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Um. Did I just miss something, or did the guest above simply quote the original post and hit "submit"?

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Re: Collision Detection?Posted: Fri Dec 02, 2011 7:17 pm
 King Code Monkey

Joined: Wed Sep 01, 2004 3:05 pm
Posts: 11204
Location: Abingdon, MD
Nope. Unless he forgot to add something.

_________________
Bored? Head on over to my blog and see what I'm up to.

Microsoft XNA MVP

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 8 posts ]

 All times are UTC

#### Who is online

Users browsing this forum: Google [Bot] and 2 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ Forums    Forum Rules and Posting Guidelines Wiki Discussion    Help    Content Issues Game Programming Discussion    C and C++ Game Programming    Java Game Programming    Language Agnostic Programming    .NET Game Programming    VB Game Programming    Mobile Game Programming    Web-Based Game Programming    Other Languages    OpenGL Development    Direct X Development Game Development Discussion    Game Design    Game Media Off-Topic Discussion    Announcements    Off-Topic    Community Projects    News