Skip to content

Instantly share code, notes, and snippets.

@eweitnauer
Last active December 26, 2015 22:39
Show Gist options
  • Save eweitnauer/7225181 to your computer and use it in GitHub Desktop.
Save eweitnauer/7225181 to your computer and use it in GitHub Desktop.
Path Finding with Simulated Annealing
<!doctype html>
<meta charset="utf-8">
<title>Path Finding using Simulated Annealing</title>
<script src="http://d3js.org/d3.v3.min.js"></script>
<style>
.obstacle { fill: lightpink }
.point { fill: steelblue }
</style>
<body>
<script>
var width = 960
,height = 500
,x_mar = 200
,y_mar = 50
,jump = max_jump = 100
,annealing_rate = 0.99
,N_points = 30
,N_obstacles = 20
,radius_o = 30
,radius_p = 3;
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
svg.append('rect')
.attr({x: x_mar, y: y_mar, width: width-2*x_mar, height: height-2*y_mar})
.style({fill: 'white', stroke: 'silver', 'stroke-width': 4})
.on('click', function() { jump = max_jump })
.on('touchstart', function() { jump = max_jump });
var obstacles = d3.range(N_obstacles).map(function () {
return {x: Math.random()*(width-2*x_mar-2*radius_o)+x_mar+radius_o
,y: Math.random()*(height-2*y_mar-2*radius_o)+y_mar+radius_o
,r: radius_o };
});
var x0=x_mar, x1=width-x_mar, y0=y1=height/2;
var points = d3.range(N_points).map(function(x, i) {
return { x: x0+(x1-x0)*i/(N_points-1)
,y: y0+(y1-y0)*i/(N_points-1) }
});
var osel = svg.selectAll('.obstacle')
.data(obstacles)
.enter()
.append('circle')
.each(function (d) {
d3.select(this)
.attr({cx: d.x, cy: d.y, r: d.r, class: 'obstacle'})
});
var psel = svg.selectAll('.point')
.data(points)
.enter()
.append('circle')
.each(function (d) {
d3.select(this)
.attr({cx: d.x, cy: d.y, r: radius_p, class: 'point'})
});
function update_view() {
psel.attr('cx', function (d) { return d.x })
.attr('cy', function (d) { return d.y });
}
step();
function step() {
// update all points
points.forEach(function (p, i, pts) {
if (i==0 || i==N_points-1) return;
// loop to give points in regions with more obstacles
// several changes to jump to a new point
for (var c=0; c<4; c++) {
var x = (pts[i-1].x + pts[i+1].x) / 2;
var y = (pts[i-1].y + pts[i+1].y) / 2;
x += Math.random()*2*jump - jump;
y += Math.random()*2*jump - jump;
if (!hit_test(x,y)) {
p.x = x;
p.y = y;
break;
}
}
})
// update view
update_view();
// anneal and trigger next step
jump *= annealing_rate;
setTimeout(step, 40);
}
function hit_test(x, y) {
var r2 = (radius_o+radius_p)*(radius_o+radius_p);
if ((x<=x_mar+radius_p) || (x>=width-x_mar-radius_p) ||
(y<=y_mar+radius_p) || (y>=height-y_mar-radius_p)) return true;
return obstacles.some(function (o) {
return (o.x-x)*(o.x-x) + (o.y-y)*(o.y-y) <= r2;
});
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment