seako/README.md

## README.md

      
    Raw
  

              README.md
            
          
    tweaking the colors of mbostock's Color Flood III
Prim’s algorithm is used to flood a 960×500 canvas with color.
Compare to Wilson’s algorithm and randomized breadth-first traversal.

  
## index.html
<!DOCTYPE html>
<meta charset="utf-8">
<body>
<script src="http://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 cells = new Array(width * height), // each cell’s edge bits
    frontier = minHeap(function(a, b) { return a.weight - b.weight; });

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

var context = canvas.node().getContext("2d"),
    image = context.createImageData(1, 1);

// Add a random cell and two initial edges.
var start = (height - 1) * width;
cells[start] = 0;
context.fillStyle = d3.hsl(0, 1, .5) + "";
context.fillRect(0, height - 1, 1, 1);
frontier.push({index: start, direction: N, distance: 1, weight: Math.random()});
frontier.push({index: start, direction: E, distance: 1, weight: Math.random()});

// Explore the frontier until the tree spans the graph.
d3.timer(function() {
  var done, k = 0;
  while (++k < 1000 && !(done = exploreFrontier()));
  return done;
});

function saturation(hue) {
  var s;
  if (hue >= 70 && hue <= 150) s = 1 - Math.abs(Math.cos(hue) / 20);
  else s = .6;
  return s;
};

function luminosity(hue) {
  var l
  if (hue >= 70 && hue <= 150) l = .5 + Math.abs(Math.sin(hue) / 20);
  else l = .5 + Math.abs(Math.sin(hue) / 10);
  return l;
};

function exploreFrontier() {
  if ((edge = frontier.pop()) == null) return true;

  var edge,
      i0 = edge.index,
      d0 = edge.direction,
      i1;

  if (d0 === N) i1 = i0 - width;
  else if (d0 === S) i1 = i0 + width;
  else if (d0 === W) i1 = i0 - 1;
  else i1 = i0 + 1;

  if (cells[i1] == null) { // not yet part of the maze
    var x0 = i0 % width,
        y0 = i0 / width | 0,
        x1,
        y1,
        d1,
        z0 = edge.distance,
        z1 = z0 + 1,
        hue = z0 % 360,
        sat = saturation(hue),
        lum = luminosity(hue),
        color = d3.hsl(hue, sat, lum).rgb();

    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;

    cells[i0] |= d0, cells[i1] |= d1;

    image.data[0] = color.r;
    image.data[1] = color.g;
    image.data[2] = color.b;
    image.data[3] = color.g;
    context.putImageData(image, x1, y1);

    if (y1 > 0 && !cells[i1 - width]) frontier.push({index: i1, direction: N, distance: z1, weight: Math.random()});
    if (y1 < height - 1 && !cells[i1 + width]) frontier.push({index: i1, direction: S, distance: z1, weight: Math.random()});
    if (x1 > 0 && !cells[i1 - 1]) frontier.push({index: i1, direction: W, distance: z1, weight: Math.random()});
    if (x1 < width - 1 && !cells[i1 + 1]) frontier.push({index: i1, direction: E, distance: z1, weight: Math.random()});
  }
}

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

</script>

## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!DOCTYPE html>
	<meta charset="utf-8">
	<body>
	<script src="http://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 cells = new Array(width * height), // each cell’s edge bits
	frontier = minHeap(function(a, b) { return a.weight - b.weight; });

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

	var context = canvas.node().getContext("2d"),
	image = context.createImageData(1, 1);

	// Add a random cell and two initial edges.
	var start = (height - 1) * width;
	cells[start] = 0;
	context.fillStyle = d3.hsl(0, 1, .5) + "";
	context.fillRect(0, height - 1, 1, 1);
	frontier.push({index: start, direction: N, distance: 1, weight: Math.random()});
	frontier.push({index: start, direction: E, distance: 1, weight: Math.random()});

	// Explore the frontier until the tree spans the graph.
	d3.timer(function() {
	var done, k = 0;
	while (++k < 1000 && !(done = exploreFrontier()));
	return done;
	});

	function saturation(hue) {
	var s;
	if (hue >= 70 && hue <= 150) s = 1 - Math.abs(Math.cos(hue) / 20);
	else s = .6;
	return s;
	};

	function luminosity(hue) {
	var l
	if (hue >= 70 && hue <= 150) l = .5 + Math.abs(Math.sin(hue) / 20);
	else l = .5 + Math.abs(Math.sin(hue) / 10);
	return l;
	};

	function exploreFrontier() {
	if ((edge = frontier.pop()) == null) return true;

	var edge,
	i0 = edge.index,
	d0 = edge.direction,
	i1;

	if (d0 === N) i1 = i0 - width;
	else if (d0 === S) i1 = i0 + width;
	else if (d0 === W) i1 = i0 - 1;
	else i1 = i0 + 1;

	if (cells[i1] == null) { // not yet part of the maze
	var x0 = i0 % width,
	y0 = i0 / width \| 0,
	x1,
	y1,
	d1,
	z0 = edge.distance,
	z1 = z0 + 1,
	hue = z0 % 360,
	sat = saturation(hue),
	lum = luminosity(hue),
	color = d3.hsl(hue, sat, lum).rgb();

	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;

	cells[i0] \|= d0, cells[i1] \|= d1;

	image.data[0] = color.r;
	image.data[1] = color.g;
	image.data[2] = color.b;
	image.data[3] = color.g;
	context.putImageData(image, x1, y1);

	if (y1 > 0 && !cells[i1 - width]) frontier.push({index: i1, direction: N, distance: z1, weight: Math.random()});
	if (y1 < height - 1 && !cells[i1 + width]) frontier.push({index: i1, direction: S, distance: z1, weight: Math.random()});
	if (x1 > 0 && !cells[i1 - 1]) frontier.push({index: i1, direction: W, distance: z1, weight: Math.random()});
	if (x1 < width - 1 && !cells[i1 + 1]) frontier.push({index: i1, direction: E, distance: z1, weight: Math.random()});
	}
	}

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

	</script>