Collision Detection With Bezier Curves

XNA Game Studio Express

Fusion1224

Hi,

I'm currently making a small 2D game in XNA Game Studio Express. It involves a player moving around a terrain and being able to collide with it. Nearly all the graphics and settings in my game are user generated so this allows for everything to be quite customisable.
For collision detection the user specifies paths made of Bezier curves which are stored in a file. The game reads this file and stores a number of points on the curves in an array. The player is also made of Bezier curves that are converted into points:

This shows how I want collision detection to happen; if any of the lines that make up the player intersect with any of the lines that make up the terrain, then a collision has occurred. Once a collision has occurred two things need to be done:
  • Move the player the shortest distance possible so they are no longer intersecting the terrain
  • Reflect the velocity of the player off the line of the terrain so they appear to bounce off the terrain.
Bouncing the player should be straightforward but I'm having trouble with moving the player out of the terrain. This is basically what I want to happen:

It seems simple enough to just write:
playerPosition += intersectionPoint - new Vector2(x4, y4)
Which would work for the visual example that I gave but what if points 1 and 2 swap places or points 3 and 4 swap What if the player is colliding with the ceiling not the ground There are many different ways in which these 4 points can intersect. How can I create an equation to move the player properly Or is there a better way of doing collision detection with Bezier curves

Thanks in advance for your help,
Fusion.
Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

DanBrink

I've never even heard of Bezier Curvers but couldn't you check which direction you need to move with a conditional and then loop through adding or subtracting till it isn't colliding

Something like:

While(Touching)
{
MoveAway();
}


Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

Fusion1224

I think this method might be too slow, and how would the MoveAway() method know which direction to move and how much
One way could be to calculate a unit vector pointing away from the terrain and then work out how much the player would need to be moved along that vector to get out of the terrain.
If you looped through adding or subtracting until it isn't colliding, that would leave how fast you would get the player out of the terrain up to chance. I don't think I can do that since the "if the two lines are intersecting" statement is inside 4 nested for loops .


Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

Arek Bal

1st problem solution - do the check on place before actually moving object onto this place...(pretty simple and no "old school wall stutter effect").

2nd ... I understand that you want to make some formula for bouncing - while you have some formulas for bezier...you should already know how to do it. When hit occurs recalculate bezier formula with objects parameters(speed, direction) for bounceOut parameters.
I am not gonna do it for ya.

Since it's 2d you could try some diiferent approach - "per pixel collision". But your method could be very powerful and more accurate then per pixel, so don't give up.


Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

Fusion1224

As I was saying a bouncing algorithm wouldn't be difficult to implement, I created one that could work:
(lineNormal - playerDirection) * 2 + playerDirection
With lineNormal being the normal of the terrain line.

So I don't think bouncing is too much of an issue. What my problem is is that the only way to tell if the player has collided is to test for line intersection between the player and the terrain. But by the time an intersection happens, the player has penetrated the terrain. Before I draw the position of the player on the screen I need to calculate where the player should be so it looks like they never penetrated the terrain. Then after I have corrected the position of the player I can bounce them off the terrain. I'm not sure of an algorithm to calculate this new position.

By the way I am using Verlet integration in the game but that shouldn't really affect the collision detection method.


Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

Arek Bal

My old test code(new is in creation process)
if (inputs.LeftState > 0)
{
if (maps[0].CollisionMap[(int)mapAllocator.X - 4, (int)mapAllocator.Y] != 0)
{
testModelPosition.X -= 3;
mapAllocator.X -= 4;
}
else
{
testModelPosition.X += 0;
mapAllocator.X += 0;
}
}
if (inputs.RightState > 0)
{
if (maps[0].CollisionMap[(int)mapAllocator.X + 4, (int)mapAllocator.Y] != 0)
{
testModelPosition.X += 3;
mapAllocator.X += 4;
}
else
{
testModelPosition.X -= 0;
mapAllocator.X -= 0;
}
}
of course it's not too much similar to your bezier...
That is absolutly simple...and it works.


Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

Kyle_W

Well maybe I'm missing something, but it seems to me that the game will know the direction the player was moving when the collision occurred, and so I would think you could simply move the player in the opposite direction to the previous motion until a collision is no longer detected.


Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

Fusion1224

I made an algorithm that reflects one vector off another (the player off the terrain) so I could move the player along that vector. But for the sake of speed I would have to determine exactly how much to move the player along this vector so it is not colliding any more.

I could move the player maybe a pixel in that direction until it is not intersecting but that would slow down the game too much. Could anyone suggest a suitable algorithm to do what I am saying




Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

Arek Bal

I guess your looking for your x5,y5 point...right

It's primarys school algebraic math(I had to say that I am also forgot much of it).
http://mathforum.org/library/drmath/view/62814.html


Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

Fusion1224

I'm not looking for the intersection point, I already have an equation for that.


Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

waruwaru

Fusion1224 wrote:
I'm not looking for the intersection point, I already have an equation for that.

Then you already have your answer, don't you The vector between your starting point to the intersecting point is the max that point can move before going under terrain line. If you calculate that for all points in your objects and all the terrain line, the minimum length is the maximum length you can move.

Point3 and Point4 defines your terrain. Does your intersection formula care if they swap position If it does, then you should make sure your data structures keeps the points sorted the way you want, or have an easy way to tell which one is which.

Doesn't Point1 define your player's current position and Point2 is player's next position If the player starts above ground, and you never allow the player to cross the intersection point, then Point1 will always be above the line. Unless you can have overhangs/tunnel, it should be easy to determine which point is the one above your terrain.





Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

Fusion1224

Point1 and Point2 define the terrain and Point3 and Point4 define the part of the player that has been detected as intersecting the terrain. All 4 points apply to the current frame.
The game doesn't actually know that a collision will happen next frame, it only recognises a collision by the time the player has intersected the terrain, and I need a method to get it out of the terrain.


Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

Arek Bal

I can't understand where is your problem from getting your object from point x4,y4 to x5,y5.

I am gonna write it 3rd time: You're not wanna allow real intersection because it will make more problem than gain.You wanna check that if in next step collision gonna happen. if collision gonna happen return zero movement or your x5,y5. Then calculate bounce or smth like that.

There is no problem until it's well defined.


Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

Fusion1224

Just an update: I shifted the whole terrain 20 pixels in a top-left direction, and the collision detection is looking a lot more realistic! I observed that when the player hit the roof it bounced off before it actually seemed to touch the roof, and when it hit the floor it penetrated the terrain before bouncing off.
Because of the dynamically scrolling background in my game, rendering the player position is a bit more complicated than just drawing the player at its position. When the player hits the edges of the screen I move the background and keep the player still. This creates the illusion that the player is moving around a terrain bigger than the screen.
Possibly the misalignment of the terrain was due to my algorithms that moved the player in relation to the background. I'll review these algorithms, but for the time being moving the terrain 20 pixels seems to work for some reason.

The player is still penetrating the terrain, but now its penetration is making more sense. The Verlet integration is performed first in the Update() method, then gravity is applied, then collision detection is performed. This happens each frame. Having things in this order means that a collision is detected before the player is actually moved into the terrain. I didn't notice that it did this before, but now I do .
So the reason the player is still penetrating the terrain a small amount may be because things are happening in the following order:
  • Player is not intersecting the terrain.
  • Gravity is applied, now they are (but the player hasn't been drawn as intersecting the terrain because the integration hasn't been performed yet).
  • Collision detection recognises a collision. Velocity of player is bounced off terrain.
  • Velocity of player is applied to position, and player is drawn.
In the last step the player may be drawn penetrating the terrain because the reflected velocity wasn't enough to move them out of the terrain in one step (if you know what I mean).
But the important thing is that when a collision is detected the player needs to be moved onto the terrain line. I understand what Arek Bal said about moving the player position to x5, y5 (the intersection point).
It isn't quite that simple unfortunately because the player just isn't a dot at the player position, it is a series of lines. So what I would need to do (in the case of the visual example given in my first post) is to set x4, y4 to the intersection point. This would involve moving the player position according to a certain equation. As I sort of said in my first post one possible way of doing this would be:
playerPosition = new Vector2(x4, y4) - intersectionPoint;
Though I'm not exactly sure if this works, the theory of it seems right though if you look at the diagram in my first post.

Anyway thanks for everyone's suggestions, I'm nearly there in implementing Bezier curve collision detection.

Fusion


Top

Re: XNA Game Studio Express Collision Detection With Bezier Curves

Arek Bal

Nice.

Maybe when you will end this "Bezier curves CD" you can try to share it
That would be great. This method for CD is one of most usable for any game where you are moving in 2d(Final Fantasy, Biohazards from 1 to 3). Add some method for height and you can use it for anything you want.




Top