Java - 无法摆脱这种递归方法

Question

我正在尝试实现深度优先搜索算法(我的代码可能很糟糕，我很抱歉)。现在我想使其成为一种递归方法，但一旦满足最终条件，我似乎就无法摆脱它。您在方法中看到的第一个 if 条件应该脱离该方法。当我调试项目时，它到达了 return 语句，然后立即跳转到方法的末尾。但它并没有停止整个事情，而是返回到 while(!allNeighboursVisited) 循环并继续无限循环。

我试图自己解决这个问题，但没有成功，并开始在网络上搜索，但我找不到任何解决我的问题的方法。

编辑:决定在我的 github 上分享该项目的链接，供大家尝试一下:https://github.com/Equiphract/Maze

编辑2:更新了代码；我把它拼凑在一起，所以请不要指望有什么好看的:)

这是递归方法:

public void depthFirstSearch(int x, int y, Tile[][] maze) {
    // Return method after every Tile is visited.
    if (this.visitedCounter == maze.length * maze[0].length) {
        this.stack.clear();
        return;
    }

    Tile currentTile = maze[x][y];
    Random r = new Random();
    int neighbourAmount = currentTile.getNeighbourAmount();
    boolean allNeighboursVisited = false;
    int stopCounter = 0;

    // If it is a new Tile, mark it as visited
    if (!currentTile.isVisited()) {
        currentTile.setVisited(true);
        this.visitedCounter++;
        stack.add(currentTile);
    }

    // Check if neighbours are not yet visited and "visit" one of them.
    while (!allNeighboursVisited) {
        int random;
        do {
            random = r.nextInt(neighbourAmount);
        } while (this.excludeList.contains(random));

        Tile neighbour = currentTile.getNeighbours().get(random);
        if (!neighbour.isVisited()) {
            if (neighbour.getX() == currentTile.getX() - 1) {
                currentTile.getWall(4).setOpen(true);
                neighbour.getWall(2).setOpen(true);
            } else if (neighbour.getX() == currentTile.getX() + 1) {
                currentTile.getWall(2).setOpen(true);
                neighbour.getWall(4).setOpen(true);
            } else if (neighbour.getY() == currentTile.getY() - 1) {
                currentTile.getWall(1).setOpen(true);
                neighbour.getWall(3).setOpen(true);
            } else if (neighbour.getY() == currentTile.getY() + 1) {
                currentTile.getWall(3).setOpen(true);
                neighbour.getWall(1).setOpen(true);
            }
            this.excludeList.clear();
            depthFirstSearch(neighbour.getX(), neighbour.getY(), maze);
            if (this.visitedCounter == maze.length * maze[0].length) {
                this.stack.clear();
                return;
            }
        } else {
            this.excludeList.add(random);
            stopCounter++;
        }

        if (stopCounter == neighbourAmount) {
            allNeighboursVisited = true;
        }
    }

    // If every neighbour has already been visited, go back one Tile.
    if (!this.stack.isEmpty()) {
        this.stack.remove(this.stack.size() - 1);
        if (!this.stack.isEmpty()) {
            Tile backtrackTile = this.stack.get(this.stack.size() - 1);
            this.excludeList.clear();
            depthFirstSearch(backtrackTile.getX(), backtrackTile.getY(), maze);
            if (this.visitedCounter == maze.length * 3) {
                this.stack.clear();
                return;
            }
        }
        this.excludeList.clear();
    }
}

你知道吗，这是平铺对象(很抱歉在短时间内进行了大量编辑):

public class Tile {
    private ArrayList<Wall> walls;
    private ArrayList<Tile> neighbours;
    private int x;
    private int y;
    private boolean visited;

    /*
     * Constructor of the Tile class.
     */
    public Tile(int x, int y) {
        this.walls = new ArrayList<Wall>();
        this.neighbours = new ArrayList<Tile>();

        this.walls.add(new Wall(1));
        this.walls.add(new Wall(2));
        this.walls.add(new Wall(3));
        this.walls.add(new Wall(4));

        this.x = x;
        this.y = y;
        this.visited = false;
    }

    /*
     * Returns the ArrayList walls.
     */
    public ArrayList<Wall> getWalls() {
        return walls;
    }

    /*
     * Returns the value of visited.
     */
    public boolean isVisited() {
        return visited;
    }

    /*
     * Sets the value of visited to a specified value.
     * 
     * @param visited a boolean value
     */
    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    /*
     * Returns a wall with the specified position.
     * 
     * @param position the position of the wall
     */
    public Wall getWall(int position) {
        for(Wall w : this.walls) {
            if(w.getPosition() == position) {
                return w;
            }
        }
        return null;
    }

    public int getNeighbourAmount() {
        return this.neighbours.size();
    }

    public ArrayList<Tile> getNeighbours(){
        return this.neighbours;
    }


    /*
     * Adds a Tile to the ArrayList neighbours-
     * 
     * @param t a Tile
     */
    public void addNeighbour(Tile t) {
        this.neighbours.add(t);
    }

    /**
     * @return the x
     */
    public int getX() {
        return x;
    }

    /**
     * @return the y
     */
    public int getY() {
        return y;
    }
}

Answer 1

好吧，我想我找到了问题的解决方案。它远非完美，需要大量优化，也许你们中的一个人想要这样做并将其发布在这里^^。

我的主要错误是每次递归调用该方法后没有添加返回，这导致了无限循环。

这是我的解决方案:

public void depthFirstSearch(int x, int y, Tile[][] maze) {
    // Return method after every Tile is visited.
    if (this.visitedCounter == maze.length * maze[0].length) {
        this.stack.clear();
        return;
    }

    Tile currentTile = maze[x][y];
    Random r = new Random();
    int neighbourAmount = currentTile.getNeighbourAmount();
    boolean allNeighboursVisited = false;
    int stopCounter = 0;

    // If it is a new Tile, mark it as visited
    if (!currentTile.isVisited()) {
        currentTile.setVisited(true);
        this.visitedCounter++;
        stack.add(currentTile);
    }

    // Check if neighbours are not yet visited and "visit" one of them.
    while (!allNeighboursVisited) {
        int random;
        do {
            random = r.nextInt(neighbourAmount);
        } while (this.excludeList.contains(random));

        Tile neighbour = currentTile.getNeighbours().get(random);
        if (!neighbour.isVisited()) {
            if (neighbour.getX() == currentTile.getX() - 1) {
                currentTile.getWall(4).setOpen(true);
                neighbour.getWall(2).setOpen(true);
            } else if (neighbour.getX() == currentTile.getX() + 1) {
                currentTile.getWall(2).setOpen(true);
                neighbour.getWall(4).setOpen(true);
            } else if (neighbour.getY() == currentTile.getY() - 1) {
                currentTile.getWall(1).setOpen(true);
                neighbour.getWall(3).setOpen(true);
            } else if (neighbour.getY() == currentTile.getY() + 1) {
                currentTile.getWall(3).setOpen(true);
                neighbour.getWall(1).setOpen(true);
            }
            this.excludeList.clear();
            depthFirstSearch(neighbour.getX(), neighbour.getY(), maze);
            return;
        } else {
            this.excludeList.add(random);
            stopCounter++;
        }

        if (stopCounter == neighbourAmount) {
            allNeighboursVisited = true;
        }
    }

    // If every neighbour has already been visited, go back one Tile.
    if (!this.stack.isEmpty()) {
        this.stack.remove(this.stack.size() - 1);
        if (!this.stack.isEmpty()) {
            Tile backtrackTile = this.stack.get(this.stack.size() - 1);
            this.excludeList.clear();
            depthFirstSearch(backtrackTile.getX(), backtrackTile.getY(), maze);
            return;
        }
        this.excludeList.clear();
    }
}