解决网格路径查找算法中的无限循环：深度优先搜索改进指南

private Queue<Point> findPath(Rectangle[][] matrix, Point destPoint) {
    Point move = null;
    var dir = new ArrayList<Point>();
    dir.add(new Point(1, 0)); // right
    dir.add(new Point(0, 1)); // down
    dir.add(new Point(-1, 0)); // left
    dir.add(new Point(0, -1)); // up

    Point start = new Point(0, 0); // 当前探索的起点
    var tmpPath = new ArrayDeque<Point>(); // 临时存储下一个要探索的点
    var path = new ArrayDeque<Point>(); // 存储当前已走过的路径片段
    tmpPath.add(new Point(0, 0));

    while (!tmpPath.isEmpty()) {
        for (int dc = 0; dc < dir.size(); dc++) { // 遍历所有方向
            move = new Point(start.x() + dir.get(dc).x(), start.y() + dir.get(dc).y());
            if (!move.isValid(matrix[0].length, matrix.length)) {
                continue; // 边界检查
            }
            if (matrix[move.y()][move.x()].getFill() != Color.MAGENTA) { // 如果不是墙壁
                start = move; // 立即更新当前探索点为新移动点
                tmpPath.add(move); // 将新移动点加入临时队列
                path.add(tmpPath.poll()); // 将tmpPath中“旧”的起点移出并加入到path中
                System.out.println(path.peek());
                if (path.getLast().equals(destPoint)) { // 检查path的最后一个点是否是目的地
                    path.poll(); // 移除路径的第一个点（0,0）
                    return path;
                }
                break; // *** 缺陷1：找到第一个有效移动后立即跳出，停止探索其他方向 ***
            }
        }
    }
    return null;
}

import java.awt.Color; // 假设Color类存在
import java.awt.Point; // 假设Point类存在，且包含x(), y()方法
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Queue;

// 假设Rectangle类和isValid方法存在
// 示例：
class Rectangle {
    private Color fill;
    public Rectangle(Color c) { this.fill = c; }
    public Color getFill() { return fill; }
}

// 假设Point类已扩展，包含isValid方法
class Point {
    int x, y;
    public Point(int x, int y) { this.x = x; this.y = y; }
    public int x() { return x; }
    public int y() { return y; }

    // 假设isValid方法检查点是否在网格边界内
    public boolean isValid(int gridWidth, int gridHeight) {
        return x >= 0 && x < gridWidth && y >= 0 && y < gridHeight;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point point = (Point) o;
        return x == point.x && y == point.y;
    }

    @Override
    public int hashCode() {
        return java.util.Objects.hash(x, y);
    }

    @Override
    public String toString() {
        return "(" + x + ", " + y + ")";
    }
}

public class PathFinder {

    public Deque<Point> findPath(Rectangle[][] matrix, Point destPoint) {
        Point startPoint = new Point(0, 0); // 起始点固定为(0,0)

        // 定义移动方向：右、下、左、上
        var dir = new ArrayList<Point>();
        dir.add(new Point(1, 0));  // 右
        dir.add(new Point(0, 1));  // 下
        dir.add(new Point(-1, 0)); // 左
        dir.add(new Point(0, -1)); // 上

        // availablePaths 存储所有待探索的完整路径。
        // 每个内部的 Deque<Point> 代表一条从起点到当前点的路径。
        Deque<Deque<Point>> availablePaths = new ArrayDeque<>();

        // 初始化：将包含起始点的路径加入待探索集合
        Deque<Point> initialPath = new ArrayDeque<>();
        initialPath.add(startPoint);
        availablePaths.add(initialPath);

        // 当仍有路径可以探索时循环
        while (!availablePaths.isEmpty()) {
            // 从 availablePaths 中取出一条路径进行探索。
            // removeLast() 实现深度优先搜索 (DFS)。
            // 如果使用 removeFirst() 则实现广度优先搜索 (BFS)。
            Deque<Point> currentPath = availablePaths.removeLast();

            // 获取当前路径的最后一个点，即当前探索位置
            Point currentPosition = currentPath.getLast();

            // 检查当前点是否为目的地
            if (currentPosition.equals(destPoint)) {
                return currentPath; // 找到路径，返回
            }

            // 探索当前位置的所有可能移动方向
            for (int dc = 0; dc < dir.size(); dc++) {
                Point nextMove = new Point(currentPosition.x() + dir.get(dc).x(), currentPosition.y() + dir.get(dc).y());

                // 边界检查
                if (!nextMove.isValid(matrix[0].length, matrix.length)) {
                    continue;
                }

                // *** 关键改进：防止路径自交叉 ***
                // 检查下一个移动点是否已在当前路径中，避免无限循环
                if (currentPath.contains(nextMove)) {
                    continue;
                }

                // 检查下一个移动点是否是墙壁 (Color.MAGENTA)
                if (matrix[nextMove.y()][nextMove.x()].getFill() != Color.MAGENTA) {
                    // 创建一条新路径，它是当前路径的副本，并添加新的移动点
                    Deque<Point> newPath = new ArrayDeque<>(currentPath);
                    newPath.add(nextMove);

                    // 将新路径加入待探索集合
                    availablePaths.add(newPath);
                    // 注意：这里不再使用 break，确保探索所有可能的方向
                }
            }
        }

        return null; // 如果所有路径都探索完毕仍未找到目的地，则返回null
    }
}