Skip to content

Instantly share code, notes, and snippets.

@saifuddin778

saifuddin778/README.md

Last active July 5, 2017 18:33
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 saifuddin778/3acd119586b99918e36b4336c300187e to your computer and use it in GitHub Desktop.
Save saifuddin778/3acd119586b99918e36b4336c300187e to your computer and use it in GitHub Desktop.
Download ZIP
Cost Paths + d3 Node Caching
Raw
README.md

Demonstration of how different real-time optimal cost finding approaches can work. This example utilizes d3's element/node caching, which gives a benefit of drastically reducing the element/node lookup time. This way, no application of select() or selectAll() is done to find and filter nodes in the directional vicinity: [(x+k, y), (x, y+k), (x+k, y+k)].

Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
text-align: center;
}
svg {
background: none;
}
#major {
width: 700px;
margin: auto;
}
.label {
margin: 5px;
font-size: 12px;
color: #663399;
text-align: left;
display: inline-block;
font-family: monospace;
}
</style>
<body>
<div id="major">
<div id="a" class="label"></div>
<div id="b" class="label"></div>
<div id="c" class="label"></div>
<div id="d" class="label"></div>
</div>
<script src="http://d3js.org/d3.v3.js"></script>
<script>
var n = 30;
var width = 224;
var height = 224;
var color = d3.scale.linear()
.domain([0, 1])
.interpolate(d3.interpolateHsl)
.range(["#A2DED0", "#1F3A93"]);
var costpaths = {
random_cost: function(point, collection, counter, path) {
//three directions to go (right, down-right, down)
//pick random direction and move.
var newps = [
[point[0], point[1] + collection.pad_y],
[point[0] + collection.pad_x, point[1] + collection.pad_y],
[point[0] + collection.pad_x, point[1]]
].filter(function(d, i) {
return ([String(d[0]), String(d[1])] in collection.data)
});
if (!newps.length) {
return point;
}
var candidate = newps[parseInt(newps.length * Math.random())];
var ckey = [String(candidate[0]), String(candidate[1])];
//add cost
var rgb = d3.rgb(collection.data[ckey].style("fill"));
var mag = magnitude([rgb.r, rgb.g, rgb.b]);
if (mag != 0) {
var cost = 1 / mag;
} else {
var cost = mag;
}
highlight(collection.data[ckey], counter);
paths[path].total_cost += cost;
d3.select("#" + paths[path].div + " #cost")
.transition().delay(200 * counter)
.text(" (" + paths[path].total_cost.toFixed(4) + ")");
return candidate;
},
min_local_cost: function(point, collection, counter, path) {
//three directions to go (right, down-right, down)
//pick the one with least cost and move
var newps = [
[point[0], point[1] + collection.pad_y],
[point[0] + collection.pad_x, point[1] + collection.pad_y],
[point[0] + collection.pad_x, point[1]]
].filter(function(d, i) {
return ([String(d[0]), String(d[1])] in collection.data)
});
if (!newps.length) {
return point;
}
var minindex = 0;
var mincost = Number.POSITIVE_INFINITY;
for (var i = 0; i < newps.length; i++) {
//since darker colors have lower values;
var ckey = [String(newps[i][0]), String(newps[i][1])];
var celement = collection.data[ckey];
var rgb = d3.rgb(celement.style("fill"));
var mag = magnitude([rgb.r, rgb.g, rgb.b]);
if (!mag) {
var cost = 0;
} else {
var cost = 1 / mag;
}
if (cost < mincost) {
mincost = cost;
minindex = i;
}
}
var candidate = newps[minindex];
var ckey = [String(newps[minindex][0]), String(newps[minindex][1])];
highlight(collection.data[ckey], counter);
//add cost
paths[path].total_cost += cost;
d3.select("#" + paths[path].div + " #cost")
.transition().delay(200 * counter)
.text(" (" + paths[path].total_cost.toFixed(4) + ")");
return candidate;
},
min_local_vicinity_cost: function(point, collection, counter, path) {
//three directions to go (right, down-right, down)
//pick the one with least aggregated vicinity cost and move
var newps = [
[point[0], point[1] + collection.pad_y],
[point[0] + collection.pad_x, point[1] + collection.pad_y],
[point[0] + collection.pad_x, point[1]]
].filter(function(d, i) {
return ([String(d[0]), String(d[1])] in collection.data)
});
if (!newps.length) {
return point;
}
var minindex = 0;
var mincost = Number.POSITIVE_INFINITY;
for (var i = 0; i < newps.length; i++) {
//get the vicinity
var pspoint = newps[i];
var cost = d3.sum([
[pspoint[0], pspoint[1] + collection.pad_y],
[pspoint[0] + collection.pad_x, pspoint[1] + collection.pad_y],
[pspoint[0] + collection.pad_x, pspoint[1]]
].filter(function(d, i) {
return ([String(d[0]), String(d[1])] in collection.data)
}).map(function(d, i) {
var ckey = [String(d[0]), String(d[1])];
var celement = collection.data[ckey];
//highlight vicinity
collection.data[ckey]
.transition()
.delay(200 * counter)
.style("fill", "#2ECC71");
var rgb = d3.rgb(celement.style("fill"));
var mag = magnitude([rgb.r, rgb.g, rgb.b]);
if (!mag) {
var cost = 0;
} else {
var cost = 1 / mag;
}
return cost;
}));
if (cost < mincost) {
mincost = cost;
minindex = i;
}
}
var candidate = newps[minindex];
var ckey = [String(newps[minindex][0]), String(newps[minindex][1])];
highlight(collection.data[ckey], counter);
//add cost
paths[path].total_cost += cost;
d3.select("#" + paths[path].div + " #cost")
.transition().delay(200 * counter)
.text(" (" + paths[path].total_cost.toFixed(4) + ")");
return candidate;
},
cycle_vicinity_cost: function(point, collection, counter, path) {
//three directions to go (right, down-right, down)
//cycle through them one by one
var newps = [
[point[0], point[1] + collection.pad_y],
[point[0] + collection.pad_x, point[1] + collection.pad_y],
[point[0] + collection.pad_x, point[1]]
].filter(function(d, i) {
return ([String(d[0]), String(d[1])] in collection.data)
});
if (!newps.length) {
return point;
}
var cycle = counter % 3;
if (cycle < newps.length) {
var candidate = newps[cycle];
} else {
var candidate = newps[cycle - 1];
}
var ckey = [String(candidate[0]), String(candidate[1])];
var rgb = d3.rgb(collection.data[ckey].style("fill"));
var mag = magnitude([rgb.r, rgb.g, rgb.b]);
if (!mag) {
var cost = 0;
} else {
var cost = 1 / mag;
}
highlight(collection.data[ckey], counter);
//add cost
paths[path].total_cost += cost;
d3.select("#" + paths[path].div + " #cost")
.transition().delay(200 * counter)
.text(" (" + paths[path].total_cost.toFixed(4) + ")");
return candidate;
}
};
function magnitude(v) {
var sum = d3.sum(v.map(function(d, i) {
return Math.pow(d, 2)
}));
if (sum > 0) {
var mag = Math.sqrt(sum);
} else {
var mag = sum;
}
return mag;
}
function logit(val) {
return 1 / (1 + Math.exp(-val));
}
function euclidean(v1, v2) {
return Math.sqrt(d3.sum(v1.map(function(d, i) {
return Math.pow(v1[i] - v2[i], 2);
})));
}
function highlight(node, counter) {
node
.transition()
.delay(200 * counter)
.style("fill", "red");
return true;
}
function getcostpoints(nvals) {
var npoints = 50;
var costpoints = d3.range(npoints).map(function(d) {
return parseInt(nvals * Math.random());
});
//add the top left corner too
costpoints.push(0);
return costpoints;
}
function fillcost(items, count, costpoints) {
var rnd = Math.random();
var radius = 15;
var allkeys = Object.keys(items);
var keys = Object.keys(items).filter(function(d, i) {
return costpoints.indexOf(i) >= 0;
});
for (var i = 0; i < keys.length; i++) {
var key = keys[i].split(",").map(function(e) {
return +e
});
allkeys.filter(function(d, i) {
var dkey = d.split(",").map(function(e) {
return +e;
});
return ((dkey[0] <= key[0] + radius) && (dkey[0] >= key[0] - radius));
})
.filter(function(d, i) {
var dkey = d.split(",").map(function(e) {
return +e;
});
return ((dkey[1] <= key[1] + radius) && (dkey[1] >= key[1] - radius));
})
.map(function(d) {
var dkey = d.split(",").map(function(e) {
return +e
});
items[d].style("fill", color(Math.random() / logit(euclidean(dkey, key))));
});
}
}
function grid(width, height, n, div, name, costpoints) {
var container = d3.select("#" + div);
var space = container
.append("svg")
.attr("width", width)
.attr("height", height)
.append("g");
var pad_x = parseInt(width / n);
var pad_y = parseInt(height / n);
var x = 0;
var y = 0 - pad_y;
var items = {};
d3.range(n * n).map(function(d, i) {
x = pad_x * (d % n);
if ((d % n) == 0) {
y += pad_y;
}
var cx = parseInt(x);
var cy = parseInt(y);
var item = space.append("rect")
.attr("x", cx)
.attr("y", cy)
.attr("width", pad_x)
.attr("height", pad_y)
.attr("rx", 3)
.style("fill", "none")
.style("stroke", "green")
.style("stroke-width", 0.2);
items[[cx, cy]] = item;
});
var label = container.append("div").text(name);
label.append("span").attr("id", "cost").text(" (" + 0 + ") ");
//now fill cost in the grid
fillcost(items, n * n, costpoints);
return {
data: items,
pad_x: pad_x,
pad_y: pad_y,
width: width,
height: height,
n: n,
};
}
function begin_traversal(collection, path, pathobj) {
var point = [0, 0];
var ppoint = null;
collection.data[[String(point[0]), String(point[1])]].style("fill", "red");
var counter = 0;
while (true) {
ppoint = point;
point = pathobj.method(point, collection, counter, path);
counter += 1;
if (counter >= (n * n) || (ppoint === point)) {
break
}
}
}
var costpoints = getcostpoints(n * n);
var paths = {
random: {
div: "a",
method: costpaths.random_cost,
total_cost: 0
},
min_local_cost: {
div: "b",
method: costpaths.min_local_cost,
total_cost: 0
},
min_local_vicinity_cost: {
div: "c",
method: costpaths.min_local_vicinity_cost,
total_cost: 0
},
cycle_vicinity_cost: {
div: "d",
method: costpaths.cycle_vicinity_cost,
total_cost: 0
},
};
for (var path in paths) {
var collection = grid(width, height, n, paths[path].div, path, costpoints);
begin_traversal(collection, path, paths[path]);
}
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment