思路
步骤一：选择一个节点
步骤二：选择该节点的其中一个邻接节点进行访问
步骤三：选择该邻接节点的邻接节点进行访问，重复步骤一，步骤二，
步骤四：当该节点没有邻接节点，返回上一个节点，搜寻邻接节点进行访问，重复步骤一，二，三，否则重复步骤四
步骤五：所有节点都已访问过，即结束访问
简单说：选择一个节点一直访问下去，直到该节点没有邻接节点，再访问上一级节点，直到所有节点都已经访问
图示讲解
原始图
步骤一：
选择一个节点1访问
步骤二：
选择节点1的邻接节点访问2(默认从左到右，从上到下)
步骤三：
选择邻接节点2的邻接节点4进行访问
步骤四：
发现节点4没有邻接节点，返回上一级查找有没有访问的节点，找到节点3没有，即访问节点3
节点3访问后，发现没有邻接节点，最后发现节点5没有访问，即访问节点5，所有节点都已访问，即结束访问
核心代码
/// <summary>
/// 广度优先算法/BFS算法
/// </summary>
/// <param name="origin">开始节点</param>
/// <param name="target">目标节点</param>
/// <param name="passNodeList">路径列表</param>
public static void Search(Node origin, Node target, ref List<Node> passNodeList)
{
//清除地图数据
passNodeList.Clear();
for(int i = 1; i < mapLength; i++)
{
for(int j = 0; j < mapWidth; j++)
{
//是否访问过
if(!map[i, j].bVisit)
{
//没访问
BFSSearch(map[i, j], origin, target, ref passNodeList);
}
}
}
//保存路径
Node currentNode = map[target.X, target.Y];
while(currentNode.Value != origin.Value)
{
passNodeList.Add(currentNode);
currentNode = currentNode.parent;
}
passNodeList.Add(origin);
}
/// <summary>
/// 根据当前节点，检查自己的邻接节点
/// </summary>
/// <param name="currentNode">当前节点</param>
/// <param name="origiNode">开始节点</param>
/// <param name="target">目标节点</param>
/// <param name="passNodeList">路径列表</param>
private static void BFSSearch(Node currentNode, Node origiNode, Node target, ref List<Node> passNodeList)
{
//将当前节点加入到队列中
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(currentNode);
//当前节点
while(queue.Count > 0)
{
//获取邻接节点
Node head = queue.Dequeue();
//检查邻接节点(上下左右)
List<Node> neighbors = getNeighbor(head);
for(int i = 0; i < neighbors.Count; i++)
{
//没有访问才&&不是不可走的路径点
if(!neighbors[i].bVisit && neighbors[i].Value != NODE_BLOCK)
{
//标记节点为已经访问
neighbors[i].bVisit = true;
neighbors[i].parent = head;
queue.Enqueue(neighbors[i]);
//是目标节点，return
if(neighbors[i].Value == target.Value)
{
return;
}
}
}
}
}
/// <summary>
/// 搜索邻接节点
/// </summary>
/// <param name="currentNode">当前节点</param>
/// <returns></returns>
private static List<Node> getNeighbor(Node currentNode)
{
List<Node> nodes = new List<Node>();
int x = currentNode.X;
int y = currentNode.Y;
if(x - 1 >= 0)
{
//左边
nodes.Add(map[x - 1, y]);
}
if(x + 1 >= 0 && x + 1 < mapLength)
{
//右边
nodes.Add(map[x + 1, y]);
}
if(y - 1 >= 0)
{
//上边
nodes.Add(map[x, y - 1]);
}
if(y + 1 >= 0 && y + 1 < mapWidth)
{
//下边
nodes.Add(map[x, y + 1]);
}
return nodes;
}