I'm working on a 2D game in which I would like to do collision detection between a moving circle and some kind of static curves (maybe Bezier curves).
Currently my game features only straight lines as the static geometry and I'm doing the collision detection by calculating the distance from the circle to the lines, and projecting the circle out of the line in case the distance is less than the circles radius.
How can I do this kind of collision detection in a relative straightforward way? I know for instance that Box2D features collision detection with Bezier curves. I don't need a full featured collision detection mechanism, just something that can do what I've described.
UPDATE: Thanks a lot for the great answers! I'll have to read up on Bezier curves to fully understand the method you've described. Then I'll get back to you.
Answer
29/09/2012 - 23:20
I created a git Repo here: https://github.com/ArthurWulfWhite/Bezier-Distance/
You are welcome to download the source files as a zip from there. It also includes a demo you can compile using FlashDevelop. To use the demo, open the project in Flash Develop and click 'Test Project'. While running the demo, click the LMB to randomize a new Bezier curve and a new Circle.
Good luck!
The zip link is hard to see - just use Ctrl + F and type zip. This source represents a couple of weeks of reasearch and programming, I hope you enjoy it.
If you plan on dividing the bezier recursively into segments and checking for collisions with them, I suggest making a 100,100 array (grid) and placing each segment in the four nearest squares, so you only have to check for collisions with 4 / 10,000 of the segments each frame.
I do think you will benefit from box2d both as a programmer and as a game creator, since there are lots of hidden little hurdles in making a 'simple' physics engine that make the motion seem a little bumpy and less fluid then it could be.
Old answer: The pure way.
You can actually see if a circle is colliding with a Bezier curve, by checking the distance between the distance between the center of the circle and the closest point on the curve.
The equation for the distance (in general)
explained:
Bezier equation:
q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))
This can be summed up to (with some algebra) - I will omit .(x,y) for readability (they are still points, not one number)
q(t) = (start -2 * cont + end) t^2 + (-2 * start + 2 * control) + start
The distance from point (x,y) is:
sqrt ((q(t).x - point.x)^2 + (q(t).y - point.y)^2)
To find the closest point on the bezier to the ball, you need to derive and find all the points where the derivative equals zero (the roots). It is a polynomial of the third degree so you could use a closed formula but it could be unreliable since the precision of the computer floating point represented fractions may not be sufficient. It is far better to use Newton or something of that nature.
The derivative you need to find the roots for is:
Assuming: a = start b = control c = end d = cirlce center point
The tricky part is multiplying this points, you have to use dot product.
If you like, I have the code for this and I can share it here in the form of a function that simply returns a boolean if there is a collision or not and an angle of collision. Some problems could appear in naive implementation of a collision engine like this for instance a fast moving ball could get caught between two curves.
I recommend avoiding it for now, just sum up the coefficients for the x axis and for the y axis and add them up.
The use any reliable method you may choose like Newton to find the roots, check the distance from the root points on the bezier, 0 <= t <= 1 to the circle center and check the distance for the two ends of the bezier (start and end) to the circle center, whichever one is closest, will tell you if there is a collision.
If the radius is smaller than the minimal distance, there is a collision.
The angle is approximately the one between the center of the circle and the closest point on the bezier.
That being said, if you truly wish to make a game with collision physics, I suggest you just iterate over the bezier
q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))
Divide each piece in the middle recursively until it is small enough, lets say 10 pixels or less, then build the bezier roughly from boxes and use Box2d for the physics cause it is possible that writing all this collision detection code will prove to be a great time sink that doesn't enhance the gameplay much. Using Box2d has proven itself in countless projects in the past.
No comments:
Post a Comment