Maze Hover by mbostock

index.html

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

body {
  background: #000;
}

</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>

var width = 960,
    height = 960;

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)),
    marginLeft = Math.round((width - cellWidth * cellSize - (cellWidth + 1) * cellSpacing) / 2),
    marginTop = Math.round((height - cellHeight * cellSize - (cellHeight + 1) * cellSpacing) / 2),
    cells = generateMaze(cellWidth, cellHeight), // each cell’s edge bits
    parents = computeParents(cells, cellWidth, cellHeight),
    hoverIndex = cellWidth - 1;

var canvas = d3.select("body").append("canvas")
    .attr("width", width)
    .attr("height", height)
    .on("ontouchstart" in document ? "touchmove" : "mousemove", mousemoved);

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

context.translate(marginLeft, marginTop);

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);
  }
}

context.fillStyle = "#f00";
fillPath(hoverIndex);

function mousemoved() {
  var m = d3.mouse(this),
      x = Math.max(0, Math.min(cellWidth - 1, Math.floor((m[0] - marginLeft - cellSpacing) / (cellSize + cellSpacing)))),
      y = Math.max(0, Math.min(cellHeight - 1, Math.floor((m[1] - marginTop - cellSpacing) / (cellSize + cellSpacing))));
  context.fillStyle = "#fff";
  fillPath(hoverIndex);
  context.fillStyle = "#f00";
  fillPath(hoverIndex = y * cellWidth + x);
}

function fillPath(i0) {
  var i1;
  while (true) {
    i1 = parents[i0];
    fillCell(i0);
    if (i1 === i0 - 1) fillEast(i1);
    else if (i1 === i0 + 1) fillEast(i0);
    else if (i1 === i0 - cellWidth) fillSouth(i1);
    else if (i1 === i0 + cellWidth) fillSouth(i0);
    else break;
    i0 = i1;
  }
}

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 computeParents(cells, width, height) {
  var parents = new Array(width * height),
      i0 = (height - 1) * width,
      i1,
      frontier = [i0];

  parents[i0] = i0;

  while ((i0 = frontier.pop()) != null) {
    if (cells[i0] & E && isNaN(parents[i1 = i0 + 1])) parents[i1] = i0, frontier.push(i1);
    if (cells[i0] & W && isNaN(parents[i1 = i0 - 1])) parents[i1] = i0, frontier.push(i1);
    if (cells[i0] & S && isNaN(parents[i1 = i0 + width])) parents[i1] = i0, frontier.push(i1);
    if (cells[i0] & N && isNaN(parents[i1 = i0 - width])) parents[i1] = i0, frontier.push(i1);
  }

  return parents;
}

function generateMaze(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 i0,
        i1,
        x0,
        y0;

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

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

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

      // If this new cell was visited previously during this walk,
      // erase the loop, rewinding the path to its earlier state.
      if (previous[i1] >= 0) eraseWalk(i0, i1);

      // Otherwise, just add it to the walk.
      else previous[i1] = i0;

      // If this cell is part of the maze, we’re done walking.
      if (cells[i1] >= 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 ((i0 = previous[i1]) !== i1) {
          if (i1 === i0 + 1) cells[i0] |= E, cells[i1] |= W;
          else if (i1 === i0 - 1) cells[i0] |= W, cells[i1] |= E;
          else if (i1 === i0 + width) cells[i0] |= S, cells[i1] |= N;
          else cells[i0] |= N, cells[i1] |= S;
          previous[i1] = NaN;
          i1 = i0;
        }

        previous[i1] = NaN;
        return;
      }

      i0 = i1;
    }
  }

  function eraseWalk(i0, i2) {
    var i1;
    do i1 = previous[i0], previous[i0] = NaN, i0 = i1; while (i1 !== i2);
  }
}

d3.select(self.frameElement).style("height", height + "px");

</script>