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

Question

I'm trying to implement a wavefront algorithm and I have a problem with the function, that produces the map with specific gradients.

I've tried several different versions of the code below and none of them worked.

The starting point for the algorithm (the goal) is set to 1 before and from that point on each neighbour's gradient should be increased (similar to every wavefront algorithm), if the gradient hasn't bin altered yet.

originX and originY is the goal, from which the alorithm should start. mapMatrix is a global variable

mapMatrix looks like this:

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 for rails, N(nil) for obstacles)

expected output example:

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

And with this code for example:

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

I get this 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

And if I switch the if statements arround it produces different version of mapMatrix

After making northDir, etc local the output looks like this: 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

If more code or information is needed, I'd be happy to help

Answer 1

Your code is just wrong at all. As pathFinder is called recursively in the first check, it will be just going in that direction until any obstacle appears, and than going in the next direction, and so on.

---

BFS is actually a pretty simple algorithm. It can be easily implemented iteratively on a queue without any recursion as follow:

1. Put initial node to a queue;
2. Pop first node from the queue and process it;
3. Push unprocessed adjacent nodes to the end of the queue;
4. If queue is not empty, go to the step 2.

In Lua on a rectangular matrix it can be implemented in about two or three dozen of lines:

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
]]

This is a complete script, runnable in the console.

---

But although, for illustrative purposes, this code is very simple, it is not very efficient. Each removal of the first item from the queue causes reindexing of the remaining items. For production code you should implement a linked list or something similar for the queue.