Unity2D-怪物AI启发式寻路算法（多目标，任意怪物大小，攻击范围）

完整工程下载在最后，先上效果：

红色方块为怪物体积大小为2x2个数1。
黄色为目标个数3。
白色点为障碍物。
怪物攻击范围2x2（自身大小）。
（这里为了方便观看，对算法每一步都进行了延时）

怪物大小1x1，怪物攻击范围1x1（自身大小）。
搜索过程中出现的红色路线就是路径，最后重新绘制的红色路径为对允许斜方向行走的路径。

实现步骤

1. 使用BFS（广度优先搜索）
   每次将当前搜索位置周围的位置加入到搜索队列。

周围位置是一个抽象的概念，如果加入为 上下左右，4个方向，那么每次就只会在4个方向进行挑选最优路径。

扩展一下：
Q：如果我需要进行任意角度斜着走呢？如果我需要45度角走呢？
A：那么只需要改变周围位置的定义即可。

添加优先条件

其实就是对BFS进行了优先级排序，每次选取目标都从我们计算出的最优值进行搜索。（这样搜索就是有目的性的）
即：BFS + 优先队列 = A*，（这差不多就是A*的核心思想了，优先队列只是一种选最优的方法）

如何找到最优路径

可以先假设我们已经找到了最优路径，那么最优路径有哪些性质？
对于每一个点我总是能到达，只是到达方式不同，导致到达使用的步数不同。因此我们可以在地图中记录到达这个点当前点使用的最小步数。如果有更小的步数的走法，我们就覆盖掉它。
通过记录最小步数来源的方向我们可以还原整条路径。（当然对于任意方向，如8方向同理）。

实现碰撞体积

实现体积的需要处理的其实只有两个部分。

• 物体的中心在哪？
• 物体的体积怎么表示
  当我们确定体积的表示方法后就简单了：
  我们只需要在搜索过程中使用对每个体积单位进行碰撞检查就可以！

如何动态搜索多个目标

1. 一种最简单的方法就是搜索多次，每次对不同的目标进行搜索
   这种方法的弊端很明显，就是随着目标的增多，搜索次数会不断增大。
   而且在第一个目标的搜索中我们已经知道了很多地方的最短来源，而搜索第二个目标的时候却需要重新搜索，这实在是一种浪费。

顶部的演示图就是使用这种方法。切换到多目标同时搜索很容易。

2. 同时对多个目标进行搜索
   每次搜索都将多个目标的距离进行计算对比，并且只走最短的那条路。
   这种方式的优点就很明显，可以对很多目标进行搜索，并且快速选出最短的那个。

下面是使用同时搜索多个目标，并且只找最近目标的路径。

演示时使用的配置信息：

项目完整演示包：
https://download.csdn.net/download/qq_41709801/86911269