蜂巢型六边形A星寻路算法unity完整流程

作者：云影 Unity官方平台2020-07-27

一、需求

我们需要一个这样的函数：给定六边形网格的一个起点和一个终点，函数能够返回从起点到终点的通路经过哪些六边形。

适应场景：战棋类游戏，常常因为六边形网格更好的美术表现及游戏性选择蜂巢型的网格作为游戏内寻路的基础，而一些moba类游戏也常常因为NaviMesh网格型寻路消耗过大、服务端客户端网格算法不同（例如unity内置的网格寻路功能，服务端就没办法使用）等原因，最终选择A星寻路算法来制作功能（节点需要足够小，且寻路结果需要平滑优化）。

二、算法讲解

1. 搜索区域

节点：就是单个六边形，整个搜索区域需要被节点铺满。

首先需要明确的一点是，正方形网格和六边形的网格没有本质上的区别，只不过正方形可以行走的方向是4个，六边形是6个，这个在程序上的区别主要体现在一个节点的相邻节点集上，正方形的相邻节点在4个以内，六边形的相邻节点在6个以内，不过对于算法理解没有影响。

2. 开始搜索

开启列表：需要考虑的节点都会被放到开启列表中，刚开始的时候开启列表只有起点一个节点，然后根据节点的相邻节点集，会逐渐把附近的节点都加到开启列表中。

关闭列表：所有不在考虑的节点的集合。

六边形网格，红色为不可通过点

我们以节点11为起点，节点8为终点。

先把节点11加入开启列表，再通过节点11找到他的相邻节点，也就是节点1、3、12、14、15、10，把他们放入开启列表，并为他们设置父节点为节点11。将节点11放入关闭列表。

3. 估值

上面讲的是如何扩大搜索范围，而如果想要获得一条最优路径，那么必然是有一个估值方式，在A星算法中，我们为每个节点都做估值，估算值F = G + H:

G：从起点，沿着产生的路径，移动到网格上指定方格的移动耗费。在这里，我们认为相邻的六边形，移动消耗是1，例如，从节点11移动到3，移动消耗就是1.

H：从网格上那个方格移动到终点B的预估移动耗费。这经常被称为启发式的，可因为它只是个猜测。这个H值的估算方式有很多种，我们暂时使用两个节点的直线距离，对应unity的实现就是Vector3.Distance(curHex.transform.position, tarHex.transform.position)。

F = G + H估值

很容易得到，节点3的估值是最低，估值最低则代表最优先。

4. 继续搜索

找到F值最低的节点3作为当前结点，我们把节点3从开启列表中删除，然后添加到关闭列表中。

找到节点3的所有相邻节点，跳过那些已经在关闭列表中、不可通过的点（节点2、4）。

如果该节点已经在开启列表中，则计算从当前节点到这个节点的G估算值为多少，例如节点12已经在开启列表中了，从当前节点（也就是节点3）到节点12的G估算值等于节点3当前G估值 + 1（从3走到12），也就是2。如果这个G估值比原先的G估值大，则什么都不做；如果比原来的G估值小，则把该节点的父节点改为当前节点，并将该节点的G估值设为更小的那个值。

再从开启列表中选取F值最低的那个，设为当前节点，重复以上过程。

在图中示例的六边形网格中，节点3的相邻网格有1、12、16，节点1和12已经在开启列表中了，节点3的G估值1+从3走到12的移动消耗1 = 2，2>节点12的当前G估值，所以什么都不做（节点1类似）。现在开启列表中有1、10、15、14、12、16，计算F估值，节点16最小，所以再以节点16为当前节点，重复以上过程。最终得到路径11、3、16、13、8。

三、在unity内的具体实现

1. 使用6个cube（每个cube旋转角差距60度）拼成一个六边形，用这些六边形拼出来一块网格，为方便调试，以数字依次命名。

2. 复制以下代码，命名为Hexagon，附加到每个六边形上：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class Hexagon : MonoBehaviour
{
Hexagon father = null;
public Hexagon[] neighbors = new Hexagon[6];
public bool passFlag = true;
float gValue = 999f;
float hValue = 999f;
public Material redMat;
public Material greenMat;
void Start()
{
}
public void reset()
{
}
public Hexagon[] getNeighborList()
{
return neighbors;
}
public void setFatherHexagon(Hexagon f)
{
father = f;
}
public Hexagon getFatherHexagon()
{
return father;
}
public void setCanPass(bool f)
{
passFlag = f;
}
public bool canPass()
{
return passFlag;
}
public float computeGValue(Hexagon hex)
{
return 1f;
}
public void setgValue(float v)
{
gValue = v;
}
public float getgValue()
{
return gValue;
}
public void sethValue(float v)
{
hValue = v;
}
public float gethValue()
{
return hValue;
}
public float computeHValue(Hexagon hex)
{
return Vector3.Distance(transform.position, hex.transform.position);
}
}

复制代码

3. 为所有六边形添加一个空的父gameobject，命名为HexManager，为HexManager添加以下代码：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;
public class HexManager : MonoBehaviour {
Dictionary name2Hex = new Dictionary();
static List openList = new List();
static List closeList = new List();
void Start()
{
foreach (Transform child in transform)
{
name2Hex.Add(child.name, child.GetComponent());
}
}
public Hexagon GetHexByName(string i)
{
Hexagon v = new Hexagon();
name2Hex.TryGetValue(i, out v);
return v;
}
public Dictionary GetAllHex()
{
return name2Hex;
}
public static List searchRoute(Hexagon thisHexagon, Hexagon targetHexagon)
{
Hexagon nowHexagon = thisHexagon;
nowHexagon.reset();
openList.Add(nowHexagon);
bool finded = false;
while (!finded)
{
openList.Remove(nowHexagon);//将当前节点从openList中移除
closeList.Add(nowHexagon);//将当前节点添加到关闭列表中
Hexagon[] neighbors = nowHexagon.getNeighborList();//获取当前六边形的相邻六边形
//print("当前相邻节点数----" + neighbors.size());
foreach (Hexagon neighbor in neighbors)
{
if (neighbor == null) continue;
if (neighbor == targetHexagon)
{//找到目标节点
//System.out.println("找到目标点");
finded = true;
neighbor.setFatherHexagon(nowHexagon);
}
if (closeList.Contains(neighbor) || !neighbor.canPass())
{//在关闭列表里
//print("无法通过或者已在关闭列表");
continue;
}
if (openList.Contains(neighbor))
{//该节点已经在开启列表里
//print("已在开启列表，判断是否更改父节点");
float assueGValue = neighbor.computeGValue(nowHexagon) + nowHexagon.getgValue();//计算假设从当前节点进入，该节点的g估值
if (assueGValue < neighbor.getgValue())
{//假设的g估值小于于原来的g估值
openList.Remove(neighbor);//重新排序该节点在openList的位置
neighbor.setgValue(assueGValue);//从新设置g估值
openList.Add(neighbor);//从新排序openList。
}
}
else
{//没有在开启列表里
//print("不在开启列表，添加");
neighbor.sethValue(neighbor.computeHValue(targetHexagon));//计算好他的h估值
neighbor.setgValue(neighbor.computeGValue(nowHexagon) + nowHexagon.getgValue());//计算该节点的g估值（到当前节点的g估值加上当前节点的g估值）
openList.Add(neighbor);//添加到开启列表里
neighbor.setFatherHexagon(nowHexagon);//将当前节点设置为该节点的父节点
}
}
if (openList.Count <= 0)
{
//print("无法到达该目标");
break;
}
else
{
nowHexagon = openList[0];//得到f估值最低的节点设置为当前节点
}
}
openList.Clear();
closeList.Clear();
List route = new List();
if (finded)
{//找到后将路线存入路线集合
Hexagon hex = targetHexagon;
while (hex != thisHexagon)
{
route.Add(hex);//将节点添加到路径列表里
Hexagon fatherHex = hex.getFatherHexagon();//从目标节点开始搜寻父节点就是所要的路线
hex = fatherHex;
}
route.Add(hex);
}
route.Reverse();
return route;
// resetMap();
}
//通过无阻挡寻路确定两个六边形的距离
public static int GetRouteDis(Hexagon thisHexagon, Hexagon targetHexagon)
{
Hexagon nowHexagon = thisHexagon;
nowHexagon.reset();
openList.Add(nowHexagon);
bool finded = false;
while (!finded)
{
openList.Remove(nowHexagon);//将当前节点从openList中移除
closeList.Add(nowHexagon);//将当前节点添加到关闭列表中
Hexagon[] neighbors = nowHexagon.getNeighborList();//获取当前六边形的相邻六边形
//print("当前相邻节点数----" + neighbors.size());
foreach (Hexagon neighbor in neighbors)
{
if (neighbor == null) continue;
if (neighbor == targetHexagon)
{//找到目标节点
//System.out.println("找到目标点");
finded = true;
neighbor.setFatherHexagon(nowHexagon);
}
if (closeList.Contains(neighbor))
{//在关闭列表里
//System.out.println("无法通过或者已在关闭列表");
continue;
}
if (openList.Contains(neighbor))
{//该节点已经在开启列表里
//System.out.println("已在开启列表，判断是否更改父节点");
float assueGValue = neighbor.computeGValue(nowHexagon) + nowHexagon.getgValue();//计算假设从当前节点进入，该节点的g估值
if (assueGValue < neighbor.getgValue())
{//假设的g估值小于于原来的g估值
openList.Remove(neighbor);//重新排序该节点在openList的位置
neighbor.setgValue(assueGValue);//从新设置g估值
openList.Add(neighbor);//从新排序openList。
}
}
else
{//没有在开启列表里
//System.out.println("不在开启列表，添加");
neighbor.sethValue(neighbor.computeHValue(targetHexagon));//计算好他的h估值
neighbor.setgValue(neighbor.computeGValue(nowHexagon) + nowHexagon.getgValue());//计算该节点的g估值（到当前节点的g估值加上当前节点的g估值）
openList.Add(neighbor);//添加到开启列表里
neighbor.setFatherHexagon(nowHexagon);//将当前节点设置为该节点的父节点
}
}
if (openList.Count <= 0)
{
//System.out.println("无法到达该目标");
break;
}
else
{
nowHexagon = openList[0];//得到f估值最低的节点设置为当前节点
}
}
openList.Clear();
closeList.Clear();
List route = new List();
if (finded)
{//找到后将路线存入路线集合
Hexagon hex = targetHexagon;
while (hex != thisHexagon)
{
route.Add(hex);//将节点添加到路径列表里
Hexagon fatherHex = hex.getFatherHexagon();//从目标节点开始搜寻父节点就是所要的路线
hex = fatherHex;
}
route.Add(hex);
}
return route.Count - 1;
}
}