There is an interesting probabilistic angle of this classic AI story with Machine Learning applications here: https://github.com/imagry/aleph_star (paper, presentation, etc).
This and the hex grids get a lot of views on Amit's site, but he has a lot of neat things on there.
He just finished mapgen4:
"Paint your own mountains, oceans, and valleys. It will procedurally generate rivers and biomes based on wind, evaporation, and rainfall. Rendered in 3D to look like hand-painted 2D."
For a good application of A* I made a 15 (slide) puzzle that you can play in the browser. It basically exposes a websocket API and provides some skeleton code for you to solve. [1] There is also a tutorial for solving it if you need some help.
A* the traveler doesn't know about the obstacles or nodes on its path, it's discovering it as it goes. The preprocessing step of the contraction hierarchies sounds like it can be quite lengthy. A* can have not just dynamic weights, but dynamic nodes, e.g. car accidents, construction, etc.
Unless I'm missing something, seems like contraction hierarchies would be good for something like planning new roads with known existing obstacles. Less applicable for something like a MMORPG with randomized maps each game.
gugagore
This is not quite right.
A* and Contraction hierarchies (and other graph pre-processing techniques) make the same assumptions on what data is available at planning time.
The difference is whether you expect to make multiple shortest-path queries on the same graph, or not. If you will make several queries on the same graph (e.g. turn-by-turn navigation), then it makes sense to spend time to process the graph to make queries more efficient.
If you'll make a single query, because your graph is changing dynamically, then pre-processing doesn't help.
But A* still needs to have access to the whole graph at plan time. You might be thinking of D* and algorithms for that class of problems.
ziaddotcom
Ah, so in your example we're using the term "turn-by-turn navigation" in the textbook accurate version of the term (actually evaluates each turn as you go in case something has changed or the driver missed the turn, etc) to contrast it with a series of turn by turn directions given on a single query prior to the trip (like printing off directions before you leave).
So, to get even more specific with contraction hierarchies, google maps has a feature where you can avoid highways, and/or avoid tolls, and/or avoid ferries.
Therefor to answer the original question of this thread, is a* is superseded by contraction hierarchies, the short answer is yes if you have even the slightest amount of time to preprocess a graph (If i'm understanding gugagore and reference material correctly).
However, the answer is no in a more arcane/toy/hypothetical context. In an example of something like a randomly generated massive pac man vs ai ms pac man game where one of the two can can win if he/she reaches a single randomly generated exit first, contraction hierarchies don't really help/apply over a-star. The randomly generated map sort of implies we don't even want to give the computer time to preprocess the map, ultimately its human a-star-ish vs ai a* in real time, while trying to avoid ghosts. Otherwise we could simply give the preprocessed shortest path to ai ms pacman upfront, and tell the ghosts to avoid ai ms pac man. This would seem very similar to the player, but would be far less insightful for someone trying to learn and understand a* vs contraction hierarchies and pathfinding in general.
gugagore
To be clear, "turn-by-turn navigation" was an example of a query that happens on a fairly static graph: the road network. If the driver misses the turn, that just triggers another query on a static graph. I was not talking about needing to incorporate changes in connectivity, or in edge weights (due to e.g. road closures, or traffic updates).
Regarding "if you have even the slightest amount of time", no I don't think that's accurate. It's a trade-off between "offline" and "online" computation (sorry those words are so loaded, but they are often used in research on planning algorithms).
You could conceivably solve the All-Pairs Shortest Path for the road network offline, and then when you received a query online, you would be able to answer "immediately" by look-up table.
You could do nothing offline, and just run A* when you get a query. You won't be leveraging anything from the fact that the road network is fairly static.
Those are two endpoints of the trade-off spectrum, and approaches like contraction hierarchy lie in between.
Saying "contraction hierarchies supersedes A*" is kind of like saying "database indexing supersedes grep". If you're only going to grep a document once, it is not worth it to build an index. An index usually only helps if you will do multiple queries on the data.
pmalynin
Yes, I believe for path-finding on 2d / 3d maps, Jump Point Search+ is the king along with Goal Bounding. But A* is still very much useful, for example certain AI engines for games use it for action planning (GOAP).
Zeetah
I've tried to understand Jump Point Search+ multiple times but not succeeded. Is there a good tutorial?
gradstudent
No. CH depends on offline preprocessing while A* is entirely online. Even if you allow for only static environments, vanilla CH are not necessarily the best choice for games maps.
He just finished mapgen4: "Paint your own mountains, oceans, and valleys. It will procedurally generate rivers and biomes based on wind, evaporation, and rainfall. Rendered in 3D to look like hand-painted 2D."
Check it out if you're interested: https://www.redblobgames.com/maps/mapgen4/
1. https://pointatinfinity.com/fifteen
[1] https://www.hackerneue.com/item?id=8059237
Unless I'm missing something, seems like contraction hierarchies would be good for something like planning new roads with known existing obstacles. Less applicable for something like a MMORPG with randomized maps each game.
A* and Contraction hierarchies (and other graph pre-processing techniques) make the same assumptions on what data is available at planning time.
The difference is whether you expect to make multiple shortest-path queries on the same graph, or not. If you will make several queries on the same graph (e.g. turn-by-turn navigation), then it makes sense to spend time to process the graph to make queries more efficient.
If you'll make a single query, because your graph is changing dynamically, then pre-processing doesn't help.
But A* still needs to have access to the whole graph at plan time. You might be thinking of D* and algorithms for that class of problems.
So, to get even more specific with contraction hierarchies, google maps has a feature where you can avoid highways, and/or avoid tolls, and/or avoid ferries.
So in this scenario google has likely done "customization contraction hierarchies" as described here https://dl.acm.org/citation.cfm?doid=2886843
Therefor to answer the original question of this thread, is a* is superseded by contraction hierarchies, the short answer is yes if you have even the slightest amount of time to preprocess a graph (If i'm understanding gugagore and reference material correctly).
However, the answer is no in a more arcane/toy/hypothetical context. In an example of something like a randomly generated massive pac man vs ai ms pac man game where one of the two can can win if he/she reaches a single randomly generated exit first, contraction hierarchies don't really help/apply over a-star. The randomly generated map sort of implies we don't even want to give the computer time to preprocess the map, ultimately its human a-star-ish vs ai a* in real time, while trying to avoid ghosts. Otherwise we could simply give the preprocessed shortest path to ai ms pacman upfront, and tell the ghosts to avoid ai ms pac man. This would seem very similar to the player, but would be far less insightful for someone trying to learn and understand a* vs contraction hierarchies and pathfinding in general.
Regarding "if you have even the slightest amount of time", no I don't think that's accurate. It's a trade-off between "offline" and "online" computation (sorry those words are so loaded, but they are often used in research on planning algorithms).
You could conceivably solve the All-Pairs Shortest Path for the road network offline, and then when you received a query online, you would be able to answer "immediately" by look-up table.
You could do nothing offline, and just run A* when you get a query. You won't be leveraging anything from the fact that the road network is fairly static.
Those are two endpoints of the trade-off spectrum, and approaches like contraction hierarchy lie in between.
Saying "contraction hierarchies supersedes A*" is kind of like saying "database indexing supersedes grep". If you're only going to grep a document once, it is not worth it to build an index. An index usually only helps if you will do multiple queries on the data.