001package squidpony.squidgrid.mapping;
002
003
004import squidpony.annotation.Beta;
005import squidpony.squidgrid.Direction;
006import squidpony.squidmath.Coord;
007import squidpony.squidmath.RNG;
008
009import java.util.ArrayList;
010
011/**
012 *
013 *
014 * Based in part on code from http://weblog.jamisbuck.org/2011/1/27/maze-generation-growing-tree-algorithm
015 *
016 * @author Eben Howard - http://squidpony.com - howard@squidpony.com
017 */
018@Beta
019public class GrowingTreeMazeGenerator {
020
021    private RNG rng;
022    private int width, height;
023
024    public GrowingTreeMazeGenerator(int width, int height) {
025        this.width = width;
026        this.height = height;
027        rng = new RNG();
028    }
029    public GrowingTreeMazeGenerator(int width, int height, RNG rng) {
030        this.width = width;
031        this.height = height;
032        this.rng = rng;
033    }
034
035    /**
036     * Builds and returns a boolean mapping of a maze using the provided chooser method object.
037     * 
038     * @param choosing the callback object for making the split decision
039     * @return 
040     */
041    public boolean[][] create(ChoosingMethod choosing) {
042        boolean[][] map = new boolean[width][height];
043        boolean[][] visited = new boolean[width][height];
044
045        int x = rng.nextInt(width / 2);
046        int y = rng.nextInt(height / 2);
047        x *= 2;
048        y *= 2;
049
050        ArrayList<Coord> deck = new ArrayList<>();
051        deck.add(Coord.get(x, y));
052
053        Direction[] dirs = Direction.CARDINALS;
054        while (!deck.isEmpty()) {
055            int i = choosing.chooseIndex(deck.size());
056            Coord p = deck.get(i);
057            dirs = rng.shuffle(dirs, new Direction[dirs.length]);
058
059            boolean foundNeighbor = false;
060            for (Direction dir : dirs) {
061                x = p.x + dir.deltaX * 2;
062                y = p.y + dir.deltaY * 2;
063                if (x >= 0 && x < width && y >= 0 && y < height) {
064                    if (!visited[x][y]) {
065                        foundNeighbor = true;
066//                        if (rng.nextBoolean()) {
067                            visited[x][y] = true;
068//                        }
069                        map[x][y] = true;
070                        map[p.x + dir.deltaX][p.y + dir.deltaY] = true;
071                        deck.add(Coord.get(x, y));
072                        break;
073                    }
074                }
075            }
076
077            if (!foundNeighbor) {
078                deck.remove(p);
079            }
080        }
081
082        return map;
083    }
084
085    public interface ChoosingMethod {
086
087        /**
088         * Given the size to choose from, will return a single value smaller than the passed in value and greater than
089         * or equal to 0. The value chosen is dependant on the individual implementation.
090         *
091         * @param size
092         * @return
093         */
094        int chooseIndex(int size);
095    }
096}