Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Flow Chart Edge Routing
<!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