Lua (trAInsported)：尝试实施波前算法，但无法正常工作

Question

我正在尝试实现波前算法，但我遇到了生成具有特定梯度的地图的函数的问题。

我已经尝试了以下代码的几个不同版本，其中 none 个有效。

算法的起点（目标）设置为 1，如果梯度还没有改变，那么每个邻居的梯度应该增加（类似于每个波前算法）。

originX 和 originY 是目标，算法应该从那里开始。 mapMatrix是一个全局变量

mapMatrix 看起来像这样：

0 0 0 0 0 0 0
0 0 N 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 N 0 0 N 0 N
N N 0 0 N 0 0 
0 0 0 0 0 0 0

（0 表示 rails，N（零）表示障碍物）

预期输出示例：

7 6 5 4 3 4 5
6 5 N 3 2 3 4
5 4 3 2 1 2 3
6 5 4 3 2 3 3
7 N 5 4 N 4 N
N N 6 5 N 5 6 
9 8 7 6 7 6 7

并以此代码为例：

function pathFinder(originX, originY)
    northDir = originY - 1
    eastDir = originX + 1
    southDir = originY + 1
    westDir = originX - 1

    if northDir > 0 and mapMatrix[originX][northDir] == 0 then 
        mapMatrix[originX][northDir] = mapMatrix[originX][originY] + 1
        pathFinder(originX, northDir)

    end
    if eastDir <= 7 and mapMatrix[eastDir][originY] == 0 then 
        mapMatrix[eastDir][originY] = mapMatrix[originX][originY] + 1
        pathFinder(eastDir, originY)

    end
    if southDir <= 7 and mapMatrix[originX][southDir] == 0 then 
        mapMatrix[originX][southDir] = mapMatrix[originX][originY] + 1
        pathFinder(originX, southDir)

    end
    if westDir > 0 and mapMatrix[westDir][originY] == 0 then 
        mapMatrix[westDir][originY] = mapMatrix[originX][originY] + 1
        pathFinder(westDir, originY)
    end
end

我明白了 mapMatrix:

0 0 0 0 3 4 5
0 0 N 0 2 10 6
0 0 0 0 1 9 7
0 0 0 0 0 0 8
0 N 0 0 N 0 N
N N 0 0 N 0 0 
0 0 0 0 0 0 0

如果我切换周围的 if 语句，它会产生不同版本的 mapMatrix

在制作 northDir 等 local 之后，输出如下所示：EDIT

33 24 23 22 3 4 5
32 25 N 21 2 11 6
31 26 27 20 1 10 7
30 29 28 19 20 9 8
31 N 29 18 N 10 N
N N 30 17 N 11 12
33 32 31 16 15 14 13

如果需要更多代码或信息，我很乐意提供帮助

Answer 1

您的代码完全错误。由于 pathFinder 在第一次检查中被递归调用，它只会朝那个方向前进，直到出现任何障碍物，然后再朝下一个方向前进，依此类推。

BFS 实际上是一个非常简单的算法。它可以很容易地在队列上迭代实现，无需任何递归，如下所示：

将初始节点放入队列；
从队列中弹出第一个节点并处理它；
将未处理的相邻节点推到队列末尾；
如果队列不为空，转到步骤2。

在Lua一个矩形矩阵上大概两三行就可以实现：

function gradient(matrix, originX, originY)
    -- Create queue and put origin position and initial value to it.
    local queue = { { originX, originY, 1 } }

    repeat
        -- Pop first position and value from the queue.
        local x, y, value = unpack(table.remove(queue, 1))

        -- Mark this position in the matrix.
        matrix[y][x] = value

        -- Check position to the top.
        if y > 1 and matrix[y - 1][x] == 0 then
            -- If it is not already processed, push it to the queue.
            table.insert(queue, { x, y - 1, value + 1 })
        end

        -- Check position on the left.
        if x > 1 and matrix[y][x - 1] == 0 then
            table.insert(queue, { x - 1, y, value + 1 })
        end

        -- Check position to the bottom.
        if y < #matrix and matrix[y + 1][x] == 0 then
            table.insert(queue, { x, y + 1, value + 1 })
        end

        -- Check position on the right.
        if x < #matrix[y] and matrix[y][x + 1] == 0 then
            table.insert(queue, { x + 1, y, value + 1 })
        end

    -- Repeat, until queue is not empty.
    until #queue == 0
end

-- Just helper function to print a matrix.
function printMatrix(matrix)
    for _, row in pairs(matrix) do
        for _, value in pairs(row) do
            io.write(string.format("%2s", value))
        end
        io.write('\n')
    end
end

local mapMatrix = {
    {   0,   0,   0, 0,   0, 0,   0, },
    {   0,   0, 'N', 0,   0, 0,   0, },
    {   0,   0,   0, 0,   0, 0,   0, },
    {   0,   0,   0, 0,   0, 0,   0, },
    {   0, 'N',   0, 0, 'N', 0, 'N', },
    { 'N', 'N',   0, 0, 'N', 0,   0, },
    {   0,   0,   0, 0,   0, 0,   0, },
}

gradient(mapMatrix, 5, 3)
printMatrix(mapMatrix)

--[[
Produces:
 7 6 5 4 3 4 5
 6 5 N 3 2 3 4
 5 4 3 2 1 2 3
 6 5 4 3 2 3 4
 7 N 5 4 N 4 N
 N N 6 5 N 5 6
 9 8 7 6 7 6 7
]]

这是一个完整的脚本，可在控制台中运行。

但是，尽管出于说明目的，此代码非常简单，但效率不高。每次从队列中移除第一个项目都会导致对剩余项目重新编制索引。对于生产代码，您应该为队列实现一个链表或类似的东西。

Lua (trAInsported)：尝试实施波前算法，但无法正常工作

Lua (trAInsported): trying to implement Wavefront Algorithm, not working

algorithm

lua

breadth-first-search

wavefront