<!DOCTYPE html>
<html>
<head>
<link data-require="bootstrap-css@3.3.6" data-semver="3.3.6" rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.css" />
<link rel="stylesheet" href="style.css" />
</head>
<body class="container-fluid">
<div class="header-row">
<div class="row">
<div class="col-sm-12">
<h1>Maze Generator</h1>
</div>
</div>
<div class="row">
<div class="col-sm-12">
<div class="pull-right">
<div class="btn-group">
<button id="resetBtn" class="btn btn-danger">Reset</button>
</div>
</div>
<div class="btn-group">
<button id="generateBtn" class="btn btn-success">Generate</button>
<button id="stepBtn" class="btn btn-info">Step</button>
</div>
<div class="btn-group">
<button id="helpBtn" class="btn btn-warning">Help</button>
<button id="solveBtn" class="btn btn-danger">Solve</button>
</div>
<div class="label">
<label id="triesLabel"></label>
</div>
</div>
</div>
</div>
<div class="grid-row">
<div id="grid"></div>
</div>
<div id="scripts">
<script src="https://code.angularjs.org/tools/typescript.js"></script>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.2.4/jquery.min.js"></script>
<script src="https://cdn.rawgit.com/systemjs/systemjs/master/dist/system.js"></script>
<script src="config.js"></script>
<script>
System.import('app').catch(console.error.bind(console));
</script>
</div>
</body>
</html>
@gridSize: 600px;
@hiddenBorder: none; //3px solid transparent;
@borderColor: #000;
@backgroundColor: #eee;
@borderSize: 1px;
html, body{
height: 100%;
-moz-user-select: none;
-webkit-user-select: none;
-ms-user-select: none;
overflow: hidden;
}
.row+.row{
margin-top: 8px;
}
.container-fluid{
display: flex;
flex-direction: column;
.header-row{
padding-bottom: 15px;
.label {
display: inline-block;
color: #000;
font-size: 18px;
}
}
.grid-row{
flex-grow: 1;
padding-bottom: 15px;
#grid {
border: @borderSize solid @borderColor;
background-color: @backgroundColor;
margin: 0 auto;
.cell {
float: left;
box-sizing: border-box;
border: @borderSize solid @borderColor;
&.N {
border-top: @hiddenBorder;
}
&.E {
border-right: @hiddenBorder;
}
&.S {
border-bottom: @hiddenBorder;
}
&.W {
border-left: @hiddenBorder;
}
&.start{
background-color: #427533 !important;
}
&.finish{
background-color: #f00 !important;
}
&.safepath{
background-color: yellow;
}
&.deadend{
background-color: darken(@backgroundColor, 50%);
}
}
}
}
}
import {Maze, Cell} from './maze';
import {Ellers} from './ellers';
import {Lookup} from './helpers';
const START = 'start';
const FINISH = 'finish';
const DEADEND = 'deadend';
const SAFEPATH = 'safepath';
const SIZE = 20;
let isDragging = false;
let isAdding = true;
let generationTimers = [];
let drawCalls = {};
let isSolved = false;
let currentAvailableCells;
let width = 0;
let height = 0;
$(() => {
let grid = $('#grid');
grid
.mousedown(e => {
isDragging = true;
isAdding = !$(e.target).hasClass(DEADEND);
if(isAdding){
$(e.target).addClass(DEADEND);
} else {
$(e.target).removeClass(DEADEND);
}
})
.mouseup(e => {
if(isAdding){
$(e.target).addClass(DEADEND);
} else {
$(e.target).removeClass(DEADEND);
}
isDragging = false;
});
$('#resetBtn').click(() => clearGrid(grid));
$('#generateBtn').click(() => regenerate(grid))
$('#stepBtn').click(() => regenerate(grid, 1));
$('#helpBtn').click(() => pruneDeadEnds());
$('#solveBtn').click(() => solve(grid));
$(window).on('resize', () => regenerate(grid, 0, true));
regenerate(grid, 0, true);
});
function regenerate(grid: JQuery, delay: number = 0, rebuild: boolean = false): void {
if(rebuild) buildGrid(grid);
$('#triesLabel').text('Awaiting command...');
generateMaze(delay, grid, width, height);
isSolved = false;
currentAvailableCells = grid.children();
}
function clearGrid(grid: JQuery): void {
grid.children().each((i, cell) => {
resetCell($(cell));
});
generationTimers.forEach(timer => clearTimeout(timer));
generationTimers = [];
}
function resetCell(cell: JQuery): void {
let [x, y] = cell[0].id.split('x').map(n => parseInt(n, 10));
let classNames = cell[0].className.split(' ').filter(s => s.length > 1 && s !== DEADEND && s !== SAFEPATH);
if(x === 0 && y === 0){
classNames.push(SAFEPATH);
}
if(y === height - 1 && x === width - 1){
classNames.push(SAFEPATH);
}
cell.attr('class', classNames.join(' '));
}
function buildGrid(grid: JQuery): void {
grid.empty();
const gridContainer = grid.parent();
width = Math.floor(gridContainer.outerWidth()/SIZE);
height = Math.floor(($(window).outerHeight() - $('.header-row').outerHeight())/SIZE);
grid.width(width*SIZE);
grid.height(height*SIZE);
for (let r = 0; r < height; r++) {
for (let c = 0; c < width; c++) {
let cell = $('<div class="cell" id="' + c + 'x' + r + '" title="' + c + ' x ' + r + '"/>');
if(r === 0 && c === 0){
cell.addClass(START).addClass(SAFEPATH);
}
if(r === height - 1 && c === width - 1){
cell.addClass(FINISH).addClass(SAFEPATH);
}
cell
.css({
'width': SIZE + 'px',
'height': SIZE + 'px'
})
.mouseenter(e => {
if(isDragging){
if(isAdding){
$(e.target).addClass(DEADEND);
} else {
$(e.target).removeClass(DEADEND);
}
}
});
grid.append(cell);
}
}
}
function generateMaze(duration: number, grid: JQuery, width: number, height: number): void {
drawCalls = {};
let maze = new Maze(width, height, displayCell);
let generator = new Ellers(width);
if(duration){
let delay = (1000*duration) / height;
for(let rowNum = 0; rowNum < height; rowNum++){
((r) => {
generationTimers.push(setTimeout(() => {
let rowStates = generator.step(r + 1 === height);
for(let c = 0; c < rowStates.length; c++){
maze.updateCell(c, r, rowStates[c]);
}
}, delay * r));
})(rowNum)
}
} else {
for(let r = 0; r < height; r++){
let rowStates = generator.step(r + 1 === height);
for(let c = 0; c < rowStates.length; c++){
maze.updateCell(c, r, rowStates[c]);
}
}
}
}
function displayCell(cell: Cell, newState: string, prevState: string): void {
const id = `#${cell.x}x${cell.y}`;
drawCalls[id] = (drawCalls[id] || 0) + 1;
const cellDiv = $(id);
resetCell(cellDiv);
cellDiv.addClass(cell.state.split('').join(' '));
}
function getNeighbor(x: number, y: number, dir: string): JQuery {
switch(dir){
case 'N':
return $(`#${x}x${y-1}`);
case 'S':
return $(`#${x}x${y+1}`);
case 'E':
return $(`#${x+1}x${y}`);
case 'W':
return $(`#${x-1}x${y}`);
default:
return $();
}
}
function pruneDeadEnds(): boolean {
let prevCellCount = currentAvailableCells.length;
currentAvailableCells = currentAvailableCells.filter((i, cell) => {
let [x, y] = cell.id.split('x').map(n => parseInt(n, 10));
let $cell = $(cell);
if($cell.hasClass(START) || $cell.hasClass(FINISH)){
return true;
}
if($cell.hasClass(DEADEND)){
return false;
}
let paths = cell.className.split(' ').filter(x => x.length === 1);
let safePaths = [];
let deadEnds = [];
if(paths.length === 1) {
$cell.addClass(DEADEND);
return false;
}
let unknownPaths = paths.filter(dir => {
let neighbor = getNeighbor(x, y, dir);
if(neighbor.hasClass(SAFEPATH)){
safePaths.push(dir);
return false;
}
if(neighbor.hasClass(DEADEND)){
deadEnds.push(dir);
return false;
}
return true;
});
if(paths.length === 1){
$cell.addClass(DEADEND);
return false;
} else if(paths.length === 2) {
if(deadEnds.length > 0){
$cell.addClass(DEADEND);
return false;
}
if(safePaths.length > 0) {
$cell.addClass(SAFEPATH);
return false;
}
} else {
let possiblePaths = paths.length - deadEnds.length;
if(possiblePaths < 2){
$cell.addClass(DEADEND);
return false;
}
if(safePaths.length === 1){
if(!$cell.hasClass(START) && unknownPaths.length === 1) {
$cell.addClass(SAFEPATH);
return false;
}
} else if(safePaths.length === 2){
if(unknownPaths.length === 0){
$cell.addClass(SAFEPATH);
return false;
} else {
$cell.addClass(SAFEPATH);
unknownPaths.forEach(dir => {
getNeighbor(x,y, dir).addClass(DEADEND);
})
return;
}
}
}
return true;
});
return currentAvailableCells.length !== prevCellCount;
}
let solving = false;
function solve(grid: JQuery): void {
if(solving){
return;
}
if(isSolved){
regenerate(grid);
}
solving = true;
let start = performance.now();
let iterations = 0;
let worker = () => {
let anyChanges = pruneDeadEnds();
//console.log(currentAvailableCells);
iterations++;
if(anyChanges){
setTimeout(() => worker(), 25);
} else {
let duration = (performance.now() - start);
let text = '';
if(duration < 1000){
text = `${iterations} Iterations (${Math.round(duration*10)/10}ms)`;
} else {
text = `${iterations} Iterations (${Math.round(duration/10)/100}s)`;
}
$('#triesLabel').text(text);
isSolved = true;
solving = false;
}
};
worker();
}
{
"compileOnSave": true,
"compilerOptions": {
"target": "es5",
"moduleResolution": "node",
"emitDecoratorMetadata": true,
"experimentalDecorators": true,
"removeComments": false
}
}
import {} from './helpers';
export class Maze {
private _cells: Cell[][];
constructor(public width: number, public height: number, onStateChanged: (cell: Cell, newState: string, prevState: string) => void) {
this._cells = new Array<Cell[]>(this.height);
for (let r = 0; r < this.height; r++) {
for (let c = 0; c < this.width; c++) {
if (c === 0) {
this._cells[r] = new Array<Cell>(this.width);
}
this._cells[r][c] = new Cell(c, r, onStateChanged);
}
}
}
public getCell(c: number, r: number): Cell {
return this._cells[r][c];
}
public updateCell(c: number, r: number, state: string): void {
let cell = this.getCell(c, r);
state += cell.state;
return this.setCell(c, r, state);
}
public setCell(c: number, r: number, state: string): void {
//console.log(`Setting ${r}x${c} to ${state}!`);
let cell = this.getCell(c, r);
cell.state = state;
if(r-1 >= 0){
let northern = this.getCell(c, r-1);
northern.toggle('S', state.includes('N'));
}
if(r+1 < this.height){
let southern = this.getCell(c, r+1);
southern.toggle('N', state.includes('S'));
}
if(c+1 < this.width){
let eastern = this.getCell(c+1, r);
eastern.toggle('W', state.includes('E'));
}
if(c-1 >= 0){
let western = this.getCell(c-1, r);
western.toggle('E', state.includes('W'));
}
}
}
export class Cell {
public N: boolean = false;
public E: boolean = false;
public S: boolean = false;
public W: boolean = false;
private _state: string = '';
private _prevState: string;
constructor(public x: number, public y: number, public onStateChanged: (cell: Cell, newState: string, prevState: string) => void) { }
public get state(): string {
return this._state;
}
public set state(stateString: string) {
stateString = stateString.toUpperCase().split('').filter(function(x,i,arr){
return i==arr.indexOf(x);
}).join('');
this.N = (stateString.includes('N'));
this.E = (stateString.includes('E'));
this.S = (stateString.includes('S'));
this.W = (stateString.includes('W'));
this._prevState = this._state;
this._state = stateString;
this.onStateChanged.call(this, this, this._state, this._prevState);
}
public toggle(stateChar: string, enabled: boolean): void {
stateChar = stateChar.toUpperCase();
if(this._state.includes(stateChar) === enabled){
return;
}
this[stateChar] = enabled;
this._prevState = this._state;
if(enabled){
this._state += stateChar;
} else {
this._state = this._state.replace(stateChar, '');
}
this.onStateChanged.call(this, this, this._state, this._prevState);
}
public add(stateChar: string): void {
this.toggle(stateChar, true);
}
public remove(stateChar: string): void {
this.toggle(stateChar, false);
}
}
import {Lookup, randInt, randBool, shuffle} from './helpers';
class State
{
//private _id: number = 1000 + Math.floor(Math.random()*9999)
private _sets: Lookup<number[]> = {};
private _cells: Lookup<number> = {};
constructor(public width: number, private _nextSet: number = 0) {
}
public next(): State
{
return new State(this.width, this._nextSet);
}
public populate(): this {
//console.log(`(${this._id}) Populate[Before]: ${this}`);
for (let cell = 0; cell < this.width; cell++) {
if (typeof this._cells[cell] === 'undefined') {
let set = this._nextSet++;
this._sets[set] = this._sets[set] || [];
this._sets[set].push(cell);
this._cells[cell] = set;
}
}
//console.log(`(${this._id}) Populate[After]: ${this}`);
return this;
}
public merge(sinkCell: number, targetCell: number): void {
//console.log(`(${this._id}) Merge[Before]: ${this}`);
let sink = this._cells[sinkCell];
let target = this._cells[targetCell];
this._sets[sink] = [...this._sets[sink], ...this._sets[target]];
this._sets[target].forEach(cell => this._cells[cell] = sink);
delete this._sets[target];
//console.log(`(${this._id}) Merge[After]: ${this}`);
}
public same(cell1: number, cell2: number): boolean {
return this._cells[cell1] === this._cells[cell2];
}
public add(cell: number, set: number): this {
this._cells[cell] = set;
this._sets[set] = this._sets[set] || [];
this._sets[set].push(cell);
return this;
}
public forEach(func: (id: number, cells: Array<number>) => void, thisArg?: any): void {
Object.keys(this._sets).forEach(set => {
set = parseInt(set, 10);
func.call(thisArg, set, this._sets[set]);
});
}
public toString(): string {
let str = '|';
let cellSets = [];
for (let cell = 0; cell < this.width; cell++) {
let setNum = this._cells[cell];
if(typeof setNum === 'number'){
cellSets.push(setNum);
} else if (typeof setNum === 'string'){
cellSets.push('*'+setNum);
} else {
cellSets.push('?');
}
}
return `| ${cellSets.join(' | '} |`;
}
}
export class Ellers<T>
{
private _state: State;
constructor(width: number) {
this._state = (new State(width)).populate();
}
public step(finish: boolean = false): Array<string> {
let connectedSets: number[][] = [];
let connectedSet: number[] = [0];
for (let c = 0; c < this._state.width-1; c++){
if (this._state.same(c, c + 1) || (!finish && randBool())) {
connectedSets.push(connectedSet);
connectedSet = [c + 1];
} else {
this._state.merge(c, c + 1);
connectedSet.push(c + 1);
}
}
connectedSets.push(connectedSet);
let verticals: Array<number> = [];
let nextState = this._state.next();
if (!finish) {
this._state.forEach((id, set) => {
let cellsToConnect = shuffle(set).slice(0, randInt(1, set.length));
verticals = [...verticals, ...cellsToConnect];
cellsToConnect.forEach(cell => {
nextState.add(cell, id);
});
});
}
let row: Array<string> = [];
connectedSets.forEach(connectedSet => {
connectedSet.forEach((cell, index) => {
let last = (index + 1 === connectedSet.length);
let map = last ? '' : 'E';
map += (verticals.indexOf(cell) > -1 ? 'S' : '');
row.push(map);
});
});
this._state = nextState.populate();
return row;
}
}
System.config({
//use typescript for compilation
transpiler: 'typescript',
//typescript compiler options
typescriptOptions: {
emitDecoratorMetadata: true
},
//map tells the System loader where to look for things
map: {
app: "./"
},
//packages defines our app package
packages: {
app: {
main: './index.ts',
defaultExtension: 'ts'
}
}
});
export interface Lookup<TValue> {
[key: number]: TValue;
[key: string]: TValue;
}
export function randInt(min: number, max: number = null): number {
if(max === null){
max = min;
min = 0;
}
let diff = max - min;
return Math.floor(min + (Math.random() * diff));
}
export function randBool(): boolean {
return Math.random() > 0.5;
}
export function shuffle<T>(a: T[]): T[] {
a = a.slice();
for (let i = a.length; i; i--) {
let j = Math.floor(Math.random() * i);
let x = a[i - 1];
a[i - 1] = a[j];
a[j] = x;
}
return a;
}