在游戏开发的过程中,我们经常会需要处理一些地图的寻路AI,其中有不同的算法,会适用于不同的应用场景中。这里记录几种比较常用的寻路算法,便于日后用到的时候作为一个索引。
(1)A算法
A算法是我们用的最多的寻路算法了。它很好的解决了最优路径的问题。性能消耗比较大。
(2)B算法
B算法(Branch Star 分支寻路算法)适用于游戏中怪物的自动寻路,其效率远远超过A算法,经过测试,效率是普通A算法的几十上百倍。
(3)D算法
D算法是动态A(D-Star,Dynamic A),由静态A算法发展而来,Stentz(卡内及梅隆机器人中心)在1994和1995年两篇文章提出,主要用于机器人探路。最早用于火星探测器采用的寻路算法。 D是一种启发式的路径搜索算法,适合面对周围环境未知或者周围环境存在动态变化的场景。 特点:与A相反,A从起点到目标点进行搜索,而D是从目标点向起点进行搜索——反向传播,反向搜索。
游戏开发中常用的几种寻路算法
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 本文由 伯乐在线 - Janzou 翻译,之似 校稿。未经许可,禁止转载!英文出处:theory.stanford...
- 有限状态机: ①:最简单的有限状态机实现是在类似update的方法中调用switch方法,判断状态,调用不同的方法...