首页 > Unity3D引擎 > 进阶系列 > A*寻路算法在Unity中的简单应用
2016
08-18

A*寻路算法在Unity中的简单应用

前言

在使用Unity开发游戏项目时,经常会遇到一些角色的导航需求,然而Unity提供给我们的NavMesh+NavMeshAgent并不能很好帮我们实现,且寻路网格的烘焙,以及在导航过程中寻路网格的检测,都是非常消耗性能的,因此在很多企业项目中,会自己写一下高效的寻路算法来完成需求,其中有一种就是A*寻路算法。A*寻路算法是一种启发式算法,从所有可以行走的路径中找出估量代价最小的,递归每步这样的操作,最终到达目标点。

  • A*寻路算法的估量代价
    在A*算法中核心的寻路依据就是估量代价,在A*中通常用 F 表示。

    F = G + H
    其中G表示当前点到起始点的估量代价,H表示当前点到终点的代价。

A*寻路算法在Unity中的简单应用 - 第1张  | u3d8技术分享

FGH示意图

因此从当前格子周边的八个格子中找到下一步所走的格子,依据F值,当F值相同时随机选择。

当然在寻路过程中,会有障碍,不能通过,通过可以行走的格子走到终点。下图中绿色为起点,红色为终点,蓝色是障碍,浅蓝边框是参与计算的格子,A*就是通过这样的一系列计算完成的最优寻路。

A*寻路算法在Unity中的简单应用 - 第2张  | u3d8技术分享

A*行走路线
下面我写了一个小例子,方便大家学习。
  • 简单效果
    A*寻路算法在Unity中的简单应用 - 第3张  | u3d8技术分享

    简单效果
  • 首先需要创建一个格子类Grid

  • 然后主逻辑AStar类

  • 最后是参考预设体方块的简单实现

  • 多障碍效果图
    A*寻路算法在Unity中的简单应用 - 第4张  | u3d8技术分享

    多障碍效果图
  • 遍历流程监测
    其实A*遍历的格子还是蛮多的,因为曼哈顿计算的H值是不考虑障碍物的,所以会有很多格子的F值会很小,但不一定此时很小的F值格子就是要走的路径,最终的最优路径是通过,终点格子反推回来的,就如代码中GenerateResult递归方法所示,为了方便大家理解,我做了一个小动画,方便大家对A*的理解。(粉色是此时F值最小的格子,蓝色是最小F值格子周边正在遍历的格子,黄色格子是从未设置父物体,第一次被遍历的格子)

    A*寻路算法在Unity中的简单应用 - 第5张  | u3d8技术分享

    遍历流程监测
    A*寻路算法在Unity中的简单应用 - 第6张  | u3d8技术分享

    慢放版

    结束语

    A*只是游戏算法中的凤毛麟角,其中的逻辑也相对简单,所以想要提升编码质量,想要写出高效的游戏逻辑,还需要更多的算法学习。还是那个道理,编程 = 数据结构 + 算法,不带班的这段时间我会尽量分享一些东西给大家,同仁们加油。本文项目下载链接: https://pan.baidu.com/s/1hrVwBcw 密码: cfas

最后编辑:
作者:网虫虫
网虫虫
分享是一种快乐; 分享是一种美德; 分享是一种幸福!

留下一个回复

你的email不会被公开。