本教程旨在解决Java网格路径查找算法中常见的无限循环问题。原始实现因未能有效管理路径探索状态和防止路径重复访问节点而陷入死循环。我们将介绍一种基于深度优先搜索（DFS）的优化方案，通过维护所有潜在路径集合，确保全面探索，并引入路径内节点重复访问检测机制，从而实现稳定、高效的路径查找。
1. 问题背景与分析
在开发基于网格的路径查找应用时，开发者常会遇到算法陷入无限循环的困境。典型的表现是，寻路实体（例如示例中的“星鱼”）在网格的某个区域反复来回移动，却始终无法到达目标点。这种现象通常源于路径查找逻辑的缺陷，未能正确处理节点访问和路径探索。
原始代码中，findPath 方法试图通过一个单一的 Queue
- 贪婪且不完整的探索：在遍历当前点的四个方向时，一旦找到一个非墙壁的有效移动点，它会立即更新 start 点并 break 掉方向循环。这意味着算法只沿着第一个发现的有效方向前进，而放弃了探索其他潜在的分支路径。
- 缺乏路径内循环检测：算法没有机制来判断即将移动到的点是否已经在当前路径中。这使得寻路实体可以在已走过的节点之间反复移动，形成死循环（例如，从A到B，再从B回到A，然后又从A到B）。
- 状态管理不足：仅维护一个 tmpPath 和 path 队列，未能有效保存和管理所有待探索的路径分支，导致算法在遇到死胡同或需要回溯时无法继续。
这些问题共同导致了路径查找算法无法正确探索整个网格，最终陷入无限循环。
立即学习“Java免费学习笔记（深入）”；
2. 路径查找算法基础
路径查找算法的核心目标是从起点出发，系统地探索所有可能的路径，直到找到目标点。常用的策略包括：
- 深度优先搜索 (DFS)：优先沿着一条路径深入探索，直到达到终点或死胡同，然后回溯并尝试其他路径。
- 广度优先搜索 (BFS)：逐层探索，首先访问所有邻近节点，然后是它们的邻近节点，以此类推。BFS能找到最短路径。
本教程的优化方案将基于深度优先搜索的思想进行改进，以解决原始代码的无限循环问题。
3. 优化方案：基于深度优先搜索的路径探索
为了解决上述问题，我们需要对路径查找算法进行根本性改造，使其能够：
- 维护并探索所有可能的路径分支。
- 避免在同一条路径中重复访问节点，从而防止循环。
以下是改进后的 findPath 方法，它采用了一种基于深度优先搜索（DFS）的策略：
3.1 核心思想
不再维护一个单一的当前路径，而是维护一个包含所有正在探索的潜在路径的集合（Deque
3.2 示例代码
为了使代码可运行，我们假设 Rectangle 和 Point 类具有以下基本结构和方法。在实际项目中，这些类通常来自 java.awt 或自定义实现。
import java.awt.Color;
import java.awt.Point; // 使用 java.awt.Point
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Objects;
import java.util.Queue;
// 假设 Rectangle 类具有 getFill() 方法
// 实际项目中可能来自 GUI 库
class GridRectangle {
private Color fill;
public GridRectangle(Color fill) { this.fill = fill; }
public Color getFill() { return fill; }
}
// 假设 Point 类（或其扩展）具有 isValid 方法
// java.awt.Point 默认没有 isValid，这里为演示添加
// 并且为了在集合中正确比较，需要重写 equals 和 hashCode
class GridPoint extends Point {
public GridPoint(int x, int y) {
super(x, y);
}
// 检查点是否在网格范围内
public boolean isValid(int gridWidth, int gridHeight) {
return x >= 0 && x < gridWidth && y >= 0 && y < gridHeight;
}
// 重写 equals 和 hashCode 以确保在集合中正确比较
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
GridPoint gridPoint = (GridPoint) o;
return x == gridPoint.x && y == gridPoint.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
@Override
public String toString() {
return "(" + x + ", " + y + ")";
}
}
public class PathfindingSolver {
public Queue findPath(GridRectangle[][] matrix, GridPoint destPoint) {
// 定义移动方向：右、下、左、上
var dir = new ArrayList();
dir.add(new GridPoint(1, 0)); // right
dir.add(new GridPoint(0, 1)); // down
dir.add(new GridPoint(-1, 0)); // left
dir.add(new GridPoint(0, -1)); // up
GridPoint start = new GridPoint(0, 0); // 起始点固定为 (0,0)
// 存储所有待探索的路径。每个Deque代表一条从起点到当前点的完整路径。
// 使用 Deque 作为 Queue 的实现，因为它提供了 removeLast() 来实现 DFS
Deque> availablePaths = new ArrayDeque<>();
// 初始化：将起始点作为第一条路径加入待探索集合
Deque initialPath = new ArrayDeque<>();
initialPath.add(start);
availablePaths.add(initialPath);
// 当还有待探索的路径时，继续循环
while (!availablePaths.isEmpty()) {
// 从集合中取出一条路径进行探索。
// removeLast() 实现深度优先搜索 (DFS)。
// 若使用 removeFirst() 则实现广度优先搜索 (BFS)。
Deque currentPath = availablePaths.removeLast();
GridPoint currentPoint = currentPath.getLast(); // 获取当前路径的末端点
// 检查当前路径是否已到达目标点
if (currentPoint.equals(destPoint)) {
return currentPath; // 找到路径，返回该路径
}
// 探索当前点的所有可能移动方向
for (int dc = 0; dc < dir.size(); dc++) {
GridPoint move = new GridPoint(currentPoint.x + dir.get(dc).x, currentPoint.y + dir.get(dc).y);
// 1. 检查移动点是否在网格范围内
if (!move.isValid(matrix[0].length, matrix.length)) {
continue;
}
// 2. 关键改进：检查移动点是否已经被当前路径访问过，防止循环
if (currentPath.contains(move)) {
continue;
}
// 3 
