3
\$\begingroup\$

I want to do a 2D game, where you can mouse click anywhere on the map and the player will go there. If there is obstacle in the way, the player will go as close as possible to where you clicked without going into the non-walkable area. What would be the optimal way to accomplish this?

Idea of collision

\$\endgroup\$
  • \$\begingroup\$ Editing in the "path finding" might mislead people. I do not want the player to move around the obstacle. Rather stop at obstacle. I am using convex polygon. The idea is the player clicks wherever he wants to move, but will stop if there's obstacle in his path. \$\endgroup\$ – user3448051 Aug 5 '14 at 10:08
  • 2
    \$\begingroup\$ I've reverted the previous edits, and edited the title a bit. This question really is about collision-detection, not path-finding, since, as I read it, the OP wants to detect and stop at obstacles, not to go around them. \$\endgroup\$ – Ilmari Karonen Aug 5 '14 at 10:50
1
\$\begingroup\$

If you want, you can predict your movement with the Periodic Interference Test (PIT), which is fancy for "Place myself in the next position and if I collide with something, revert me to the last safe position". This is fast, easy, relativly safe and should be sufficient for your game as long as you don't move to fast (aka make two big jumps in a frame).

However: I can guarantee you that you never will come as close as possible to your obstacle. Simply the fact that you make jumps of a fixed size guarantees that you are somewhere in the Interval [0,stepSize) next to your target.


If you want the best possible answer, use Predicted Instant of Collision (PIC). This will compute your way before you actually take your step, and, if it finds an obstacle, moves you only as close as possible without colliding the obstacle. This will bring your Player nearly to 0 distance to the obstacle.

However No. 1: This works only for linear pathes! For a solution for non-linear pathes relate to this question at stackoverflow.

However No. 2: PIC is relativly trivial for round objects (disk/spheres). You seem to use a Square as player, which might lead to a problem. You can use a bounding disk around your Square to get close and then use really small steps to approach the obstacle (aka a tiny PIC).


A good explanation for PIT and PIC can be found here and here.

An alternate solution is described here

\$\endgroup\$
  • \$\begingroup\$ To clarify the context with the other solution: When you know your path (and you do, i mean it is a simple line) you move along it and check every time if your next step will collide you, and compute the correct position if this is the case. As soon as I have a proper terminal I will update the answer with proper links. \$\endgroup\$ – J_F_B_M Aug 5 '14 at 10:16
  • \$\begingroup\$ Edited answer to match the intention of the question (and to make clearer what I meant). \$\endgroup\$ – J_F_B_M Aug 5 '14 at 14:42
  • \$\begingroup\$ Lightthink gave a wonderful example of a simple Periodic Interference Test. \$\endgroup\$ – J_F_B_M Aug 5 '14 at 14:46
0
\$\begingroup\$

Given you can do a discrete collision check between the agent (that is you player) and all the obstacles you can do something like this:

while ( not_found_collision )
{
    move the agent a distance D along the path; // D must be small enough to prevent
            // tunneling - the radius of a sphere that is fully contained in the agent
            // shape should be enough --- for a square, that is its edge length
    check if it now collides with any obstacle;
    if it does
        execute bisection until the error is small enough 
}

For what bisection actually is take a look here

Also, did you considered using a 2D engine, like Box2D?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.