注意: 这里可以查看https://github.com/qiao/PathFinding.js各种寻路算法,并查看其在线演示.

A*(基础算法)

优点

• 简单，易于实现
• 对地图编辑器友好
• 特定方格的消耗/可通行性易于修改，当然重新加权的方格太多也会影响速度
• 从游戏地图位置容易映射到方格位置，坐标除以每个网格的边长即可

缺点

• 对于大型地图，方格属于内存密集型
• 通常需要对所得的路径进行路径平滑
• 由于粒度过细，路径规划的消耗可能较大
• 通常含有许多对称路径，增加了路径规划的成本。这一问题可以通过一些技术缓解

适合场景

• 策略游戏的策略搜索
• 方块格子游戏中的格子寻路

WayPoint()

此寻路算法设置的导航点必须满足"任何坐标都可以直接到达导航点".

优点

• 同样易于实现
• 如果能够提前预知改动（例如一扇门的开关），则同样易于修改
• 稀疏的表示使得存储和路径规划的消耗都较低

缺点

• 如果边过少，路径质量会受到影响；过多则会影响存储与路径规划的复杂度
• 需要手动放置节点才能得到较好的路径质量
• 玩家的位置映射到路点图的数据结构（localization）较为困难，玩家被碰撞出边时可能难以定位
• 未储存明确的物理等底层状态空间表示信息，平滑路径时可能会导致角色卡在物理对象上
• 如果改动无法被预知，修改的过程较为复杂，需要验证附近的所有路点是否因为地形修改导致可被连接。（例如角色可以任意地进行墙体破坏）

适合场景

• 塔防怪物行进路径
• AI巡逻路线

涉及算法

• 起止点不在导航点上时, 需获取起止导航点, 需要最临近算法, 如果不用最临近算法就要遍历所有导航点并计算距离.
• A*算法计算最佳路径

NavMesh(NAV导航网格寻路)

优点

• 多边形可以比网格更精确地表示游戏世界，因为它可以处理非网格对齐的地图
• 多边形精确表示有利于路径的平滑
• 路径规划非常快且不影响质量
• 不像网格一样消耗内存

缺点

• 实现过于复杂，不过有非常不错的开源实现
• 需要使用特殊的几何算法，在某些特殊情况（如平行线）可能导致失败。这更增加了实现的难度
• 对导航网格的改动可能难以实现且消耗较大
• 如果实现不好，localization可能比较复杂。优秀的实现可能会借助额外的数据结构，如gird进行映射

适合场景

• 游戏场景的怪物寻路
• 动态规避障碍

涉及算法

• 有序顶点组成的凸多边形.
• 判断一个坐标点在凸多边形内部: 射线法(交叉计数法), 坐标点引出一条射线,如果与多边形相交数量为奇数个则在内部, 偶数个则在外部. 详解:坐标点水平向右做一个射线, 计算其与每一条边的交点, 如果有交点, 且交点数是奇数, 则在内部. 注意需要考虑在边上的情况.
• 凸包算法, 用于生成凸多边形算法

目前寻路算法大致可分为四类

• 对 A的改进，例如 Relaxed A(RA)和 A Bucket
• 利用格子特点的算法，例如 Jump Point Search(JPS)和 SubGoal Graphs
• 预先生成任意两点第一个路点的压缩数据库，例如 SRC
• 基于节点优先级的算法，例如 Contraction Hierarchy(CH)

扩展阅读

PathFinding.js在线演示
游戏A星寻路算法教程详解 a星寻路算法路径优化
A*算法简介
深入理解游戏中寻路算法
NAV导航网格寻路
游戏中寻路与导航的初步实践
WayPoint寻路
Bresenham 直线算法

最后更新于  2024-03-04 18:02:03  并被添加「」标签，已有 592 位童鞋阅读过。

本站使用「署名 4.0 国际」创作共享协议，可自由转载、引用，但需署名作者且注明文章出处