MeteorCat / 最简单的游戏寻路实现

Created Sun, 05 May 2024 00:12:28 +0800 Modified Wed, 29 Oct 2025 23:25:01 +0800
2276 Words
游戏数学

最简单的游戏寻路实现

这种寻路方法是之前在游戏应用到相对简单的游戏寻路方法, 通过客户端设计编辑 (X1, Y1) - (X2, Y2) 多段线段导出JSON格式:

// A点->B点的线段
[
  // 起点 = A
  {
    x: 1,
    y: 4
  },
  // 终点 = B
  {
    x: 8,
    y: 5,
  }
]

// C点->E点的线段
[
  // 起点 = C
  {
    x: 3,
    y: 7
  },
  // 终点 = B
  {
    x: 6,
    y: 7,
  }
]

两点之间就能确定线段, 那么就可以转化成数学问题:

  1. 确定玩家的终点(x1,y1), 转化成 坐标系中求终点到多条线段的最小距离 数学运算, 反推出终点到哪条线段距离最短
  2. 现在已经确定好路径线段, 之后通过玩家起点(x2,y2)转化成 坐标系中求玩家点到选中线段的最小距离, 推出玩家启动选中路径最短距离

到这里已经确定好几段路径:

  • 玩家终点应该走哪条预设路径最短线路: <point(x1,y1) -> line(x1,y1)>,
  • 玩家起点到路径的最短线路: <point(x2,y2) -> line(x2,y2) >
  • 最终线路组合: <point(x2,y2),玩家起点> -> <line(x2,y2),玩家距离最短距离> -> 走到端点 -> <point(x1,y2),路径端点到终点>

那么最后得出的路径就连接接起来就是这样:

  1. 先从玩家起点到选中路径最短路径点步入寻路路径
  2. 之后通过寻路路径移动到路径的端点( 寻路线段的起点|终点 )
  3. 最后从路径端点移动到玩家最后的终点

这种方式作为最初版的路径引入用于比较基础地图线路预设之后寻路, 日常这种方式可能还需要细化处理, 但是如果要求不是那么高可以直接使用.

矢量算法

那么现在归结到数学问题就是求点到线段的距离, 在求点到线条最短距离有很多方法但这里只介绍 矢量算法(适合计算量大).

这种方式其实就是以空间几何方式来求出最短距离, 设 P = 玩家坐标 和 A->B = 玩家路径, 求出 A->P 和 A->B 的投影( C )即为最短路径的位置.

$$ \overrightarrow{AC} = \frac{(\overrightarrow{AP} \cdot \overrightarrow{AB})}{|\overrightarrow{AB|}^{2}}, 这里求出 ( \overrightarrow{AP} \cdot \overrightarrow{AB})为两个向量内积, 且 (\overrightarrow{AP} \cdot \overrightarrow{AB}) = |\overrightarrow{AP}| |\overrightarrow{AB}| \cos \theta $$

$$ \theta 为向量 AP 到 AB 之间的夹角, 而 \overrightarrow{AB} 则是向量的长度, 也就是游戏预定义的路径线路 $$

这里图片展示出空间投影的几种情况:

路径规划

这里三种投影情况以此对应:

$$ 根据 r = \frac{(\overrightarrow{AP} \cdot \overrightarrow{AB})}{|\overrightarrow{AB|}^{2}} 的 r 值对应图里三种情况 $$

$$ (a)情况 {\color{Red} 0 < r < 1},(b)情况 {\color{Red} r >= 1},(c)情况 {\color{Red} r <= 1} $$

如果只需要判断计算距离最近的线路, 只要计算出多条预先规划好的线路 r 值取绝对值就能得出最近路径.

代码实现

这里先用 Lua 脚本实现, 实际上我不推荐这种动态类型脚本做测试实现; 因为如果不小心很容易出现类型推断错误, 不如采用强类型直接编译的时候让其检查具体逻辑更好点.

print("Lua版本: " .. _VERSION) -- lua5.4

--- 定义点到线段的最短距离, 用于寻路计算
--- (x,y) 代表点坐标系, [(x1,y2),(x2,y2)] 代表线坐标系
--- 这里假定坐标点(x,y) 设置P, 线段 (x1,y1) 设置A, (x2,y2) 设置B
function point2line(x, y, x1, y1, x2, y2)
    -- 计算叉乘, 得出当中的向量积
    -- x2-x1 空间几何意义就是得出从 x1->x2 的向量, 也就是 A->B
    -- x-x1 空间几何意义就是得出从 x1->x 的向量, 也就是 A->P
    local cross = (x2 - x1) * (x - x1) + (y2 - y1) * (y - y1)

    -- 如果向量积小于等于0代表 A->B 和 P 直接垂直, 也就是之前演示的图片情况(a)
    -- 这也就代表 A->B 和 A->P 之间夹角在90°内
    if cross <= 0 then
        -- 直接得出投影 C 的距离, 返回 CP 投影距离的 r 值, 得出 r <= 0, 返回 A->P
        local cp = (x - x1) * (x - x1) + (y - y1) * (y - y1)
        return math.sqrt(cp)
    end

    -- 当 A->B, A->P 大于 0 代表了 P 和 AB 无法形成垂直关系, 也就是夹角超过90°
    -- 需要计算投影 C 是投射到 B->P 图片情况(b) 还是 A->P图片情况(c)
    local degree = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)

    -- 如果 A->P 大于 A->B, 说明了投影 C 的坐标是处于 B->P 之间投影夹角
    if cross >= degree then
        local bp = (x - x2) * (x - x2) + (y - y2) * (y - y2)
        return math.sqrt(bp)
    end

    -- 最后就是计算 ap 的投影距离
    local r = cross / degree
    local xp = x1 + (x2 - x1) * r
    local yp = y1 + (y2 - y1) * r
    local ap = (x - xp) * (x - xp) + (yp - y1) * (yp - y1)
    return math.sqrt(ap)
end



-- 测试样例
-- Point(5,4), Line[ (2,1),(9,8),... ]
local point = { x = 5, y = 4 }
local lines = setmetatable({}, {
    __tostring = function(owner)
        local fmt = {}
        for i, v in pairs(owner) do
            local b = v[1]
            local e = v[2]
            local s = string.format("Line - %d[ (%d,%d)->(%d,%d) ]", i, b.x, b.y, e.x, e.y)
            table.insert(fmt, s)
        end
        return table.concat(fmt, '\r\n')
    end
})

-- 先追加预定义的路径, 这里随机生成十条路径
for _ = 1, 10 do
    local line = {}

    local line_begin_x = math.random(1, 20)
    local line_begin_y = math.random(1, 20)
    local line_begin = { x = line_begin_x, y = line_begin_y }
    table.insert(line, line_begin)

    local line_end_x = math.random(1, 20)
    local line_end_y = math.random(1, 20)
    local line_end = { x = line_end_x, y = line_end_y }
    table.insert(line, line_end)

    table.insert(lines, line)
end

-- 打印所有路径坐标信息
print("终点位置:", string.format("Point( %d,%d )", point.x, point.y))
print("定义线路:", lines)
print(string.rep("=", 64))


-- 遍历多条预定义路径
local short_r, short_i, short_abs_r
for i, path in pairs(lines) do
    local ab_begin = path[1] -- 注意Lua下标从0开始
    local ab_end = path[2]
    local r = point2line(point.x, point.y, ab_begin.x, ab_begin.y, ab_end.x, ab_end.y)
    local abs_r = math.abs(r) -- 绝对值, 用于比较选取最短的路径对象
    print("路径: ", i, ",得出最短距离: ", r, ",绝对值: ", abs_r)

    -- 比较选中最短路径
    if not short_abs_r or abs_r < short_abs_r then
        short_i = i
        short_r = r
        short_abs_r = abs_r
    end
end

-- 最后得出命中的路径对象
print("目前选出终点最短路径: ", short_i, ", 路径距离: ", short_r)
print(string.format("玩家需要复位到路径(%d), 复位路径后直接移动到 A|B 坐标点, 最后通过 A|B 移动到终点P", short_i))


-- todo: 玩家坐标这时候需要反向设计, 求出 玩家P -> Line 的最短距离
-- todo: 玩家P 需要先移动到命中路径的投影点, 再通过路径移动到最靠近终点P

这里还有个 C# 版本用来给客户端同步寻路结果:

using System;


class HelloWorld {
    
    public static double Point2Line(double x, double y, double x1, double y1, double x2, double y2){
        double cross = (x2 - x1) * (x - x1) + (y2 - y1) * (y - y1);
        if (cross <= 0) return Math.Sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
        
        double d2 = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
        if (cross >= d2) return Math.Sqrt((x - x2) * (x - x2) + (y - y2) * (y - y2));
         
        double r = cross / d2;
        double px = x1 + (x2 - x1) * r;
        double py = y1 + (y2 - y1) * r;
        return Math.Sqrt((x - px) * (x - px) + (py - y1) * (py - y1));
    }    
        

  static void Main() {
    double l1 = Point2Line(5,4,2,1,9,8);
    double l2 = Point2Line(5,4,1,3,6,9);
    Console.WriteLine(string.Format("Line1: {0}, Line2: {1}",l1,l2));
  }
}

这只适用于比较简单的寻路逻辑, 没有采用多点路径和碰撞这方面功能; 但是可以应用于比较简单 AI寻路 方面, 最后的结果如下:

寻路结果

通过预定义 AI 的寻路路径, 当玩家经过其寻路路径的时候触发出游戏战斗状态.