前言
半年前我写了一篇《十几种排序算法的可视化效果，快来看看！👀》，还是很有意思的。这篇文章中的内容还被张风捷特烈张老师收录进了FlutterUnit：《FlutterUnit 周边 | 收录排序算法可视化》。今天让我们再来做一个有关寻路算法的可视化效果吧！
效果图：
BFS算法 |
DFS算法 |
AStar算法 |
|
|
|
BestFS算法 |
Dijkstra算法 |
|
|
|
代码下载：https://www.alipan.com/s/3kvCHKTgaon
迷宫地图的绘制
迷宫地图的生成有很多很多方法，常见的有随机生成算法、递归分割算法、深度优先搜索算法等，都可以用于迷宫地图的生成。这次我们使用深度优先遍历+广度优先遍历+随机队列去制作迷宫地图，这样会让地图有更多的随机性。
定义迷宫地图的数据类及初始化方法：
定义BlockModel类：
class BlockModel{ int? rowSize; int? columnSize; int? startX; int? startY; int? endX; int? endY; int road = 1; //路 int wall = 0; //墙 //路径是否被访问过 List<List<bool>> visitedList = []; //迷宫地图 List<List<int>> blockList = []; //寻找到的正确路线 List<List<bool>> pathList = []; //方向 List<List<int>> direction = [ [-1, 0], [0, -1], [1, 0], [0, 1] ]; }
初始化基本的地图数据：
设置迷宫的起点和终点位置，并给所有行坐标为奇数且列坐标为奇数的区块设置为路。其余位置设置为墙。
BlockModel(int r, int c) { if (r % 2 == 0 || c % 2 == 0) { throw "地图行数和列数不能为偶数"; } rowSize = r; columnSize = c; startX = 1; startY = 0; endX = r - 2; endY = c - 1; blockList = []; visitedList = []; pathList = []; //初始化迷宫遍历的方向（上、左、右、下）顺序（迷宫趋势） //随机遍历顺序，提高迷宫生成的随机性（共12种可能性） List.generate(direction.length, (index) { int random = Random().nextInt(direction.length); List<int> temp = direction[random]; direction[random] = direction[index]; direction[index] = temp; }); List.generate(r, (i) { List<bool> tempVisited = []; List<int> tempMazeList = []; List<bool> tempPath = []; List.generate(c, (j) { //行和列为奇数都设置为路，否则设置为墙 if (i % 2 == 1 && j % 2 == 1) { tempMazeList.add(1); //设置为路 } else { tempMazeList.add(0); //设置为墙 } //初始化访问过的区块，现在所有都没有访问过 tempVisited.add(false); tempPath.add(false); }); visitedList.add(tempVisited); blockList.add(tempMazeList); pathList.add(tempPath); }); blockList[startX!][startY!] = 1; blockList[endX!][endY!] = 1; }
地图的生成
地图的创建需要一个随机队列的帮助，那让我们先来实现一个随机队列：
借助dart的LinkedList链表结合随机数来决定插入和移除元素的位置，从而实现随机队列。
class RandomQueue { LinkedList<Position> _queue = LinkedList<Position>(); RandomQueue() { _queue = LinkedList<Position>(); } void addRandomQueue(Position position) { if (Random().nextInt(100) < 50) { _queue.addFirst(position);// 插入到队列头部 } else { _queue.add(position);// 插入到队列尾部 } } ///返回随机队列中的一个元素 Position removeRandomQueue() { if (_queue.isEmpty) { throw "数组为空"; } else { if (Random().nextInt(100) < 50) { Position position = _queue.first; _queue.remove(position); return position; } else { Position position = _queue.last; _queue.remove(position); return position; } } } //返回随机队列元素数量 int getSize() { return _queue.length; } //判断随机队列是否为空 bool isEmpty() { return _queue.isEmpty; } }
创建地图：
使用随机队列去生成地图，从指定的起始位置开始，随机选择下一个要访问的位置（访问的方向在初始化BlockModel时已经随机打乱），并在访问时标记该区块已访问。通过这种方式，可以生成具有一定随机性的地图结构。
/// 创建地图并使用随机队列生成地图结构 void createMap(int startX, int startY) { RandomQueue randomQueue = RandomQueue(); // 创建一个随机队列实例 Position start = Position(startX, startY); // 创建起始位置 randomQueue.addRandomQueue(start); // 将起始位置加入随机队列 model.visitedList[startX][startY] = true; // 标记起始位置为已访问 // 使用随机队列生成地图 while (randomQueue.getSize() != 0) { Position position = randomQueue.removeRandomQueue(); // 移除队列中的一个位置 // 生成四个方向的新位置 List.generate(4, (i) { int newX = position.x! + model.direction[i][0] * 2; int newY = position.y! + model.direction[i][1] * 2; // 检查新位置是否在地图内且未被访问过 if (model.isInMap(newX, newY) && !model.visitedList[newX][newY]) { // 将新位置加入随机队列，并记录为已访问 randomQueue .addRandomQueue(Position(newX, newY, prePosition: position)); model.visitedList[newX][newY] = true; // 设置新位置与当前位置之间的路径或道路 setWithRoad(position.x! + model.direction[i][0], position.y! + model.direction[i][1]); } }); } // 把visitedList全部设置为没有访问 model.visitedList = model.visitedList .map((innerList) => innerList.map((element) => false).toList()) .toList(); }
flutter布局实现
布局非常简单，通过Column结合Row，通过两层List.generate遍历地图数据，即可渲染完布局：
Widget board() { mapHeight = screenWidth.floor(); cellSize = screenWidth.floor() ~/ rowSize; List<Row> rowList = []; List.generate(model.blockList.length, (i) { List<Container> columnList = []; List.generate(model.blockList[i].length, (j) { columnList.add(Container( width: cellSize.toDouble(), height: cellSize.toDouble(), decoration: BoxDecoration( color: getBoxColor(i, j), ), )); }); rowList.add(Row( mainAxisAlignment: MainAxisAlignment.center, children: columnList, )); }); return SizedBox( width: mapHeight.toDouble(), height: mapHeight.toDouble(), child: Column( mainAxisAlignment: MainAxisAlignment.center, children: rowList, ), ); }
算法的实现
辅助函数
为了让算法更好的融入我们的地图寻路需求，还需要几个辅助函数：
///设置该区块为路 void setWithRoad(int x, int y) { setState(() { model.blockList[x][y] = model.road; }); } ///设置该区块为正确的路径 void setModelWithPath(int x, int y, bool isPath) { setState(() { if (model.isInMap(x, y)) { model.pathList[x][y] = isPath; } }); }
接下来让我们正式开始算法的实现！
算法的详细细节就不过多展开了，想要学习的朋友可以自行搜索，相关资料很多
BFS（广度优先搜索）
|
广度优先搜索是图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，因此得名。一般可以用它做什么呢？一个最直观经典的例子就是走迷宫，我们从起点开始，找出到终点的最短路程，很多最短路径算法就是基于广度优先的思想成立的。
/// 广度优先搜索（BFS）寻找路径 Future<bool> searchPathBFS(int startX, int startY) async { // 创建队列并添加起始位置 Queue<List<int>> queue = Queue(); queue.add([startX, startY]); // 初始化访问标记、路径记录和父节点记录 model.visitedList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); model.pathList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); List<List<List<int>>> parent = List.generate(model.columnSize!, (_) => List.generate(model.rowSize!, (_) => [-1, -1])); // 开始广度优先搜索 while (queue.isNotEmpty) { List<int> current = queue.removeFirst(); int x = current[0]; int y = current[1]; // 检查当前位置是否越界 if (!model.isInMap(x, y)) { throw "坐标越界"; } // 如果已经访问过当前位置，则继续下一个循环 if (model.visitedList[x][y]) continue; model.visitedList[x][y] = true; // 标记当前位置为已访问 setState(() {}); // 检查是否到达终点 if (x == model.endX && y == model.endY) { print("找到路径了"); // 回溯路径并记录到 path 列表中 List<List<int>> path = []; int curX = x; int curY = y; while (curX != -1 && curY != -1) { path.add([curX, curY]); List<int> prev = parent[curX][curY]; curX = prev[0]; curY = prev[1]; } // 清空原路径记录，并设置新的路径记录为找到的路径 model.pathList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); for (var point in path) { setModelWithPath(point[0], point[1], true); // 设置路径标记 await Future.delayed(const Duration( milliseconds: 50)); } return true; // 返回找到路径的结果 } // 遍历当前位置的四个方向 for (int i = 0; i < 4; i++) { int newX = x + model.direction[i][0]; int newY = y + model.direction[i][1]; // 检查新位置是否在地图范围内，并且是可通过的道路，并且未访问过 if (model.isInMap(newX, newY) && model.blockList[newX][newY] == model.road && !model.visitedList[newX][newY]) { queue.add([newX, newY]); // 将新位置添加到队列中 parent[newX][newY] = [x, y]; // 记录新位置的父节点 setState(() {}); await Future.delayed(const Duration( milliseconds: 50)); // 等待一段时间，以便显示搜索过程（如果在 Flutter 中） } } } return false; // 如果队列为空仍未找到路径，则返回 false }
DFS（深度优先搜索）
DFS 是一种递归或栈（堆栈）数据结构的算法，用于图的遍历。
从一个起始节点开始，尽可能深入图的分支，直到无法继续深入，然后回溯并探索其他分支。
通过标记已访问的节点来避免重复访问。
DFS最有意思的就是回溯这一步，回溯就是在搜索尝试过程中寻找问题的解，当发现不满足条件时，就回溯，尝试别的路径。强调的是此路不通，另寻他路。先打标记，记录路径；然后下一层，回到上一层，清除标记。
/// 深度优先搜索（DFS）寻找路径 Future<bool> searchPathDFS(int startX, int startY) async { // 初始化访问标记、路径记录和父节点记录 model.visitedList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); model.pathList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); List<List<List<int>>> parent = List.generate(model.columnSize!, (_) => List.generate(model.rowSize!, (_) => [-1, -1])); // 定义DFS递归函数 Future<bool> dfs(int x, int y) async { // 检查当前位置是否越界 if (!model.isInMap(x, y)) { throw "坐标越界"; } // 如果已经访问过当前位置，则返回 false if (model.visitedList[x][y]) return false; model.visitedList[x][y] = true; // 标记当前位置为已访问 setState(() {}); // 更新界面状态（如果在 Flutter 中） // 检查是否到达终点 if (x == model.endX && y == model.endY) { print("找到路径了"); // 回溯路径并记录到 path 列表中 List<List<int>> path = []; int curX = x; int curY = y; while (curX != -1 && curY != -1) { path.add([curX, curY]); List<int> prev = parent[curX][curY]; curX = prev[0]; curY = prev[1]; } // 清空原路径记录，并设置新的路径记录为找到的路径 model.pathList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); for (var point in path) { setModelWithPath(point[0], point[1], true); // 设置路径标记 await Future.delayed(const Duration(milliseconds: 50)); } return true; // 返回找到路径的结果 } // 遍历当前位置的四个方向 for (int i = 0; i < 4; i++) { int newX = x + model.direction[i][0]; int newY = y + model.direction[i][1]; // 检查新位置是否在地图范围内，并且是可通过的道路，并且未访问过 if (model.isInMap(newX, newY) && model.blockList[newX][newY] == model.road && !model.visitedList[newX][newY]) { parent[newX][newY] = [x, y]; // 记录新位置的父节点 setState(() {}); // 更新界面状态（如果在 Flutter 中） await Future.delayed(const Duration(milliseconds: 50)); if (await dfs(newX, newY)) { return true; // 如果找到路径，则返回 true } } } return false; // 如果当前位置无法继续搜索，则返回 false } // 调用DFS函数并返回最终结果 return await dfs(startX, startY); }
AStar算法（A*）
A*（AStar)算法是一种静态路网中求解最短路最有效的方法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。
- 和Dijkstra一样，AStar能用于搜索最短路径。
- 和BFS一样，AStar能用启发式函数引导它自己。
左图为Astar算法效果图，右图为Dijkstra算法效果图。Astar算法与Dijkstra算法的效果差不多，但Astar算法访问的节点数明显比Dijkstra算法少得多，代表其速度更快，运行时间更短。
（图片来源于网络）
实现这个算法我们需要编写一个Node类：
Node 类表示了AStar搜索算法中的节点。节点在A算法中的作用是记录搜索过程中的状态信息，包括当前位置的坐标、从起始节点到当前节点的路径长度（g值）、以及从当前节点到目标节点的估计距离（启发值h）。
class Node { int x, y, g; // 节点的坐标和当前路径长度g值 double h; // 启发值h Node? parent; // 父节点 Node(this.x, this.y, this.g, this.h, [this.parent]); double get f => g + h; // 计算节点的总代价f值 } class PriorityQueue { final List<Node> _queue = []; // 优先队列使用的列表 bool get isEmpty => _queue.isEmpty; // 判断队列是否为空 void add(Node node) { _queue.add(node); // 添加节点到队列 _queue.sort((a, b) => a.f.compareTo(b.f)); // 根据f值排序，f值小的在前面 } Node removeFirst() { return _queue.removeAt(0); // 移除并返回队列中f值最小的节点 } }
编写AStar算法：
节点的估值算法我们使用曼哈顿距离用于估值，曼哈顿距离是平面上两点之间的距离，定义为从一个点沿着网格状的路径到另一个点的距离，沿路径只能朝着水平或垂直方向移动，而不能斜向移动。就是横向和纵向的距离之和。
具体计算方法如下：
heuristic(x,y)=∣x−model.endX∣+∣y−model.endY∣
/// AStar算法 Future<bool> searchPathAStar(int startX, int startY) async { // 创建优先队列作为开放列表 PriorityQueue openList = PriorityQueue(); openList.add(Node(startX, startY, 0, heuristic(startX, startY))); // 初始化路径记录和访问标记 model.visitedList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); model.pathList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); while (!openList.isEmpty) { // 从开放列表中移除f值最小的节点作为当前节点 Node current = openList.removeFirst(); int x = current.x; int y = current.y; // 检查当前节点是否超出地图范围 if (!model.isInMap(x, y)) { throw "坐标越界"; } // 如果当前节点已经访问过，则继续下一个节点 if (model.visitedList[x][y]) continue; model.visitedList[x][y] = true; setState(() {}); // 检查是否到达终点 if (x == model.endX && y == model.endY) { print("找到路径了"); // 回溯路径 List<List<int>> path = []; Node? curNode = current; while (curNode != null) { path.add([curNode.x, curNode.y]); curNode = curNode.parent; } // 将路径标记到pathList中，并显示路径动画 model.pathList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); for (var point in path) { setModelWithPath(point[0], point[1], true); await Future.delayed(const Duration(milliseconds: 50)); } return true; } // 遍历当前节点的四个方向 for (int i = 0; i < 4; i++) { int newX = x + model.direction[i][0]; int newY = y + model.direction[i][1]; // 如果新节点在地图范围内且是可通行的空地且未被访问过 if (model.isInMap(newX, newY) && model.blockList[newX][newY] == model.road && !model.visitedList[newX][newY]) { int g = current.g + 1; // 更新新节点的g值 double h = heuristic(newX, newY); // 计算新节点的启发值h openList.add(Node(newX, newY, g, h, current)); // 将新节点加入开放列表 setState(() {}); await Future.delayed(const Duration(milliseconds: 50)); // 延迟显示效果 } } } return false; // 开放列表为空，未找到路径，搜索失败 } // 估价函数（曼哈顿距离） double heuristic(int x, int y) { return ((x - model.endX!).abs() + (y - model.endY!).abs()).toDouble(); }
BestFS算法（最佳优先算法）
主要运用贪心算法的思想，优先搜索离终点近的点。
/// BestFS算法 Future<bool> searchPathBestFS(int startX, int startY) async { // 初始化优先队列、起始节点和父节点数组 PriorityQueue priorityQueue = PriorityQueue(); Node startNode = Node(startX, startY, 0, euclideanDistance(startX, startY, model.endX!, model.endY!)); priorityQueue.add(startNode); // 初始化 visitedList、pathList 和 parent // 初始化路径记录和访问标记 model.visitedList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); model.pathList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); List<List<int>> parent = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, -1)); while (!priorityQueue.isEmpty) { Node currentNode = priorityQueue.removeFirst(); int x = currentNode.x; int y = currentNode.y; // 如果当前节点已访问过，则跳过 if (model.visitedList[x][y]) continue; model.visitedList[x][y] = true; setState(() {}); // 检查是否到达终点 if (x == model.endX && y == model.endY) { print("找到路径了"); // 回溯路径 List<List<int>> path = []; int curX = x; int curY = y; while (curX != -1 && curY != -1) { path.add([curX, curY]); int prevX = parent[curX][curY] ~/ model.rowSize!; int prevY = parent[curX][curY] % model.rowSize!; curX = prevX; curY = prevY; print("curX:$curX,curY:$curY"); // 防止出现死循环，检查是否回溯到起点 if (curX == startX && curY == startY) { break; } } // path = path.reversed.toList(); // 绘制路径到界面上 model.pathList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); for (var point in path) { setModelWithPath(point[0], point[1], true); await Future.delayed(const Duration(milliseconds: 50)); } return true; // 找到路径并绘制完成，返回true } // 探索当前节点的邻居节点 for (int i = 0; i < 4; i++) { int newX = x + model.direction[i][0]; int newY = y + model.direction[i][1]; // 如果邻居节点在地图范围内且是可通行的道路且未访问过 if (model.isInMap(newX, newY) && model.blockList[newX][newY] == model.road && !model.visitedList[newX][newY]) { Node newNode = Node(newX, newY, currentNode.g + 1, euclideanDistance(newX, newY, model.endX!, model.endY!)); priorityQueue.add(newNode); parent[newX][newY] = x * model.rowSize! + y; // 记录父节点 setState(() {}); await Future.delayed(const Duration(milliseconds: 50)); } } } return false; // 未找到路径，返回false }
Dijkstra算法
最初我学习到这个算法是在计算机网络中，关于网络路由的部分。它非常适合用于找到从起始节点到所有其他节点的最短路径。不过，它仅适用于非负权重的图，因为它依赖于贪婪策略来选择当前最短路径。
/// Dijkstra算法 Future<bool> searchPathDijkstra(int startX, int startY) async { // 初始化优先队列、距离数组和父节点数组 PriorityQueue priorityQueue = PriorityQueue(); List<List<int>> distance = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, -1)); List<List<int>> parent = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, -1)); model.visitedList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); model.pathList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); // 将起始节点加入优先队列并初始化距离 priorityQueue.add(Node(startX, startY, 0, 0.0)); distance[startX][startY] = 0; while (!priorityQueue.isEmpty) { // 从优先队列中取出当前节点 Node currentNode = priorityQueue.removeFirst(); int x = currentNode.x; int y = currentNode.y; int currentDistance = currentNode.g; // 如果当前节点已访问过，则跳过 if (model.visitedList[x][y]) continue; model.visitedList[x][y] = true; setState(() {}); // 检查是否到达终点 if (x == model.endX && y == model.endY) { print("找到路径了"); // 回溯路径 List<List<int>> path = []; int curX = x; int curY = y; while (curX != -1 && curY != -1) { path.add([curX, curY]); int prevX = parent[curX][curY] ~/ model.rowSize!; int prevY = parent[curX][curY] % model.rowSize!; curX = prevX; curY = prevY; print("curX:$curX,curY:$curY"); // 防止出现死循环，检查是否回溯到起点 if (curX == startX && curY == startY) { break; } } // path = path.reversed.toList(); // 绘制路径到界面上 model.pathList = List.generate( model.columnSize!, (_) => List.filled(model.rowSize!, false)); for (var point in path) { setModelWithPath(point[0], point[1], true); await Future.delayed(const Duration(milliseconds: 50)); } return true; // 找到路径并绘制完成，返回true } // 探索当前节点的邻居节点 for (int i = 0; i < 4; i++) { int newX = x + model.direction[i][0]; int newY = y + model.direction[i][1]; // 如果邻居节点在地图范围内且是可通行的道路且未访问过 if (model.isInMap(newX, newY) && model.blockList[newX][newY] == model.road && !model.visitedList[newX][newY]) { int newDistance = currentDistance + 1; // 更新距离 // 如果是第一次访问或找到更短的路径，则更新距离和父节点，并加入优先队列 if (distance[newX][newY] == -1 || newDistance < distance[newX][newY]) { distance[newX][newY] = newDistance; Node newNode = Node(newX, newY, newDistance, 0.0); // Dijkstra没有启发式函数，h设为0 priorityQueue.add(newNode); parent[newX][newY] = x * model.rowSize! + y; // 记录父节点 setState(() {}); await Future.delayed(const Duration(milliseconds: 50)); } } } } return false; // 未找到路径，返回false }
