const WALL = 'X';
const EMPTY = ' ';
const PORTAL = '$';

class MazeGenerator {
    constructor(rows, cols) {
    	this.numRows = rows;
    	this.numCols = cols;
        this.visited = [];
        this.render = [];

    	for (let i = 0; i < rows + 2; ++i) {
            this.visited.push(Array(cols + 2).fill(false));
            this.render.push(Array(cols + 2).fill(WALL));
    	}

        // set borders as visited
        for (let i = 0; i < rows + 2; ++i) {
            this.visited[i][0] = true;
            this.visited[i][cols + 1] = true;
        }

        for (let i = 0; i < cols + 2; ++i) {
            this.visited[0][i] = true;
            this.visited[rows + 1][i] = true;
        }

    }

    init(startPos, exitPos) {
	   let [x, y] = this.offset(startPos);
    	this.render[x][y] = PORTAL;
    	for (const exit of exitPos) {
            [x, y] = this.offset(exit);
    	    this.render[x][y] = PORTAL;
    	}
    }

    offset(pos) {
    	let [i, j] = pos;
    	if (i === 0) i++;
    	if (j === 0) j++;
    	return [i,  j];
    }

    generate(x, y) {
        this.visited[x][y] = true;
        if (this.render[x][y] === WALL) this.render[x][y] = ' ';
        let paths = this.adjacent(x, y);
        for (const [a, b] of paths) {
            if (this.numWalls(a, b) >= 6 && !this.hasDiagWalls(a, b)) {
                this.generate(a, b);
            }
        }
    }

    numWalls(x, y) {
        let count = 0;
        for (let i = x - 1; i <= x + 1; ++i) {
            for (let j = y - 1; j <= y + 1; ++j) {
                if (this.render[i][j] === WALL) count++;
            }
        }
        return count;
    }

    adjacent(x, y) {
        let paths = [];
        let dirs = [
            [x - 1, y],
            [x + 1, y],
            [x, y - 1],
            [x, y + 1],
        ];
        for (let [a, b] of dirs) {
            if (!this.visited[a][b]) {
                paths.push([a, b]);
            }
        }
        this.shuffle(paths);
        return paths;
    }

    hasDiagWalls(x, y) {
        let corners = [
            [x - 1, y -  1],
            [x - 1, y + 1],
            [x + 1, y - 1],
            [x + 1, y + 1],
        ];
        let adjacent = [
            [[x - 1, y], [x, y - 1]],
            [[x - 1, y], [x, y + 1]],
            [[x + 1, y], [x, y - 1]],
            [[x + 1, y], [x, y + 1]],
        ];
        for (let i = 0; i < 4; ++i) {
            let [a, b] = corners[i];
            let [[c1, c2], [c3, c4]] = adjacent[i];
            let vtx = this.render[a][b];
            let n1 = this.render[c1][c2];
            let n2 = this.render[c3][c4];
            if (vtx === EMPTY && n1 === WALL && n2 === WALL) {
                return true;
            }
        }
        return false;
    }

    shuffle(arr) {
        for (let i = arr.length - 1; i > 0; --i) {
            const idx = Math.floor(Math.random() * i);
            this.swap(arr, i, idx);
        }
    }

    swap(arr, x, y)  {
        const temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    display() {
        for (let i = 0; i < this.numRows + 2; ++i) {
            let line = '';
            for (let j = 0; j < this.numCols + 2; ++j) {
                line += this.render[i][j];
            }
            console.log(line);
        }
    }
}


function test() {
    const maze = new MazeGenerator(20, 20);
    const startPos = [0, 0];
    const exits = [[0, 20], [20, 20], [20, 7], [15, 0]];
    maze.init(startPos, exits);
    maze.generate(1, 1);
    maze.display()
}

test()