Skip to content

Instantly share code, notes, and snippets.

@sunetos

sunetos/hillclimb.js

Created June 18, 2010 23:59
Show Gist options
  • Save sunetos/444396 to your computer and use it in GitHub Desktop.
Save sunetos/444396 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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();
};
Raw
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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment