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}