"fewest turns" refinement?

[leeoniya]

hey @anvaka,

nice lib!

how feasible is it to add some post-processing pass to produce a "fewest turns" route to reduce the number of left-right-left-right turns in the path at the expense of some configurable "cost" for additional distance added to the route.

i frequently find it ultra aggravating when a destination can be reached with 3 turns and an extra 0.25mi rather than 7 turns. it simplifies the directions and number of legs in each route. google maps has a habit of providing such "scenic" routes.

thanks!

[anvaka]

I remember asking similar question to @redblobgames (Amit Patel) and if I recall correctly, Amit suggested to model turns as additional edges in a graph with non-zero cost.

That way turns will be more costly and algorithm should try to reduce their amount

[redblobgames]

The A* graph nodes should be the important state for making decisions. Normally we just use location for this. But if you want to take turns into account you would want location and direction for the graph nodes.

The edges can be two types:

• road: (location A, east) → (location B, east) is traveling along a road, keeping the same direction
• intersection: (location A, east) → (location A, south) is turning right at an intersection

You can then assign costs to the turns, e.g. left turns (X, east) → (X, north) might cost more than right turns (X, east) → (X, south), and both might cost more than going straight through an intersection (X, east) → (X, east).

(It is also possible to merge these two into one edge type but that's an optimization that adds some complexity)

One of these days I should make an interactive demo showing how this works.

[leeoniya]

i wonder if it'd be practical to pre-adjust the cost of some edges using custom weighting criteria, eg. known traffic, street capacity/size, typical speed, number of intersections/stop signs, construction, potholes. this could force the existing algo to prefer main roads more frequently than small ones (which is usually where this behavior becomes a nuisance). then it would just be a matter of properly tweaking the weighting amount.

[redblobgames]

There are lots of fun things to do with costs once you switch from "cost is distance" to "cost is time" and then "cost is time plus annoyance" or "cost is upper bound on time" or other things like that. You can also model time of day or current traffic (as Google Maps does) if you want the costs to vary. And another possibly fun thing is to refine the path further by taking into account lanes. The road link A → B would be A₁ → B₁ (stay in right lane), A₁ → B₂ (change lanes), A₂ → B₁ (change lanes), A₂ → B₂ (stay in left lane). Then you can have intersections model turn restrictions, such as you can only turn right from the right lane or only turn left from the left lane. That then allows you to factor in annoying maneuvers like "you just turned right onto a road but you have to quickly get into the left lane to make the next left". Lots of tweaks and additional modeling you can do (in theory) depending on how important it is to the application. However I haven't worked with ngraph to see which ones work nicely with it.

[georeith]

I've made a PR to expose the parent node to the distance() function to enable this: https://github.com/anvaka/ngraph.path/pull/42