A* search algorithm（グラフ探索） #JavaScript

こんにちは。
A* search algorithm の Javascript 実装（下記）を利用し、最短経路探索を行ってみました¹ ²。地図表示には d3.mapzoom を利用しました³。

A* Search Algorithm in JavaScript (Updated) - Brian Grinstead
- javascript-astar (demo)
- https://github.com/bgrins/javascript-astar

始点は Paris、終点は Cannes の条件（query = {"start": "Paris", "end": "Cannes"};）を与えると下記の結果（および計算時間、最短経路解は地図上で矢印付き表示）が得られます。

astar.html

<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="utf-8" />
<meta http-equiv="content-language" content="ja">
<title>A-star</title>
<!-- A* (A-star) route finding on a zoomable map using javascript-astar (astar.js) by Brian Grinstead and d3.mapzoom by Simon Jacobs
- astar.js (https://github.com/bgrins/javascript-astar)
- d3.mapzoom.js (http://bl.ocks.org/sdjacobs) -->
<script src="astar.js"></script>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="http://d3js.org/d3.geo.tile.v0.min.js"></script>
<script src="d3.mapzoom.js"></script>
<style>
circle {
  fill: #ccc;
  stroke: #333;
  stroke-width: 1.5px;
}
</style>
</head>
<body>
<div id="canvas"></div>
<script>
  var width = 800, height = 600;
  var MILE=1609, KM=1000, RE=6371*KM, DEGREE=Math.PI/180;
  var query, nodes, links, mapCenter, mapScale, unitDistance=KM;

  mapCenter = [8.0, 47.0], mapScale = 1800;
  query = {"start": "Paris", "end": "Cannes"};
  nodes = [
    {name: "Paris", lon: 2.3508, lat: 48.8567},
    {name: "Lyon", lon: 4.84, lat: 45.76},
    {name: "Marseille", lon: 5.37, lat: 43.2964},
    {name: "Bordeaux", lon: -0.58, lat: 44.84},
    {name: "Cannes", lon: 7.0128, lat: 43.5513},
    {name: "Toulouse", lon: 1.444, lat: 43.6045},
    {name: "Reims", lon: 4.0347, lat: 49.2628}
  ];
  links = [
    {source:"Paris", target:"Lyon", distance:464},
    {source:"Paris", target:"Bordeaux", distance:582},
    {source:"Paris", target:"Reims", distance:144},
    {source:"Lyon", target:"Marseille", distance:314},
    {source:"Marseille", target:"Cannes", distance:175},
    {source:"Marseille", target:"Toulouse", distance:403},
    {source:"Bordeaux", target:"Toulouse", distance:245}
  ];

  links = links.concat(createReverseLinks(links));
  var result = astarRouting(nodes, links);

  document.write(result.route.join(', ')+" ("+String(result.calculationTime)+" ms)<br>");

  markRoute(result.path);
  drawMap(nodes, links);


  function createReverseLinks(links) {
    return links.map(function(d) {return {"source":d.target, "target":d.source, "distance":d.distance}})
  }
  function markRoute(routePath) {
    routePath.forEach(function(i) {links[i.index]["route"]=true;});
  }

  function astarRouting(nodes, links) {

    function GeoGraph(nodes, links) {
      this.nodes = {};
      this.links = links;
      for (var i = 0; i < nodes.length; ++i) {
        var node = nodes[i],
            obj = new GeoNode(node.name, +node.lon, +node.lat);
        this.nodes[obj.name] = obj;
      }
      this.init();
    }

    GeoGraph.prototype.init = function() {
      this.dirtyNodes = [];
      for (var k in this.nodes) {
        astar.cleanNode(this.nodes[k]);
      }
    };
    GeoGraph.prototype.cleanDirty = Graph.prototype.cleanDirty;
    GeoGraph.prototype.markDirty = Graph.prototype.markDirty;

    GeoGraph.prototype.neighbors = function(node) {
      var nodes=this.nodes, 
          neighs=createNeighbors(node,this.links);
      return neighs.map(function(name) {return nodes[name];});
    };

    createNeighbors = function(node, links) {
    var neighs = node.neighbors;
    if (!Object.keys(neighs).length) {
      for (var n,i=links.length-1; i>=0; i--) {
        if (links[i].source==node.name) {
          n=links[i].target;
          neighs[n] = new Neighbor(i, links[i].distance*unitDistance);
        }
      }
      node.neighbors = neighs;    
      }
    return Object.keys(neighs);
    };

    function Neighbor(index, cost) {
      this.index = index;
      this.cost = cost;
    }

    function GeoNode(name, lon, lat) {
      this.name = name;
      this.lon = lon*DEGREE;
      this.lat = lat*DEGREE;
      this.neighbors = {};
    }

    GeoNode.prototype.weight = 1;
    GeoNode.prototype.isWall = function() {
      return this.weight === 0;
    };
    GeoNode.prototype.getCost = function(nodeSource) {
      return nodeSource.neighbors[this.name].cost;
    };

    GeoNode.prototype.getLinks = function(node) {
      return this.neighbors[node.name];
    };

    var GeoDistance = function(p, q) {
      var y=p.lat-q.lat, x=(p.lon-q.lon)*Math.cos((p.lat+q.lat)/2)
      return Math.hypot(x,y)*RE;
    };

    var graph = new GeoGraph(nodes, links);
    var startEnd = ["start", "end"].map(function(x) {return graph.nodes[query[x]];});
    var sTime = new Date();
    var result = astar.search(graph, startEnd[0], startEnd[1], {heuristic: GeoDistance});
    var deltaTime = new Date() - sTime;
    var route = [query["start"]].concat(result.map(function(x) {return x.name}));
    var path = result.map(function(x) {return x.parent.getLinks(x);});
    return {"route": route, "path": path, "calculationTime": deltaTime};
  }

  function drawMap(nodes, links) {
    var mapzoom = d3.mapzoom()
        .center(mapCenter)
        .scale(mapScale);
    var svg = d3.select("body").append("svg")
        .attr("width", width)
        .attr("height", height)
        .call(mapzoom);
    var frame = svg.append("g");

    mapzoom.addTileLayer(frame, "tiles.mapbox.com/v4/mapbox.light/", ".png");

    var projection = mapzoom.projection(), nodesByName = {};

    nodes.forEach(function(d) {
      d.coord = [+d.lon, +d.lat]
      nodesByName[d.name] = d;
      d.links = [];
    });
    links.forEach(function(d) {
      d.source = nodesByName[d.source]
      d.target = nodesByName[d.target]
      d.distance = +d.distance;
    });

    var link = svg.append("g").selectAll(".link")
      .data(links)
      .enter().append("path")
      .attr("class", "link")
      .style("stroke", "#00c000")
      .style("stroke-width", 1);

    var node = svg.append("g").selectAll(".node")
        .data(nodes)
        .enter().append("circle")
        .attr("class", "node")
        .attr("r", 3)
        .attr("fill", "grey")

    node.append("title")
        .text(function(d) { return d.name; });

    midPoint = function(a,b) {
      var n=7;
      return [(a[0]*n+b[0])/(n+1),(a[1]*n+b[1])/(n+1)];
    }

    mapzoom.addLayer(function() {
        node
            .each(function(d) {d.proj = projection(d.coord);})
            .attr("transform", function(d) { return "translate(" + d.proj + ")" })
        link
            .attr("d", function(d) { return "M " + d.source.proj + " L " + midPoint(d.source.proj,d.target.proj) + " L " + d.target.proj })
            .attr("marker-mid", function(d) {if(d.route===true) return 'url(#arrowhead)';});
     });

    svg.append('defs').append('marker')
        .attr({'id':'arrowhead',
               'viewBox':'0 -5 10 10',
               'refX':0,
               'refY':0,
               'orient':'auto',
               'markerWidth':10,
               'markerHeight':10,
               'xoverflow':'visible'})
        .append('svg:path')
            .attr('d', 'M 2,0 L 0,-3 L 10,0 L 0,3')
            .attr('fill', '#0080ff');
  }
</script>
</body>
</html>

pathfinding (wikipedia) or route finding。 ↩
「AStar.js(A*アルゴリズム)を使ってみた」 ↩
表示にMapboxGLを利用した版は「A* search algorithm（グラフ探索、MapboxGL）」。 ↩