Waypoints Only Pathfinding by Fox

eloquentUtils.js

//Utility Functions to make JS more Functional
var op = {
  "+": function(a, b){return a + b;},
  "==": function(a, b){return a == b;},
  "===": function(a, b){return a === b;},
  "!": function(a){return !a;}
};

var asArray = function(quasiArray, start) {
  var result = [];
  for (var i = (start || 0); i < quasiArray.length; i++)
    result.push(quasiArray[i]);
  return result;
}

function partial(func) {
  var fixedArgs = asArray(arguments, 1);
  return function(){
    return func.apply(null, fixedArgs.concat(asArray(arguments)));
  };
}

var Break = {toString: function() {return "Break";}};

var forEach = function(array, action) {
  try {
    for (var i = 0; i < array.length; i++)
      action(array[i]);
  }
  catch (exception) {
    if (exception != Break)
      throw exception;
  }
}

var reduce = function(combine, base, array) {
  forEach(array, function (element) {
    base = combine(base, element);
  });
  return base;
}

var map = function(func, array) {
  var result = [];
  forEach(array, function (element) {
    result.push(func(element));
  });
  return result;
}

var any= function(test, array) {
  for (var i = 0; i < array.length; i++) {
    var found = test(array[i]);
    if (found)
      return found;
  }
  return false;
}

var every=function(test, array) {
  for (var i = 0; i < array.length; i++) {
    var found = test(array[i]);
    if (!found)
      return found;
  }
  return true;
}

var member=function(array, value) {
  return any(partial(op["==="], value), array);
}

var flatten=function(arrays) {
    var result = [];
    forEach(arrays, function (array) {
      forEach(array, function (element){result.push(element);});
    });
    return result;
  }

var filter=function(test, array) {
  var result = [];
  forEach(array, function (element) {
    if (test(element))
      result.push(element);
  });
  return result;
}

var minimise=function(func, array) {
  var minScore = null;
  var found = null;
  forEach(array, function(element) {
    var score = func(element);
    if (minScore == null || score < minScore) {
      minScore = score;
      found = element;
    }
  });
  return found;
}

var getProperty=function(propName) {
  return function(object) {
    return object[propName];
  };
}

enlroads.js

var roads = {};

// just a function
function makeRoad(from, to, length)
{
  function addRoad(from, to)
    {
        if(!(from in roads))
            roads[from] = [];
      roads[from].push({to: to, distance: length});
    }
  addRoad(from, to);
  addRoad(to, from);
}

function makeRoads(start)
{
     for ( var i = 1; i < arguments.length; i+=2)
       makeRoad(start,arguments[i],arguments[i+1]);
}

function roadsFrom(place) {
    var found = roads[place];
    
    if (found == undefined)
        throw new error("No place named '" + place + "' found.");
    else
        return found;
}

function printRoads(start)
{
  var temp = roadsFrom(start);
  for( var x in temp)
    console.log(temp[x]);
}

function member(array, value) {
  for(var x in array){
    if(array[x] === value) return true;
  }
  return false;
}

function possibleRoutes(from, to) {
  function findRoutes(route) {
    function notVisited(road) {
      return !member(route.places, road.to);
    }
    function continueRoute(road) {
      return findRoutes({places: route.places.concat([road.to]), length: route.length + road.distance});
    }
    var end = route.places[route.places.length - 1];
    if (end == to)
      return [route];
    else
      return flatten(map(continueRoute, filter(notVisited,roadsFrom(end)) ) );
  }

  return findRoutes({places: [from], length: 0});
}

function shortestRoute(from,to) {
  var currentShortest = null;
  forEach(possibleRoutes(from,to), function(route){
    if(!currentShortest || currentShortest.length > route.length)
      currentShortest = route; 
  });
  return currentShortest;
}

function computeRealDistance(from, to){
  var sqrd = Math.pow(from, 2) + Math.pow(to,2);
  var dist = Math.sqrt(sqrd);
  return dist;
}

//Load data in to our map
makeRoads("Conference-Room2", "Conference-Room3", 19, "Water Fountain 2", 15, "Sales Department", 15);
makeRoads("Main Atrium", "Conference-Room3", 6, "Water Fountain 2", 5, "Info Kiosk", 4, "Check In", 11);
makeRoads("Marketing", "Water Fountain 2", 8, "Sales Department", 4);
makeRoads("Info Kiosk", "Sales Department", 3, "Water Fountain", 1);
makeRoads("Elevator Exit", "Water Fountain", 6, "Check In", 5);
makeRoads("Water Fountain", "Main Atrium", 3);
makeRoads("Extra Conference Room", "Check In", 3);
makeRoads("Conference Room 1", "Check In", 13, "Corridor to Building B", 14);

enlvis.js

//Setup Some Parameters
var mapWidth = 640;
var mapHeight = 320;
var nodeSize = 7;
var mapRoads = [];
var placeKeys = [];
var shortRoute = {};
var to = "",
    from = "";

var mapLocations = [{x:11.062, y:118.5, id:"Conference-Room2" },
                    {x:230.062, y:35.5, id:"Conference-Room3" },
                    {x:150.062, y:111.5, id:"Water Fountain 2" },
                    {x:150.062, y:224.5, id:"Sales Department" },
                    {x:206.062, y:104.5, id:"Main Atrium" },
                    {x:177.062, y:173.5, id:"Info Kiosk" },
                    {x:311.062, y:114.5, id:"Check In" },
                    {x:131.062, y:173.5, id:"Marketing" },
                    {x:213.062, y:166.5, id:"Water Fountain" },
                    {x:297.062, y:210.0, id:"Elevator Exit" },
                    {x:319.062, y:74.5, id:"Extra Conference Room" },
                    {x:425.062, y:97.5, id:"Conference Room 1" },
                    {x:549.062, y:101.5, id:"Corridor to Building B"}];

var mapOutline = "0,50 100,0 530,0 630,50 630,90 560,90 560,110 630,110 630,240 310,240 310,220 280,220, 280,240 0,240"

//Get all possible places, we need this to lookup routes
for(var temp in roads) placeKeys.push(temp);
// Get our Links between Nodes/Places
// Nodes, and PlaceKeys are in the same order, so we can lookup via the index and for our purposes assume they are 1:1
forEach(mapLocations, function(place){
    
    forEach(roads[place.id], function(road) {
        console.log(roads)
      mapRoads.push({source: place, target: mapLocations[placeKeys.indexOf(road.to)], dist: road.distance});
    });
});


//Translate the results of the Shortest path finder in to a friendlier format for D3 to visualize
//lookup all of the places in our roads object, and calculate distances from last place, and from start
function convertRoute(route) 
{
var newRoute = [];
var lastPlace = "";

map(function(place){
    newRoute.push({place: place, distanceFromLast: 0, distanceFromStart: 0});
    if(roads[lastPlace]) {
      forEach(roads[lastPlace],function(element){
        if(element.to == place) {
            newRoute[newRoute.length-1].distanceFromLast = element.distance;
            newRoute[newRoute.length-1].distanceFromStart = newRoute[newRoute.length-2].distanceFromStart + element.distance;
          }
      });
    }
    lastPlace = place;
},route.places);

return newRoute;
} 

//Visualize the Shortest Path on a subway style Route Map
function drawStraightRoute(){

var shortPath = convertRoute(shortRoute);

//Clear out the old SVG if one exists.
d3.select("#routeContainer").selectAll("svg").remove();

//Setup our chart size, radius of nodes, padding, and textSize
var w = 640,
    h = 300,
    r = 6,
    lp = 20, //padding for left side of chart range
    //padding for right, HACK way to make sure text labels aren't clipped.
    //the "correct" solution might be to draw the entire chart off screen check for clipping, then redraw on-screen.
    rp = 100, 
    xAx = h/3 + .5, // axis height
    textSize = 12;

    var x = d3.scale.linear()
    .domain([0, shortRoute.length])
    .range([r+lp, w-rp]);

//Quantize scale to avoid overlaps
function fit(val){

    var scaled = x(val);
    return scaled-scaled%((r*2));
}

//Create the SVG needed to display the route
var chart = d3.select("#routeContainer").append("svg")
    .attr("width", w)
    .attr("height", h);

//Create the circles that will represent our map points
var node = d3.select("#routeContainer").select("svg").selectAll("circle")
    .data(shortPath);

//Create the text labels for the node names
var placeLabel = d3.select("#routeContainer").select("svg").selectAll("text")
    .data(shortPath);

var distanceLabel = d3.select("#routeContainer").select("svg").selectAll("distanceLabel")
    .data(shortPath);

var distancePath = d3.select("#routeContainer").select("svg").selectAll("distancePath")
    .attr("class","distancePath")
    .data(shortPath);

// Enter…
node.enter().append("circle")
    .attr("class","routeNode")
    .attr("cx",function(d) {
      return fit(d.distanceFromStart);})
    .attr("cy",xAx)
    .attr("r",r);

placeLabel.enter().append("text")
    .attr("class","placeLabel")
    .style("text-anchor","start")
    .style("font-size",textSize + "px")
    .text(function(d) {return d.place})
    .attr("transform",function(d) { return "translate(" + (fit(d.distanceFromStart) + r/2 ) + ", " + (xAx + r + (textSize/2)) + ") rotate(45)"; });

distanceLabel.enter().append("text")
    .attr("class","distanceLabel")
    .style("text-anchor","middle")
    .style("font-size", textSize*.8 + "px")
    .text(function(d) {return d.distanceFromLast})
    .attr("transform",function(d) { 
      if(d.distanceFromLast != 0) 
        return "translate(" + ((fit(d.distanceFromStart - d.distanceFromLast) + fit(d.distanceFromStart))/2.0)  + ", " + (xAx - 4*r - 5) + ")";     
       // return "translate(" + (fit(d.distanceFromStart - d.distanceFromLast) + (fit(d.distanceFromStart) - fit(d.distanceFromStart - d.distanceFromLast))/2.0)  + ", " + (xAx - 4*r - 5) + ")"; 
      else return ""});

distancePath.enter().append("path")
  .attr("class","distancePath")
  .attr("d",function(d){
      if(d.distanceFromLast != 0) {
        var a = d.distanceFromStart;
        var b = d.distanceFromLast;

        //Path definition for curly brackets
        return ("M " + fit(a) + " " + (xAx-r) +
          " Q " + fit(a) + " " + (xAx-2*r) + " " + (fit(a) - .25*(fit(a)-fit(a-b))) + " " + (xAx -2*r) + 
          " T " + ((fit(a - b) + fit(a))*.5) + " " + (xAx-4*r) +
          " M " + (fit(a - b)) + " " + (xAx-r) +
          " Q " + (fit(a - b)) + " " + (xAx-2*r) + " " + (fit(a) - .75*(fit(a)-fit(a-b))) + " " + (xAx - 2*r) + 
          " T " + ((fit(a - b) + fit(a))*.5) + " " + (xAx-4*r));
    }
      else return });

// Exit…
node.exit().remove();
placeLabel.exit().remove();
distanceLabel.exit().remove();
distancePath.exit().remove();

}

function nodeClicked(place)
{   
    d3.select("#" + removeWhiteSpace(place)).attr("class","mapNodeActive");

    from = to;
    to = place;

    if (from != "") {
      shortRoute = shortestRoute(from,to);
      updateMap();
      drawStraightRoute();
    }
    
}

function updateMap()
{
    //reset our highlighted styles
    d3.selectAll(".mapLinkActive").attr("class","mapLink");
    d3.selectAll(".mapNodeActive").attr("class","mapNode");

    var lastPlace = "";
    forEach(shortRoute.places, function(place){
        d3.select("#" + removeWhiteSpace(place)).attr("class","mapNodeActive");
        //Try both directions to find link
        d3.select("#" + removeWhiteSpace(place) + "-" + removeWhiteSpace(lastPlace)).attr("class","mapLinkActive");
        d3.select("#" + removeWhiteSpace(lastPlace) + "-" + removeWhiteSpace(place)).attr("class","mapLinkActive");
        lastPlace = place;
    });
}

function drawMap()
{
    var svg = d3.select("#mapContainer").append("svg")
    .attr("width", mapWidth)
    .attr("height", mapHeight);

    var outline = d3.select("#mapContainer").select("svg")
    .append("polyline")
    .attr("points",mapOutline)
    .attr("class","mapOutline");
    
    var nodes = d3.select("#mapContainer").select("svg").selectAll("mapNode")
    .attr("class", "mapNode").data(mapLocations);

    var links = d3.select("#mapContainer").select("svg").selectAll("mapLinks")
    .attr("class", "mapLinks").data(mapRoads);

    var labels = d3.select("#mapContainer").select("svg").selectAll("mapLabels")
    .attr("class", "mapLabels").data(mapLocations);

    links.enter().append("line")
    .attr("class","mapLink")
    .attr("id",function(d){ return removeWhiteSpace(d.source.id) + "-" + removeWhiteSpace(d.target.id);})
    .attr("x1",function(d){ return d.source.x;})
    .attr("y1",function(d){ return d.source.y;})
    .attr("x2",function(d){ return d.target.x;})
    .attr("y2",function(d){ return d.target.y;});

    nodes.enter().append("circle")
    .attr("class","mapNode")
    .attr("id",function(d){ return removeWhiteSpace(d.id);})
    .attr("cx",function(d){ return d.x;})
    .attr("cy",function(d){ return d.y;})
    .attr("r", nodeSize)
    .on("click", function(d) { nodeClicked(d.id); });

    labels.enter().append("text")
    .attr("class","mapLabels")
    .text(function(d){ return d.id;})
    .style("fill","white")
    .style("text-anchor", function(d){
        if(d.x < 100) return "start"; // Hack to prevent label clipping
        if(d.x > 400) return "end"; // Hack to prevent label clipping
        else return "middle";
    })
    .attr("transform", function(d){ 
      if(d.id == "Hanakee Pearl Lodge") return "translate(" + d.x + ", " + (d.y - 10) + ")"; // Hack to prevent label overlap
      return "translate(" + d.x + ", " + (d.y + 14) + ")";});
    
    outline.exit().remove();
    links.exit().remove();
    nodes.exit().remove();
}

function removeWhiteSpace(str)
{
  return str.replace(/\s/g, '');
}

drawMap();

index.html

<html>
<title> Simple JS Waypoints with customizable heuristic </title>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script type="text/javascript" src="eloquentUtils.js"></script>
<script type="text/javascript" src="enlroads.js"></script>
<style>

body {
  background: #a8a8a8;
	font-family: Arial, Helvetica, sans-serif;
	min-height: 900px
}

#routeContainer {
	text-align: center;
}

#mapContainer {
	text-align: center;
}

.routeNode {
	fill: #4682B4;
	stroke: #4A4A4A;
}

.distancePath {
	stroke: #666666;
	stroke-width: 1px;
	fill: none;
}

.mapOutline {
	fill: #070707;
	stroke: #747474;
	stroke-width: 3px;
}

.mapLink {
	stroke:#ffffff;
	stroke-width: .5px;
}

.mapNode {
	fill: #666666;
  stroke: #ffffff;
	stroke-width: .5px;
}

.mapLinkActive {
	fill:#ffffff;
	stroke:#c13030;
	stroke-width: 1px;
}

.mapNodeActive {
	fill:#c13030;
	stroke:#ffffff;
	stroke-width:.5px;
}

.mapLabels {
	font-size: 10px;
  color: #ffffff;
}

p {
	text-align: center;
	font-size: .8em;
}

</style>

<body>
<p>A pure waypoints solution for path finding. Click on two points to find the least "cost" path between them.</p>
<div id="mapContainer"></div>
<p>This is a proof of concept that any heuristic can be used with waypoints; it does not have to be shortest distance. Shortest distance in most cases will make sense, but there will be exceptions. Below, you can visualize the "cost" of each distance on a simplified chart. See what the cost was for each traversal between points in the user's definition. For shortest distance, its a simple matter of using the getTotalLength built in or the Pythagorean distance for point-to-point. </p>
<div id="routeContainer"></div>
<script type="text/javascript" src="enlvis.js"></script>
</body>
</html>