문제

I have a maze generating algorithm working with depth-first search.
It first generates a raw maze which looks like this:
raw maze
Then it creates the maze using this algorithm: http://www.mazeworks.com/mazegen/mazetut/index.html
The result looks like this:
result
The red pixel marks the goal, the green one the start.
It gets stuck at the goal and jumps back and forth until it thinks it finished.
Maze Generator source:

public Maze generate(int width, int height) {
    Maze maze = getRawMaze(width, height);

    List<Point> cellStack = new LinkedList<Point>();
    int totalAirCells = maze.getTotalAirCells();
    Point currentCell = maze.getRandomAirCell(ran);
    maze.setCellTypeAt(currentCell, Maze.CellType.START);       
    int visitedCells = 1;

    while(visitedCells<totalAirCells) {
        Point[] unvisitedNeighbors = getUnvisitedNeighbors(maze, currentCell);
        if(unvisitedNeighbors.length!=0) {
            System.out.println("Go Foward");
            Point newCell = unvisitedNeighbors[ran.nextInt(unvisitedNeighbors.length)];
            maze.connect(newCell, currentCell);
            cellStack.add(currentCell);
            currentCell = newCell;
            visitedCells++;
        }else {
            System.out.println("Go Back");
            Point recentCell = cellStack.get(cellStack.size()-1);
            cellStack.remove(cellStack.size()-1);
            currentCell = recentCell;
        }
    }

    maze.setCellTypeAt(currentCell, Maze.CellType.GOAL);

    return maze;
}

public Point[] getUnvisitedNeighbors(Maze maze, Point p) {
    List<Point> unvisitedNeighbors = new ArrayList<Point>();
    Point[] neighbors = maze.getNeighbors(p);
    for(Point n : neighbors) {
        if(maze.getSurroundingWalls(n)==4)unvisitedNeighbors.add(n);
    }
    return unvisitedNeighbors.toArray(new Point[unvisitedNeighbors.size()]);
}

additional source:

public int getSurroundingWalls(Point p) {
    if(getCellTypeAt(p)==CellType.AIR) {
        int walls = 0;
        if(getCellTypeAt(new Point(p.x+1, p.y))==CellType.WALL)walls++;
        if(getCellTypeAt(new Point(p.x-1, p.y))==CellType.WALL)walls++;
        if(getCellTypeAt(new Point(p.x, p.y+1))==CellType.WALL)walls++;
        if(getCellTypeAt(new Point(p.x+1, p.y-1))==CellType.WALL)walls++;
        return walls;
    }else return -1;
}

public Point[] getNeighbors(Point p) {
    Point[] neighbors = new Point[4];
    neighbors[0] = new Point(p.x+2, p.y);
    neighbors[1] = new Point(p.x-2, p.y);
    neighbors[2] = new Point(p.x, p.y+2);
    neighbors[3] = new Point(p.x, p.y-2);
    return neighbors;
}

public void connect(Point a, Point b) {
    if((a.x==b.x-2)&&(a.y==b.y))setCellTypeAt(new Point(a.x+1, a.y), CellType.AIR);
    else if((a.x==b.x+2)&&(a.y==b.y))setCellTypeAt(new Point(a.x-1, a.y), CellType.AIR);
    else if((a.x==b.x)&&(a.y==b.y-2))setCellTypeAt(new Point(a.x, a.y+1), CellType.AIR);
    else if((a.x==b.x)&&(a.y==b.y+2))setCellTypeAt(new Point(a.x, a.y-1), CellType.AIR);
}

public Point getRandomAirCell(Random ran) {
    List<Point> airCells = new LinkedList<Point>();
    for(int x = 0; x<getWidth(); x++) {
        for(int y = 0; y<getHeight(); y++){
            Point p = new Point(x, y);
            if(getCellTypeAt(p)==Maze.CellType.AIR)airCells.add(p);
        }
    }
    return airCells.get(ran.nextInt(airCells.size()));
}

public int getTotalAirCells() {
    int airCells = 0;
    for(int x = 0; x<getWidth(); x++) {
        for(int y = 0; y<getHeight(); y++){
            if(getCellTypeAt(new Point(x, y))==Maze.CellType.AIR)airCells++;
        }
    }
    return airCells;
}

Why does the algorithm not finish the maze?

도움이 되었습니까?

해결책

Check getSurroundingWalls(), the fourth point checked is p.x+1, p.y-1 but I suppose it should be p.x, p.y-1.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top