mbostock/.block

## .block
license: gpl-3.0
redirect: https://observablehq.com/@mbostock/best-first-search

## README.md

      
    Raw
  

              README.md
            
          
    This maze is generated using random traversal, and then solved using best-first search. Compare to random search. See best-first search on a maze generated using Wilson’s algorithm.

  
## 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 = 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,
    frontier = minHeap(function(a, b) { return score(a) - score(b); });

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

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

function exploreFrontier() {
  var i0 = frontier.pop(),
      i1,
      s0 = score(i0);

  fillCell(i0);

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

  if (cells[i0] & E && isNaN(parent[i1 = i0 + 1])) parent[i1] = i0, fillEast(i0), frontier.push(i1);
  if (cells[i0] & W && isNaN(parent[i1 = i0 - 1])) parent[i1] = i0, fillEast(i1), frontier.push(i1);
  if (cells[i0] & S && isNaN(parent[i1 = i0 + cellWidth])) parent[i1] = i0, fillSouth(i0), frontier.push(i1);
  if (cells[i0] & N && isNaN(parent[i1 = i0 - cellWidth])) parent[i1] = i0, fillSouth(i1), frontier.push(i1);
}

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 score(i) {
  var x = goalX - (i % cellWidth), y = goalY - (i / cellWidth | 0);
  return x * x + y * y;
}

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 generateMaze(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 minHeap(compare) {
  var heap = {},
      array = [],
      size = 0;

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

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

  heap.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 heap;
}

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

</script>

## thumbnail.png

      
    Raw
  

              thumbnail.png
	license: gpl-3.0
	redirect: https://observablehq.com/@mbostock/best-first-search
	<!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 = 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,
	frontier = minHeap(function(a, b) { return score(a) - score(b); });

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

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

	function exploreFrontier() {
	var i0 = frontier.pop(),
	i1,
	s0 = score(i0);

	fillCell(i0);

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

	if (cells[i0] & E && isNaN(parent[i1 = i0 + 1])) parent[i1] = i0, fillEast(i0), frontier.push(i1);
	if (cells[i0] & W && isNaN(parent[i1 = i0 - 1])) parent[i1] = i0, fillEast(i1), frontier.push(i1);
	if (cells[i0] & S && isNaN(parent[i1 = i0 + cellWidth])) parent[i1] = i0, fillSouth(i0), frontier.push(i1);
	if (cells[i0] & N && isNaN(parent[i1 = i0 - cellWidth])) parent[i1] = i0, fillSouth(i1), frontier.push(i1);
	}

	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 score(i) {
	var x = goalX - (i % cellWidth), y = goalY - (i / cellWidth \| 0);
	return x * x + y * y;
	}

	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 generateMaze(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 minHeap(compare) {
	var heap = {},
	array = [],
	size = 0;

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

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

	heap.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 heap;
	}

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

	</script>