syntagmatic/README.md

## README.md

      
      Raw
    
  
              README.md
            
          
    Another variation of color-cycling a spanning tree generated by Prim’s algorithm. Here the periodicity of the color scale by tree depth is varied over time, alternating between emphasis of micro and macro structure. This idea was suggested in a Hacker News comment.

  
## generate-prims.js
var N = 1 << 0,
    S = 1 << 1,
    W = 1 << 2,
    E = 1 << 3;

self.addEventListener("message", function(event) {
  postMessage(generateMaze(event.data.width, event.data.height));
});

function generateMaze(cellWidth, cellHeight) {
  var cells = new Array(cellWidth * cellHeight),
      frontier = minHeap(function(a, b) { return a.weight - b.weight; }),
      startIndex = (cellHeight - 1) * cellWidth;

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

  while ((edge = frontier.pop()) != 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, weight: Math.random()});
      if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) frontier.push({index: i1, direction: S, weight: Math.random()});
      if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W, weight: Math.random()});
      if (x1 < cellWidth - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: E, weight: Math.random()});
    }
  }

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

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

#wait {
  padding: 10px;
  position: absolute;
}

canvas {
  position: relative;
}

</style>
<div id="wait">Generating maze; please wait…</div>
<canvas width="960" height="500"></canvas>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script>

var canvas = d3.select("canvas"),
    context = canvas.node().getContext("2d"),
    width = canvas.property("width"),
    height = canvas.property("height");


var brewer = ["#ffffd9","#edf8b1","#c7e9b4","#7fcdbb","#41b6c4","#1d91c0","#225ea8","#253494","#081d58"];

var brewerupdown = brewer.slice(0);
brewerupdown = brewerupdown.concat(brewer.reverse().slice(1))

var color = d3.scale.linear()
  .domain(d3.range(0,360,360/brewerupdown.length))
  .range(brewerupdown)
  .interpolate(d3.interpolateLab);

var colors = d3.range(360)
    .map((function() {
      return function(i) {
        return d3.rgb(color(i));
      };
    })());

var worker = new Worker("generate-prims.js");
worker.postMessage({width: width, height: height});
worker.addEventListener("message", function(event) {
  worker.terminate();

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

  var d = 0,
      r = -1,
      n = width * height,
      cells = event.data,
      distance = new Array(n),
      frontier = [(height - 1) * width],
      image = context.createImageData(width, height),
      imageData = image.data;

  distance[frontier[0]] = 0;

  for (var i = 0, c, i4 = 3; i < n; ++i, i4 += 4) {
    imageData[i4] = 255;
  }

  while (frontier.length) {
    var frontier1 = [],
        i0,
        n0 = frontier.length,
        i1;

    ++d;
    for (var i = 0; i < n0; ++i) {
      i0 = frontier[i];
      if (cells[i0] & E && distance[i1 = i0 + 1] == null) distance[i1] = d, frontier1.push(i1);
      if (cells[i0] & W && distance[i1 = i0 - 1] == null) distance[i1] = d, frontier1.push(i1);
      if (cells[i0] & S && distance[i1 = i0 + width] == null) distance[i1] = d, frontier1.push(i1);
      if (cells[i0] & N && distance[i1 = i0 - width] == null) distance[i1] = d, frontier1.push(i1);
    }

    frontier = frontier1;
  }

  d3.timer(function(elapsed) {
    for (var i = 0, c, i4 = 0, s = 1.1 - Math.cos(elapsed / 9000); i < n; ++i, i4 += 4) {
      c = colors[(c = Math.floor(distance[i] * s) % 360) < 0 ? c + 360 : c];
      imageData[i4] = c.r;
      imageData[i4 + 1] = c.g;
      imageData[i4 + 2] = c.b;
    }
    context.putImageData(image, 0, 0);
  });
});

</script>

## thumbnail.png

      
      Raw
    
  
              thumbnail.png
	var N = 1 << 0,
	S = 1 << 1,
	W = 1 << 2,
	E = 1 << 3;

	self.addEventListener("message", function(event) {
	postMessage(generateMaze(event.data.width, event.data.height));
	});

	function generateMaze(cellWidth, cellHeight) {
	var cells = new Array(cellWidth * cellHeight),
	frontier = minHeap(function(a, b) { return a.weight - b.weight; }),
	startIndex = (cellHeight - 1) * cellWidth;

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

	while ((edge = frontier.pop()) != 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, weight: Math.random()});
	if (y1 < cellHeight - 1 && cells[i1 + cellWidth] == null) frontier.push({index: i1, direction: S, weight: Math.random()});
	if (x1 > 0 && cells[i1 - 1] == null) frontier.push({index: i1, direction: W, weight: Math.random()});
	if (x1 < cellWidth - 1 && cells[i1 + 1] == null) frontier.push({index: i1, direction: E, weight: Math.random()});
	}
	}

	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;
	}
	<!DOCTYPE html>
	<meta charset="utf-8">
	<style>

	#wait {
	padding: 10px;
	position: absolute;
	}

	canvas {
	position: relative;
	}

	</style>
	<div id="wait">Generating maze; please wait…</div>
	<canvas width="960" height="500"></canvas>
	<script src="http://d3js.org/d3.v3.min.js"></script>
	<script>

	var canvas = d3.select("canvas"),
	context = canvas.node().getContext("2d"),
	width = canvas.property("width"),
	height = canvas.property("height");


	var brewer = ["#ffffd9","#edf8b1","#c7e9b4","#7fcdbb","#41b6c4","#1d91c0","#225ea8","#253494","#081d58"];

	var brewerupdown = brewer.slice(0);
	brewerupdown = brewerupdown.concat(brewer.reverse().slice(1))

	var color = d3.scale.linear()
	.domain(d3.range(0,360,360/brewerupdown.length))
	.range(brewerupdown)
	.interpolate(d3.interpolateLab);

	var colors = d3.range(360)
	.map((function() {
	return function(i) {
	return d3.rgb(color(i));
	};
	})());

	var worker = new Worker("generate-prims.js");
	worker.postMessage({width: width, height: height});
	worker.addEventListener("message", function(event) {
	worker.terminate();

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

	var d = 0,
	r = -1,
	n = width * height,
	cells = event.data,
	distance = new Array(n),
	frontier = [(height - 1) * width],
	image = context.createImageData(width, height),
	imageData = image.data;

	distance[frontier[0]] = 0;

	for (var i = 0, c, i4 = 3; i < n; ++i, i4 += 4) {
	imageData[i4] = 255;
	}

	while (frontier.length) {
	var frontier1 = [],
	i0,
	n0 = frontier.length,
	i1;

	++d;
	for (var i = 0; i < n0; ++i) {
	i0 = frontier[i];
	if (cells[i0] & E && distance[i1 = i0 + 1] == null) distance[i1] = d, frontier1.push(i1);
	if (cells[i0] & W && distance[i1 = i0 - 1] == null) distance[i1] = d, frontier1.push(i1);
	if (cells[i0] & S && distance[i1 = i0 + width] == null) distance[i1] = d, frontier1.push(i1);
	if (cells[i0] & N && distance[i1 = i0 - width] == null) distance[i1] = d, frontier1.push(i1);
	}

	frontier = frontier1;
	}

	d3.timer(function(elapsed) {
	for (var i = 0, c, i4 = 0, s = 1.1 - Math.cos(elapsed / 9000); i < n; ++i, i4 += 4) {
	c = colors[(c = Math.floor(distance[i] * s) % 360) < 0 ? c + 360 : c];
	imageData[i4] = c.r;
	imageData[i4 + 1] = c.g;
	imageData[i4 + 2] = c.b;
	}
	context.putImageData(image, 0, 0);
	});
	});

	</script>