sunetos/hillclimb.js

## hillclimb.js
/**
 * @preserve
 *
 * Javascript Hill Climb Algorithm.
 * @author Adam R. Smith http://codi.st/
 *
 * Licensed under the new BSD License:
 * http://www.opensource.org/licenses/bsd-license.php
 */

var c3d = c3d || {};
c3d.MIN_INT = (1<<31);
c3d.MAX_INT = ((1<<30) - 1) | (1<<30);

/**
 * Hill climb algorithm object, steppable.
 * This version is flexible and easy to use for educational purposes.
 * For high performance needs the functions should probably be inlined
 * in a custom class/function, and it should step until complete automatically.
 * Inlining could be done with a JS compiler like Closure.
 *
 * @constructor
 */
c3d.HillClimb = function(neighborsFunc, valueFunc, start, steepest) {
	this.neighborsFunc = neighborsFunc;
	this.valueFunc = valueFunc;
	this.setNode(start);
	this.steps = 0;
	this.steepest = !!steepest;
};

/** Avoid mistakes by always setting the value to match the node. */
c3d.HillClimb.prototype.setNode = function(node) {
	this.node = node;
	this.value = this.valueFunc(node);
};

/** Run one or more steps toward the solution. */
c3d.HillClimb.prototype.step = function(stepCount) {
	if (!stepCount || stepCount < 0) stepCount = 1<<30;
	var neighborsFunc = this.neighborsFunc, valueFunc = this.valueFunc, steepest = this.steepest;
	var node = this.node, value = this.value, i = 0;
	for (i = 0; i < stepCount; ++i) {
		var nbs = neighborsFunc(node), nbsl = nbs.length;
		var nextVal = value;
		var nextNode = node;
		for (var j = 0; j < nbsl; ++j) {
			var nb = nbs[j];
			var nbVal = valueFunc(nb);
			if (nbVal > nextVal) {
				nextNode = nb;
				nextVal = nbVal;
				if (!steepest && j > 0) break;
			}
		}
		if (nextVal <= valueFunc(node)) break;
		node = nextNode;
		value = nextVal;
	}
	this.steps += i + 1;
	this.setNode(node);

	return node;
};

/** Run until solved, local maximum only. Optionally fire callbacks at each step and when finished. */
c3d.HillClimb.prototype.run = function(stepMs, stepCb, doneCb) {
	var lastNode = this.node, lastValue = this.value;
	var stepInt = null;
	var hillclimb = this;
	stepInt = setInterval(function() {
		hillclimb.step(1);
		if (stepCb) stepCb(hillclimb.node, hillclimb.value, hillclimb.steps);
		if (hillclimb.value == lastValue) {
			clearInterval(stepInt);
			if (doneCb) doneCb(hillclimb.node, hillclimb.value, hillclimb.steps);
			return;
		}
		lastNode = hillclimb.node; lastValue = hillclimb.value;
	}, stepMs);
};

/** Try restart several times until a global maximum is found. */
c3d.HillClimb.prototype.runWithRestart = function(stepMs, stepCb, doneCb, localDoneCb, nodeFunc) {
	var bestNode = this.node, bestValue = this.value;
	var hillclimb = this;

	var complete = function() {
		hillclimb.setNode(bestNode);
		doneCb(hillclimb.node, hillclimb.value, hillclimb.steps);
	};

	var maxFails = 4, fails = 0;
	var attempt = function() {
		hillclimb.setNode(nodeFunc());

		hillclimb.run.call(hillclimb, stepMs, stepCb, function() {
			localDoneCb.apply(hillclimb, arguments);
			if (hillclimb.value > bestValue) {
				bestNode = hillclimb.node;
				bestValue = hillclimb.value;
				fails = 0;
			} else {
				++fails;
			}
			if (fails == maxFails) {
				complete();
			} else {
				setTimeout(attempt, 0);
			}
		});
	};
	attempt();
};

## index.html
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>

	<meta http-equiv="X-UA-Compatible" content="IE=8">
	<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

	<title>Hill Climb Algorithm</title>

	<link rel="stylesheet" href="http://github.com/joshuaclayton/blueprint-css/raw/master/blueprint/screen.css" type="text/css" media="screen, projection">
	<link rel="stylesheet" href="http://github.com/joshuaclayton/blueprint-css/raw/master/blueprint/print.css" type="text/css" media="print">
	<!--[if lt IE 8]><link rel="stylesheet" href="http://github.com/joshuaclayton/blueprint-css/raw/master/blueprint/ie.css" type="text/css" media="screen, projection"><![endif]-->

	<style type="text/css">
		body {
			padding: 1.5em;
			background: #181818;
			color: #FFFFFF;
			overflow: hidden;
		}
		body * {
			color: #EEEEEE;
		}
		input {
			color: #000000;
		}
		.view, #noiseview-container {
			width: 256px;
			height: 256px;
			background: transparent;
		}
		#noiseview-container {
			background-color: #000000;
			position: relative;
			margin-bottom: 1.5em;
		}
		.view {
			position: absolute;
			top: 0;
			left; 0;
		}
		#noiseview { z-index: 1; }
		#pathview { z-index: 2; }

		label {
			display: inline-block;
			width: 9em;
		}
		#result {
			border: 1px solid black;
			background-color: #DDDDDD;
			color: black;
			font-size: 1.5em;
			padding: 5px;
		}
	</style>

	<!--[if IE]><script src="excanvas.min.js"></script><![endif]-->

	<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js" type="text/javascript" charset="utf-8"></script>
	<script src="noise.js" type="text/javascript" charset="utf-8"></script>
	<script src="hillclimb.js" type="text/javascript" charset="utf-8"></script>

	<script type="text/javascript" charset="utf-8">
		var w = 0, h = 0;
		var noiseview, ctx, noiseMap, pathview, pathCtx;

		// Workaround javascript's annoying negative modulo bug
		function mod(x, n) {
			return ((x%n) + n)%n;
		}

		function clearPath() {
			pathCtx.clearRect(0, 0, w, h);
		}
		function generateMap() {
			noiseview = $('#noiseview').fadeTo(0, 0.75);
			w = noiseview.width(); h = noiseview.height();
			noiseview.attr('width', w).attr('height', h);
			ctx = noiseview.get(0).getContext('2d');
			pathview = $('#pathview');
			pathview.attr('width', w).attr('height', h);
			pathCtx = pathview.get(0).getContext('2d');

			// Generate the noise map data
			//var perlin = new SimplexNoise();
			var perlin = new ClassicalNoise();
			var scale = 2.0;
			var xFactor = scale/w, yFactor = scale/h;
			noiseMap = new Array(h);
			for (var y = 0; y < h; ++y) {
				noiseMap[y] = new Array(w);
				for (var x = 0; x < w; ++x) noiseMap[y][x] = perlin.noise(x*xFactor, y*yFactor, 0)*255 | 0;
			}

			// Render the map
			var pixelData = ctx.getImageData(0, 0, w, h), pixels = pixelData.data;
			for (var y = 0; y < h; ++y) {
				for (var x = 0; x < w; ++x) {
					var val = 128 + (noiseMap[y][x]>>1);
					pixels[((y*w + x)<<2) + 0] =
					pixels[((y*w + x)<<2) + 1] =
					pixels[((y*w + x)<<2) + 2] =
					pixels[((y*w + x)<<2) + 3] = val;
				}
			}
			ctx.putImageData(pixelData, 0, 0);
		}

		function randomPoint() {
			return { x: Math.random()*w | 0, y: Math.random()*h | 0 };
		}

		function runAlgo() {
			var result = $('#result').empty().show();

			var startNode = randomPoint();
			var _d = noiseMap;
			var hillclimb = new c3d.HillClimb(function(p) {
				// Support wraparound
				var ym1 = mod(p.y - 1, h), ycc = p.y, yp1 = mod(p.y + 1, h);
				var xm1 = mod(p.x - 1, w), xcc = p.x, xp1 = mod(p.x + 1, w);

				return [
					{ y: ym1, x: xm1 }, { y: ym1, x: xcc }, { y: ym1, x: xp1 },
					{ y: ycc, x: xm1 },                    { y: ycc, x: xp1 },
					{ y: yp1, x: xm1 }, { y: yp1, x: xcc }, { y: yp1, x: xp1 }
				];

				return ps;

			}, function(p) {
				return _d[p.y][p.x];
			}, startNode, $('#steepest').attr('checked'));

			var stepMs = 15;
			var stepCb = function(p, value, steps) {
				pathCtx.fillStyle = '#0033DD';
				pathCtx.fillRect(p.x - 1, p.y - 1, 2, 2);
				result.text('Step #' + steps);
			};
			var doneCb = function(p, value, steps) {
				pathCtx.fillStyle = '#00DD00';
				pathCtx.fillRect(p.x - 2, p.y - 2, 4, 4);
				result.text('Took ' + steps + ' steps.');
			};
			var localDoneCb = function(p, value, steps) {
				pathCtx.fillStyle = '#999900';
				pathCtx.fillRect(p.x - 2, p.y - 2, 4, 4);
				//console.log('Took', steps, 'steps.');
			};
			if ($('#random-restart').attr('checked')) {
				hillclimb.runWithRestart(stepMs, stepCb, doneCb, localDoneCb, randomPoint);
			} else {
				hillclimb.run(stepMs, stepCb, doneCb, localDoneCb, randomPoint);
			}
		}
		$(document).ready(function() {
			$('#result').hide();
			$('#generate').click(generateMap);
			$('#run').click(runAlgo);
			$('#clear').click(clearPath);
			generateMap();
		});
	</script>

</head>
<body>
	<div class="container">
		<div class="span-13 last">
			<div class="span-5">
				<div><nobr><label for="steepest" title="Steepest Ascent heads in the direction of the greatest improvement over the current position.">Steepest Ascent</label><input type="checkbox" id="steepest" name="steepest" checked /></nobr></div>
				<div><nobr><label for="random-restart" title="Random Restart keeps trying random positions until there has been no improvement for several attempts.">Random Restart</label><input type="checkbox" id="random-restart" name="random-restart" /></nobr></div>
				<br/>
				<div><input type="button" id="run" name="run" value="Run" /></div>
				<br/>
				<p id="result"></p>
			</div>
			<div class="span-8 last">
				<div id="noiseview-container">
					<canvas id="noiseview" class="view"></canvas>
					<canvas id="pathview" class="view"></canvas>
				</div>
				<div><input type="button" id="generate" name="generate" value="Generate Map" /><input type="button" id="clear" name="clear" value="Clear Paths" /></div>
			</div>
		</div>
	</div>
</body>
</html>
	/**
	* @preserve
	*
	* Javascript Hill Climb Algorithm.
	* @author Adam R. Smith http://codi.st/
	*
	* Licensed under the new BSD License:
	* http://www.opensource.org/licenses/bsd-license.php
	*/

	var c3d = c3d \|\| {};
	c3d.MIN_INT = (1<<31);
	c3d.MAX_INT = ((1<<30) - 1) \| (1<<30);

	/**
	* Hill climb algorithm object, steppable.
	* This version is flexible and easy to use for educational purposes.
	* For high performance needs the functions should probably be inlined
	* in a custom class/function, and it should step until complete automatically.
	* Inlining could be done with a JS compiler like Closure.
	*
	* @constructor
	*/
	c3d.HillClimb = function(neighborsFunc, valueFunc, start, steepest) {
	this.neighborsFunc = neighborsFunc;
	this.valueFunc = valueFunc;
	this.setNode(start);
	this.steps = 0;
	this.steepest = !!steepest;
	};

	/** Avoid mistakes by always setting the value to match the node. */
	c3d.HillClimb.prototype.setNode = function(node) {
	this.node = node;
	this.value = this.valueFunc(node);
	};

	/** Run one or more steps toward the solution. */
	c3d.HillClimb.prototype.step = function(stepCount) {
	if (!stepCount \|\| stepCount < 0) stepCount = 1<<30;
	var neighborsFunc = this.neighborsFunc, valueFunc = this.valueFunc, steepest = this.steepest;
	var node = this.node, value = this.value, i = 0;
	for (i = 0; i < stepCount; ++i) {
	var nbs = neighborsFunc(node), nbsl = nbs.length;
	var nextVal = value;
	var nextNode = node;
	for (var j = 0; j < nbsl; ++j) {
	var nb = nbs[j];
	var nbVal = valueFunc(nb);
	if (nbVal > nextVal) {
	nextNode = nb;
	nextVal = nbVal;
	if (!steepest && j > 0) break;
	}
	}
	if (nextVal <= valueFunc(node)) break;
	node = nextNode;
	value = nextVal;
	}
	this.steps += i + 1;
	this.setNode(node);

	return node;
	};

	/** Run until solved, local maximum only. Optionally fire callbacks at each step and when finished. */
	c3d.HillClimb.prototype.run = function(stepMs, stepCb, doneCb) {
	var lastNode = this.node, lastValue = this.value;
	var stepInt = null;
	var hillclimb = this;
	stepInt = setInterval(function() {
	hillclimb.step(1);
	if (stepCb) stepCb(hillclimb.node, hillclimb.value, hillclimb.steps);
	if (hillclimb.value == lastValue) {
	clearInterval(stepInt);
	if (doneCb) doneCb(hillclimb.node, hillclimb.value, hillclimb.steps);
	return;
	}
	lastNode = hillclimb.node; lastValue = hillclimb.value;
	}, stepMs);
	};

	/** Try restart several times until a global maximum is found. */
	c3d.HillClimb.prototype.runWithRestart = function(stepMs, stepCb, doneCb, localDoneCb, nodeFunc) {
	var bestNode = this.node, bestValue = this.value;
	var hillclimb = this;

	var complete = function() {
	hillclimb.setNode(bestNode);
	doneCb(hillclimb.node, hillclimb.value, hillclimb.steps);
	};

	var maxFails = 4, fails = 0;
	var attempt = function() {
	hillclimb.setNode(nodeFunc());

	hillclimb.run.call(hillclimb, stepMs, stepCb, function() {
	localDoneCb.apply(hillclimb, arguments);
	if (hillclimb.value > bestValue) {
	bestNode = hillclimb.node;
	bestValue = hillclimb.value;
	fails = 0;
	} else {
	++fails;
	}
	if (fails == maxFails) {
	complete();
	} else {
	setTimeout(attempt, 0);
	}
	});
	};
	attempt();
	};
	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
	<html>
	<head>

	<meta http-equiv="X-UA-Compatible" content="IE=8">
	<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

	<title>Hill Climb Algorithm</title>

	<link rel="stylesheet" href="http://github.com/joshuaclayton/blueprint-css/raw/master/blueprint/screen.css" type="text/css" media="screen, projection">
	<link rel="stylesheet" href="http://github.com/joshuaclayton/blueprint-css/raw/master/blueprint/print.css" type="text/css" media="print">
	<!--[if lt IE 8]><link rel="stylesheet" href="http://github.com/joshuaclayton/blueprint-css/raw/master/blueprint/ie.css" type="text/css" media="screen, projection"><![endif]-->

	<style type="text/css">
	body {
	padding: 1.5em;
	background: #181818;
	color: #FFFFFF;
	overflow: hidden;
	}
	body * {
	color: #EEEEEE;
	}
	input {
	color: #000000;
	}
	.view, #noiseview-container {
	width: 256px;
	height: 256px;
	background: transparent;
	}
	#noiseview-container {
	background-color: #000000;
	position: relative;
	margin-bottom: 1.5em;
	}
	.view {
	position: absolute;
	top: 0;
	left; 0;
	}
	#noiseview { z-index: 1; }
	#pathview { z-index: 2; }

	label {
	display: inline-block;
	width: 9em;
	}
	#result {
	border: 1px solid black;
	background-color: #DDDDDD;
	color: black;
	font-size: 1.5em;
	padding: 5px;
	}
	</style>

	<!--[if IE]><script src="excanvas.min.js"></script><![endif]-->

	<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js" type="text/javascript" charset="utf-8"></script>
	<script src="noise.js" type="text/javascript" charset="utf-8"></script>
	<script src="hillclimb.js" type="text/javascript" charset="utf-8"></script>

	<script type="text/javascript" charset="utf-8">
	var w = 0, h = 0;
	var noiseview, ctx, noiseMap, pathview, pathCtx;

	// Workaround javascript's annoying negative modulo bug
	function mod(x, n) {
	return ((x%n) + n)%n;
	}

	function clearPath() {
	pathCtx.clearRect(0, 0, w, h);
	}
	function generateMap() {
	noiseview = $('#noiseview').fadeTo(0, 0.75);
	w = noiseview.width(); h = noiseview.height();
	noiseview.attr('width', w).attr('height', h);
	ctx = noiseview.get(0).getContext('2d');
	pathview = $('#pathview');
	pathview.attr('width', w).attr('height', h);
	pathCtx = pathview.get(0).getContext('2d');

	// Generate the noise map data
	//var perlin = new SimplexNoise();
	var perlin = new ClassicalNoise();
	var scale = 2.0;
	var xFactor = scale/w, yFactor = scale/h;
	noiseMap = new Array(h);
	for (var y = 0; y < h; ++y) {
	noiseMap[y] = new Array(w);
	for (var x = 0; x < w; ++x) noiseMap[y][x] = perlin.noise(xxFactor, yyFactor, 0)*255 \| 0;
	}

	// Render the map
	var pixelData = ctx.getImageData(0, 0, w, h), pixels = pixelData.data;
	for (var y = 0; y < h; ++y) {
	for (var x = 0; x < w; ++x) {
	var val = 128 + (noiseMap[y][x]>>1);
	pixels[((y*w + x)<<2) + 0] =
	pixels[((y*w + x)<<2) + 1] =
	pixels[((y*w + x)<<2) + 2] =
	pixels[((y*w + x)<<2) + 3] = val;
	}
	}
	ctx.putImageData(pixelData, 0, 0);
	}

	function randomPoint() {
	return { x: Math.random()w \| 0, y: Math.random()h \| 0 };
	}

	function runAlgo() {
	var result = $('#result').empty().show();

	var startNode = randomPoint();
	var _d = noiseMap;
	var hillclimb = new c3d.HillClimb(function(p) {
	// Support wraparound
	var ym1 = mod(p.y - 1, h), ycc = p.y, yp1 = mod(p.y + 1, h);
	var xm1 = mod(p.x - 1, w), xcc = p.x, xp1 = mod(p.x + 1, w);

	return [
	{ y: ym1, x: xm1 }, { y: ym1, x: xcc }, { y: ym1, x: xp1 },
	{ y: ycc, x: xm1 }, { y: ycc, x: xp1 },
	{ y: yp1, x: xm1 }, { y: yp1, x: xcc }, { y: yp1, x: xp1 }
	];

	return ps;

	}, function(p) {
	return _d[p.y][p.x];
	}, startNode, $('#steepest').attr('checked'));

	var stepMs = 15;
	var stepCb = function(p, value, steps) {
	pathCtx.fillStyle = '#0033DD';
	pathCtx.fillRect(p.x - 1, p.y - 1, 2, 2);
	result.text('Step #' + steps);
	};
	var doneCb = function(p, value, steps) {
	pathCtx.fillStyle = '#00DD00';
	pathCtx.fillRect(p.x - 2, p.y - 2, 4, 4);
	result.text('Took ' + steps + ' steps.');
	};
	var localDoneCb = function(p, value, steps) {
	pathCtx.fillStyle = '#999900';
	pathCtx.fillRect(p.x - 2, p.y - 2, 4, 4);
	//console.log('Took', steps, 'steps.');
	};
	if ($('#random-restart').attr('checked')) {
	hillclimb.runWithRestart(stepMs, stepCb, doneCb, localDoneCb, randomPoint);
	} else {
	hillclimb.run(stepMs, stepCb, doneCb, localDoneCb, randomPoint);
	}
	}
	$(document).ready(function() {
	$('#result').hide();
	$('#generate').click(generateMap);
	$('#run').click(runAlgo);
	$('#clear').click(clearPath);
	generateMap();
	});
	</script>

	</head>
	<body>
	<div class="container">
	<div class="span-13 last">
	<div class="span-5">
	<div><nobr><label for="steepest" title="Steepest Ascent heads in the direction of the greatest improvement over the current position.">Steepest Ascent</label><input type="checkbox" id="steepest" name="steepest" checked /></nobr></div>
	<div><nobr><label for="random-restart" title="Random Restart keeps trying random positions until there has been no improvement for several attempts.">Random Restart</label><input type="checkbox" id="random-restart" name="random-restart" /></nobr></div>
	<br/>
	<div><input type="button" id="run" name="run" value="Run" /></div>
	<br/>
	<p id="result"></p>
	</div>
	<div class="span-8 last">
	<div id="noiseview-container">
	<canvas id="noiseview" class="view"></canvas>
	<canvas id="pathview" class="view"></canvas>
	</div>
	<div><input type="button" id="generate" name="generate" value="Generate Map" /><input type="button" id="clear" name="clear" value="Clear Paths" /></div>
	</div>
	</div>
	</div>
	</body>
	</html>