lua - 在巨大的 map 上寻路

Question

我需要某种类型的寻路，所以我在互联网上搜索并找到了一些算法。

似乎他们都需要某种类型的 map 。 该 map 可以表示为:

• 网格
• 节点

由于我的 map 目前相当大(20.000 x 20.000 像素)，1 x 1 像素图 block 的网格 map 将导致网格上400.000.000 个独特的点，并且也是我最好的质量会想。但这对我来说意义重大，所以我可以

• 增加图 block 大小(例如 50 x 50 像素 = 160.000 个唯一点)
• 切换到节点

由于 160.000 个独特点对我来说也太多了，或者我想说，这不是我想要的质量，因为有些单位更大到 50 像素，我认为节点是更好的选择。

我在互联网上找到了这个2D Nodal Pathfinding without a Grid并做了一些计算:

local radius = 75                               -- this varies for some units so i stick to the biggest value
local DistanceBetweenNodes = radius * 2         -- to pass tiles diagonaly
local grids = 166                               -- how many col/row
local MapSize = grids * DistanceBetweenNodes    -- around 25.000
local walkable = 0                              -- used later

local Map = {}

function even(a)
    return ((a / radius) % 2 == 0)
end

for x = 0, MapSize, radius do
    Map[x] = {}
    for y = 0, MapSize, radius do
        if (even(x) and even(y)) or (not even(x) and not even(y)) then
            Map[x][y] = walkable
        end
    end
end

如果不删除无法通过的节点和 75 的单元大小，我最终会得到 ~55445 个唯一节点。如果我删除无法通过的节点，节点将急剧缩小，但由于我的单位具有不同的大小，我需要将半径设置为我得到的最小单位。我不知道这是否适用于以后更大的单位。

于是我又上网搜索了一下，发现了这个Nav Meshes 。 在我看来，这会将节点减少到只有“几个”，并且适用于任何单位大小。

更新 28.09 我已经创建了所有可通行区域的节点 map ，现在约有 30.000 个节点。

这是一个完全随机的 map 示例和我拥有的点: Example Map

Answer 1

这需要一些优化，并减少您拥有的节点数量。

几乎所有寻路算法都可以采用非网格的节点列表。不过，您需要调整节点之间的距离。

您还可以增加网格大小，使其没有那么多的方 block 。不过，您需要以某种方式补偿又小又窄的路径。

最终，我建议您通过简单地将节点放置在已安排的路径中来减少节点数量，您知道可以从 A 点到达 B 点，并指定邻居。不过，您需要为每个级别手动创建节点路径。以我的测试为例(没有墙，只有节点路径):

对于您提供的 map ，您最终会得到与此类似的路径节点:

它有大约 50 个节点，而一个网格可以有数百个节点。

这可以在任何规模上工作，因为与网格方法相比，您的节点数量大大减少。您将需要进行一些调整，例如计算节点之间的距离，因为它们不在网格中。对于此测试，我在 Corona SDK (Lua) 中使用 dijkstra 算法，但您可以尝试使用任何其他算法，例如 A-star (A*)，它在许多游戏中使用，并且速度更快。

我发现了一个 Unity 示例，它采用了使用节点的类似方法，您可以看到该方法也适用于 3D: