Jump to content
  • Advertisement
Sign in to follow this  

Collision detection in 2d maze

This topic is 4900 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi , I am making a maze game where a ball is to be taken from some start to end position with keyboard keys.Ball is not allowed to go through different walls present in the maze.I am using SDL to make this game ...can someone suggest me some way to achieve this collision detection with those walls so that ball don't go through them..or some tutorial on that kind of collision detection?? Thanks

Share this post

Link to post
Share on other sites
Guest Anonymous Poster
just check after you get the input if the ball's new x,y is going to be equal to the wall's x,y. If so, dont move the ball, if not, move it move it

Share this post

Link to post
Share on other sites
There is a method which I think would give you exactly the behavior you're looking for. It would allow you to 'slide' the ball around walls and corners in a natural way, rather than 'sticking' or stopping altogether.

I assume your walls are (or can be) represented as line segments with endpoints p1 and p2. This can be converted to the parametric form O+tD, where O=p1 and D=p2-p1.

The next thing you need to be able to do is find the closest point on a segment to another point. This can be done easily by finding the parametric projection of the point onto the supporting line, and clamping to the range [0, 1], like this:

float t = Dot(p-O, D)/Dot(D, D);
t = Clamp(t, 0, 1);
return O+t*D;

To intersect a circle with a line segment, use the above method to find the point on the segment closest to the circle center. Let d=C-closest, where C is the circle center and 'closest' is the point returned by the above code. Then, the circle intersects the segment iff Dot(d, d) <= r*r, where r is the radius of the circle.

If there is an intersection, then you already have the information you need to 'push' the circle away from the wall and resolve the collision. The direction to push the circle is normalize(d). The distance is r-length(d). The code might look like this:

Vector2 closest = ClosestPoint(C, p1, p2);
Vector2 d = C - closest;
float ll = d.Dot(d);
if (ll > r * r) return;
float l = sqrt(ll);
d /= l;
C += d * (r - l);

The square root can be avoided in the boolean test, but I don't know that it can be avoided in the collision resolution step. Also, if the walls are axis-aligned the code can be simplified somewhat. Lastly, note that this method relies on the displacement of the ball per frame being < r.

Anyway, unless I messed something up, that should give you everything you need to add natural collision detection and response to your game. Let me know if you have any questions about anything.

Share this post

Link to post
Share on other sites
sorry off topic but jyk i understand your last test completely but do you know how to sweep the sphere against the static segment. Like the sphere starts A0 and ends A1 and find a t such that

| A0 + t ( A1 - A0 ) | = DistanceToSegment

Share this post

Link to post
Share on other sites
sorry off topic but jyk i understand your last test completely but do you know how to sweep the sphere against the static segment...
Sure. If I have time later I'll post the solution - it may be of interest to the OP as well.

Share this post

Link to post
Share on other sites
...do you know how to sweep the sphere against the static segment.
Ok, for those who are interested here's a brief overview.

Sweeping a sphere against a segment involves sweeping first against the infinite line supporting the segment, and then if necessary against one or the other endpoint.

Let the supporting line be L(s) = O+sD, where O = p0 and D = p1 - p0. The circle has center C at time t0, radius r, and velocity V. The circle center traces out the line segment C+tV. Let us assume that the sphere is not initially intersecting the line. We are interested in finding the times at which the perpendicular distance from L to C+tV is exactly r; these are the times at which the sphere first touches the line, and then ceases to touch the line.

I'll have to skip some stuff or this will be a long post. The above problem can be expressed as a quadratic equation of the form:

at2+2bt+c = 0


d = C-O
a = (D.D)(V.V)-(D.V)2
b = (D.D)(d.V)-(D.V)(d.D)
c = (D.D)((d.d)-r2)-(d.D)2

(This is also the equation for intersecting the line C+tV with the infinite cylinder O, D, r.)

If a = 0, the sphere is travelling parallel to the line and does not intersect it. Otherwise find the discriminent as b2-ac. If disc < 0, the sphere misses the line. Else the first solution for t is (-b-sqrt(disc))/a. If t in [0, 1], the sphere intersects the line at time t.

Now we need to know if the sphere hit the line past an endpoint of the segment. For this we need to know the parametric projection of C+tV onto O+sD. The solution is s = ((d.D)+t(D.V))/(D.D).

If s is not in [0, 1], we need to sweep the sphere against the appropriate endpoint. Again we solve a quadratic equation of the form at2+2bt+c = 0. Regardless of the endpoint, a = V.V.

If s < 0:

b = d.V
c = d.d-r2

If s > 1:

b = d.V-D.V
c = (d.d)-2(d.D)+(D.D)-r2

In either case, solve the quadratic as described above to find the first time of intersection, if any, between the endpoint and the sphere.

Note that all of the equations are in terms of just a few dot products, which can be pre-calculated and used throughout the function. Note also that I believe the algorithm works as-is in 2d using circles instead of spheres. In a 2d environment with walls that have pre-computed unit-length normals, you could probably come up with a more optimized version.

Unfortunately implementing this sort of collision detection robustly can be a bit tricky. I have not addressed these issues here.

I should say that I haven't tested this particular form of the algorithm. Also I don't have time at the moment to do a thorough proof, so there may be errors in the above. But the general idea is correct.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!