qycyfjy/maze.html

## maze.html
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <style>
        canvas {
            border: 0px solid;
            position: absolute;
            left: 25%;
            margin-left: 10px;
        }
    </style>
    <script src="./maze.js"></script>
    <title>Canvas</title>
</head>
<body>
    <canvas id="maze" width="1000" height="900"></canvas>
    <script>
        main();
    </script>
</body>
</html>

## maze.js
'use strict';

class UnionSet {
    constructor(size) {
        this.set = new Array(size);
        this.rank = new Array(size);
        for (let i = 0; i < size; i++) {
            this.set[i] = i;
            this.rank[i] = 1;
        }
    }

    merge(i, j) {
        let x = this.find(i);
        let y = this.find(j);
        if (this.rank[x] <= this.rank[y]) {
            this.set[x] = y;
        } else {
            this.set[y] = x;
        }
        if (x != y && this.rank[x] === this.rank[y]) {
            this.rank[y]++;
        }
    }

    find(x) {
        if (x === this.set[x]) {
            return x;
        } else {
            this.set[x] = this.find(this.set[x]);
            return this.set[x];
        }
    }

    same(i, j) {
        return this.find(i) === this.find(j);
    }
}

class Maze {
    constructor(rows, columns, canvas) {
        this.canvas = canvas;
        this.rows = rows;
        this.columns = columns;
        this.cells = rows * columns;

        this.linked = new Map();
        this.unionSet = new UnionSet(this.cells);
    }

    isLinked(x1, y1, x2, y2) {
        let i1 = x1 + y1 * this.columns;
        let i2 = x2 + y2 * this.columns;
        return this.linked.has(i1) || this.linked.get(i1).includes(i2);
    }

    addLinked(a, b) {
        if (!this.linked.has(a)) {
            this.linked.set(a, new Array());
        }
        if (!this.linked.has(b)) {
            this.linked.set(b, new Array());
        }
        this.linked.get(a).push(b);
        this.linked.get(b).push(a);
    }

    seLinked() {
        for(let i = 1; i < this.cells; i++) {
            if(!this.unionSet.same(0, i)) {
                return false;
            }
        }
        return true;
    }

    pickRandomPair() {
        let cell = Math.random() * this.cells >> 0;
        let r = cell / this.columns >> 0;
        let c = cell % this.columns >> 0;
        let neighbours = [];
        if (r > 0) {
            neighbours.push(cell - this.columns);
        }
        if (r < this.rows - 1) {
            neighbours.push(cell + this.columns);
        }

        if (c > 0) {
            neighbours.push(cell - 1);
        }
        if (c < this.columns - 1) {
            neighbours.push(cell + 1);
        }

        return [cell, neighbours[Math.random() * neighbours.length >> 0]];
    }

    generate() {
        while (!this.seLinked()) {
            let pair = this.pickRandomPair();
            if (!this.unionSet.same(pair[0], pair[1])) {
                this.unionSet.merge(pair[0], pair[1]);
                this.addLinked(pair[0], pair[1]);
            }
        }
    }

    draw() {
        let cellHeight = this.canvas.height / this.rows >> 0;
        let cellWidth = this.canvas.width / this.columns >> 0;

        let ctx = this.canvas.getContext('2d');
        ctx.translate(0.5,0.5);
        for (let i = 0; i < this.cells; i++) {
            let r = i / this.columns >> 0;
            let c = i % this.columns;

            // 不和右边的联通就画墙
            if (c !== (this.columns - 1) && (!this.linked.has(i) || !this.linked.get(i).includes(i + 1))) {
                ctx.moveTo((c + 1) * cellWidth, r * cellHeight);
                ctx.lineTo((c + 1) * cellWidth, (r + 1) * cellHeight);
            }

            // 不和下边的联通就画墙
            if (r !== (this.rows - 1) && (!this.linked.has(i) || !this.linked.get(i).includes(i + this.columns))) {
                ctx.moveTo(c * cellWidth, (r + 1) * cellHeight);
                ctx.lineTo((c + 1) * cellWidth, (r + 1) * cellHeight);
            }
        }

        // border
        ctx.moveTo(0,0);
        ctx.lineTo(this.columns * cellWidth-0.5, 0);
        ctx.lineTo(this.columns * cellWidth-0.5, (this.rows-1) * cellHeight-0.5);
        ctx.moveTo(0, cellHeight);
        ctx.lineTo(0, this.rows * cellHeight-0.5)
        ctx.lineTo(this.columns * cellWidth, this.rows * cellHeight-0.5)
        ctx.stroke();
    }
}

function main() {
    let canvas = document.getElementById('maze');
    let maze = new Maze(50, 50, canvas);
    console.time('Gen');
    maze.generate();
    console.timeEnd('Gen');
    console.time('Draw');
    maze.draw();
    console.timeEnd('Draw');
}
	<!DOCTYPE html>
	<html lang="en">
	<head>
	<meta charset="UTF-8">
	<meta http-equiv="X-UA-Compatible" content="IE=edge">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<style>
	canvas {
	border: 0px solid;
	position: absolute;
	left: 25%;
	margin-left: 10px;
	}
	</style>
	<script src="./maze.js"></script>
	<title>Canvas</title>
	</head>
	<body>
	<canvas id="maze" width="1000" height="900"></canvas>
	<script>
	main();
	</script>
	</body>
	</html>
	'use strict';

	class UnionSet {
	constructor(size) {
	this.set = new Array(size);
	this.rank = new Array(size);
	for (let i = 0; i < size; i++) {
	this.set[i] = i;
	this.rank[i] = 1;
	}
	}

	merge(i, j) {
	let x = this.find(i);
	let y = this.find(j);
	if (this.rank[x] <= this.rank[y]) {
	this.set[x] = y;
	} else {
	this.set[y] = x;
	}
	if (x != y && this.rank[x] === this.rank[y]) {
	this.rank[y]++;
	}
	}

	find(x) {
	if (x === this.set[x]) {
	return x;
	} else {
	this.set[x] = this.find(this.set[x]);
	return this.set[x];
	}
	}

	same(i, j) {
	return this.find(i) === this.find(j);
	}
	}

	class Maze {
	constructor(rows, columns, canvas) {
	this.canvas = canvas;
	this.rows = rows;
	this.columns = columns;
	this.cells = rows * columns;

	this.linked = new Map();
	this.unionSet = new UnionSet(this.cells);
	}

	isLinked(x1, y1, x2, y2) {
	let i1 = x1 + y1 * this.columns;
	let i2 = x2 + y2 * this.columns;
	return this.linked.has(i1) \|\| this.linked.get(i1).includes(i2);
	}

	addLinked(a, b) {
	if (!this.linked.has(a)) {
	this.linked.set(a, new Array());
	}
	if (!this.linked.has(b)) {
	this.linked.set(b, new Array());
	}
	this.linked.get(a).push(b);
	this.linked.get(b).push(a);
	}

	seLinked() {
	for(let i = 1; i < this.cells; i++) {
	if(!this.unionSet.same(0, i)) {
	return false;
	}
	}
	return true;
	}

	pickRandomPair() {
	let cell = Math.random() * this.cells >> 0;
	let r = cell / this.columns >> 0;
	let c = cell % this.columns >> 0;
	let neighbours = [];
	if (r > 0) {
	neighbours.push(cell - this.columns);
	}
	if (r < this.rows - 1) {
	neighbours.push(cell + this.columns);
	}

	if (c > 0) {
	neighbours.push(cell - 1);
	}
	if (c < this.columns - 1) {
	neighbours.push(cell + 1);
	}

	return [cell, neighbours[Math.random() * neighbours.length >> 0]];
	}

	generate() {
	while (!this.seLinked()) {
	let pair = this.pickRandomPair();
	if (!this.unionSet.same(pair[0], pair[1])) {
	this.unionSet.merge(pair[0], pair[1]);
	this.addLinked(pair[0], pair[1]);
	}
	}
	}

	draw() {
	let cellHeight = this.canvas.height / this.rows >> 0;
	let cellWidth = this.canvas.width / this.columns >> 0;

	let ctx = this.canvas.getContext('2d');
	ctx.translate(0.5,0.5);
	for (let i = 0; i < this.cells; i++) {
	let r = i / this.columns >> 0;
	let c = i % this.columns;

	// 不和右边的联通就画墙
	if (c !== (this.columns - 1) && (!this.linked.has(i) \|\| !this.linked.get(i).includes(i + 1))) {
	ctx.moveTo((c + 1) * cellWidth, r * cellHeight);
	ctx.lineTo((c + 1) * cellWidth, (r + 1) * cellHeight);
	}

	// 不和下边的联通就画墙
	if (r !== (this.rows - 1) && (!this.linked.has(i) \|\| !this.linked.get(i).includes(i + this.columns))) {
	ctx.moveTo(c * cellWidth, (r + 1) * cellHeight);
	ctx.lineTo((c + 1) * cellWidth, (r + 1) * cellHeight);
	}
	}

	// border
	ctx.moveTo(0,0);
	ctx.lineTo(this.columns * cellWidth-0.5, 0);
	ctx.lineTo(this.columns * cellWidth-0.5, (this.rows-1) * cellHeight-0.5);
	ctx.moveTo(0, cellHeight);
	ctx.lineTo(0, this.rows * cellHeight-0.5)
	ctx.lineTo(this.columns * cellWidth, this.rows * cellHeight-0.5)
	ctx.stroke();
	}
	}

	function main() {
	let canvas = document.getElementById('maze');
	let maze = new Maze(50, 50, canvas);
	console.time('Gen');
	maze.generate();
	console.timeEnd('Gen');
	console.time('Draw');
	maze.draw();
	console.timeEnd('Draw');
	}