001package squidpony.squidgrid.mapping; 002 003import squidpony.GwtCompatibility; 004import squidpony.squidmath.RNG; 005 006/** 007 * Meant to produce the sort of narrow, looping, not-quite-maze-like passages found in a certain famous early arcade game. 008 * Created by Tommy Ettinger on 3/30/2016. 009 */ 010public class PacMazeGenerator { 011 public RNG rng; 012 public int width, height; 013 private boolean[][] map; 014 private int[][] env; 015 private char[][] maze; 016 public PacMazeGenerator() 017 { 018 this(250, 250); 019 } 020 public PacMazeGenerator(int width, int height) 021 { 022 this.height = height; 023 this.width = width; 024 rng = new RNG(); 025 } 026 public PacMazeGenerator(int width, int height, RNG rng) 027 { 028 this.height = height; 029 this.width = width; 030 this.rng = rng; 031 } 032 033 private static final byte[] //unbiased_connections = new byte[]{3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15}, 034 connections = new byte[]{ 035 3, 5, 6, 9, 10, 12,/* 036 3, 5, 6, 9, 10, 12, 037 3, 5, 6, 9, 10, 12, 038 3, 5, 6, 9, 10, 12, 039 7, 11, 13, 14, 040 7, 11, 13, 14, 041 15*/ 042 }; 043 private static final int connections_length = connections.length; 044 private boolean write(boolean[][] m, int x, int y, int xOffset, int yOffset, boolean value) 045 { 046 int nx = x * 3 + xOffset + 1, ny = y * 3 + yOffset + 1; 047 if(nx >= 0 && nx < m.length && ny >= 0 && ny < m[nx].length) { 048 m[nx][ny] = value; 049 return true; 050 } 051 return false; 052 } 053 public boolean[][] create() 054 { 055 map = new boolean[width][height]; 056 byte[][] conns = new byte[(width+2) / 3][(height+2) / 3]; 057 int xOff = (width % 3 == 1) ? -1 : 0, yOff = (height % 3 == 1) ? -1 : 0; 058 for (int x = 0; x < (width+2) / 3; x++) { 059 for (int y = 0; y < (height+2) / 3; y++) { 060 conns[x][y] = connections[rng.nextInt(connections_length)]; 061 } 062 } 063 for (int x = 0; x < (width+2) / 3; x++) { 064 for (int y = 0; y < (height+2) / 3; y++) { 065 write(map, x, y, xOff, yOff, true); 066 if(x > 0 && ((conns[x - 1][y] & 1) != 0 || (conns[x][y] & 2) != 0)) 067 { 068 conns[x - 1][y] |= 1; 069 conns[x][y] |= 2; 070 } 071 if(x < conns.length - 1 && ((conns[x + 1][y] & 2) != 0 || (conns[x][y] & 1) != 0)) 072 { 073 conns[x + 1][y] |= 2; 074 conns[x][y] |= 1; 075 } 076 if(y > 0 && ((conns[x][y - 1] & 4) != 0 || (conns[x][y] & 8) != 0)) 077 { 078 conns[x][y - 1] |= 4; 079 conns[x][y] |= 8; 080 } 081 if(y < conns[0].length - 1 && ((conns[x][y + 1] & 8) != 0 || (conns[x][y] & 4) != 0)) 082 { 083 conns[x][y + 1] |= 8; 084 conns[x][y] |= 4; 085 } 086 } 087 } 088 089 for (int x = 1; x < (width-1) / 3; x++) { 090 for (int y = 1; y < (height-1) / 3; y++) { 091 if (Integer.bitCount(conns[x][y]) >= 4) { 092 //byte temp = connections[rng.nextInt(connections_length)]; 093 int temp = 1 << rng.nextInt(4); 094 conns[x][y] ^= temp; 095 if((temp & 2) != 0) conns[x - 1][y] ^= 1; 096 else if((temp & 1) != 0) conns[x + 1][y] ^= 2; 097 else if((temp & 8) != 0) conns[x][y - 1] ^= 4; 098 else if((temp & 4) != 0) conns[x][y + 1] ^= 8; 099 } 100 } 101 } 102 for (int x = 0; x < (width+2) / 3; x++) { 103 for (int y = 0; y < (height+2) / 3; y++) { 104 write(map, x, y, xOff, yOff, true); 105 if(x > 0 && (conns[x][y] & 2) != 0) 106 write(map, x, y, xOff - 1, yOff, true); 107 if(x < conns.length - 1 && (conns[x][y] & 1) != 0) 108 write(map, x, y, xOff + 1, yOff, true); 109 if(y > 0 && (conns[x][y] & 8) != 0) 110 write(map, x, y, xOff, yOff - 1, true); 111 if(y < conns[0].length - 1 && (conns[x][y] & 4) != 0) 112 write(map, x, y, xOff, yOff + 1, true); 113 } 114 } 115 int upperY = height - 1; 116 int upperX = width - 1; 117 for (int i = 0; i < width; i++) { 118 map[i][0] = false; 119 map[i][upperY] = false; 120 } 121 for (int i = 0; i < height; i++) { 122 map[0][i] = false; 123 map[upperX][i] = false; 124 } 125 return map; 126 } 127 public char[][] generate() 128 { 129 create(); 130 maze = new char[width][height]; 131 env = new int[width][height]; 132 for (int x = 0; x < width; x++) { 133 for (int y = 0; y < height; y++) { 134 maze[x][y] = map[x][y] ? '.' : '#'; 135 env[x][y] = map[x][y] ? MixedGenerator.CORRIDOR_FLOOR : MixedGenerator.CORRIDOR_WALL; 136 } 137 } 138 139 return maze; 140 } 141 142 public int[][] getEnvironment() 143 { 144 if(env == null) 145 return GwtCompatibility.fill2D(MixedGenerator.CORRIDOR_WALL, width, height); 146 return env; 147 } 148 149 /** 150 * Gets the maze as a 2D array of true for passable or false for blocked. 151 * @return a 2D boolean array; true is passable and false is not. 152 */ 153 public boolean[][] getMap() 154 { 155 if(map == null) 156 return new boolean[width][height]; 157 return map; 158 } 159 160 /** 161 * Gets the maze as a 2D array of ',' for passable or '#' for blocked. 162 * @return a 2D boolean array; '.' is passable and '#' is not. 163 */ 164 public char[][] getMaze() { 165 if(maze == null) 166 return GwtCompatibility.fill2D('#', width, height); 167 return maze; 168 } 169}