How many moves to reach a destination? Efficient flood filling

Question

I want to compute the distance of cells from a destination cell, using number of four-way movements to reach something. So the the four cells immediately adjacent to the destination have a distance of 1, and those on the four cardinal directions of each of them have a distance of 2 and so on. There is a maximum distance that might be around 16 or 20, and there are cells that are occupied by barriers; the distance can flow around them but not through them.

I want to store the output into a 2D array, and I want to be able to compute this 'distance map' for any destination on a bigger maze map very quickly.

I am successfully doing it with a variation on a flood fill where the I place incremental distance of the adjacent unfilled cells in a priority queue (using C++ STL).

I am happy with the functionality and now want to focus on optimizing the code, as it is very performance sensitive.

What cunning and fast approaches might there be?

Answer 1

I think you have done everything right. If you coded it correct it takes O(n) time and O(n) memory to compute flood fill, where n is the number of cells, and it can be proven that it's impossible to do better (in general case). And after fill is complete you just return distance for any destination with O(1), it easy to see that it also can be done better.

So if you want to optimize performance, you can only focused on CODE LOCAL OPTIMIZATION. Which will not affect asymptotic but can significantly improve your real execution time. But it's hard to give you any advice for code optimization without actually seeing source.

So if you really want to see optimized code see the following (Pure C):

include

int* BFS()
{
    int N, M; // Assume we have NxM grid.
    int X, Y; // Start position. X, Y are unit based.
    int i, j;
    int movex[4] = {0, 0, 1, -1}; // Move on x dimension.
    int movey[4] = {1, -1, 0, 0}; // Move on y dimension.

    // TO DO: Read N, M, X, Y

    // To reduce redundant functions calls and memory reallocation 
    // allocate all needed memory once and use a simple arrays.
    int* map = (int*)malloc((N + 2) * (M + 2)); 
    int leadDim = M + 2;
    // Our map. We use one dimension array. map[x][y] = map[leadDim * x + y];
    // If (x,y) is occupied then map[leadDim*x + y] = -1;
    // If (x,y) is not visited map[leadDim*x + y] = -2;

    int* queue = (int*)malloc(N*M);
    int first = 0, last =1; 

    // Fill the boarders to simplify the code and reduce conditions
    for (i = 0; i < N+2; ++i)
    {
        map[i * leadDim + 0] = -1;
        map[i * leadDim + M + 1] = -1;
    }

    for (j = 0; j < M+2; ++j)
    {
        map[j] = -1;
        map[(N + 1) * leadDim + j] = -1;
    }

    // TO DO: Read the map.

    queue[first] = X * leadDim + Y;
    map[X * leadDim + Y] = 0;

    // Very simple optimized process loop.
    while (first < last) 
    {
        int current = queue[first];
        int step = map[current];

        for (i = 0; i < 4; ++i)
        {
            int temp = current + movex[i] * leadDim + movey[i];
            if (map[temp] == -2) // only one condition in internal loop.
            {
                map[temp] = step + 1;
                queue[last++] = temp;
            }
        }

        ++first;
    }

    free(queue);

    return map;
}

Code may seems tricky. And of course, it doesn't look like OOP (I actually think that OOP fans will hate it) but if you want something really fast that's what you need.

Answer 2

It's common task for BFS. Complexity is O(cellsCount)

My c++ implementation:

vector<vector<int> > GetDistance(int x, int y, vector<vector<int> > cells)
{
    const int INF = 0x7FFFFF;
    vector<vector<int> > distance(cells.size());
    for(int i = 0; i < distance.size(); i++)
        distance[i].assign(cells[i].size(), INF);
    queue<pair<int, int> > q;

    q.push(make_pair(x, y));
    distance[x][y] = 0;

    while(!q.empty())
    {
        pair<int, int> curPoint = q.front();
        q.pop();
        int curDistance = distance[curPoint.first][curPoint.second];
        for(int i = -1; i <= 1; i++)
            for(int j = -1; j <= 1; j++)
            {
                if( (i + j) % 2 == 0 ) continue;
                pair<int, int> nextPoint(curPoint.first + i, curPoint.second + j);
                if(nextPoint.first >= 0 && nextPoint.first < cells.size()
                   && nextPoint.second >= 0 && nextPoint.second < cells[nextPoint.first].size()
                   && cells[nextPoint.first][nextPoint.second] != BARRIER
                   && distance[nextPoint.first][nextPoint.second] > curDistance + 1)
                   {
                       distance[nextPoint.first][nextPoint.second] = curDistance + 1;
                       q.push(nextPoint);
                   }                    
            }
    }
    return distance;
}

Answer 3

8-bit computers in the 1970s did this with an optimization that has the same algorithmic complexity, but in the typical case is much faster on actual hardware.

Starting from the initial square, scan to the left and right until "walls" are found. Now you have a "span" that is one square tall and N squares wide. Mark the span as "filled," in this case each square with the distance to the initial square.

For each square above and below the current span, if it's not a "wall" or already filled, pick it as the new origin of a span.

Repeat until no new spans are found.

Since horizontal rows tend to be stored contiguously in memory, this algorithm tends to thrash the cache far less than one that has no bias for horizontal searches.

Also, since in the most common cases far fewer items are pushed and popped from a stack (spans instead of individual blocks) there is less time spent maintaining the stack.

Answer 4

Start with a recursive implementation: (untested code)

 int visit( int xy, int dist) {
    int ret =1;
    if (array[xy] <= dist) return 0;
    array[xy] = dist;
    if (dist == maxdist) return ret;
    ret += visit ( RIGHT(xy) , dist+1);
    ... 
    same for left, up, down
    ...
    return ret;
    }

You'l need to handle the initalisation and the edge-cases. And you have to decide if you want a two dimentional array or a one dimensonal array.

A next step could be to use a todo list and remove the recursion, and a third step could be to add some bitmasking.