LoginSignup
2
3

More than 5 years have passed since last update.

@kkdd

A* search algorithm（グラフ探索、Mapbox GL JS）

Last updated at Posted at 2016-12-02

こんにちは。
A* search algorithm の Javascript 実装（下記）の利用による最短経路探索で1 2、今回は地図表示に Mapbox GL JS を利用し、interactive 風にしてみました。

地図上の二箇所をマウスでクリックすると近傍都市を始点終点とした経路探索が走ります（下記例は始点 Paris、終点 Cannes）。

astar.jpg

astar.html
<!DOCTYPE html>
<html>
<meta charset="utf-8">
<script src="astar.js"></script>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src='https://api.tiles.mapbox.com/mapbox-gl-js/v0.29.0/mapbox-gl.js'></script>
<link href='https://api.tiles.mapbox.com/mapbox-gl-js/v0.29.0/mapbox-gl.css' rel='stylesheet' />
<style>
body { margin:0; padding:0; }
#map { position:absolute; top:0; bottom:0; width:100%; }
svg {
  position: absolute;
  width: 100%;
  height: 100%;
}
circle {
  stroke: #222;
  stroke-width: 0.7px;
}
</style>
</head>
<body>
<div id="map"></div>
<script>
var MILE=1609, KM=1000, RE=6371*KM, DEGREE=Math.PI/180;
var units = {mi: MILE, km: KM};
var mapCenter = [4.0, 46.0], mapScale = 4, unitDistance='km';
var 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}
  ];
var 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}
  ];

main(nodes, links);

function main(nodes, links) {
  links = setupNodesLinks(nodes, links);

  mapboxgl.accessToken = '<your access token here>';

  var map = new mapboxgl.Map({
    container: 'map', // container id
    style: "mapbox://styles/mapbox/light-v9",
    center: mapCenter,
    zoom: mapScale,  
  })

  map.addControl(new mapboxgl.NavigationControl());
  var container = map.getCanvasContainer()
  var svg = d3.select(container).append("svg")

  function markRoute(routePath) {
    links.forEach(function(l) {delete l.route;});
    routePath.forEach(function(i) {links[i.index]["route"]=true});
  }

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

  function mapboxProjection(lonlat) {
    var p = map.project(new mapboxgl.LngLat(lonlat[0], lonlat[1]))
    return [p.x, p.y];
  }

  function modName(name) {
    return name.replace(/\s/g,"_").replace(/\./g,"");
  }

  function lngLat2coord(lngLat) {
    return {coord:[lngLat.lng, lngLat.lat]};
  }

  function markNode(nodeName) {
    if (nodeName=="deselectAll") {d3.selectAll('circle').style("fill", defaultNodeColor);}
    else {
      var markNodeColor = 'blue';
      d3.select('circle#'+modName(nodeName)).style("fill", markNodeColor);
    }
  }

  svg.append('defs').append('marker')
      .attr({'id':'arrowhead',
             'viewBox':'0 -5 10 10',
             'refX':0,
             'refY':0,
             'orient':'auto',
             'markerWidth':10,
             'markerHeight':10,
             'markerUnits':'userSpaceOnUse',
             'xoverflow':'visible'})
      .append('svg:path')
      .attr('d', 'M 2,0 L 0,-3 L 10,0 L 0,3')
      .attr('fill', '#2080f0');

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

  var defaultRadius = 3, defaultNodeColor = "#ccc";
  var node = svg.append("g").selectAll(".node")
      .data(nodes)
      .enter().append("circle")
      .attr("class", "node")
      .attr("r", defaultRadius)
      .attr("id", function(d) {return modName(d.name);})
      .style("fill", defaultNodeColor)

  link.each(function(d) {
      d.source.links.push(d);
      d.selection = d3.select(this);
  });

  node.each(function(d) {
      d.selection = d3.select(this);
  });

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

  link.append("title")
      .text(function(d) { return d.source.name + " → " + d.target.name + "\n" + d.distance + " " + unitDistance});

  var query = {};

  map.on('click', function(e) {
    var q=lngLat2coord(e.lngLat);
    var nodeDistance=nodes.map(function(p) {return GeoDistance(p,q)});
    var imin = nodeDistance.indexOf(Math.min.apply(null,nodeDistance));    
    if (query.start==undefined) {
      query.start=nodes[imin].name;
      markNode("deselectAll");
    }
    else if (query.end==undefined) {
      query.end=nodes[imin].name;
      var result = astarRouting(nodes, links, query);
      markRoute(result.path);
      render();
      query = {};
    }
    markNode(nodes[imin].name);
  });


  function render() {
    node
      .each(function(d) {d.proj = mapboxProjection(d.coord); })
      .attr("transform", function(d) { return "translate(" + d.proj + ")" });
    link
      .attr("d", function(d) {var a=mapboxProjection(d.source.coord), c=mapboxProjection(d.target.coord), b=midPoint(a,c); return "M "+a+" L "+b+" L "+c;})
      .attr("marker-mid", function(d) {return (d.route===true)?'url(#arrowhead)':'none';})
  }

  map.on("viewreset", function() {
    render()
  })

  map.on("move", function() {
    render()
  })

  render()

}


function GeoDistance(p, q) {
  var x=p.coord[0]-q.coord[0], y=p.coord[1]-q.coord[1], t=p.coord[1]+q.coord[1];
  x*=Math.cos(t/2*DEGREE);
  return Math.hypot(x*x+y*y)*DEGREE*RE;
};


function setupNodesLinks(nodes, links) {

  function createReverseLinks(links) {
    return links.map(function(d) {
      return {"source":d.target, "target":d.source, "distance":d.distance}
    })
  }

  links = links.concat(createReverseLinks(links));

  var 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]  // overwrite
    d.target = nodesByName[d.target]
    d.distance = +d.distance;
  });

  return links;
}


function astarRouting(nodes, links, query) {

  function GeoGraph(nodes, links) {
    this.nodes = {};
    this.links = links;
    for (var i=nodes.length-1; i>=0; i--) {
      var node = nodes[i];
      this.nodes[node.name] = new GeoNode(node);
    }
    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 neighs=Object.keys(node.neighbors);
    if (!neighs.length) {
        neighs = createNeighbors(node, this.links);
    }
    return nodesByName(neighs, this.nodes);
  };

  function nodesByName(names, nodes) {
      return names.map(function(n) {return nodes[n];});
  }

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

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

  function GeoNode(node) {
    this.name = node.name;
    this.coord = node.coord;
    this.neighbors = {};
  }

  GeoNode.prototype.weight = 1;
  GeoNode.prototype.isWall = function() {
    return this.weight === 0;
  };
  GeoNode.prototype.getCost = function(nodeSource) {
    return this.getNeighbor(nodeSource).cost;
  };

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

  function getLink(node) {
    return node.getNeighbor(node.parent);
  }

  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 getLink(x);});
  return {"route": route, "path": path, "calculationTime": deltaTime};
}

</script>
</body>
</html>

  1. 前回は地図表示に d3.mapzoom を利用しました。 ↩

  2. なお Dijkstra アルゴリズムについては、"Putting Dijkstra's algorithm on the map (Simon Jacobs’s Block)" のコードがほぼ同様に動くと思います。 ↩

2
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
3