如何在 Lua 中实现 brushfire 算法？

Question

我正在努力实施 "Goal-based vector field pathfinding"（在 this link 的文章中进行了演示）它要求我用到目标节点的路径距离标记我的世界图中的每个节点，并建议使用brushfire（波前）算法来做到这一点。这是我遇到问题的地方。当我到达我的 while 循环的第 8 次迭代和我的嵌套 for 的第 6 次迭代时，我在标记的行上得到一个 nil 引用错误。

g是我的图，它有一个8向邻接表形式。

q 是 this FIFO lua 库的实例。

rtx和rty是根节点的x和y坐标。

d 是添加的迭代器，用于跟踪分配给每个节点的路径距离。

图中每个节点的结构与正在处理的节点的结构不同。

处理节点：

n = {}
n[1] = x coord
n[2] = y coord
n[3] = adjacency list (eight entries)
n.vX = x componant of vector for vector field
n.vY = y componant of vector for vector field

图中存储的节点：

n = {}
n[1] = adjacency list
n.vX = x componant of vector for vector field
n.vY = y componant of vector for vector field

下面是我到目前为止的实现。 for 循环中的 t 只是一个临时节点，用于将信息传递到队列。顺便说一句，t 是设置所有节点距离的地方。

local function brushFire( g, rtx, rty )
    local q = q.new()
    local s = {}
    s[1] = rtx
    s[2] = rty
    s[3] = g[rtx][rty][3]
    s.dist = 0
    q:pushRight( s )
    s = nil
    local d = 0

    while( table.getn( q.list[q.first] ) ~= 0 ) do
        print( d )
        local n = q:popLeft()
        setDist( g, n )
        print( #n[3] )
        for i = 1, #n[3] do
            print( ":"..i )
            if( g[n[3][i][4]][n[3][i][2]].v ~= true ) then
                g[n[3][i][5]][n[3][i][2]].v = true
                local t = {}
                t[1] = n[3][i][1]
                t[2] = n[3][i][2]
                t[3] = g[n[3][i][7]][n[3][i][2]][1]  <------Error here
                t.dist = d
                q:pushRight( t )
                t = nil
            end
        end
        d = d + 1
    end
end

如果您需要更多信息来回答我的问题，请告诉我。

Answer 1

我找到了问题的答案。如果有人想使用源代码，我将其发布在下面：

队列模块：

local q = {}
local q_mt = { __index = q }

function q.new()
    local nq = { first = 0, last = -1, list = {} }

    return setmetatable( nq, q_mt )
end

function q:pushLeft( value )
    local first = self.first - 1
    self.first = first
    self.list[first] = value
end

function q:pushRight( value )
    local last = self.last + 1
    self.last = last
    self.list[last] = value
end

function q:popLeft()
    local first = self.first
    if first > self.last then error( "list is empty" ) end
    local value = self.list[first]
    self.list[first] = nil
    self.first = first + 1
    return value
end

function q:popRight()
    local last = self.last
    if self.first > last then error( "list is empty" ) end
    local value = self.list[last]
    self.list[last] = nil
    self.last = last - 1
    return value
end

return q

调用 pathFind.findPath 时，以下模块创建指向目标的矢量场：

local q = require( "Queue" )

local pathFind = {}
local pathFind_mt = { __index = pathFind }

--  Private Functions

local function genDistMap( g, rtx, rty )      -<-<-<- genDistMap is the brushfire part
    local q = q.new()
    local g = g
    g[rtx][rty].v = true
    g[rtx][rty].dist = 0
    local s = {}
    s[1] = rtx
    s[2] = rty
    s[3] = g[rtx][rty][1]
    s.dist = 0
    q:pushRight( s )
    s = nil

    while( q.list[q.first] ~= nil ) do
        local n = q:popLeft()
        for i = 1, #n[3] do
            local x, y = n[3][i][1], n[3][i][2]
            if( g[x][y].v ~= true ) then
                g[x][y].v = true
                local t = {}
                t[1] = x
                t[2] = y
                t[3] = g[x][y][1]
                t.dist = n.dist + 1
                g[x][y].dist = n.dist + 1
                q:pushRight( t )
                t = nil
            end
        end
    end

    return g
end

local function genVectorField( nodes )
    local nodes = nodes

    for i = 2, #nodes - 1 do
        for j = 2, #nodes[i] - 1 do
            local a = nodes[i - 1][j].dist - nodes[i + 1][j].dist
            local b = nodes[i][j - 1].dist - nodes[i][j + 1].dist
            local c = math.sqrt( a*a + b*b )
            nodes[i][j].vX = a/c*5
            nodes[i][j].vY = b/c*5
        end
    end

    return nodes
end

--  Public Functions

function pathFind.new()
    local newPathFind = {}

    return setmetatable ( newPathFind, pathFind_mt )
end

function pathFind.findPath( nodeSet, rootX, rootY )
    local nodes = nodeSet

    nodes = genDistMap( nodes, rootX, rootY )

    nodes = genVectorField( nodes )

    return( nodes )
end

return pathFind

如何在 Lua 中实现 brushfire 算法？

How do I implement a brushfire algorithm in Lua?

algorithm

lua

breadth-first-search

adjacency-list