有几步到达目的地？高效的洪水填充 [英] How many moves to reach a destination? Efficient flood filling

问题描述

我想使用四次移动达到目标的次数来计算出目标细胞与目标细胞的距离。因此，紧邻目的地的四个单元格之间的距离为1，而每个方向上四个方向上的单元格之间的距离为2，依此类推。最大距离可能约为16或20，并且某些单元格被障碍物占据；

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.

我想将输出存储到2D数组中，并且希望能够计算出此距离图

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.

我成功地完成了这一工作，对洪水填充进行了更改，在该填充中，我将相邻未填充单元的增量距离放置在优先级队列（使用C ++ STL）。

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?

推荐答案

我认为您所做的一切都正确。如果正确编码，则需要O（n）时间和O（n）内存来计算泛洪填充，其中n是单元数，并且可以证明做得更好（通常情况下）。填充完成后，您只需返回O（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.

因此，如果您真的想查看优化的代码，请参见以下内容（纯C）：

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

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;
}

代码似乎很棘手。当然，它看起来并不像OOP（我实际上认为OOP粉丝会讨厌它），但是如果您想要快速的东西，这就是您所需要的。

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.

这篇关于有几步到达目的地？高效的洪水填充的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！