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