AStar 寻路

这种是游戏服务端当中最常见的碰撞检测游戏寻路方式, 日常AI机器人也十分依赖寻路策略.

静态可以采用 AStar, 而动态则需要 Dstar 的 Dijkstra 处理运算寻路, 移动端游戏尽可能采用静态寻路处理

游戏客户端大部分实现这些插件让其更加易用( Unity的NavMesh ),
但是服务端则缺失这部分功能也就没办法在服务端模拟玩家行走路线从而同步.

AStar寻路实际上是采用 网格(Gird) 的寻路计算, 具体原理就是先把整个地图分解成 Width * Height 多个格子,
然后通过网格周边连线来处理出最短路径, 同时支持标识障碍物绕过计算, 这种过程就是将 平面栅格化.

大部分寻路都是基于这种方式, 只是按照不同算法评估周边格子从而采样路径处理.

路径初始化

注: 在空间寻路当中必须要具有 方向 和 距离 才能形成正确的寻路路径(向量|矢量)

寻路方式按照不同方式计算寻路:

  • 曼哈顿估价法(Manhattan Heuristic)

  • 几何估价法(Euclidean Heuristic)

  • 对角线估价法(Diagonal Heuristic)

对应三种寻路方式图示处理:

路径寻路方法

曼哈顿估价法

基于 四向移动(十字形位移) 的计算, 也就是只有 上下左右 方向, 这种四向计算性能消耗相对比较小但是只支持四向寻路:

1
2
3
4
5
6
7
8
9
10
---d为计算的相邻正方体网格间移动成本, 也就是从起始坐标格子位移到周边格子路径
---node节点是网格起始的点坐标, goal节点则是最后的终点坐标
---@param node { x = 0,y = 0 } 起始点
---@param goal { x = 0,y = 0 } 最终点
---@param d number
function ManhattanHeuristic(node, goal, d)
    local dx = math.abs(node.x - goal.x)
    local dy = math.abs(node.y - goal.y)
    return d * (dx + dy)
end

几何估价法

基于 任意方向移动 的, 利用几何计算来让寻路支持任意方向位移, 但是计算开销极大:

1
2
3
4
5
6
7
8
9
10
---d为计算的相邻正方体网格间移动成本, 也就是从起始坐标格子位移到周边格子路径
---node节点是网格起始的点坐标, goal节点则是最后的终点坐标
---@param node { x = 0,y = 0 } 起始点
---@param goal { x = 0,y = 0 } 最终点
---@param d number
function EuclideanHeuristic(node, goal, d)
    local dx = math.abs(node.x - goal.x)
    local dy = math.abs(node.y - goal.y)
    return d * math.sqrt(dx * dx + dy * dy)
end

对角线估价法

基于 八向移动(米字形位移) 的计算, 在原来 曼哈顿估价法 引入对角线移动的方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
---d为计算的相邻正方体网格间移动成本, 也就是从起始坐标格子位移到周边格子路径
---这里引入的 d2 就是附近格子斜角线路的距离
---node节点是网格起始的点坐标, goal节点则是最后的终点坐标
---@param node { x = 0,y = 0 } 起始点
---@param goal { x = 0,y = 0 } 最终点
---@param d number
---@param d2 number
function DiagonalHeuristic(node, goal, d, d2)
    local dx = math.abs(node.x - goal.x)
    local dy = math.abs(node.y - goal.y)
    -- 以下等价于: d * math.max(dx,dy) + (d2-d) * math.min(dx,dy)
    -- 亦是等价于: if dx > dy then d * (dx-dy) + d2 * dy else d * (dy-dx) + d2 * dx end
    -- 取 min(dx, dy) 是为了计算短对角长度距离
    return d * (dx + dy) + (d2 - 2 * d) * math.min(dx, dy)
end

估价意义

上面有个名词叫 估价, 把寻路的过程当作 代价|价值, 有代价就需要对其进行评估 估算 最短需要投入的开销;
也就是需要把需要把寻路步骤量化成 价值估算,
因为从 (0,0)走向(1,1)算是走得通, 而(0,0)走(3,3)再走(1,1)也算是走得通, 关键是衡量走通的性价比.

1
2
3
4
5
6
函数公式: f(n) = g(n) + h(n)

n 代表任意的地图区块格
g(n) 代表玩家起点到 n 的实际消耗距离代价
h(n) 代表 n 到终点的大概消耗距离代价
f(n) 就是最后的综合优先计算成本

以下摘录网络的寻路估价计算方式

这里采用八向移动法, 支持 米字移动 方式,
从而计算路径估值代价( 绿色代表玩家, 红色代表终点, 灰色代表障碍物, 棕色代表最优选中路径网格 ):

初始化地图区块

首先是套用 f(n) = g(n) + h(n) 公式, 计算出玩家周边格子的估价, 图片如下:

计算路径估价

1
2
3
4
5
6
7
8
9
10
11
12
这里先说明下 ( f = 3, g = 1, h =2 ) 是估价出来的:
1. 以玩家起点做 (0, 0) 起始点
2. 这里采用八向移动, 上/下/左/右移动到对应身边周边网格消耗记作 1, 如果是斜上/斜下等方式需要追加消耗 1.4, 记作 g
3. 最终需要计算从当前玩家周边网格移动到终点, 也就是如果从该格子移动到终端的代价, 记作 h
4. 那么最后计算套用公式 f = g(1) + h(2) = 3 

注意: 上/下/左/右移动成本是 1, 那么斜上/斜下/斜左/斜右移动成本则是 1.2~1.4 做成本计算, 这里取 1.4 为斜角估值成本

也就是如果从右上角起步的话, 那么估价成本如下:
g = 1.4 (斜角移动, 如果采用曼哈顿估值则只有 1 取值而不带有斜角估值)
h = 2.4 (先往右移动再斜角移动, 这里最后取值得出 2.4 )
f = 1.4 + 2.4 = 3.8 (最后得出右上角路径估算价值)

这里取值 ( f=3 ) 作为下一步的坐标路径, 那么要以 ( f=3 ) 继续套用公式继续计算最短路径:

下步路径估价

这里需要计算出格子的四周和终点是否相邻，如果相邻并终止算法得出估算的路径成本, 否则计算出没有与终点相邻需要重新进行下一步估值计算.

下一步得出估价

下一步得出估价

在不断递归检索 f(n) 路径最优值的时候, 最终若干次估算得出到达终点的场值:

最终得出估价

这就是整体的估算意义, 通过这种不断 启发性 估值出下步节点, 最终计算出最短距离来反推回起点距离;
优点就是寻路性能比较好且方便实现, 但是缺点就是实时性差且随着网格增多检索路径的效率越发变低,
所以寻路切割的尽可能不要将网格分割过于细小从而保持效率; 这里展示最后的计算路径过程:

估计运算过程

代码实现初始化

这里主要采用 曼哈顿估值法 和 对角线估价法 就能应用日常游戏寻路方式, 而几何因为计算性能不在考虑范围内.

这里先说明下怎么采用代码实现上面 十和米字型 公式移动, 从而理解公式转代码的流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
---二维坐标系类对象
---@class Vec2
---@field x number
---@field y number
Vec2 = Vec2 or {
    New = function(x, y)
        local vec2 = { x = x, y = y }
        setmetatable(vec2, Vec2)
        return vec2
    end,
    ---@param self Vec2
    __tostring = function(self)
        return string.format("Vec(%d, %d)", self.x, self.y)
    end
}

--- 四向计算: 上下左右 - 曼哈顿估值
---@param startPos Vec2
---@param endPos Vec2
---@param d number
---@return number h
function ManhattanHeuristic(startPos, endPos, d)
    local dx = math.abs(startPos.x - endPos.x)
    local dy = math.abs(startPos.y - endPos.y)
    return d * (dx + dy)
end

--- 八向计算: 上下左右,斜上下左右 - 对角线估值
---@param startPos Vec2
---@param endPos Vec2
---@param d number
---@param d2 number
---@return number h
function DiagonalHeuristic(startPos, endPos, d, d2)
    local dx = math.abs(startPos.x - endPos.x)
    local dy = math.abs(startPos.y - endPos.y)
    -- 以下等价于: d * math.max(dx,dy) + (d2-d) * math.min(dx,dy)
    -- 亦是等价于: if dx > dy then d * (dx-dy) + d2 * dy else d * (dy-dx) + d2 * dx end
    -- 取 min(dx, dy) 是为了计算短对角长度距离
    return d * (dx + dy) + (d2 - 2 * d) * math.min(dx, dy)
end



-- 打印获取坐标, 这里都是采用上面图示的位移坐标, 结果可以与上文结合得出
local startVec = Vec2.New(0, 0)
local endVec = Vec2.New(3, 0)
local d = 1 -- 上下左右移动估值
local d2 = 1.4 -- 斜角方向移动估值

-- 右左上下 - 获取 h(n) - 四向的估值
print("============================================")
print("Manhattan: ")
local rightManhattanVec = ManhattanHeuristic(Vec2.New(startVec.x + 1, startVec.y), endVec, d)
print("right", tostring(rightManhattanVec))
local topManhattanVec = ManhattanHeuristic(Vec2.New(startVec.x, startVec.y - 1), endVec, d)
print("top", tostring(topManhattanVec))
local leftManhattanVec = ManhattanHeuristic(Vec2.New(startVec.x - 1, startVec.y), endVec, d)
print("left", tostring(leftManhattanVec))
local downManhattanVec = ManhattanHeuristic(Vec2.New(startVec.x, startVec.y + 1), endVec, d)
print("down", tostring(downManhattanVec))

-- 八向计算 - 获取 h(n) - 八向的估值
print("============================================")
print("Diagonal: ")
local rightDiagonalVec = DiagonalHeuristic(Vec2.New(startVec.x + 1, startVec.y), endVec, d, d2)
print("right", tostring(rightDiagonalVec))
local rightTopDiagonalVec = DiagonalHeuristic(Vec2.New(startVec.x + 1, startVec.y - 1), endVec, d, d2)
print("rightTop", tostring(rightTopDiagonalVec))
local topDiagonalVec = DiagonalHeuristic(Vec2.New(startVec.x, startVec.y - 1), endVec, d, d2)
print("top", tostring(topDiagonalVec))
local leftTopDiagonalVec = DiagonalHeuristic(Vec2.New(startVec.x - 1, startVec.y - 1), endVec, d, d2)
print("leftTop", tostring(leftTopDiagonalVec))
local leftDiagonalVec = DiagonalHeuristic(Vec2.New(startVec.x - 1, startVec.y), endVec, d, d2)
print("left", tostring(leftDiagonalVec))
local leftDownDiagonalVec = DiagonalHeuristic(Vec2.New(startVec.x - 1, startVec.y + 1), endVec, d, d2)
print("leftDown", tostring(leftDownDiagonalVec))
local downDiagonalVec = DiagonalHeuristic(Vec2.New(startVec.x, startVec.y + 1), endVec, d, d2)
print("down", tostring(downDiagonalVec))
local rightDownDiagonalVec = DiagonalHeuristic(Vec2.New(startVec.x + 1, startVec.y + 1), endVec, d, d2)
print("rightDown", tostring(rightDownDiagonalVec))

-- 关于 g(n) 的取值实际上取逐步递进移动格子数值
-- 对于曼哈顿估值法: 第一次往右走得出 d = 1, 而再次往右走则 + 1 估值等于 2, 以此类推递增
-- 对于对角线估值法: 第一次往右上得出 d2 = 1.4 估值, 而再次往右走(非斜角)得出 d + d2 = 1 + 1.4 = 2.4, 以此类推递增

以上就是单步公式套用方式最后计算周边网格 h(n) 值, 而 g(n) 取值则是需要计算内部已行走开放节点格子数值;
另外这里还需要说明位图数据标识地图信息, 这里也是用 Lua 演示如果客户端导出的地图格子通行信息的格式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-- 实例化位图网格对象
local tiles = setmetatable({}, {
    __tostring = function(self)
        local t = {}
        for _, v in ipairs(self) do
            table.insert(t, "[" .. table.concat(v, ", ") .. "]")
        end
        return table.concat(t, "\n")
    end
})
table.insert(tiles, { 0, 0, 0, 0, 0, 0, 0 })
table.insert(tiles, { 0, 0, 1, 0, 0, 0, 0 })
table.insert(tiles, { 0, 0, 1, 0, 0, 0, 0 })
table.insert(tiles, { 0, 0, 1, 0, 0, 0, 0 })
table.insert(tiles, { 0, 0, 0, 0, 0, 0, 0 })
print("位图网格数据")
print(tiles)

这里最后展示出来的就是地图的网格状态:

1
2
3
4
5
6
7
位图网格数据坐标, 内部如果网格值大于 0 可以识别网格状态, 比如现在标识 1 代表阻挡物, 所以寻路要避开:
   X →
Y↓ [0, 0, 0, 0, 0, 0, 0]
   [0, 0, 1, 0, 0, 0, 0]
   [0, 0, 1, 0, 0, 0, 0]
   [0, 0, 1, 0, 0, 0, 0]
   [0, 0, 0, 0, 0, 0, 0]

后续客户端需要开发地图编辑器提供给策划|客户端等进行地图去 刷 地图网格导出成 lua|json|python 等表格式,
从而让服务器启动|玩家登录时候加载场景地图用于 玩家|AI地图寻路.

现在大概理解了寻路要素:

  • 玩家起始点 - startPoint

  • 到达终点 - endPoint

  • 场景位图位图 - tiles

只要理解寻路这些要素就可以进行下一步代码部署, 下面编写个示例导出的数据格式文件用于做客户端参考:

1
2
# 创建编写地图导出位图, 后续要客户端暴露给
vim tiles.json

网格区块内容如下, 先设定个 16 * 9 的网格数据用来导出给服务端加载:

1
2
3
4
5
6
7
8
9
10
11
12
//  Titles = [Y][X], 这里就是个 16(X):9(Y) 比例的场地网格位图 
[
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
]

那么现在就是开始解析寻路处理.

代码抽象

现在准备处理最短路径寻路编写功能:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
---二维坐标象限
---@class Vec2
---@field x number
---@field y number
Vec2 = Vec2 or { x = 0, y = 0 }

---获取实例
---@return Vec2
function Vec2:New(x, y)
    local obj = { x = x, y = y }
    return setmetatable(obj, {
        __index = Vec2,
        ---@param self Vec2
        __tostring = function(self)
            return string.format("Vec2{ x=%d, y=%d }", self.x, self.y)
        end
    })
end

---位图对象
---@class Tiles
Tiles = Tiles or { tiles = {} }

---@return Tiles
function Tiles:New()
    local obj = { tiles = {} }
    return setmetatable(obj, {
        __index = Tiles,
        __tostring = function(self)
            local t = {}
            for _, v in ipairs(self.tiles) do
                table.insert(t, "[ " .. table.concat(v, ", ") .. " ]")
            end
            return table.concat(t, "\n")
        end
    })
end

---追加网格信息
function Tiles:AddTile(tile)
    table.insert(self.tiles, tile)
end

---检索位图数据
function Tiles:GetTileInfo(y, x)
    local rows = self.tiles[y + 1]
    if rows ~= nil then
        return rows[x + 1]
    end

    return nil
end

--- 实例化起点和终点
local startPos = Vec2:New(0, 0)
local endPos = Vec2:New(5, 8)
print(startPos, endPos)

--- 实例化位图表 16x9 的网格地图, 留意出目前的 1 就是阻挡不可寻路
--- 留意 ( x, y ) = ( 5, 5 ) = 1, 这里是被阻挡的; Lua是以 1 做索引, 其他语言以 0 起始
--- 为了统一所有编程语言, 所以需要最好内部设计
local tiles = Tiles:New()
tiles:AddTile({ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 })
tiles:AddTile({ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 })
tiles:AddTile({ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 })
tiles:AddTile({ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 })
tiles:AddTile({ 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 })
tiles:AddTile({ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 })
tiles:AddTile({ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 })
tiles:AddTile({ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 })
tiles:AddTile({ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 })
tiles:AddTile({ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 })

--- 这里采用 index = 0 做起始
print("Tile", tiles:GetTileInfo(4, 4))

之后就是具体的 AStar 寻路工具类设计:

未完待续

地图编辑

之前看过要求平面格式化成多个小格子,而之前说到客户端开个地图编辑器通过策划刷格子标识格子可以移动|会被阻挡等状态,
最后导出成 Json|Lua 等通用位图格式提供给服务端启动生成场景在服务端构建公用地图模块寻路.

注意: 规定地图的 (X,Y) 必须能够被格子整除, 也就是如果美术地图设计出 1920 * 1080, 格子块必须能被宽高整除(被2整除)

导出位图就是各自格子的分布情况, 实际上所有地图都可以进行切分小格子按比例切割 , 对于服务端来说人物寻路其实就像象棋走格子.