eweitnauer/index.html

## index.html
<!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>

## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!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-2x_mar, height: height-2y_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-2x_mar-2*radius_o)+x_mar+radius_o
	,y: Math.random()(height-2y_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()2jump - jump;
	y += Math.random()2jump - 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>