Do you have a trick to apply a function on a circle?

Question

I want to find a good path from a point A to a point B on a limited hardware (CPU: Vortex86, 256 MB) using the A* algorithm. I have a grid of 300x200 cells with fixed obstacles. The hit box to avoid obstacles is a disk.

I'm looking for an optimized way to check if my hit box is in collision with obstacles as it is done very often in A*.

The most obvious way was to check the whole area of the disk like:

bool check(std::function<bool(const Coordinates &)> collide)
{
    const std::uint32_t RADIUS2 = radius * radius;
    Coordinates cell(-radius, -radius);

    for (; cell.x <= radius; cell.x++)
    {
        for (cell.y = -radius; cell.y <= radius; cell.y++)
        {
            if (cell.x * cell.x + cell.y * cell.y <= RADIUS2 && !collide(center + cell))
            {
                return false;
            }
        }
    }

    return true;
}

Where radius is the radius of the disk and center the coordinates of the center of the disk.

A better solution could be to only check the perimeter of the disk. But both solutions need to use 2 for loops and it doesn't fit the disk area a big part of the time.

Do you have any solution to do it a clever way?

Answer 1

Inside a nested loop, you're calling std::function::operator(). That's an indirect call, with a non-trivial abstraction penalty. Now a modern CPU will have branch prediction, which will successfully predict that branch after the first few calls. But your old chip will suffer a lot right there.

So, you indeed need to avoid this. Luckily, the first comment already hits the nail on the head. You can efficiently pre-calculate the hit test, by calculating the no-go zone around obstacles.

Alternatively, assuming that the obstacles don't move, you can cache the results of the hit test on each cell. This is especially effective if you have a large grid where you initially need only a small part.