Comments (5)
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
from ngraph.path.
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.
from ngraph.path.
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.
from ngraph.path.
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.
from ngraph.path.
I've made a PR to expose the parent node to the distance()
function to enable this: #42
from ngraph.path.
Related Issues (18)
- Publish graph-from-ascii separately HOT 2
- Turn penalties HOT 4
- The CDN is down HOT 1
- contraction hierarchies HOT 1
- Subgraphs around a center node?
- Possible to get the total path distance from a pathFinder lookup? HOT 1
- Getting specific link when used with multigraph
- is It possible to get more than one path ?? HOT 2
- How to use HTML? HOT 1
- createGraph doesn't exist HOT 2
- Using GPU to speed up pathfinding on large graphs
- allow providing custom goal? HOT 2
- Stop when a condition is met
- Unable to use blocked and distance HOT 1
- What about providing a simple installation way? HOT 4
- Option to have multiple paths HOT 4
- Usage in a grid based system HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from ngraph.path.