talesa/maze.html

## maze.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>

body {
  background: #000;
}

</style>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<!-- <script src="https://d3js.org/d3-timer.v1.min.js"></script> -->
<!-- <script src="d3.v3.min.js"></script> -->
<!-- <script src="d3-timer.v1.min.js"></script> -->
<script>

var width = 960,
    height = 500;

var N = 1 << 0,
    S = 1 << 1,
    W = 1 << 2,
    E = 1 << 3;

var cellSize = 4,
    cellSpacing = 4,
    cellWidth = Math.floor((width - cellSpacing) / (cellSize + cellSpacing)),
    cellHeight = Math.floor((height - cellSpacing) / (cellSize + cellSpacing)),
    cells = generateMaze(cellWidth, cellHeight), // each cell’s edge bits
    parent = new Array(cellHeight * cellWidth), // path tracking
    minScore = Infinity,
    minIndex = (cellHeight - 1) * cellWidth,
    goalX = cellWidth - 1,
    goalY = 0,

    // this is how the frontier_func() variable you supply is initialised
    frontier = frontier_func();

// this is the first cell
frontier.push(minIndex);
parent[minIndex] = null;

var canvas = d3.select("body").append("canvas")
    .attr("width", width)
    .attr("height", height);

var context = canvas.node().getContext("2d");

context.translate(
  Math.round((width - cellWidth * cellSize - (cellWidth + 1) * cellSpacing) / 2),
  Math.round((height - cellHeight * cellSize - (cellHeight + 1) * cellSpacing) / 2)
);

context.fillStyle = "#fff";
for (var y = 0, i = 0; y < cellHeight; ++y) {
  for (var x = 0; x < cellWidth; ++x, ++i) {
    fillCell(i);
    if (cells[i] & S) fillSouth(i);
    if (cells[i] & E) fillEast(i);
  }
}

var interval_value = 100;

context.fillStyle = "#777";
d3.timer(function() {
  for (var i = 0; i < interval_value; ++i) {
    if (exploreFrontier()) {
      console.log('Finished timer.')
      return true;
    }
  }
});

function fillPath(i1) {
  while (true) {
    fillCell(i1);
    var i0 = parent[i1];
    if (i0 == null) break;
    (Math.abs(i0 - i1) === 1 ? fillEast : fillSouth)(Math.min(i0, i1));
    i1 = i0;
  }
}

function fillCell(i) {
  var x = i % cellWidth, y = i / cellWidth | 0;
  context.fillRect(x * cellSize + (x + 1) * cellSpacing, y * cellSize + (y + 1) * cellSpacing, cellSize, cellSize);
}

function fillEast(i) {
  var x = i % cellWidth, y = i / cellWidth | 0;
  context.fillRect((x + 1) * (cellSize + cellSpacing), y * cellSize + (y + 1) * cellSpacing, cellSpacing, cellSize);
}

function fillSouth(i) {
  var x = i % cellWidth, y = i / cellWidth | 0;
  context.fillRect(x * cellSize + (x + 1) * cellSpacing, (y + 1) * (cellSize + cellSpacing), cellSize, cellSpacing);
}

function generateMazeRandom(cellWidth, cellHeight) {
  var cells = new Array(cellWidth * cellHeight),
      frontier = [],
      startIndex = (cellHeight - 1) * cellWidth;

  cells[startIndex] = 0;
  frontier.push({index: startIndex, direction: N});
  frontier.push({index: startIndex, direction: E});

  while ((edge = popRandom(frontier)) != null) {
    var edge,
        i0 = edge.index,
        d0 = edge.direction,
        i1 = i0 + (d0 === N ? -cellWidth : d0 === S ? cellWidth : d0 === W ? -1 : +1),
        x0 = i0 % cellWidth,
        y0 = i0 / cellWidth | 0,
        x1,
        y1,
        d1,
        open = cells[i1] == null; // opposite not yet part of the maze

    if (d0 === N) x1 = x0, y1 = y0 - 1, d1 = S;
    else if (d0 === S) x1 = x0, y1 = y0 + 1, d1 = N;
    else if (d0 === W) x1 = x0 - 1, y1 = y0, d1 = E;
    else x1 = x0 + 1, y1 = y0, d1 = W;

    if (open) {
      cells[i0] |= d0, cells[i1] |= d1;
      if (y1 > 0 && cells[i1 - cellWidth] == null) frontier.push({index: i1, direction: N});
      if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) frontier.push({index: i1, direction: S});
      if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W});
      if (x1 < cellWidth - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: E});
    }
  }

  return cells;
}

function generateMazeWilson(width, height) {
  var cells = new Array(width * height), // each cell’s edge bits
      remaining = d3.range(width * height), // cell indexes to visit
      previous = new Array(width * height); // current random walk

  // Add the starting cell.
  var start = remaining.pop();
  cells[start] = 0;

  // While there are remaining cells,
  // add a loop-erased random walk to the maze.
  while (!loopErasedRandomWalk());

  return cells;

  function loopErasedRandomWalk() {
    var direction,
        index0,
        index1,
        i,
        j;

    // Pick a location that’s not yet in the maze (if any).
    do if ((index0 = remaining.pop()) == null) return true;
    while (cells[index0] >= 0);

    // Perform a random walk starting at this location,
    previous[index0] = index0;
    while (true) {
      i = index0 % width;
      j = index0 / width | 0;

      // picking a legal random direction at each step.
      direction = Math.random() * 4 | 0;
      if (direction === 0) { if (j <= 0) continue; --j; }
      else if (direction === 1) { if (j >= height - 1) continue; ++j; }
      else if (direction === 2) { if (i <= 0) continue; --i; }
      else { if (i >= width - 1) continue; ++i; }

      // If this new cell was visited previously during this walk,
      // erase the loop, rewinding the path to its earlier state.
      // Otherwise, just add it to the walk.
      index1 = j * width + i;
      if (previous[index1] >= 0) eraseWalk(index0, index1);
      else previous[index1] = index0;
      index0 = index1;

      // If this cell is part of the maze, we’re done walking.
      if (cells[index1] >= 0) {

        // Add the random walk to the maze by backtracking to the starting cell.
        // Also erase this walk’s history to not interfere with subsequent walks.
        while ((index0 = previous[index1]) !== index1) {
          direction = index1 - index0;
          if (direction === 1) cells[index0] |= E, cells[index1] |= W;
          else if (direction === -1) cells[index0] |= W, cells[index1] |= E;
          else if (direction < 0) cells[index0] |= N, cells[index1] |= S;
          else cells[index0] |= S, cells[index1] |= N;
          previous[index1] = NaN;
          index1 = index0;
        }

        previous[index1] = NaN;
        return;
      }
    }
  }

  function eraseWalk(index0, index1) {
    var index;
    while ((index = previous[index0]) !== index1) previous[index0] = NaN, index0 = index;
    previous[index0] = NaN;
  }
}

function popRandom(array) {
  if (!array.length) return;
  var n = array.length, i = Math.random() * n | 0, t;
  t = array[i], array[i] = array[n - 1], array[n - 1] = t;
  return array.pop();
}

function exploreFrontier() {
  // this is how the frontier variable you supply is used
  var i0 = frontier.pop(),
      s0 = score(i0);

  fillCell(i0);

  if (s0 < minScore) {
    fillPath(minIndex);
    context.fillStyle = "magenta";
    minScore = s0, minIndex = i0;
    fillPath(minIndex);
    context.fillStyle = "#777";
    console.log(s0);
    if (!s0) {
      console.log('Finished');
      return true;
    }
  }

  expandFrontier(i0);
}

function priorityQueue(compare) {
  var queue = {},
      array = [],
      size = 0;

  queue.empty = function() {
    return !size;
  };

  queue.push = function(value) {
    up(array[size] = value, size++);
    return size;
  };

  queue.pop = function() {
    if (size <= 0) return;
    var removed = array[0], value;
    if (--size > 0) value = array[size], down(array[0] = value, 0);
    return removed;
  };

  function up(value, i) {
    while (i > 0) {
      var j = ((i + 1) >> 1) - 1,
          parent = array[j];
      if (compare(value, parent) >= 0) break;
      array[i] = parent;
      array[i = j] = value;
    }
  }

  function down(value, i) {
    while (true) {
      var r = (i + 1) << 1,
          l = r - 1,
          j = i,
          child = array[j];
      if (l < size && compare(array[l], child) < 0) child = array[j = l];
      if (r < size && compare(array[r], child) < 0) child = array[j = r];
      if (j === i) break;
      array[i] = child;
      array[i = j] = value;
    }
  }

  return queue;
}

function score(i) {
  var x = goalX - (i % cellWidth), y = goalY - (i / cellWidth | 0);
  return x * x + y * y;
}

function nextCellIndex(i0, direction) {
  switch (direction) {
    case E: i1 = i0 + 1; break;
    case W: i1 = i0 - 1; break;
    case S: i1 = i0 + cellWidth; break;
    case N: i1 = i0 - cellWidth; break;
    default: prompt('Error: Unknown direction!');
  }
  return i1;
}

// checks whether you can go from cell i0 in the given direction
// returns false if that is the direction you came from
function isFree(i0, direction) {
  i1 = nextCellIndex(i0, direction);
  if (cells[i0] & direction && isNaN(parent[i1])) return i1;
  return false;
}

// fills the appropriate cell in the given direction from cell i0 with gray colour
function fillGray(i0, direction) {
  var i1 = nextCellIndex(i0, direction)
  switch (direction) {
    case E: fillEast(i0); break;
    case W: fillEast(i1); break;
    case S: fillSouth(i0); break;
    case N: fillSouth(i1); break;
    default: prompt('Error: Unknown direction!');
  }
}

function generateMaze(cellWidth, cellHeight) {
  return generateMazeWilson(cellWidth, cellHeight);
  // return generateMazeRandom(cellWidth, cellHeight);
}

function frontier_func() {
  return [];
}


// START LOOKING HERE

// Returns a random integer between min (inclusive) and max (exclusive)
function getRandomInt(min, max) {
    return Math.floor(Math.random() * (max - min)) + min;
}

function expandFrontier(i0) {
  // You are at cell i0, i0 is the current cell index (address)

  var directions = [E, W, S, N];

  // example
  // This is the code that only tries to go East

  // What is the index (address) of the cell in the direction East from i0, the current cell?
  i1 = nextCellIndex(i0, E);
  if (isFree(i0, E)) {
    // Inform the system that you came to cell i1 from i0 by setting the parent of i1 to i0
    parent[i1] = i0;
    // Fill in the new cell with gray colour to show that we've visited that cell
    fillGray(i0, E);
    // Add the new cell to the list of the new cells to be explored/visited
    frontier.push(i1)
  }

  /*
  Tasks:
  1. Modify the script to try going East and North.
  2. Modify the script to try going in all directions. Does the order matter?
  */

}

</script>
	<!DOCTYPE html>
	<meta charset="utf-8">
	<style>

	body {
	background: #000;
	}

	</style>
	<body>
	<script src="http://d3js.org/d3.v3.min.js"></script>
	<!-- <script src="https://d3js.org/d3-timer.v1.min.js"></script> -->
	<!-- <script src="d3.v3.min.js"></script> -->
	<!-- <script src="d3-timer.v1.min.js"></script> -->
	<script>

	var width = 960,
	height = 500;

	var N = 1 << 0,
	S = 1 << 1,
	W = 1 << 2,
	E = 1 << 3;

	var cellSize = 4,
	cellSpacing = 4,
	cellWidth = Math.floor((width - cellSpacing) / (cellSize + cellSpacing)),
	cellHeight = Math.floor((height - cellSpacing) / (cellSize + cellSpacing)),
	cells = generateMaze(cellWidth, cellHeight), // each cell’s edge bits
	parent = new Array(cellHeight * cellWidth), // path tracking
	minScore = Infinity,
	minIndex = (cellHeight - 1) * cellWidth,
	goalX = cellWidth - 1,
	goalY = 0,

	// this is how the frontier_func() variable you supply is initialised
	frontier = frontier_func();

	// this is the first cell
	frontier.push(minIndex);
	parent[minIndex] = null;

	var canvas = d3.select("body").append("canvas")
	.attr("width", width)
	.attr("height", height);

	var context = canvas.node().getContext("2d");

	context.translate(
	Math.round((width - cellWidth * cellSize - (cellWidth + 1) * cellSpacing) / 2),
	Math.round((height - cellHeight * cellSize - (cellHeight + 1) * cellSpacing) / 2)
	);

	context.fillStyle = "#fff";
	for (var y = 0, i = 0; y < cellHeight; ++y) {
	for (var x = 0; x < cellWidth; ++x, ++i) {
	fillCell(i);
	if (cells[i] & S) fillSouth(i);
	if (cells[i] & E) fillEast(i);
	}
	}

	var interval_value = 100;

	context.fillStyle = "#777";
	d3.timer(function() {
	for (var i = 0; i < interval_value; ++i) {
	if (exploreFrontier()) {
	console.log('Finished timer.')
	return true;
	}
	}
	});

	function fillPath(i1) {
	while (true) {
	fillCell(i1);
	var i0 = parent[i1];
	if (i0 == null) break;
	(Math.abs(i0 - i1) === 1 ? fillEast : fillSouth)(Math.min(i0, i1));
	i1 = i0;
	}
	}

	function fillCell(i) {
	var x = i % cellWidth, y = i / cellWidth \| 0;
	context.fillRect(x * cellSize + (x + 1) * cellSpacing, y * cellSize + (y + 1) * cellSpacing, cellSize, cellSize);
	}

	function fillEast(i) {
	var x = i % cellWidth, y = i / cellWidth \| 0;
	context.fillRect((x + 1) * (cellSize + cellSpacing), y * cellSize + (y + 1) * cellSpacing, cellSpacing, cellSize);
	}

	function fillSouth(i) {
	var x = i % cellWidth, y = i / cellWidth \| 0;
	context.fillRect(x * cellSize + (x + 1) * cellSpacing, (y + 1) * (cellSize + cellSpacing), cellSize, cellSpacing);
	}

	function generateMazeRandom(cellWidth, cellHeight) {
	var cells = new Array(cellWidth * cellHeight),
	frontier = [],
	startIndex = (cellHeight - 1) * cellWidth;

	cells[startIndex] = 0;
	frontier.push({index: startIndex, direction: N});
	frontier.push({index: startIndex, direction: E});

	while ((edge = popRandom(frontier)) != null) {
	var edge,
	i0 = edge.index,
	d0 = edge.direction,
	i1 = i0 + (d0 === N ? -cellWidth : d0 === S ? cellWidth : d0 === W ? -1 : +1),
	x0 = i0 % cellWidth,
	y0 = i0 / cellWidth \| 0,
	x1,
	y1,
	d1,
	open = cells[i1] == null; // opposite not yet part of the maze

	if (d0 === N) x1 = x0, y1 = y0 - 1, d1 = S;
	else if (d0 === S) x1 = x0, y1 = y0 + 1, d1 = N;
	else if (d0 === W) x1 = x0 - 1, y1 = y0, d1 = E;
	else x1 = x0 + 1, y1 = y0, d1 = W;

	if (open) {
	cells[i0] \|= d0, cells[i1] \|= d1;
	if (y1 > 0 && cells[i1 - cellWidth] == null) frontier.push({index: i1, direction: N});
	if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) frontier.push({index: i1, direction: S});
	if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W});
	if (x1 < cellWidth - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: E});
	}
	}

	return cells;
	}

	function generateMazeWilson(width, height) {
	var cells = new Array(width * height), // each cell’s edge bits
	remaining = d3.range(width * height), // cell indexes to visit
	previous = new Array(width * height); // current random walk

	// Add the starting cell.
	var start = remaining.pop();
	cells[start] = 0;

	// While there are remaining cells,
	// add a loop-erased random walk to the maze.
	while (!loopErasedRandomWalk());

	return cells;

	function loopErasedRandomWalk() {
	var direction,
	index0,
	index1,
	i,
	j;

	// Pick a location that’s not yet in the maze (if any).
	do if ((index0 = remaining.pop()) == null) return true;
	while (cells[index0] >= 0);

	// Perform a random walk starting at this location,
	previous[index0] = index0;
	while (true) {
	i = index0 % width;
	j = index0 / width \| 0;

	// picking a legal random direction at each step.
	direction = Math.random() * 4 \| 0;
	if (direction === 0) { if (j <= 0) continue; --j; }
	else if (direction === 1) { if (j >= height - 1) continue; ++j; }
	else if (direction === 2) { if (i <= 0) continue; --i; }
	else { if (i >= width - 1) continue; ++i; }

	// If this new cell was visited previously during this walk,
	// erase the loop, rewinding the path to its earlier state.
	// Otherwise, just add it to the walk.
	index1 = j * width + i;
	if (previous[index1] >= 0) eraseWalk(index0, index1);
	else previous[index1] = index0;
	index0 = index1;

	// If this cell is part of the maze, we’re done walking.
	if (cells[index1] >= 0) {

	// Add the random walk to the maze by backtracking to the starting cell.
	// Also erase this walk’s history to not interfere with subsequent walks.
	while ((index0 = previous[index1]) !== index1) {
	direction = index1 - index0;
	if (direction === 1) cells[index0] \|= E, cells[index1] \|= W;
	else if (direction === -1) cells[index0] \|= W, cells[index1] \|= E;
	else if (direction < 0) cells[index0] \|= N, cells[index1] \|= S;
	else cells[index0] \|= S, cells[index1] \|= N;
	previous[index1] = NaN;
	index1 = index0;
	}

	previous[index1] = NaN;
	return;
	}
	}
	}

	function eraseWalk(index0, index1) {
	var index;
	while ((index = previous[index0]) !== index1) previous[index0] = NaN, index0 = index;
	previous[index0] = NaN;
	}
	}

	function popRandom(array) {
	if (!array.length) return;
	var n = array.length, i = Math.random() * n \| 0, t;
	t = array[i], array[i] = array[n - 1], array[n - 1] = t;
	return array.pop();
	}

	function exploreFrontier() {
	// this is how the frontier variable you supply is used
	var i0 = frontier.pop(),
	s0 = score(i0);

	fillCell(i0);

	if (s0 < minScore) {
	fillPath(minIndex);
	context.fillStyle = "magenta";
	minScore = s0, minIndex = i0;
	fillPath(minIndex);
	context.fillStyle = "#777";
	console.log(s0);
	if (!s0) {
	console.log('Finished');
	return true;
	}
	}

	expandFrontier(i0);
	}

	function priorityQueue(compare) {
	var queue = {},
	array = [],
	size = 0;

	queue.empty = function() {
	return !size;
	};

	queue.push = function(value) {
	up(array[size] = value, size++);
	return size;
	};

	queue.pop = function() {
	if (size <= 0) return;
	var removed = array[0], value;
	if (--size > 0) value = array[size], down(array[0] = value, 0);
	return removed;
	};

	function up(value, i) {
	while (i > 0) {
	var j = ((i + 1) >> 1) - 1,
	parent = array[j];
	if (compare(value, parent) >= 0) break;
	array[i] = parent;
	array[i = j] = value;
	}
	}

	function down(value, i) {
	while (true) {
	var r = (i + 1) << 1,
	l = r - 1,
	j = i,
	child = array[j];
	if (l < size && compare(array[l], child) < 0) child = array[j = l];
	if (r < size && compare(array[r], child) < 0) child = array[j = r];
	if (j === i) break;
	array[i] = child;
	array[i = j] = value;
	}
	}

	return queue;
	}

	function score(i) {
	var x = goalX - (i % cellWidth), y = goalY - (i / cellWidth \| 0);
	return x * x + y * y;
	}

	function nextCellIndex(i0, direction) {
	switch (direction) {
	case E: i1 = i0 + 1; break;
	case W: i1 = i0 - 1; break;
	case S: i1 = i0 + cellWidth; break;
	case N: i1 = i0 - cellWidth; break;
	default: prompt('Error: Unknown direction!');
	}
	return i1;
	}

	// checks whether you can go from cell i0 in the given direction
	// returns false if that is the direction you came from
	function isFree(i0, direction) {
	i1 = nextCellIndex(i0, direction);
	if (cells[i0] & direction && isNaN(parent[i1])) return i1;
	return false;
	}

	// fills the appropriate cell in the given direction from cell i0 with gray colour
	function fillGray(i0, direction) {
	var i1 = nextCellIndex(i0, direction)
	switch (direction) {
	case E: fillEast(i0); break;
	case W: fillEast(i1); break;
	case S: fillSouth(i0); break;
	case N: fillSouth(i1); break;
	default: prompt('Error: Unknown direction!');
	}
	}

	function generateMaze(cellWidth, cellHeight) {
	return generateMazeWilson(cellWidth, cellHeight);
	// return generateMazeRandom(cellWidth, cellHeight);
	}

	function frontier_func() {
	return [];
	}



	// START LOOKING HERE

	// Returns a random integer between min (inclusive) and max (exclusive)
	function getRandomInt(min, max) {
	return Math.floor(Math.random() * (max - min)) + min;
	}

	function expandFrontier(i0) {
	// You are at cell i0, i0 is the current cell index (address)

	var directions = [E, W, S, N];

	// example
	// This is the code that only tries to go East

	// What is the index (address) of the cell in the direction East from i0, the current cell?
	i1 = nextCellIndex(i0, E);
	if (isFree(i0, E)) {
	// Inform the system that you came to cell i1 from i0 by setting the parent of i1 to i0
	parent[i1] = i0;
	// Fill in the new cell with gray colour to show that we've visited that cell
	fillGray(i0, E);
	// Add the new cell to the list of the new cells to be explored/visited
	frontier.push(i1)
	}

	/*
	Tasks:
	1. Modify the script to try going East and North.
	2. Modify the script to try going in all directions. Does the order matter?
	*/

	}

	</script>