sorpaas/README.md

## README.md

      
    Raw
  

              README.md
            
          
    Using best-first search.

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

body {
  background: #000;
}

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

var width = 960 * 2,
    height = 500 * 2,
    cellSize = 2,
    cellWidth = Math.ceil(width / cellSize),
    cellHeight = Math.ceil(height / cellSize);

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

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

var maze = generateMaze(cellWidth, cellHeight),
    parent = d3.range(cellHeight * cellWidth).map(function() { return NaN; }),
    minScore = Infinity,
    minIndex = index(1, cellHeight - 2),
    goalX = cellWidth - 2 - !((cellWidth & 1) | (cellHeight & 1)),
    goalY = 1,
    goalIndex = index(goalX, goalY),
    frontier = minHeap(function(a, b) { return score(a) - score(b); });

frontier.push(minIndex);

context.fillStyle = "#fff";
for (var y = 0, i = 0; y < cellHeight; ++y) {
  for (var x = 0; x < cellWidth; ++x, ++i) {
    if (!maze[i]) fillCell(i);
  }
}

context.fillStyle = "#777";

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

function exploreFrontier() {
  var i0 = frontier.pop(),
      x0 = i0 % cellWidth,
      y0 = i0 / cellWidth | 0,
      s0 = score(i0),
      i1;

  fillCell(i0);
  maze[i0] = 2;

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

  if (i0 === goalIndex) return true;

  context.fillStyle = "cyan";
  if (!maze[i1 = index(x1 = x0 + 1, y1 = y0)]) parent[i1] = i0, frontier.push(i1), fillCell(i1);
  if (!maze[i1 = index(x1 = x0 - 1, y1 = y0)]) parent[i1] = i0, frontier.push(i1), fillCell(i1);
  if (!maze[i1 = index(x1 = x0, y1 = y0 + 1)]) parent[i1] = i0, frontier.push(i1), fillCell(i1);
  if (!maze[i1 = index(x1 = x0, y1 = y0 - 1)]) parent[i1] = i0, frontier.push(i1), fillCell(i1);
  context.fillStyle = "#777";
}

function fillPath(i) {
  do fillCell(i); while (!isNaN(i = parent[i]));
}

function fillCell(i) {
  context.fillRect((i % cellWidth) * cellSize, (i / cellWidth | 0) * cellSize, cellSize, cellSize);
}

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

function index(x, y) {
  return y * cellWidth + x;
}

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 generateMaze(cellWidth, cellHeight) {
  var maze = d3.range(cellHeight * cellWidth).map(function() { return 1; }), frontier = [];
  addToMaze(1, cellHeight - 2);
  addToFrontier(2, cellHeight - 2);
  addToFrontier(1, cellHeight - 3);
  while (!exploreFrontier());
  return maze;

  function addToMaze(x, y) {
    var i = index(x, y);
    maze[i] = 0;
  }

  function addToFrontier(x, y) {
    var i = index(x, y);
    if (!maze[i]) return;
    frontier.push(i);
  }

  function exploreFrontier() {
    if (!frontier.length) return true;
    var i = frontier.splice(Math.random() * frontier.length | 0, 1)[0], // slow
        x = i % cellWidth,
        y = i / cellWidth | 0,
        ox,
        oy,
        oi = x > 0 && !maze[index(x - 1, y)] ? (x < cellWidth - 1 ? index(ox = x + 1, oy = y) : NaN)
            : x < cellWidth - 1 && !maze[index(x + 1, y)] ? (x > 0 ? index(ox = x - 1, oy = y) : NaN)
            : y > 0 && !maze[index(x, y - 1)] ? (y < cellHeight - 1 ? index(ox = x, oy = y + 1) : NaN)
            : y < cellHeight - 1 && !maze[index(x, y + 1)] ? (y > 0 ? index(ox = x, oy = y - 1) : NaN)
            : NaN;

    if (maze[oi]) { // opposite cell is filled
      addToMaze(x, y);
      var inside = true;
      if (ox > 0) addToFrontier(ox - 1, oy); else inside = false;
      if (ox < cellWidth - 1) addToFrontier(ox + 1, oy); else inside = false;
      if (oy > 0) addToFrontier(ox, oy - 1); else inside = false;
      if (oy < cellHeight - 1) addToFrontier(ox, oy + 1); else inside = false;
      if (inside) addToMaze(ox, oy);
    }
  }
}

</script>

## thumbnail.png

      
    Raw
  

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

	body {
	background: #000;
	}

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

	var width = 960 * 2,
	height = 500 * 2,
	cellSize = 2,
	cellWidth = Math.ceil(width / cellSize),
	cellHeight = Math.ceil(height / cellSize);

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

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

	var maze = generateMaze(cellWidth, cellHeight),
	parent = d3.range(cellHeight * cellWidth).map(function() { return NaN; }),
	minScore = Infinity,
	minIndex = index(1, cellHeight - 2),
	goalX = cellWidth - 2 - !((cellWidth & 1) \| (cellHeight & 1)),
	goalY = 1,
	goalIndex = index(goalX, goalY),
	frontier = minHeap(function(a, b) { return score(a) - score(b); });

	frontier.push(minIndex);

	context.fillStyle = "#fff";
	for (var y = 0, i = 0; y < cellHeight; ++y) {
	for (var x = 0; x < cellWidth; ++x, ++i) {
	if (!maze[i]) fillCell(i);
	}
	}

	context.fillStyle = "#777";

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

	function exploreFrontier() {
	var i0 = frontier.pop(),
	x0 = i0 % cellWidth,
	y0 = i0 / cellWidth \| 0,
	s0 = score(i0),
	i1;

	fillCell(i0);
	maze[i0] = 2;

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

	if (i0 === goalIndex) return true;

	context.fillStyle = "cyan";
	if (!maze[i1 = index(x1 = x0 + 1, y1 = y0)]) parent[i1] = i0, frontier.push(i1), fillCell(i1);
	if (!maze[i1 = index(x1 = x0 - 1, y1 = y0)]) parent[i1] = i0, frontier.push(i1), fillCell(i1);
	if (!maze[i1 = index(x1 = x0, y1 = y0 + 1)]) parent[i1] = i0, frontier.push(i1), fillCell(i1);
	if (!maze[i1 = index(x1 = x0, y1 = y0 - 1)]) parent[i1] = i0, frontier.push(i1), fillCell(i1);
	context.fillStyle = "#777";
	}

	function fillPath(i) {
	do fillCell(i); while (!isNaN(i = parent[i]));
	}

	function fillCell(i) {
	context.fillRect((i % cellWidth) * cellSize, (i / cellWidth \| 0) * cellSize, cellSize, cellSize);
	}

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

	function index(x, y) {
	return y * cellWidth + x;
	}

	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 generateMaze(cellWidth, cellHeight) {
	var maze = d3.range(cellHeight * cellWidth).map(function() { return 1; }), frontier = [];
	addToMaze(1, cellHeight - 2);
	addToFrontier(2, cellHeight - 2);
	addToFrontier(1, cellHeight - 3);
	while (!exploreFrontier());
	return maze;

	function addToMaze(x, y) {
	var i = index(x, y);
	maze[i] = 0;
	}

	function addToFrontier(x, y) {
	var i = index(x, y);
	if (!maze[i]) return;
	frontier.push(i);
	}

	function exploreFrontier() {
	if (!frontier.length) return true;
	var i = frontier.splice(Math.random() * frontier.length \| 0, 1)[0], // slow
	x = i % cellWidth,
	y = i / cellWidth \| 0,
	ox,
	oy,
	oi = x > 0 && !maze[index(x - 1, y)] ? (x < cellWidth - 1 ? index(ox = x + 1, oy = y) : NaN)
	: x < cellWidth - 1 && !maze[index(x + 1, y)] ? (x > 0 ? index(ox = x - 1, oy = y) : NaN)
	: y > 0 && !maze[index(x, y - 1)] ? (y < cellHeight - 1 ? index(ox = x, oy = y + 1) : NaN)
	: y < cellHeight - 1 && !maze[index(x, y + 1)] ? (y > 0 ? index(ox = x, oy = y - 1) : NaN)
	: NaN;

	if (maze[oi]) { // opposite cell is filled
	addToMaze(x, y);
	var inside = true;
	if (ox > 0) addToFrontier(ox - 1, oy); else inside = false;
	if (ox < cellWidth - 1) addToFrontier(ox + 1, oy); else inside = false;
	if (oy > 0) addToFrontier(ox, oy - 1); else inside = false;
	if (oy < cellHeight - 1) addToFrontier(ox, oy + 1); else inside = false;
	if (inside) addToMaze(ox, oy);
	}
	}
	}

	</script>