Skip to content

Instantly share code, notes, and snippets.

@emeeks
Last active August 29, 2015 14:05
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save emeeks/8edaa27a121dc2a227ec to your computer and use it in GitHub Desktop.
Simple Pathfinding

Simple topoJSON pathfinding. Click on a circle to set a source and click on another circle to set a destination.

This example derives a set of nodes for each common endpoint of a line, and as such relies on the geometry of those end points being the same. Along with an node list, the lines are annotated with their source and target and an edge map is created in the format used by the dijkstra implementation in dijkstra.js.

path,circle,rect,polygon,ellipse,line {
vector-effect: non-scaling-stroke;
}
svg, canvas {
top: 0;
}
#d3MapZoomBox {
position: absolute;
z-index: 10;
height: 100px;
width: 25px;
top: 10px;
right: 50px;
}
#d3MapZoomBox > button {
height:25px;
width: 25px;
line-height: 25px;
}
.d3MapControlsBox > button {
font-size:22px;
font-weight:900;
border: none;
height:25px;
width:25px;
background: rgba(35,31,32,.85);
color: white;
padding: 0;
cursor: pointer;
}
.d3MapControlsBox > button:hover {
background: black;
}
#d3MapPanBox {
position: absolute;
z-index: 10;
height: 100px;
width: 25px;
top: 60px;
right: 50px;
}
#d3MapPanBox > button {
height:25px;
width: 25px;
line-height: 25px;
}
#d3MapPanBox > button#left {
position: absolute;
left: -25px;
top: 10px;
}
#d3MapPanBox > button#right {
position: absolute;
right: -25px;
top: 10px;
}
#d3MapLayerBox {
position: relative;
z-index: 10;
height: 100px;
width: 120px;
top: 10px;
left: 10px;
overflow: auto;
color: white;
background: rgba(35,31,32,.85);
}
#d3MapLayerBox > div {
margin: 5px;
border: none;
}
#d3MapLayerBox ul {
list-style: none;
padding: 0;
margin: 0;
cursor: pointer;
}
#d3MapLayerBox li {
list-style: none;
padding: 0;
}
#d3MapLayerBox li:hover {
font-weight:700;
}
#d3MapLayerBox li input {
cursor: pointer;
}
div.d3MapModal {
position: absolute;
z-index: 11;
background: rgba(35,31,32,.90);
top: 50px;
left: 50px;
color: white;
max-width: 400px;
}
div.d3MapModalContent {
width:100%;
height: 100%;
overflow: auto;
}
div.d3MapModalContent > p {
padding: 0px 20px;
margin: 5px 0;
}
div.d3MapModalContent > h1 {
padding: 0px 20px;
font-size: 20px;
}
div.d3MapModalArrow {
content: "";
width: 0;
height: 0;
border-left: 20px solid transparent;
border-right: 20px solid transparent;
border-top: 20px solid rgba(35,31,32,.90);
position: absolute;
bottom: -20px;
left: 33px;
}
#d3MapSVG {
}
rect.minimap-extent {
fill: rgba(200,255,255,0.35);
stroke: black;
stroke-width: 2px;
stroke-dasharray: 5 5;
}
circle.newpoints {
fill: black;
stroke: red;
stroke-width: 2px;
}
path.newfeatures {
fill: steelblue;
fill-opacity: .5;
stroke: pink;
stroke-width: 2px;
}
var Graph = (function (undefined) {
var extractKeys = function (obj) {
var keys = [], key;
for (key in obj) {
Object.prototype.hasOwnProperty.call(obj,key) && keys.push(key);
}
return keys;
}
var sorter = function (a, b) {
return parseFloat (a) - parseFloat (b);
}
var findPaths = function (map, start, end, infinity) {
infinity = infinity || Infinity;
var costs = {},
open = {'0': [start]},
predecessors = {},
keys;
var addToOpen = function (cost, vertex) {
var key = "" + cost;
if (!open[key]) open[key] = [];
open[key].push(vertex);
}
costs[start] = 0;
while (open) {
if(!(keys = extractKeys(open)).length) break;
keys.sort(sorter);
var key = keys[0],
bucket = open[key],
node = bucket.shift(),
currentCost = parseFloat(key),
adjacentNodes = map[node] || {};
if (!bucket.length) delete open[key];
for (var vertex in adjacentNodes) {
if (Object.prototype.hasOwnProperty.call(adjacentNodes, vertex)) {
var cost = adjacentNodes[vertex],
totalCost = cost + currentCost,
vertexCost = costs[vertex];
if ((vertexCost === undefined) || (vertexCost > totalCost)) {
costs[vertex] = totalCost;
addToOpen(totalCost, vertex);
predecessors[vertex] = node;
}
}
}
}
if (costs[end] === undefined) {
return null;
} else {
return predecessors;
}
}
var extractShortest = function (predecessors, end) {
var nodes = [],
u = end;
while (u) {
nodes.push(u);
predecessor = predecessors[u];
u = predecessors[u];
}
nodes.reverse();
return nodes;
}
var findShortestPath = function (map, nodes) {
var start = nodes.shift(),
end,
predecessors,
path = [],
shortest;
while (nodes.length) {
end = nodes.shift();
predecessors = findPaths(map, start, end);
if (predecessors) {
shortest = extractShortest(predecessors, end);
if (nodes.length) {
path.push.apply(path, shortest.slice(0, -1));
} else {
return path.concat(shortest);
}
} else {
return null;
}
start = end;
}
}
var toArray = function (list, offset) {
try {
return Array.prototype.slice.call(list, offset);
} catch (e) {
var a = [];
for (var i = offset || 0, l = list.length; i < l; ++i) {
a.push(list[i]);
}
return a;
}
}
var Graph = function (map) {
this.map = map;
}
Graph.prototype.findShortestPath = function (start, end) {
if (Object.prototype.toString.call(start) === '[object Array]') {
return findShortestPath(this.map, start);
} else if (arguments.length === 2) {
return findShortestPath(this.map, [start, end]);
} else {
return findShortestPath(this.map, toArray(arguments));
}
}
Graph.findShortestPath = function (map, start, end) {
if (Object.prototype.toString.call(start) === '[object Array]') {
return findShortestPath(map, start);
} else if (arguments.length === 3) {
return findShortestPath(map, [start, end]);
} else {
return findShortestPath(map, toArray(arguments, 1));
}
}
return Graph;
})();
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Simple Topojson Pathfinding</title>
<meta charset="utf-8" />
<link type="text/css" rel="stylesheet" href="d3map.css" />
<link type="text/css" rel="stylesheet" href="https://raw.githubusercontent.com/emeeks/d3-carto-map/master/examples/example.css" />
</head>
<style>
html,body {
height: 100%;
width: 100%;
margin: 0;
}
#map {
height: 100%;
width: 100%;
position: absolute;
}
.reproject {
position: absolute;
z-index: 99;
left: 50px;
top: 250px;
}
.node {
fill: blue;
stroke: black;
stroke-width: 1
}
#pathdata {
position: fixed;
top: 20px;
left: 300px;
background: white;
border: 1px gray solid;
z-index: 99;
padding: 20px;
font-size: 20px;
}
#random {
position: fixed;
top: 50px;
left: 150px;
z-index: 99;
font-size: 20px;
}
.roads {
stroke: brown;
stroke-width: 1px;
fill: none;
}
</style>
<script>
function makeSomeMaps() {
pathSource = 0;
map = d3.carto.map();
d3.select("#map").call(map);
map.centerOn([-88,39],"latlong");
map.setScale(4);
map.refresh();
wcLayer = d3.carto.layer.tile();
wcLayer
.tileType("stamen")
.path("watercolor")
.label("Watercolor")
.visibility(true)
postLayer = d3.carto.layer.topojson();
postLayer
.path("uspost.topojson")
.label("Postal Routes")
.cssClass("roads")
.renderMode("svg")
.on("load", createMatrix);
map.addCartoLayer(wcLayer).addCartoLayer(postLayer);
function createMatrix() {
postdata = postLayer.features()
edgeList = [];
edgeMap = {};
nodes = [];
nodeHash = {};
for (x in postdata) {
var line = postdata[x].geometry.coordinates;
var lS = line[0];
var lE = line[line.length - 1];
var nA = [lS,lE];
for (y in nA) {
if (!nodeHash["node" + Math.ceil(nA[y][0] * 1000) + (nA[y][1] * 1000)]) {
var newNode = {label: "Node " + nodes.length, id: nodes.length.toString(), coordinates: [nA[y]], x: nA[y][0], y: nA[y][1]}
nodeHash["node" + Math.ceil(nA[y][0] * 1000) + (nA[y][1] * 1000)] = newNode;
nodes.push(newNode)
}
}
postdata[x].properties.source = nodeHash["node" + Math.ceil(lS[0] * 1000) + (lS[1] * 1000)];
postdata[x].properties.target = nodeHash["node" + Math.ceil(lE[0] * 1000) + (lE[1] * 1000)];
postdata[x].properties.cost = d3.geo.length(postdata[x]) * 6371;
}
nodeLayer = d3.carto.layer.xyArray();
nodeLayer
.features(nodes)
.label("Vertices")
.cssClass("node")
.renderMode("svg")
.x("x")
.y("y")
.markerSize(2)
.clickableFeatures(true)
.on("load", function() {d3.selectAll("circle.node").on("click", sourceClick)});
map.addCartoLayer(nodeLayer);
for (x in postdata) {
if (edgeMap[postdata[x].properties.source.id]) {
edgeMap[postdata[x].properties.source.id][postdata[x].properties.target.id] = postdata[x].properties.cost;
}
else {
edgeMap[postdata[x].properties.source.id] = {};
edgeMap[postdata[x].properties.source.id][postdata[x].properties.target.id] = postdata[x].properties.cost;
}
if (edgeMap[postdata[x].properties.target.id]) {
edgeMap[postdata[x].properties.target.id][postdata[x].properties.source.id] = postdata[x].properties.cost;
}
else {
edgeMap[postdata[x].properties.target.id] = {};
edgeMap[postdata[x].properties.target.id][postdata[x].properties.source.id] = postdata[x].properties.cost;
}
}
graph = new Graph(edgeMap);
randomPath();
d3.select("#map").append("button").attr("id","random").html("random path").on("click", randomPath)
}
function randomPath() {
randomSource = Math.ceil(Math.random() * nodes.length).toString();
randomTarget = Math.ceil(Math.random() * nodes.length).toString();
var pData = graph.findShortestPath(randomSource,randomTarget);
displayPath(pData);
}
function displayPath(pathData) {
var formatter = d3.format(".0f");
d3.selectAll("path").transition().duration(1000).style("stroke", function(d,i) {return "black"}).style("stroke-width", "2px");
d3.selectAll("circle.node").transition().duration(1000).style("fill", "blue");
if (pathData) {
d3.selectAll("path").filter(function(d) {return pathData.indexOf(d.properties.source.id) > -1 && pathData.indexOf(d.properties.target.id) > -1}).transition().duration(2000).style("stroke", "red").style("stroke-width", "4px");
d3.selectAll("circle.node").filter(function(d) {return pathData.indexOf(d.id) > -1}).transition().duration(2000).style("fill", "red")
var pDataArray = d3.selectAll("path").filter(function(d) {return pathData.indexOf(d.properties.source.id) > -1 && pathData.indexOf(d.properties.target.id) > -1}).data();
var totalLength = d3.sum(pDataArray, function(d) {return d.properties.cost});
d3.select("#pathdata").html("<span style='font-weight: 900'>Total Distance:</span> " + formatter(totalLength) + "km");
}
else {
d3.select("#pathdata").html("NO ROUTE");
}
}
function sourceClick(d) {
d3.selectAll("circle.node").style("stroke-width", "1px").style("stroke", "black")
pathSource = d.id;
d3.selectAll("circle.node").on("click", targetClick);
d3.select(this).style("stroke-width", "5px").style("stroke", "green")
}
function targetClick(d) {
var pData = graph.findShortestPath(pathSource,d.id);
d3.selectAll("circle.node").on("click", sourceClick)
d3.select(this).style("stroke-width", "5px").style("stroke", "red")
displayPath(pData);
}
}
</script>
<body onload="makeSomeMaps()">
<div id="map"></div>
<div id="pathdata"></div>
<footer>
<script src="http://d3js.org/d3.v3.min.js" charset="utf-8" type="text/javascript"></script>
<script src="http://d3js.org/topojson.v1.min.js" type="text/javascript">
</script>
<script src="http://d3js.org/d3.geo.projection.v0.min.js" type="text/javascript">
</script>
<script src="http://bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/tile.js" type="text/javascript">
</script>
<script src="http://bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/d3.quadtiles.js" type="text/javascript">
</script>
<script src="http://bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/d3.geo.raster.js" type="text/javascript">
</script>
<script src="https://rawgit.com/emeeks/d3-carto-map/master/d3.carto.map.js" type="text/javascript">
</script>
<script src="dijkstra.js" type="text/javascript">
</script>
</footer>
</body>
</html>
Display the source blob
Display the rendered blob
Raw
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment