MeteorCat

AStar寻路 这种是游戏服务端当中最常见的碰撞检测游戏寻路方式, 日常AI机器人也十分依赖寻路策略. 静态可以采用 AStar, 而动态则需要 Dstar 的 Dijkstra 处理运算寻路, 移动端游戏尽可能采用静态寻路处理 游戏客户端大部分实现这些插件让其更加易用( Unity的NavMesh ), 但是服务端则缺失这部分功能也就没办法在服务端模拟玩家行走路线从而同步. AStar寻路实际上是采用 网格(Gird) 的寻路计算, 具体原理就是先把整个地图分解成 Width * Height 多个格子, 然后通过网格周边连线来处理出最短路径, 同时支持标识障碍物绕过计算, 这种过程就是将 平面栅格化. 大部分寻路都是基于这种方式, 只是按照不同算法评估周边格子从而采样路径处理. 注: 在空间寻路当中必须要具有 方向 和 距离 才能形成正确的寻路路径(向量|矢量) 寻路方式按照不同方式计算寻路: 曼哈顿估价法(Manhattan Heuristic) 几何估价法(Euclidean Heuristic) 对角线估价法(Diagonal Heuristic) 对应三种寻路方式图示处理: 曼哈顿估价法 基于 四向移动(十字形位移) 的计算, 也就是只有 上下左右 方向, 这种四向计算性能消耗相对比较小但是只支持四向寻路: ---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.

最简单的游戏寻路实现 这种寻路方法是之前在游戏应用到相对简单的游戏寻路方法, 通过客户端设计编辑 (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, } ] 两点之间就能确定线段, 那么就可以转化成数学问题: 确定玩家的终点(x1,y1), 转化成 坐标系中求终点到多条线段的最小距离 数学运算, 反推出终点到哪条线段距离最短 现在已经确定好路径线段, 之后通过玩家起点(x2,y2)转化成 坐标系中求玩家点到选中线段的最小距离, 推出玩家启动选中路径最短距离 到这里已经确定好几段路径: 玩家终点应该走哪条预设路径最短线路: <point(x1,y1) -> line(x1,y1)>, 玩家起点到路径的最短线路: <point(x2,y2) -> line(x2,y2) > 最终线路组合: <point(x2,y2),玩家起点> -> <line(x2,y2),玩家距离最短距离> -> 走到端点 -> <point(x1,y2),路径端点到终点> 那么最后得出的路径就连接接起来就是这样: