寻路（二维数组）

Question

我想找到从一点到另一点的路径。黑框是障碍物，我们不能去，蓝框是起点，黄框是终点，我想从起点到终点。我在书中的算法的帮助下编写了这段代码，实际上现在我想让它动态化，这意味着 n x n 矩阵。所以我想要指导我应该采取什么步骤才能使它运行能够用于 n x n 矩阵。我还想问一下，这是在这种情况下还是其他情况下找到最短路径的最佳解决方案？

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {

        boolean[][] boolMaze = new boolean[][] {
                { true, true, true, true, true },
                { false, true, false, true, true },
                { true, false, true, true, true },
                { false, true, true, false, false },
                { false, false, false, false, false },
                { true, true, true, true, true },
                { false, true, false, true, true },
                { true, false, true, true, true },
                { false, true, true, false, false },
                { false, false, false, false, false },
                { true, true, true, true, true },
                { false, true, false, true, true },
                { true, false, true, true, true },
                { false, true, true, false, false },
                { false, false, false, false, false },
                { true, true, true, true, true },
                { false, true, false, true, true },
                { true, false, true, true, true },
                { false, true, true, false, false },
                { false, false, false, false, false } };
        Maze maze = new Maze(boolMaze);
        List<Maze.Cell> path = maze.findPath(0, 0, 3, 2);
        System.out.println("found path in maze: " + path);
    }
}
    class Maze {
        private final boolean[][] maze;

        public Maze(boolean[][] maze) {
            this.maze = maze;
        }

        public int height() {
            return maze.length;
        }

        public int width() {
            return maze[0].length;
        }

    }

    public List<Cell> findPath(int xStart, int yStart, int xGoal, int yGoal) {
        LinkedList<Cell> path = new LinkedList(); // use a linked list, since we
                                                    // don't know how many
                                                    // elements it will contain
                                                    // straight away..
        path.add(new Cell(xStart, yStart));
        HashSet<Cell> visited = new HashSet(); // this set will store all
                                                // visited cells. Make sure to
                                                // add any cell you looked at.
                                                // Don't work with cells which
                                                // you have visited previously,
                                                // by checking
                                                // visited.contains(cell).
        visited.add(path.getFirst());

        // ///////////////////////////

        if (xStart - 1 >= 0 && maze[xStart][yStart - 1]) {
            Cell cell = new Cell(xStart, yStart - 1);
            return path;
        }

        else if (yStart + 1 < height() && maze[xStart][yStart + 1]) {
            Cell cell = new Cell(xStart, yStart + 1);
            return path;
        }

        else if (xStart + 1 < width() && maze[xStart + 1][yStart]) {
            Cell cell = new Cell(xStart + 1, yStart);
            return path;
        }

        else if (xStart - 1 >= 0 && maze[xStart - 1][yStart]) {
            Cell cell = new Cell(xStart - 1, yStart);
            return path;
        }

        // //////////////////////////
        // use your path finding algorithm here (note that you can use getLast()
        // and getFirst() on your list.
    }

    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (!(o instanceof Cell))
            return false;

        Cell cell = (Cell) o;

        if (x != cell.x)
            return false;
        return y == cell.y;

    }

    @Override
    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }

    class Cell implements Comparable<Cell> {
        Cell(int x, int y) {
            this.x = x;
            this.y = y;
        }

        int x;
        int y;

        @Override
        public int compareTo(Cell o) {

            if (o.equals(x) && o.equals(y))
                return 0;

            return 1;
        }
    }

Answer 1

您的问题分为两部分。首先是使解决方案适用于 NxM 迷宫，其次是改进样式和性能。

首先，您可以使用查找和替换快速修复两件事。

用 int 替换每次出现的 Integer。 Integers 是必须由垃圾收集器创建和销毁的实际对象。并且每次使用它们进行计算时都必须进行转换，这严重影响了性能。
您的布尔数组也是如此。使用 boolean[][] 代替

请同时删除方向数组。这是毫无意义的，因为 directions[i] == i 总是 true。您可以一直使用 int 变量。枚举甚至会有更好的解决方案，但我们不要在这里引入太多新概念..

此代码：

for(int i = 0; i < directions.length; i++) {
     Cell newCell = findCell(current,directions[i]);
     //code..
 }

会变成这样的代码：

 for(int i = 0; i < 4; i++) {
     Cell newCell = findCell(current,i);
     //code..
 }

那么你应该开始使用迷宫作为对象，因为它已经是一个class。您必须从所有变量和方法中删除 static 关键字，因为它们将来会在私有成员上工作新建一个名为Main的Class，在新添加的main方法中调用如下代码：

boolean[][] boolMaze = new boolean[][]{/*initialize array*/};
Maze maze = new Maze(boolMaze);
List<Cell> path = maze.findPath(0, 0, 3, 2);
System.out.println("found path in maze: "+path)

所以我们需要两个新东西。 Maze 和方法 findPath.

的正确构造函数

class Maze 应该包含私有（可能是最终）成员 boolean[][] 迷宫并且构造函数应该设置它。

public Maze(boolean[][] maze) {
    this.maze = maze;
}

同时删除变量 WIDTH 和 HEIGHT，因为它们不一定反映数组的大小。 java 的好处是，数组会记住它们的大小。添加 public 辅助函数以便快速访问：

public int height() {
    return maze.length;
}

public int width() {
    return maze[0].length; // assuming that maze.length is always > 0
}

findPath 方法应该创建一个 List<Cell> 和 return 它：

public List<Cell> findPath(int xStart, int yStart, int xGoal, int yGoal) {
    LinkedList<Cell> path = new LinkedList(); //use a linked list, since we don't know how many elements it will contain straight away..
    path.add(new Cell(xStart, yStart));
    HashSet<Cell> visited = new HashSet(); //this set will store all visited cells. Make sure to add any cell you looked at. Don't work with cells which you have visited previously, by checking visited.contains(cell).
    visited.add(path.getFirst());
    //use your path finding algorithm here (note that you can use getLast() and getFirst() on your list.
    return path;
}

您还可以删除单元格中的父属性。并且要比较两个 Cell 是否相同，不要使用比较。该方法用于对对象进行排序。实施：

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Cell)) return false;

    Cell cell = (Cell) o;

    if (x != cell.x) return false;
    return y == cell.y;

}

@Override
public int hashCode() {
    int result = x;
    result = 31 * result + y;
    return result;
}

在Cell。检查两个单元格是否相同时，调用 cell.equals(otherCell)

进一步改进

你实际上实现了一个洪水填充算法，这意味着你只是天真地填充整个平面，直到你找到你的目标。解决迷宫的标准算法总是试图坚持一面墙。请注意，这仅在您的入口点和目标位于迷宫的边缘时才有效（通常是这种情况）使用 this 站点以了解有关该算法的更多信息您可能希望保留您的寻路算法，并且仅在您的起点和目标靠近边缘时才使用改进的算法。

寻路（二维数组）

Path Finding (2D Array)

java

path-finding

进一步改进