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.

<html xmlns="https://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);

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="https://d3js.org/d3.v3.min.js" charset="utf-8" type="text/javascript"></script>
<script src="https://d3js.org/topojson.v1.min.js" type="text/javascript">
</script>
<script src="https://d3js.org/d3.geo.projection.v0.min.js" type="text/javascript">
</script>
<script src="/emeeks/f3105fda25ff785dc5ed/example/tile.js" type="text/javascript">
</script>
<script src="/emeeks/f3105fda25ff785dc5ed/example/d3.quadtiles.js" type="text/javascript">
</script>
<script src="/emeeks/f3105fda25ff785dc5ed/example/d3.geo.raster.js" type="text/javascript">
</script>
<script src="https://cdn.jsdelivr.net/gh/emeeks/d3-carto-map/d3.carto.map.js" type="text/javascript">
</script>
<script src="dijkstra.js" type="text/javascript">
</script>
</footer>
</body>
</html>

Modified http://d3js.org/d3.v3.min.js to a secure url

Modified http://d3js.org/topojson.v1.min.js to a secure url

Modified http://d3js.org/d3.geo.projection.v0.min.js to a secure url

Updated missing url http://bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/tile.js to /emeeks/f3105fda25ff785dc5ed/example/tile.js

Updated missing url http://bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/d3.quadtiles.js to /emeeks/f3105fda25ff785dc5ed/example/d3.quadtiles.js

Updated missing url http://bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/d3.geo.raster.js to /emeeks/f3105fda25ff785dc5ed/example/d3.geo.raster.js

Updated missing url https://rawgit.com/emeeks/d3-carto-map/master/d3.carto.map.js to https://cdn.jsdelivr.net/gh/emeeks/d3-carto-map/d3.carto.map.js

https://d3js.org/d3.v3.min.js

https://d3js.org/topojson.v1.min.js

https://d3js.org/d3.geo.projection.v0.min.js

https://bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/tile.js

https://bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/d3.quadtiles.js

https://bl.ocks.org/emeeks/raw/f3105fda25ff785dc5ed/d3.geo.raster.js

https://rawgit.com/emeeks/d3-carto-map/master/d3.carto.map.js