Skip to content

Instantly share code, notes, and snippets.

@azeem

azeem/routing.html

Created December 26, 2011 16:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save azeem/1521549 to your computer and use it in GitHub Desktop.
Save azeem/1521549 to your computer and use it in GitHub Desktop.
Download ZIP
Flow Chart Edge Routing
Raw
routing.html
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd" >
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Experiment</title>
<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script>
<script type="text/javascript">
(function () {
function makeClass(proto) {
var func = function(args) {
if(this instanceof arguments.callee) {
if(typeof this.init == 'function') {
this.init.apply(this, (args&&args.callee)?args:arguments);
}
else {
return new arguments.callee(arguments);
}
}
}
if(proto) {
func.prototype = proto;
}
return func;
}
Coord = makeClass({
init: function(x, y) {
this.x = x;
this.y = y;
},
equals: function(coord) {
return this.x == coord.x && this.y == coord.y;
}
});
Window = makeClass({
init: function(tl, br) {
this.tl = tl;
this.br = br;
},
collides: function(coord) {
if(coord.x <= this.br.x && coord.x >= this.tl.x &&
coord.y <= this.br.y && coord.y >= this.tl.y) {
return true;
}
else {
return false;
}
}
});
BitArray = makeClass({
init: function(size) {
var count;
if(!size) {
count = 100;
}
else {
count = Math.ceil(size/32);
}
this.ints = [];
for(var i = 0;i < count;i++) {
this.ints.push(0);
}
},
_index: function(pos) {return Math.floor(pos/32);},
_bit_index: function(pos) {return pos%32;},
get: function(pos) {
var index = this._index(pos),
bit_index = this._bit_index(pos);
if(index >= this.ints.length) {
return false;
}
else {
return (this.ints[index] & (1<<bit_index))?true:false;
}
},
set: function(pos) {
var index = this._index(pos),
bit_index = this._bit_index(pos);
if(index >= this.ints.length) {
for(var i = 0;i < ((index+1)*2)-this.ints.length;i++) {
this.ints.push(0);
}
}
this.ints[index] |= (1<<bit_index);
}
});
var GRID_SIZE = 15;
function sleep(ms) {
var startTime = new Date().getTime();
while(new Date().getTime() < startTime + ms);
}
function renderBlip(coord, color) {
var x = coord.x*GRID_SIZE-5,
y = coord.y*GRID_SIZE-5,
title_str;
title_str = "(" + coord.x + "," + coord.y + ")\n--------\n" +
(coord.prev?("prev = (" + coord.prev.x+ "," + coord.prev.y + ")\n"):"") +
"dir=" + coord.dir+ "\n" +
"remBends=" + coord.remBends + "\n" +
"heuristic =" + coord.heuristic + "\n" +
"distance =" + coord.distance+ "\n" +
"bends =" + coord.bends+ "\n" +
"cost=" + coord.cost + "\n" +
"h=" + (coord.heuristic+coord.cost) + "\n" +
"m+c=" + (coord.remBends+coord.cost);
$('<a href="javascript:;"/>')
.attr('title', title_str)
.css('position', 'absolute')
.css('left', x)
.css('top', y)
.css('width', 10)
.css('height', 10)
.css('background-color', color?color:'red')
.hover(
function() {
var point = coord.prev;
do {
$('<div class="trace"/>')
.css('position', 'absolute')
.css('left', point.x*GRID_SIZE-5)
.css('top', point.y*GRID_SIZE-5)
.css('width', 10)
.css('height', 10)
.css('background-color', 'cyan')
.appendTo('body');
point = point.prev;
} while(point.prev);
},
function() {
$('.trace').remove();
}
)
.appendTo('body');
}
function renderWindow(win, color) {
var x = win.tl.x*GRID_SIZE,
y = win.tl.y*GRID_SIZE,
width = (win.br.x - win.tl.x)*GRID_SIZE,
height = (win.br.y - win.tl.y)*GRID_SIZE;
$('<div/>')
.css('position', 'absolute')
.css('left', x)
.css('top', y)
.css('width', width)
.css('height', height)
.css('border', '1px solid grey')
.css('background-color', color?color:'#A9D0FF')
.appendTo('body');
}
function manhattan_distance(x1, y1, x2, y2) {
return (Math.abs(x2-x1) + Math.abs(y2-y1));
}
function minBendEstimate(st, en, di) {
function wrap(start, end, dir) {
var same_line = false,
in_front = false;
if((dir == 0 || dir == 2) && (start.y == end.y)) {
same_line = true;
}
if((dir == 1 || dir == 3) && (start.x == end.x)) {
same_line = true;
}
if(dir == 0 && (start.y-end.y > 0)) {
in_front = true;
}
if(dir == 2 && (end.y-start.y > 0)) {
in_front = true;
}
if(dir == 1 && (start.x-end.x > 0)) {
in_front = true;
}
if(dir == 3 && (end.x-start.x > 0)) {
in_front = true;
}
if(same_line) {
if(in_front) {
return 0;
}
else {
return 3;
}
}
else if(in_front) {
return 1;
}
else {
return 2;
}
}
var val = wrap(st, en, di);
return val;
}
var ANIM_DELAY = 0;
function dijkstra(start, target, windows) {
var visited = new BitArray(),
queue = [];
var start_coord = new Coord(start.x, start.y);
start_coord.cost = 0;
start_coord.heuristic = manhattan_distance(start.x, start.y, target.x, target.y);
start_coord.bends = 0;
start_coord.distance = 0;
queue.push(start_coord);
var traceBack = function(coord) {
var point = coord.prev;
do {
renderBlip(point, 'black');
point = point.prev;
} while(point.prev);
renderBlip(start, 'black');
renderBlip(target, 'black');
}
var loop = function() {
var coord = queue.pop();
if(coord.equals(target)) {
traceBack(coord);
return false;
}
var neighbors = [
new Coord(coord.x, coord.y-1),
new Coord(coord.x-1, coord.y),
new Coord(coord.x, coord.y+1),
new Coord(coord.x+1, coord.y),
];
for(var i = 0;i < 4;i++) {
var n = neighbors[i];
if(visited.get(n.y*1000+n.x)) {
continue;
}
if(n.x < 0 || n.y < 0) {
continue;
}
var j;
for(j = 0;j < windows.length;j++) {
if(windows[j].collides(n)) {
break;
}
}
if(j != windows.length) {
continue;
}
for(j = 0;j < queue.length;j++) {
var qitem = queue[j];
if(qitem.equals(n)) {
n = qitem;
break;
}
}
if(j == queue.length) {
queue.push(n);
}
var distance = coord.distance+1;
var bends = coord.bends;
if(coord.prev) {
if(coord.prev.x != n.x && coord.prev.y != n.y) {
bends = coord.bends+1;
}
}
var cost = (distance+bends);
var remBends = minBendEstimate(n, target, i);
if(typeof n.cost == 'undefined' || (cost+remBends) < (n.cost+n.remBends)) {
n.cost = cost;
n.distance = distance;
n.bends = bends;
n.prev = coord;
n.remBends = remBends
n.heuristic = manhattan_distance(n.x, n.y, target.x, target.y)+remBends;
//n.heuristic = 0;
n.dir = i;
if(j == queue.length-1) {
renderBlip(n, 'yellow');
}
}
}
queue.sort(function(a, b) {
return (b.cost+b.heuristic)-(a.cost+a.heuristic);
});
visited.set(coord.y*1000+coord.x);
renderBlip(coord);
return true;
}
$('#start').fadeOut(function() {
$('#step').fadeIn().click(loop);
$('#play').fadeIn().click(function() {
var doLoop = function() {
if(loop()) {
setTimeout(doLoop, ANIM_DELAY);
}
};
$('#step').hide();
$('#play').hide();
doLoop();
});
});
//loop();
}
$(document).ready(function() {
//var start = new Coord(15, 8);
var start = new Coord(12, 16);
var target = new Coord(21, 25);
//var target = new Coord(20, 19);
var windows = [
new Window(new Coord(15, 15), new Coord(19, 19)),
new Window(new Coord(5, 20), new Coord(25, 24)),
new Window(new Coord(12, 25), new Coord(15, 30)),
new Window(new Coord(25, 25), new Coord(29, 29)),
new Window(new Coord(20, 10), new Coord(23, 18)),
new Window(new Coord(16, 27), new Coord(23, 29)),
new Window(new Coord(10, 17), new Coord(14, 19)),
new Window(new Coord(6, 9), new Coord(11, 16)),
new Window(new Coord(12, 7), new Coord(15, 13)),
];
for(var i = 0;i < windows.length;i++) {
renderWindow(windows[i]);
}
renderBlip(start, 'blue');
renderBlip(target, 'green');
$('#start').click(function() {
dijkstra(start, target, windows);
});
});
})();
</script>
</head>
<body>
<button style="position:absolute;top:1em;left:50%;" id="start">Start</button>
<button style="position:absolute;top:1em;left:50%;display:none;" id="step">step</button>
<button style="position:absolute;top:3em;left:50%;display:none;" id="play">play</button>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment