4 ms·

I've gone down a bit of a rabbit hole on path finding in the last week or two (most recently, this isn't the first time). When you have some knowledge of the to

by foota 2y ago

I've gone down a bit of a rabbit hole on path finding in the last week or two (most recently, this isn't the first time). When you have some knowledge of the topology of the graph you can use different techniques to do better than djikstra's. Of course, if you have lots of time and space and a completely static graph, you can run all pairs shortest paths and simply store all the results for O(1) path lookup, but there are intermediates for varying types of graphs. This stack exchange article is a good overview: https://cstheory.stackexchange.com/questions/11855/how-do-the-state-of-the-art-pathfinding-algorithms-for-changing-graphs-d-d-l https://cstheory.stackexchange.com/questions/11855/how-do-th.... I've been wondering about how well D* lite would perform in practice with a somewhat varying graph. I read some suggestions that if the graph is changing even a bit on occasion, then it will mostly degrade to A*, since many changed paths would need to be re-evaluated. In the context of games, I've also been thinking about a technique called true distance heurustics (TDH), where you essentially precompute the distances between some fixed set of nodes, and then use those as a part of the heurustic for A* (or D* lite in this case), but it seems like updating these TDH in the case of a changing graph might introduce just as much overhead as not having them in the first place. It might be an interesting trade off though, if you have some "lines" (e.g., think train lines) that are much faster than roadways, you could handle each of these specially via the TDH, and in exchange you would be able to assume a lower "max speed" for use with the A* heurustic, allowing you to explore fewer paths (since with a lower "max speed" paths will more rapidly increase in cost), whereas if you had to assume all car based paths could move as fast as a train, you would have to explore more paths.

kevinwang 2y ago
> When you have some knowledge of the topology of the graph you can use different techniques to do better than djikstra's. But that statement doesn't apply to the version of Dijkstra's developed in this paper right? > Universal optimality is a powerful beyond-worst-case performance guarantee for graph algorithms that informally states that a single algorithm performs as well as possible for every single graph topology.
- foota 2y ago
  No, I don't believe so. It clarifies specifically what problem it is optimal for "We prove that our working-set property is sufficient to guarantee universal optimality, specifically, for the problem of ordering vertices by their distance from the source vertex", but A* only explores a subset of vertices based on the heuristic, so it can be more efficient.
- mlyle 2y ago
  > > When you have some knowledge of the topology of the graph you can use different techniques to do better than djikstra's. > But that statement doesn't apply to the version of Dijkstra's developed in this paper right? Simple thought experiment: I have an algorithm that has path costs for one graph memorized and first compares to that graph; it's O(V+E) to compare and return the value for that memorized graph. It obviously beats this algorithm for that graph.
  - foota 2y ago
    Hm... technically they're saying that their algorithm performs as well as possible "for every single graph topology". Your special cased algorithm would only work for one particular graph in a family of isomorphic graphs (unless you have a linear time algorithm for the graph isomorphism problem, in which case please share), but would fail for the rest of the graphs in the family. So I think you could still say that their algorithm performs as well as possible for that topology.
Jadrago 2y ago
Does google maps use something like this? I imagine all pairs is too expensive, but the topology should be fairly consistent over time
- urbandw311er 2y ago
  Google maps uses something called contraction hierarchies
  - DennisL123 2y ago
    Without knowing what they actually use, I feel comfortable to state that the industry has moved on from Contraction Hierarchies to somewhat more flexible techniques. These allow you to take traffic information and road closures, and user preferences, and whatnot into account without requiring a full re-processing of the input data with each traffic update. The state of the art is a two-step preprocessing that first decomposes the road network into cells, and then processes these cells independently. Sometimes it goes by the name of customisable route planning, sometimes it is called multi-level Dijkstra.
- ahoka 2y ago
  One trick we used when I was in the transportation business is to pre-calculate the distances between border crossings and gas stations.
- DennisL123 2y ago
  Storing the distances for all pairs is prohibitively expensive. Also, you'd need to store the path information as well. Fortunately, road networks exhibit a lot of hierarchical structure. For example, when going far away, you will almost certainly use the long-distance sub-network, i.e. highways. It is possible to exploit this in a preprocessing step that adds a linear amount of information, which is in turn used to speed up queries.
bee_rider 2y ago
TDH seems like it would tend to coincidentally reproduce the tendency of animals (humans included) to create paths by having lots of people travel through somewhere. The cause and effect is flipped, but the player doesn’t have to know that, right?
- foota 2y ago
  TDH doesn't actually change the paths used, it only makes determining them more efficient. There's different names for this family of related techniques. There's an unfinished article (not mine) talking more about this here: https://www.redblobgames.com/pathfinding/heuristics/differential.html https://www.redblobgames.com/pathfinding/heuristics/differen...
telgareith 2y ago
FYI, TDH sounds like what Skyrim or one of the previous games uses. I can't remeber exactly, but $thing was supposed to be hard to find, but because of how they baked in pathing costs- if you followed something it'd lead you there.
- foota 2y ago
  I think this is what you're referring to: https://twitter.com/JoelBurgess/status/1428008041887281157 https://twitter.com/JoelBurgess/status/1428008041887281157 Some discussion here: https://news.ycombinator.com/item?id=28230305 https://news.ycombinator.com/item?id=28230305, but half of it is complaints about twitter.
  - deleted 2y ago
    [deleted]

by foota 2y ago

kevinwang 2y ago

> When you have some knowledge of the topology of the graph you can use different techniques to do better than djikstra's. But that statement doesn't apply to the version of Dijkstra's developed in this paper right? > Universal optimality is a powerful beyond-worst-case performance guarantee for graph algorithms that informally states that a single algorithm performs as well as possible for every single graph topology.

foota 2y ago
No, I don't believe so. It clarifies specifically what problem it is optimal for "We prove that our working-set property is sufficient to guarantee universal optimality, specifically, for the problem of ordering vertices by their distance from the source vertex", but A* only explores a subset of vertices based on the heuristic, so it can be more efficient.
mlyle 2y ago
> > When you have some knowledge of the topology of the graph you can use different techniques to do better than djikstra's. > But that statement doesn't apply to the version of Dijkstra's developed in this paper right? Simple thought experiment: I have an algorithm that has path costs for one graph memorized and first compares to that graph; it's O(V+E) to compare and return the value for that memorized graph. It obviously beats this algorithm for that graph.
- foota 2y ago
  Hm... technically they're saying that their algorithm performs as well as possible "for every single graph topology". Your special cased algorithm would only work for one particular graph in a family of isomorphic graphs (unless you have a linear time algorithm for the graph isomorphism problem, in which case please share), but would fail for the rest of the graphs in the family. So I think you could still say that their algorithm performs as well as possible for that topology.

Jadrago 2y ago

Does google maps use something like this? I imagine all pairs is too expensive, but the topology should be fairly consistent over time

urbandw311er 2y ago
Google maps uses something called contraction hierarchies
- DennisL123 2y ago
  Without knowing what they actually use, I feel comfortable to state that the industry has moved on from Contraction Hierarchies to somewhat more flexible techniques. These allow you to take traffic information and road closures, and user preferences, and whatnot into account without requiring a full re-processing of the input data with each traffic update. The state of the art is a two-step preprocessing that first decomposes the road network into cells, and then processes these cells independently. Sometimes it goes by the name of customisable route planning, sometimes it is called multi-level Dijkstra.
ahoka 2y ago
One trick we used when I was in the transportation business is to pre-calculate the distances between border crossings and gas stations.
DennisL123 2y ago
Storing the distances for all pairs is prohibitively expensive. Also, you'd need to store the path information as well. Fortunately, road networks exhibit a lot of hierarchical structure. For example, when going far away, you will almost certainly use the long-distance sub-network, i.e. highways. It is possible to exploit this in a preprocessing step that adds a linear amount of information, which is in turn used to speed up queries.

bee_rider 2y ago

TDH seems like it would tend to coincidentally reproduce the tendency of animals (humans included) to create paths by having lots of people travel through somewhere. The cause and effect is flipped, but the player doesn’t have to know that, right?

foota 2y ago
TDH doesn't actually change the paths used, it only makes determining them more efficient. There's different names for this family of related techniques. There's an unfinished article (not mine) talking more about this here: https://www.redblobgames.com/pathfinding/heuristics/differential.html https://www.redblobgames.com/pathfinding/heuristics/differen...

telgareith 2y ago

FYI, TDH sounds like what Skyrim or one of the previous games uses. I can't remeber exactly, but $thing was supposed to be hard to find, but because of how they baked in pathing costs- if you followed something it'd lead you there.

foota 2y ago
I think this is what you're referring to: https://twitter.com/JoelBurgess/status/1428008041887281157 https://twitter.com/JoelBurgess/status/1428008041887281157 Some discussion here: https://news.ycombinator.com/item?id=28230305 https://news.ycombinator.com/item?id=28230305, but half of it is complaints about twitter.
- deleted 2y ago
  [deleted]