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\$
2
  • 1
    \$\begingroup\$ Could you elaborate what the problems are and why do you think they are related to floating point accuracy? \$\endgroup\$ Commented May 16, 2016 at 10:57
  • \$\begingroup\$ I made some Edits. \$\endgroup\$ Commented May 16, 2016 at 12:48

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.