简介
当场景中有成千上万个寻路游戏单位需要到达同一目标点时，通过常用的A*算法进行寻路不再是合适的选择，因为每个寻路游戏单位都需要依据自身所在的位置，根据算法获得一条从自身位置寻路到目标点的路径，n个游戏单位进行寻路就需要执行n次算法，这是比较大的性能开销。而流场寻路的方式便可以很好的解决这一问题，通常用于RTS（即时战略）游戏中的群体寻路。
将场景分割为x * y个网格节点，当确认目标点时，流场寻路算法会依据目标点所在的网格，依次向周围获取邻节点，计算邻节点到当前节点的代价。代价大的节点指向代价小的节点便可以形成一个方向，而这些节点形成的方向，便是流场，如下图所示。
流场形成后，寻路游戏单位只需要根据自身所在的坐标位置，获得对应的网格节点，依据节点的方向进行移动最终便可以到达目标点。
网格节点
节点类除了节点索引对应的字段x、y之外，还包括表示代价的字段cost与fCost，以及形成流场的节点方向字段。cost为基础代价，场景中可能会有多种地形，例如水泥地、沼泽地等等，不同地形有不同的代价，本文暂不考虑不同地形的情况，假设所有节点所在的地形是相同的，只考虑节点是否为可行走区域，通过字段isWalkable表示，而fCost是指节点到目标节点的最终代价。
using UnityEngine;
public class FlowFieldPathFinding_GridNode
{
public int x;
public int y;
public int cost;
public int fCost;
public Vector3 direction;
public bool isWalkable;
public FlowFieldPathFinding_GridNode(int x, int y, bool isWalkable)
{
this.x = x;
this.y = y;
this.isWalkable = isWalkable;
cost = isWalkable ? 10 : int.MaxValue;
fCost = int.MaxValue;
}
}
x * y个网格节点形成最终的网格，将所有的网格节点存储到一个字典中，通过索引i * x + j获取对应的网格节点，i表示第几行，j表示第几列，假设通过Texture资产存储地图数据，字节为255表示为可行走区域，否则为障碍区域。
public class FlowFieldPathFinding_Grid
{
private readonly int x;
private readonly int y;
private readonly Dictionary<int, FlowFieldPathFinding_GridNode> nodesDic
= new Dictionary<int, FlowFieldPathFinding_GridNode>();
public FlowFieldPathFinding_Grid(int x, int y, bool[,] map)
{
this.x = x;
this.y = y;
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
{
int index = i * x + j;
nodesDic.Add(index, new FlowFieldPathFinding_GridNode(i, j, map[i, j]));
}
}
}
public FlowFieldPathFinding_Grid(int x, int y, Texture2D map)
{
this.x = x;
this.y = y;
byte[] bytes = map.GetRawTextureData();
if (bytes.Length != x * y)
throw new ArgumentOutOfRangeException();
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
{
int index = i * x + j;
nodesDic.Add(index, new FlowFieldPathFinding_GridNode(i, j, bytes[index] == 255));
}
}
}
}
算法思路
网格类需要提供设置目标节点的方法，设置目标节点时，将其放入一个队列中，当队列的数量大于0时，不断执行以下步骤：
- 出列，获得当前节点；
- 获取当前节点的邻节点；
- 遍历邻节点，计算邻节点到当前节点的基础代价；
- 邻节点到当前节点的基础代价加上当前节点的最终代价记为t，如果t小于邻节点的最终代价，设置邻节点的最终代价为t，并将其放入队列。
/// <summary>
/// 设置目标节点
/// </summary>
/// <param name="target"></param>
public void SetTarget(FlowFieldPathFinding_GridNode target)
{
foreach (var node in nodesDic.Values)
{
node.cost = node.isWalkable ? 10 : int.MaxValue;
node.fCost = int.MaxValue;
}
target.cost = 0;
target.fCost = 0;
target.direction = Vector3.zero;
Queue<FlowFieldPathFinding_GridNode> queue
= new Queue<FlowFieldPathFinding_GridNode>();
queue.Enqueue(target);
while (queue.Count > 0)
{
FlowFieldPathFinding_GridNode currentNode = queue.Dequeue();
List<FlowFieldPathFinding_GridNode> neighbourNodes = GetNeighbouringNodes(currentNode);
for (int i = 0; i < neighbourNodes.Count; i++)
{
FlowFieldPathFinding_GridNode neighbourNode = neighbourNodes[i];
if (neighbourNode.cost == int.MaxValue) continue;
neighbourNode.cost = CalculateCost(neighbourNode, currentNode);
if (neighbourNode.cost + currentNode.fCost < neighbourNode.fCost)
{
neighbourNode.fCost = neighbourNode.cost + currentNode.fCost;
queue.Enqueue(neighbourNode);
}
}
}
}
搜索邻节点时有两种方式，四连通与八连通，前者是指向当前节点的上、下、左、右四个方向搜索邻节点，后者是指向当前节点的上、下、左、右、左上、右上、左下、右下八个方向搜索邻节点，多数情况下会使用八连通，本文也通过八连通的方式搜索邻节点。
/// <summary>
/// 获取指定节点的邻节点
/// </summary>
/// <param name="node">要获取邻节点的节点</param>
/// <returns>邻节点列表</returns>
public List<FlowFieldPathFinding_GridNode> GetNeighbouringNodes(FlowFieldPathFinding_GridNode node)
{
List<FlowFieldPathFinding_GridNode> neighbours = new List<FlowFieldPathFinding_GridNode>();
for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1; j++)
{
if (i == 0 && j == 0) continue;
int x = node.x + i;
int y = node.y + j;
if (x >= 0 && x < this.x && y >= 0 && y < this.y)
neighbours.Add(nodesDic[x * this.x + y]);
}
}
return neighbours;
}
计价方式
每向正上、下、左右方向走一步代价为1，根据勾股定理，每向斜方向走一步代价为根号2，近似1.414，而为了便于计算、节省性能，将正方向移动一步的代价记为10，斜方向移动一步的代价记为14，都取int整数。
//计算两个节点之间的代价
private int CalculateCost(FlowFieldPathFinding_GridNode node1, FlowFieldPathFinding_GridNode node2)
{
//取绝对值
int deltaX = node1.x - node2.x;
if (deltaX < 0) deltaX = -deltaX;
int deltaY = node1.y - node2.y;
if (deltaY < 0) deltaY = -deltaY;
int delta = deltaX - deltaY;
if (delta < 0) delta = -delta;
//每向上、下、左、右方向移动一个节点代价增加10
//每斜向移动一个节点代价增加14（勾股定理，精确来说是近似14.14~）
return 14 * (deltaX > deltaY ? deltaY : deltaX) + 10 * delta;
}
流场生成
设置目标节点计算各节点的代价后生成流场，遍历节点的邻节点，如果邻节点的最终代价小于当前节点的最终代价，那么当前节点的方向便是当前节点指向邻节点的方向。若出现代价相同的情况，需要考虑哪一个邻节点更加接近目标节点。
/// <summary>
/// 生成流场
/// </summary>
public void GenerateFlowField(FlowFieldPathFinding_GridNode target)
{
foreach (var node in nodesDic.Values)
{
List<FlowFieldPathFinding_GridNode> neighbourNodes = GetNeighbouringNodes(node);
int fCost = node.fCost;
FlowFieldPathFinding_GridNode temp = null;
for (int i = 0; i < neighbourNodes.Count; i++)
{
FlowFieldPathFinding_GridNode neighbourNode = neighbourNodes[i];
if (neighbourNode.fCost < fCost)
{
temp = neighbourNode;
fCost = neighbourNode.fCost;
node.direction = new Vector3(
neighbourNode.x - node.x, 0, neighbourNode.y - node.y);
}
else if (neighbourNode.fCost == fCost && temp != null)
{
if (CalculateCost(neighbourNode, target) < CalculateCost(temp, target))
{
temp = neighbourNode;
fCost = neighbourNode.fCost;
node.direction = new Vector3(
neighbourNode.x - node.x, 0, neighbourNode.y - node.y);
}
}
}
}
}
![[Springboot 源码系列] 浅析自动配置原理](https://img-blog.csdnimg.cn/img_convert/37bf2b9d40d2e7b2f620cf486815ff97.png)
