在巨大地图上的路径规划

我需要一些路径规划算法，于是我在网上查找并找到一些算法。

它们似乎都需要一些地图。 这个地图可以表示为：

• 网格
• 节点

由于我的地图当前非常巨大(20,000 x 20,000像素)，1 x 1像素网格地图将导致网格上有400,000,000个唯一的点，我认为这是最好的品质。但这太多的点对我来说所以我可以：

• 增加网格大小(例如50 x 50像素= 160,000个唯一的点）
• 切换到节点

由于160,000个唯一的点对我也太多了，或者我应该说，对我来说不是我想要的品质，因为有些单元比50像素更大，我认为节点是更好的选择。

我在网上发现了这个内容：2D非网格化节点路径规划并进行了一些计算：

local radius = 75                               -- 这会根据一些单位而变化，所以我坚持使用最大值
local DistanceBetweenNodes = radius * 2         -- 对角线通过瓦块
local grids = 166                               -- 有多少列/行
local MapSize = grids * DistanceBetweenNodes    -- 约为25,000
local walkable = 0                              -- 之后使用

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个唯一的节点。如果删除不可通过的节点，则节点将大大缩小，但由于我的单位有不同的大小，我需要将半径设为我拥有的最小单位。我不知道这是否适用于以后的较大的单位。

所以我又在网上查找并找到了导航网格。这将将节点数量简化为我眼中的“一些”，并且适用于任何单位大小。

更新9月28日 我现在已经创建了所有可通过区域的节点图，约为30,000个节点。

这是一个完全随机的地图示例和我拥有的点： 地图示例