# Cost-distance shortest path

I want to compute the shortest paths travelling overland between the origin (Africa) and destination (North America). My goal is to recreate human migration, and the shortest path should be across the Bering Strait. First, I have converted a shapefile to a raster, imputing value 1 to land and a large value (999999999,000000) to water. If my first step is correct, I do not have any no_data cell because I pre-initialize it with a value.

Second, I compute the cost using `r.cost` function under GRASS.

Finally, I use `r.drain` to obtain the shortest path.

For some unknown reason to me, I must use the `cost raster` and the `movement direction map` ticking the `The input raster map is a cost surface` selector.

The result indicates that the shortest path consists in travelling via Iceland, thus crossing the Atlantic where each cell has a cost of 999999999 compared to the cost of 1 for travelling overland.

I think I cannot increase more the cost of water travelling. How can I modify my workflow to force the Bearing route?

• I think it's got something to do with the projection. We understand that the right edge of your map connects to the left, but the tool may not. Have you tried reprojecting your raster into a pacific-centered projection? Commented May 8, 2019 at 17:32
• I think you are missing the ice, which make travel cost less expensive than water an temperature, that should make very expensive to reach the north or south pole Commented May 9, 2019 at 5:48
• @JoshC Exactly this! Changing my projection to one centered on the Pacific solved the issue. Commented May 10, 2019 at 13:56

## 2 Answers

Your process is fine; the problem is that your projection is centered on Europe, and your tool won't "wrap" to the other side.

To address this, you can reproject your layers to a Pacific-centered projection, like the PDC Mercator (EPSG 3832). In such a projection, your tool will be able to continue its path from Asia to North America across the Bering Strait.

If you know what you're doing, you can also create a new Custom Projection, found under the Settings menu. In the Parameters area, you can adjust the `+lon_0=` parameter to change where the map is centered. Starting from something like the Mercator, such an adjustment is very simple. If you're working in other projections, this can be a perilous task without understanding what each of the parameters is.

If you're interested, you should look at PROJ's own documentation. When you understand what's happening in a given projection, you will be more able to customize it safely.

``````<!DOCTYPE html>
<html>
<head>
<meta charset='utf-8' />
<title>Full code</title>
<meta name='viewport' content='initial-scale=1,maximum-scale=1,user-scalable=no' />
<script src='https://npmcdn.com/@turf/turf/turf.min.js'></script>
<script src='https://ajax.googleapis.com/ajax/libs/jquery/3.1.1/jquery.min.js'></script>
<script src='https://api.tiles.mapbox.com/mapbox-gl-js/v1.7.0/mapbox-gl.js'></script>
<link href='https://api.tiles.mapbox.com/mapbox-gl-js/v1.7.0/mapbox-gl.css' rel='stylesheet' />
<style>

body {
margin: 0;
padding: 0;
}

#map {
position: absolute;
top: 0;
bottom: 0;
right: 0;
left: 0;
}
.truck {
margin: -10px -10px;
width: 20px;
height: 20px;
border: 2px solid #fff;
border-radius: 50%;
background: #3887be;
pointer-events: none;
}

</style>
</head>
<body>
<div id='map' class='contain'></div>
<script>
var truckLocation = [76.050797, 22.962267];
var warehouseLocation = [75.857727, 22.719568];
var lastQueryTime = 0;
var lastAtRestaurant = 0;
var keepTrack = [];
var currentSchedule = [];
var currentRoute = null;
var pointHopper = {};
var pause = true;
var speedFactor = 40;

// Add your access token
mapboxgl.accessToken = 'pk.eyJ1IjoiYWtzaGl0Y2hhcHJvdCIsImEiOiJjazYwYzU1b2IwNjExM2xzNmtsbWxxNnJ3In0.OvuCCyqVi9T5PYORKfUz4w';

// Initialize a map
var map = new mapboxgl.Map({
container: 'map', // container id
style: 'mapbox://styles/mapbox/light-v10', // stylesheet location
center: truckLocation, // starting position
zoom: 8 // starting zoom
});

// Create a GeoJSON feature collection for the warehouse
var warehouse = turf.featureCollection([turf.point(warehouseLocation)]);

// Create an empty GeoJSON feature collection for drop-off locations
var dropoffs = turf.featureCollection([]);

// Create an empty GeoJSON feature collection, which will be used as the data source for the route before users add any new data
var nothing = turf.featureCollection([]);

map.on('load', function() {
var marker = document.createElement('div');
marker.classList = 'truck';

// Create a new marker
truckMarker = new mapboxgl.Marker(marker)
.setLngLat(truckLocation)
.addTo(map);

// Listen for a click on the map
map.on('click', function(e) {
// When the map is clicked, add a new drop-off point
// and update the `dropoffs-symbol` layer
newDropoff(map.unproject(e.point));
updateDropoffs(dropoffs);
});

map.addLayer({
id: 'dropoffs-symbol',
type: 'symbol',
source: {
data: dropoffs,
type: 'geojson'
},
layout: {
'icon-allow-overlap': true,
'icon-ignore-placement': true,
'icon-image': 'marker-15',
}
});

// Create a circle layer
map.addLayer({
id: 'warehouse',
type: 'circle',
source: {
data: warehouse,
type: 'geojson'
},
paint: {
'circle-radius': 20,
'circle-color': 'white',
'circle-stroke-color': '#3887be',
'circle-stroke-width': 3
}
}
);

map.addSource('route', {
type: 'geojson',
data: nothing
});

map.addLayer({
id: 'routeline-active',
type: 'line',
source: 'route',
layout: {
'line-join': 'round',
'line-cap': 'round'
},
paint: {
'line-color': '#3887be',
'line-width': [
"interpolate",
["linear"],
["zoom"],
12, 3,
22, 12
]
}
}, 'waterway-label');

// function newDropoff(coords) {
//   // Store the clicked point as a new GeoJSON feature with
//   // two properties: `orderTime` and `key`
//   var pt = turf.point(
//     [coords.lng, coords.lat],
//     {
//       orderTime: Date.now(),
//       key: Math.random()
//     }
//   );
//   dropoffs.features.push(pt);
// }

function newDropoff(coords) {
// Store the clicked point as a new GeoJSON feature with
// two properties: `orderTime` and `key`
var pt = turf.point(
[coords.lng, coords.lat],
{
orderTime: Date.now(),
key: Math.random()
}
);
dropoffs.features.push(pt);
pointHopper[pt.properties.key] = pt;

// Make a request to the Optimization API
\$.ajax({
method: 'GET',
url: assembleQueryURL(),
}).done(function(data) {
// Create a GeoJSON feature collection
var routeGeoJSON = turf.featureCollection([turf.feature(data.trips[0].geometry)]);

// If there is no route provided, reset
if (!data.trips[0]) {
routeGeoJSON = nothing;
} else {
// Update the `route` source by getting the route source
// and setting the data equal to routeGeoJSON
map.getSource('route')
.setData(routeGeoJSON);
}

if (data.waypoints.length === 12) {
window.alert('Maximum number of points reached. Read more at docs.mapbox.com/api/navigation/#optimization.');
}
});
}

function updateDropoffs(geojson) {
map.getSource('dropoffs-symbol')
.setData(geojson);
}

// Here you'll specify all the parameters necessary for requesting a response from the Optimization API
function assembleQueryURL() {

// Store the location of the truck in a variable called coordinates
var coordinates = [truckLocation];
var distributions = [];
keepTrack = [truckLocation];

// Create an array of GeoJSON feature collections for each point
var restJobs = objectToArray(pointHopper);

// If there are any orders from this restaurant
if (restJobs.length > 0) {

// Check to see if the request was made after visiting the restaurant
var needToPickUp = restJobs.filter(function(d, i) {
return d.properties.orderTime > lastAtRestaurant;
}).length > 0;

// If the request was made after picking up from the restaurant,
// Add the restaurant as an additional stop
if (needToPickUp) {
var restaurantIndex = coordinates.length;
// Add the restaurant as a coordinate
coordinates.push(warehouseLocation);
// push the restaurant itself into the array
keepTrack.push(pointHopper.warehouse);
}

restJobs.forEach(function(d, i) {
// Add dropoff to list
keepTrack.push(d);
coordinates.push(d.geometry.coordinates);
// if order not yet picked up, add a reroute
if (needToPickUp && d.properties.orderTime > lastAtRestaurant) {
distributions.push(restaurantIndex + ',' + (coordinates.length - 1));
}
});
}

// Set the profile to `driving`
// Coordinates will include the current location of the truck,
return 'https://api.mapbox.com/optimized-trips/v1/mapbox/driving/' + coordinates.join(';') + '?distributions=' + distributions.join(';') + '&overview=full&steps=true&geometries=geojson&source=first&access_token=' + mapboxgl.accessToken;
}

function objectToArray(obj) {
var keys = Object.keys(obj);
var routeGeoJSON = keys.map(function(key) {
return obj[key];
});
return routeGeoJSON;
}

// Create a symbol layer on top of circle layer
map.addLayer({
id: 'warehouse-symbol',
type: 'symbol',
source: {
data: warehouse,
type: 'geojson'
},
layout: {
'icon-image': 'grocery-15',
'icon-size': 1
},
paint: {
'text-color': '#3887be'
}
});

map.addLayer({
id: 'routearrows',
type: 'symbol',
source: 'route',
layout: {
'symbol-placement': 'line',
'text-field': '▶',
'text-size': [
"interpolate",
["linear"],
["zoom"],
12, 24,
22, 60
],
'symbol-spacing': [
"interpolate",
["linear"],
["zoom"],
12, 30,
22, 160
],
'text-keep-upright': false
},
paint: {
'text-color': '#be4a38',
'text-halo-color': 'hsl(55, 11%, 96%)',
'text-halo-width': 3
}
}, 'waterway-label');

});

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