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}