A* (A-Star) Pathfinding Algorithm Visualization on a Real Map
Vložit
- čas přidán 6. 10. 2023
- A* (A Star) pathfinding algorithm visualized on the city streets of Chicago and Rome.
Data from OpenStreetMap, OSMnx - intersections of streets represented as nodes and streets as edges
Tools used for visualization - Python, Blender
#pathfinding #astar #chicago #rome #python #blender #openstreetmap #map
I loved the added touch of the lighting strike, awesome visualization
That's the optimal path being highlighted
Bro 😂
@@bulkvanderhuge9006 i think they know
@@bulkvanderhuge9006definitely seems inspired by a lightning strike still. The flash before especially
@@bulkvanderhuge9006nooooooooo really?
It looks very similar to a super slow motion capture of a lightning strike
In general A* looks a lot like Lichtenberg figures¹.
¹ do not attempt to do this, they’re very dangerous with the slightest mistakes
im seeing slime mold
Lightning does indeed take the path of least resistance to the ground
Thank you, that was the imagery I was going for.
I was just thinking the soundtrack should be a low key electrical buzzing until CRACK - BOOM
For anyone interested, the Chicago route seems to be Lincoln Park to the Brookfield Zoo. You can map it out on your favorite map tool to see the difference between how this pathfinder algorithm will differ from the optimal route with traffic time. This results in a trip down Rt. 34 (Ogden Ave), but that route would take far longer than using either of the two expressways available (55 or 290). I wonder if the algorithm could be programmed to use speed limit metadata to get closer to real-time route optimization.
This algo (and similar ones) use heuristic to calculate "cost" of reaching each node. I think it could be adjusted to include speed limit which cold result in a better path travel time-wise.
Yes it could, you just multiple the length of each node by the speed limit before the algorithm stores their value
You definitely could do something similar that takes into account the speed limit, steepness grade, road quality, construction hazards, and any other factors you can think of. Welcome to the field of Geographic Information Science!
was exactly my thought for creator to dynamically simulate rushhour like traffic and see how the pathing changes.
Very nice visualization, but driving that route through and inside Rome can only be dared to be thought by a naïve computer mind who happens to know very little about driving in a kind of traffic where you whish you had grenades' stocked in your dashboard ...
It'd be dope to see a comparison between A* and other pathfinding algorithms, like a race, but with this visualization effect! Especially given that some algorithms are faster than others in very specific scenarios. Very cool!
+1 for the comparison, that would be epic
I agree! That would be super cool!
For A Level Computer Science students in the UK, they frequently have to compare A* to Dijkstra's algorithm - a comparison to this would be super useful!
I'm curious about node weights here.
Are they just using position, or are they weighted so that larger, faster roads have a much lower traversal cost?
I agree. There's a ton of comparison videos for sorting algorithms. I could imagine the same for path finding.
If you made this visualisation yourself then you need to be hired in all kinds of GUI and UX jobs immediately lol its so visually pleasing
this video is a work of art
Why is the reaction to something cool often "You need to be hired by a boss who will constrain you and enslave you and never make you design something this cool ever again." People do cool shit when they they are free from constraints.
@@broli123 yea most people dont realize how much good ideas and beautiful thoughts go to waste because they were deemed to not make money and not worth the time by idiot bosses and managers, nearly all companies have their capabilities bottlenecked by these managers and bosses who only exist to greed
@@broli123 I think the idea(l) was that "You need to be paid to make these so that you can keep making these with the safety net of being paid" but, as you say, not everything have to be for money.
Yup, you generally don't get paid for your best work, but for the bare minimum that satisfies the requirements, while taking the least amount of time possible, so you can quickly move on to the next thing and do it again, but faster pls! Time is money!
gist of the algorithm for anyone curious
1. keep a list of all nodes you can currently reach and haven't been visited yet, keep a cost associated with each. The cost is equal to the shortest known path to that node plus some heuristic value (e.g. the euclidean distance between that node and the destination node).
2. Keep a list of all nodes visited, with each node in this list store the path length and the previous node visited so the path can be reconstructed
3. Visit the node with the lowest cost, update the list of reachable nodes accordingly
4. repeat 3 until you have reached the goal. If the heuristic has the right properties (consistency) it is guaranteed to be the shortest path from the start to the end
Except that time is a factor in mapping, you should pull from the value denoting speed of the road. Shortest distance while useful, in reality shortest distance in Time is the preferred solution. The shortest distance on the Rome map would be to take the ring road and exit.
@@mdyas1711Make the road weights the speed of the road, problem solved
@@marcosalazar4682Real mapping applications probably use the time it takes to traverse the road as weight, which already takes speed and distance into account.
@@mdyas1711 The dataset itself doesn't seem to have the weights for road speed, so this is the closest they can get.
Also traffic lights, left turns without traffic lights can be slower slower than right tuns, and probably a bunch of other considerations.
On one hand I love this because it's one of the coolest things I've seen. The colors and bloom effects are gorgeous!
On the other hand I now have to try (and likely fail) at re-creating this and I really had things I wanted to do today :)
Excellent work!
Saw this on Reddit yesterday. What a fantastic visual. Id love to see this done on cities with maybe more geographic limitations to their road layout. Something like the SF bay area, and and how the bay/bridges change the road layouts and flow of traffic.
I like the lightning bolt effect when it finds the path. Impressive work!
I would love to see a loading screen in a game that looks like this, where the start position is the location where you are leaving, and then destination the algorithm is trying to reach is the location you're traveling to. The lightning strike visual happens when the loading finishes.
It'd probably have to be a pre-rendered animation, so it's not wasting processing time on the visuals that could be spared for loading the game quicker. And if the loading finishes before the animation does, it could play in like x5 speed until the lightning strike graphic occurs.
The other stunt would be adjusting the loading percentage bar based on prior loads. For example the game Satisfactory might load environment, natural features, natural resources, player-made features, player-made resources, player inventory, and player appearance.
When the game first loads the natural features and resources would take the longest to load as there is so much present and the player-made items are a single drop pod, a few Miners, a power plant, and an Assembler. So 70% of the load time would be the natural features and ~20% would be player-made items.
As time goes by, the player is clear-cutting the local forest and building a giant factory. If the game does not adjust then the loading bar would advance quickly to the 70% mark and the final 20% mark would take far longer.
But if the game adjusts the loading bar as the game goes on, then the natural items would be reduced to maybe 15% of the loading bar while the player's items would be ~80% of the loading bar.
This is probably the coolest video I've seen all year! Wow. Thank you!
I could watch these for way longer than I should :)
Nicely done!
Awesome way of visualizing the search space of A* pathfinding! Love to see it instantly collapse to the best solution once it touches the destination. What could make this even cooler is the use of HDR imaging for the "lightning strike". You can see the bright colors being clipped to white when it fades as the substrate cools down.
That's beautiful! I want a 1 hour version of these videos
I am glad that CZcams recommend this. Awesome visualisation 🔥
That is soooo awesome, thanks ! Hope ur channel blows up now :)
Very cool. Satisfying to watch. just like the sorting algorithm videos. I bet if you added noise to this and made a few you'd hit the algorythm pretty quickly.
It’s like lightning! Love the visualization
I need like an hour of these, different maps :D they're immensely satisfying to watch!
Really cool animation! It makes you understand how navigation works! Thank you so much for sharing!
Amazing video, I loved the animation. It's so beautiful, I would love a video explaining how you did it
Do you think you could do a behind-the-scenes look at how you made the visualisation proper (not the algorithm itself) in Blender? I've been looking at using Blender for Python datavis and this is an excellent case study!
I really want to know this too!
fantastic visuals, would love to see this expanded out on tons of other cities too!
PLEASE MAKE MORE OF THESE VIDEOS! They make me happy!
Map direction algorithms have been a reoccurring shower thought for me but never looked it up for some reason. I've always assumed the best way would be to do run _two_ cost functions in parallel, taking the next turn based on distance to the opposing end since the last turn. Interesting to see that an established algorithm does it from one node!
Because A* has the heuristic, bidirectional isn't as important. It's still doable, though, just not the 4x faster you get from bidirectional for things without a heuristic.
The usual improvement to A* is to make it hierarchical -- there's usually no point in looking at little alleyways in the middle when you have a long way to go.
it seems to use only distance as a metrics, otherwise, if also road speed limits were taken into account, i think choosing the rome ring road would have been the best choice. Btw wonderful visualization! Love the effects
Looks great! Please post more beautiful data visualizations! ❤
I love the visualization! This is so satisfying
no audio, 1 minute long and still it's one of the best videos, I've always wanted to see exactly this 😂 thank you
This is really cool, I would totally pay for the blender file if available.
I really like the styling - great work
Congrats on the hit viral video. You deserve it. This is beautiful :)
I would LOVE to see a tutorial. It is beautiful. If you could do that, it would be amazing. Thanks
Super cool visualization, I'd love to see more of this! Can you generate this from Python directly inside Blender, or do you have to export it? I love procedural generation for games, but I haven't looked at all into non-realtime animation like this. I've been meaning to take a look at modern Blender tools like geometry nodes.
This is really nice, great work!
I could (and would) watch a lot of these.
That is absolutely awesome. Do you plan on making one with Dijkstra's Algorithm for comparison? This would be an awesome way to showcase the differences..
One of the issues I had in university was wrapping my head around the reason A-Star is faster than Dijkstra although they are so similar. Didn't quite grasp the concept of a Heuristic :D
The heuristic just says to check the paths that are closer to the objective first since they're more likely to be on the right path. That's why you see it reaching towards the goal instead of fanning out in each direction equally like Djkstra would.
It looks so good. Would you also try some other algorithms? And then compare them? Like, Djikstra, BFS etc.
Thank You! Maybe at some point yes. I have seen few videos like that and they do look interesting.
bruh you really making amazing things!!
Amazing visuals/tech!! Really is cool!!
This is a great visualisation. Thank you! I hope Google Maps don't use this algorithm. At least not in this setting. It seem to rely on a reduced data set to better visualize the way it works for us. Which is great but might be slower than working with average and current speed predictions for each connection in the graph.
Don't worry, Google maps is a decade plus worth of incredible computer science path finding algorithms optimised to incredible levels.
The A* algorithm is just one of the classical path finding algorithms in computer science along with dijkstra's algorithm. What's used in Google maps is based on the path finding algorithms but with years worth of crazy work done on it
All that doesn't change anything about the algorithm. All it needs is the "distance" between any two connected nodes. What goes into calculating that "distance" doesn't matter---all of that is just input data modelling.
@@HenryLoenwind that is assuming they are using A* and not something of their own
A* is great for finding path when we don't know much about map layout. Pathfinding algorithms in general assume a lot of closed paths, so breadth-first approach should give better results on average. However streets are build like an open grid so depth-first approach towards target position will be much faster with mostly great results, especially if map will contain additional information, like speed limit or traffic allowing to create a weighted graph. In the same way we can remove all dead-end streets from possible routes.
Anyway tracing a route on a real map can be optimized in various ways. For cloud based services it's a good idea to cache results and work on a multiple scales, for example if you're traveling between cities or even countries, first find a route between cities, then find your destination.
I think this map is weighed on traffic to some degree, you can see the algorithm makes much more progress on highways then on back roads
Yeah, the algorithm is pretty easy to do. But finding the best heuristics is the challenge. Based on Dijkstra's Algorithm
Do you still play diablo 2?
Simply not true @Leeki85. A* is optimally efficient, meaning that it guarantees to search fewer nodes to find the optimal path than any other search algorithm (so long as the heuristic for the cost-to-go is admissible).
The most efficient way is actually to use a more advanced geometry. Instead of a weighted graph, you can encode pre calculated connections of hubs into the map with very little memory cost (only a few bit per node). You end up with quasi linear lookup times for optimal routes. It gers more difficult if weights change dynamically, eg due to road and weather conditions. Also, to stick with A*, I think you start expanding from both ends, and the graphs meet somewhere in the middle.
I read a book about A* algorithm yesterday, and this is really awesome. Visualized one is so great!
Awesome visualization. Great job!
Beautiful, can you share the code to see it on my country maps?
All roads lead to Rome
Keep on the good work. I would love to see other pathfinding algorithms and comparisons on a real map
This is super interesting! And so satisfying to watch!!
Would be cool to do a bi-directional one, and easy to implement too, and way faster! just do the search from both start-goal and goal-start, then check if they touch
A good heuristic, like exists for euclidean distance, makes bidirectional less helpful. It'd be 4x faster for Dijkstra, but A* doesn't benefit so much from it.
It looks like brain activity
Now this is one of my new favourite videos.
the lighting strike was perfect; I even was expecting to see it on the first run around thats how perfectly it fits.
I wanna see more of this.
Legit looks like lightning and that is cool!
YES. More of these videos please!
I recall learning about A* using Python when I first learned about making platform games. Very cool algorithm!
This is so pretty, great job :)
that is not only informative in some way, but also absolutely gorgeous
This is so mesmerizing! I need more! 🥺
I’m your 699th subscriber!
Your videos are amazing and underrated!
This lightning effect in the end makes it so cool 😁
Would love an hour of these, with a mix of algorithms too. It would be great to fall asleep to
Really great, nice visuals!
I want to see more of these visualizations, these are so cool.
This is beautiful. Don't stop with A* please!
This is the most beautiful example ive ever seen on A* algorithms.
The visualization is beautiful!
I would love to see more of this!
Fascinating stuff bro
Nicely done.
This would make a great screensaver
This visualisation is so cool! 🤩
I would love to see how different algorithms (like A*, Dijkstra's and DFS) work on the same map!
Isn't A* just Dijkstra with a bit of stuff added into it? Or am I confusing that with a different algorithm?
@@jan-lukas That's an interesting point! Both Breadth-First Search, Dijkstra's and A* are in the same family of algorithms. They explore the space by expanding nodes at the frontier. What changes is how they pick the nodes from the frontier. Dijstraks' uses the "cost so far" to prioritise nodes, while A* also relies on a heuristic to estimate the final distance to the target. Running A* is like pouring water on an inclined plane towards the goal.
@@jan-lukas Almost, A* is actually Uniform-cost search with a heuristic added to the priority (Not the cost). A* with a heuristic of 0 boils down to UCS
This looks amazing!
:') Kinda smitten that you chose Chicago and it was the first city shown~
With love, from Chicago!
Absolutely insane how much this looks like the colonization phase of mycelium.
Love that you visualise it as lightning :)
This is a really cool visualization.
Very cool. Reminds me of a video I saw a few years back about slime mold propagating
This is utterly gorgeous.
funny fact lightning does the same thing with electrons.
It didn't needed to be this epic, yet it is, thank you
love the visualization of this.
Beautiful illustration
Looks like a great exercise for sound designers creating sound effects for futuristic interfaces
Very cool visualization, and for an update I'd love to see this with a meet-in-the-middle / bidirectional modification of A*.
Awesome visualization!
Now I want to see Tokyo one.
Would love to see a tutorial for how to do this! Absolutely blown away by the visualization. New to python and blender , so please do post a tutorial or perhaps write about one!
Wow, it looks amazing. You should teach this
What a nice way to visualise the A* algorithm~
Beautiful visualization
Looks just crazy🔥🔥
This would be the sickest loading screen in any game ever made.
This looks so cool I want to see more.
Beautiful!
Brilliant, thank you
Very nicely done.
This is mesmerizing.
This made me remember driving from six corners Irving Park Rd. to Navy Pier every single day for 4 and a half years. I was one of the contractors that brought high speed internet to the Lake Shore area of 'Windy City'.
This was back when '21st Century' cable company was bringing in fiber optic.
My company would tap that line and redesign and build a new system to retrofit existing buildings.
And now I'm perturbed by my involvement in the creation of the mass of internet zombies.
its so satisfying, i need more
Excellent visualization
Im sad this was so short, I liked this
Wow this is amazing