Lua寻路算法代码需要优化。

2016-1-23 3:41:25
收藏：0
阅读：161
评论：3

在对我的代码进行优化后，优化了大部分显而易见的问题，我得到了以下结果：

function FindPath(start, finish, path)
    --定义一个表来保存路径
    local paths = {}
    --定义默认参数
    path = path or {start}
    --循环遍历相连的节点
    for i,v in ipairs(start:GetConnectedParts()) do
        --判断是否回溯
        local loop = false
        for i,vv in ipairs(path) do
            if v == vv then
                loop = true
            end
        end
        if not loop then
            --生成路径副本
            local npath = {unpack(path)}
            npath[#npath+1] = v
            if v == finish then
                --如果到达终点，则添加路径
                return npath
            else
                --否则从此节点添加最短的部分
                paths[#paths+1] = FindPath(v, finish, npath) --在此处注意
            end
        end
    end
    --查找并返回最短路径
    if #paths > 0 then
        local lengths = {}
        for i,v in ipairs(paths) do
            lengths[#lengths+1] = #v
        end
        local least = math.min(unpack(lengths))
        for i,v in ipairs(paths) do
            if #v == least then
                return v
            end
        end
    end
end

问题是，标记的行会出现某种游戏脚本超时错误（我相信这是由于大量递归而没有yielding所导致的）。我也觉得一旦解决了这个问题，它可能在pacman板上的规模上也会很慢。有没有方法可以进一步优化它，或者类似于此的更好的方法？

更新：我最终决定放弃了我的算法，因为效率低下，而实现了一种Dijkstra算法来进行路径搜索。对于任何有兴趣查看源代码的人，可以在这里找到：http://pastebin.com/Xivf9mwv

点赞
用户858951
用户858951

你知道 Roblox 提供了 PathfindingService（路径规划服务）吗？它使用 C-side A*（A星算法）进行快速计算。我建议你使用它。

http://wiki.roblox.com/index.php?title=API:Class/PathfindingService

2016-01-20 00:00:55
用户2863960
用户2863960

尝试重新设计你的算法，利用 Lua 中提供的尾调用机制。

尾调用是一种函数递归的形式，其中你的函数作为最后的一个操作返回一个函数调用。Lua 已经实现了正确的尾调用，并将其作为“goto”在后台运行，因此避免了栈溢出的问题。

将“路径”作为 FindPath 函数的参数之一可能有所帮助。

2016-01-20 07:32:06
用户5352026
用户5352026

我看到你关于舍弃代码的修改，但仍想对其他遇到这个问题的人提供帮助:

  • ipairs 比 pairs 慢，pairs 比 for 循环慢。如果性能很重要，永远不要使用 ipairs，而是使用 for i=1,#tab 循环
  • 如果你想克隆一个表，使用 for 循环。有时，您必须使用 unpack（返回尾随动态数量的 nil 值），但这不是这种情况。拆包也是一个很慢的函数。

用循环代替拆包并将 ipairs 替换为 pairs 或数字 for 循环将大大提高性能。

如果要获取表中最小的值，请使用此代码段：

local lowestValue = values[1]
for k,v in pairs(values) do
    if v < lowestValue then
        lowestValue = k,v
    end
end

这可以重写为您的路径示例，如下所示：

local least = #path[1]
for k,v in pairs(path) do
    if #v < least then
        least = v
    end
end

我必须承认，你很有创造力。很少有人会使用 math.min（unpack（tab））（不计算它的错误性）。

2016-02-10 18:48:08

作者:

用户3979429

用户3979429
推荐文章