mazebuilder.java

一个用JAVA语言编写的迷宫程序,可以实现迷宫的行走

/**
 * 
 */
package org.freemind.maze2d;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author Jerric
 * @created Feb 9, 2006
 */
public class MazeBuilder {

    private Random rand;

    /**
     * 
     */
    public MazeBuilder(long seed) {
        rand = new Random(seed);
    }

    public Maze createMaze(int width, int height) {
        // create a maze, and initialize the rooms
        Maze maze = buildMaze(width, height);

        // then build a RoomNode for each room, and each RoomNode forms a set
        // with a tree like structure;

        RoomNode[][] rooms = buildRoomNodes(width, height);
        // build walls that separate two rooms. I don't consider the outer
        // boundary of the maze; that is, for each RoomNode except the ones on
        // the last row and last column, there two walls are created, the left
        // wall and the top wall.

        List<Wall> walls = buildWalls(rooms);
        // connect rooms by randomly choose a wall, and if the rooms separated
        // by the chosen wall belong todifferent sets, I'll make a door, and
        // merge the two sets; then the wall is removed from the list. The
        // process continues until the wall list is empty.
        // To detect if two rooms belong to the same set, I compare if the roots
        // of the two sets are the same. To merge two sets, I set the root with
        // bigger height as the parent of another root.
        buildDoors(maze, walls);

        // TEST
        System.out.println("\tTree height: "
                + rooms[0][0].getRoot().getHeight());

        // at last, return the constructed maze
        return maze;
    }

    private Maze buildMaze(int width, int height) {
        Maze maze = new Maze(width, height);
        // initialize each room in the maze as closed room without doors
        Room[][] rooms = maze.getRooms();
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                rooms[y][x] = new Room();
            }
        }
        return maze;
    }

    private RoomNode[][] buildRoomNodes(int width, int height) {
        RoomNode[][] rooms = new RoomNode[height][width];
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                rooms[y][x] = new RoomNode(x, y);
            }
        }
        return rooms;
    }

    private List<Wall> buildWalls(RoomNode[][] rooms) {
        int width = rooms[0].length;
        int height = rooms.length;
        List<Wall> walls = new ArrayList<Wall>(width * height);
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                // for each room, consider the left and top walls
                if (x > 0) { // create west wall
                    Wall wall = new Wall(rooms[y][x - 1], rooms[y][x], true);
                    walls.add(wall);
                }
                if (y > 0) { // create north wall
                    Wall wall = new Wall(rooms[y - 1][x], rooms[y][x], false);
                    walls.add(wall);
                }
            }
        }
        return walls;
    }

    private void buildDoors(Maze maze, List<Wall> walls) {
        // loop till all walls are removed from the list
        while (!walls.isEmpty()) {
            // randomly choose a wall
            Wall wall = walls.remove(rand.nextInt(walls.size()));
            // check if the rooms separated by this wall belong to the same set
            RoomNode rna = wall.getRoomA();
            RoomNode rnb = wall.getRoomB();
            RoomNode rootA = rna.getRoot();
            RoomNode rootB = rnb.getRoot();
            if (rootA != rootB) {
                // two rooms are disconnected, build a door to connect them
                Room roomA = maze.getRoom(rna.getRoomX(), rna.getRoomY());
                Room roomB = maze.getRoom(rnb.getRoomX(), rnb.getRoomY());
                if (wall.isEastWest()) { // roomA on west, roomB on east
                    roomA.openEast();
                    roomB.openWest();
                } else { // roomA on north, roomB on south
                    roomA.openSouth();
                    roomB.openNorth();
                }
                // now merge the two sets. Check the height of two sets; the set
                // with bigger height becomes new root tree
                if (rootA.getHeight() > rootB.getHeight()) rootA.setChild(rootB);
                else rootB.setChild(rootA);
            } // otherwise, discard this wall
        }
    }
}