1
\$\begingroup\$

I am experimenting with a continuous collision detection and response of points on a tile map. This are my results for now:

No problem

I did this by shooting a ray (red line) from the current position (red circle) to the target position (green circle) and check all tiles which are on it using this algorithm. If the ray hits a solid tile I calculate the exact postion of the collision (yellow circle) and a new target positition depending whether the ray hit the solid tile vertically or horizontally in the other case I can simply set the current position to the target position and be finished because no collision occurred. Now I am shooting a second ray (blue line) to this new target position and check again for solid tiles on it. If a collision occurerd I set the current position to the ray hit position (cyan circle) and be finished. In the other case I only set the the current position to the new target position (cyan circle) because no collision occurred this time.

Here the most important source code:

void update(float start_x, float start_y, float target_x, float target_y, float *corrected_x, float *corrected_y)
{
    float hit0_x;
    float hit0_y;
    LineTraceResult res0 = line_trace(start_x, start_y, target_x, target_y, &hit0_x, &hit0_y);

    switch (res0)
    {
        case LINE_TRACE_NONE:
        {
            // No collision occurred so the target position is valid and we can move to it.
            *corrected_x = target_x;
            *corrected_y = target_y;
        }
        break;

        case LINE_TRACE_VERT:
        {
            // We hit a solid tile on the vertical edge.
            *corrected_x = hit0_x;
            *corrected_y = target_y;

            float hit1_x;
            float hit1_y;
            LineTraceResult res1 = line_trace(hit0_x, hit0_y, *corrected_x, *corrected_y, &hit1_x, &hit1_y);

            if (res1 != LINE_TRACE_NONE)
            {
                // There was a second collision on the corrected position so we need to adjust it.
                // Because the x axis did not changed we don't need to change it.
                *corrected_y = hit1_y;
            }
        }
        break;

        case LINE_TRACE_HORI:
        {
            // We hit a solid tile on the horizontal edge.
            *corrected_x = target_x;
            *corrected_y = hit0_y;

            float hit1_x;
            float hit1_y;
            LineTraceResult res1 = line_trace(hit0_x, hit0_y, *corrected_x, *corrected_y, &hit1_x, &hit1_y);

            if (res1 != LINE_TRACE_NONE)
            {
                // There was a second collision on the corrected position so we need to adjust it.
                // Because the y axis did not changed we don't need to change it.
                *corrected_x = hit1_x;
            }
        }
        break;
    }

So in theory this all works great but in practice there are a lot of problems caused by the limited precision of floats.

For example in this two cases:
Problem1
Problem2

One approach to "solve" this problem is to add some kind of padding often named Epsilon every time a collision occurs but this method seems to me not very accurate and dirty.

So I am wondering how all the professional game developers are solving this kind of problem?

EDIT:
This problems occurre because the hit position calculated by the ray can not be 100% exact so it could be for example that the y coordinate gets rounded from 6.9999 to 7.0001 and 6.9999 means tile 6 and 7.0001 means tile 7 so its a huge difference.

\$\endgroup\$
  • 1
    \$\begingroup\$ Could you elaborate what the problems are and why do you think they are related to floating point accuracy? \$\endgroup\$ – msell May 16 '16 at 10:57
  • \$\begingroup\$ I made some Edits. \$\endgroup\$ – Michael May 16 '16 at 12:48

Your Answer

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

Browse other questions tagged or ask your own question.