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

A*(基础算法)

优点

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

缺点

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

适合场景

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

WayPoint()

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

优点

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

缺点

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

适合场景

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

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 直线算法

最后更新于  2023-01-13 10:55:02  并被添加「」标签，已有 373 位童鞋阅读过。

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