我该如何在Lua中实现刷子算法？

2015-1-19 23:36:40
收藏：0
阅读：127
评论：1

我正在尝试实现“基于目标的向量场路径规划”（在此链接的文章中演示）。它要求我在世界图中标记每个节点与目标节点的路径距离，并建议使用波前（wavefront）算法来实现。这是我遇到问题的地方。当我进入while循环的第8次迭代和嵌套的第6次“for”循环时，我会在标记行上得到一个nil引用错误。

g 是我的图表，具有8向邻接列表格式。

q 是 此库 的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

以下是我到目前为止的实现。循环中的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]  <------此处出错
                t.dist = d
                q:pushRight( t )
                t = nil
            end
        end
        d = d + 1
    end
end

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

点赞
用户3014065
用户3014065

我找到了解决问题的答案。如果有人想使用这个源代码，我在下面发布它：

队列模块：

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 }

--  私人功能

local function genDistMap( g, rtx, rty )      -<-<-<- genDistMap 是brushfire部分
    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

--  公共功能

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
2015-02-13 13:25:56

作者:

用户3014065

用户3014065
推荐文章