Pathfinding Algo on Real Map: Paris

Join "Navigraphix" on a captivating journey 🌐:
- GIS & Blender Creativity: Merging data and design to explore efficient routes worldwide 🏙️.
- Stunning Visual Narratives: Transforming map data into visual stories through urban mazes and landscapes 🌟.
Navigraphix Content Highlights:
- Explore Efficient Routes: Dive into the art of finding the shortest paths across cities 🗺️.
- Data to Visuals: Transforming intricate GIS data into clear, engaging visuals 📉.
Stay Connected with Navigraphix:
- Subscribe for Updates: Join our visual data journey and never miss an update 🔔.
- Support by Sharing: Help us reach more viewers interested in data visualization by sharing our content 👥.
- Feedback Welcome: Share your thoughts and suggestions in the comments section below 💬.

[@eyeamKurisu]

what's the quickest path to leave France

[@wlockuz4467]

Don't be in France

[@no_name4796]

@wlockuz4467 that's a O(1) time complexity algorithm!

[@qwantum_7821]

The way you came in, by the sewers

[@Dank_Giraffe]

Probably through Belgium, oh wait no that's entering

[@naii2481]

To be in France already is a big blunder

[@thomasharris9059]

Pretty cool visualization of how lightning works as well

[@droftrop4135]

please explain? im not good at physics theories and neither do I understand any algorithms

[@user-hw1wb6lh6h]

​@@droftrop4135same here am gonna wait for explanation

[@loztsoul4905]

​@@droftrop4135 Imagine the sky as two huge metal plates. The clouds are like one plate, and they're filled with negative charge. The ground is like the other plate, but it's filled with positive charge. We call this 'polarization.' So, when things are polarized, they want to balance out. It's like when you mix hot water and cold water, they end up balancing the temperature between them. Negative charge always wants to meet positive charge, because they attract each other for having different sign. But the air in between isn't very good at letting them meet because it's not a good conductor. So, they start moving towards each other slowly, like people in a big crowd. But when they finally meet, it's not just anywhere - it's like they found the quickest way to get together. That's why lightning bolts take the shortest path. It's like they're taking a shortcut through the air because it's easier that way and it takes less effort. (sry bad english :( hope this helps)

[@veryrealpersonwhoisreal]

This video shows bidirectional breadth first search. If you watch the Slow Mo Guys video from 5 years ago you can see the lightning forming more like unidirectional A*.

[@further_rush5138]

Electricity likes to follow the path of least resistance So how would electricity know which path has the least resistance ? It tries every path and the path with the lowest resistance ends with having the maximum electric flow Finding the path of least resistance looks a lot like a path finding algorithm shown in this video Look up "slow mo lightning"

[@xWink]

Lightning looks a lot like this in slow motion, really cool

[@krolmuch]

not really

[@not-alot-of-options]

@@krolmuch Yes really. Look it up, there's plenty of videos.

[@leo8755]

well, it kinda does try to find the shortest path to the ground

[@veryrealpersonwhoisreal]

This video shows bidirectional breadth first search. If you watch the Slow Mo Guys video from 5 years ago you can see the lightning forming more like unidirectional A*.

[@thatwasntacatnip]

@@veryrealpersonwhoisreal There are other slow-mo videos which show the branching on a receiving side. Their size is not symmetrical though - the receiving side branches are always shorter.

[@PixelSubstream]

If Google Maps had Evangelion UX Design

[@hydrochicken9854]

I'd love to see a version of this using the A* algorithm!

[@bronson4574]

There's videos on it here on YT

[@ericb8494]

This looks like Dijkstra's pathfinding algorithm from the source and destination nodes. Google Maps uses the same approach, but with the A* algorithm instead. In my CS class, we implemented ALT which is even faster, but requires pre-processing. ALT is the same as A*, but uses precomputed heuristics between landmarks which is then used for a more accurate heuristic function, significantly reducing the amount of edges that are checked. ALT is basically A* with a better heuristic function than just a Euclidean distance heuristic function.

[@ixenroh]

Interesting, makes me wonder what the computational complexity is as a whole for ALT compared to A* and if it is generally cheaper, or if it's only worth to use in certain specific circumstances?

[@simonkovacic2585]

Reminds me of slow-mo videos of lightning

[@alystair]

80's anime vibes, wow!

[@adog3129]

80's anime vibes, wow!

[@winni2701]

You have a good taste of music

[@cxgamer9680]

Could use a heuristic it seems like.

[@josephdaly]

Earned my subscription, this is an awesome visualization

[@schizoposter1499]

It would be cool to see a comparison between different path finding algorithms.

[@Mayross_]

I am your 6th subscriber ! im from paris

[@ragmt09]

bonjour

[@AbdallahAhmed-qz6uu]

how many baguettes have you eaten today mon ami

[@bounty8655]

Ok but who's in Paris?

[@Mayross_]

@@bounty8655 🤫

[@cokemango]

Very nice work, how did you achieve this animation with Blender.

[@Navigraphix]

I use the Blender Python API to insert keyframes and achieve the desired effect. 😉

[@kaancan8888]

Awesome works, Can you do İstanbul version of this too ❤

[@sametucar9544]

cool looking

[@Arch-mv5te]

wow, thats really cool and looks awesome i really want to reacreate this

[@taofeng4443]

It looks really cool

[@miloelite]

So this is how Google Maps does its thing

[@Stangy-ln6dv]

would this work with terrain? (like finding the lowest path through the mountains?)

[@ShuRugal]

you could probably make it work, but you'd have to turn the terrain data into path data first. once you turn the terrain data into path data, you would then have to come up with a weighting system for the algorithm to use to evaluate a path with a greater elevation as less desirable.

[@FutureAIDev2015]

Is that breadth-first search?

[@isbestlizard]

Now do visualisation of ant colony optimisation :D

[@ayrtonpavot3096]

how is this diferent than the "itenerary" option in google maps ?

[@RasberryPhi]

is it the most optimal algorithm possible? which one do you use?

[@hghghghghghghghghgh]

Seems like a regular Dijkstra with 2 starting points to me, could be wrong

[@eeeeeek]

this looks pretty bad

[@nitori_kawashiro]

this appears to be some sort of a meet-in-the-middle breadth first search; one'd probably be better off with dijkstra or A*

[@andrasfogarasi5014]

@@nitori_kawashiro No, I'm certain this is Dijkstra. However A* would be leagues better. We have a good admissible heuristic for this. Namely, distance as the crow flies.

[@vixtordev]

Please make this a screensaver lol

[@xaiano794]

I would imagine the quickest pathfinding would be to always choose the route in the direction of the target until the 2 lines connect, then to calculate the maximum angle using straight lines (if points a and b are the source and destination, construct triangle ABC so that AC + CB = the distance of the initial route) and then explore routes in that triangle until another connects and if it is shorter, reduce the angle appropriately. That should reduce the seek time significantly

[@FabianReschke]

Pathfinding algorithms usually dont actually see the top down perspective or even the angles. It's just points and distances. Imagine a fishernet. You can twist and turn it, would be hard to draw a triangle. For us humans things like this are kind of trivial (same with sorting numbers) but for computers you really need an algorithm that might look overly complicated for humans, yet is actually really efficient, given the knowledge that the program has.

[@xaiano794]

@FabianReschke it depends on how complex the route is to how best to calculate. The system I described is similar to the one most mapping systems use because if you used this system and asked it to calculate a route across a continent it would be forced to calculate every road in the entire continent before reaching a solution

[@yudoball]

if you have points then you can calculate a direction vector, thus making an educated guess and ruling out paths that go in the opposite direction of your destination.

[@chrisvinciguerra4128]

@@yudoballthe video appears to show dijkstra’s algorithm, but you are talking about A* with a Euclidean distance heuristic

[@8Hshan]

It would fail in any case in which you'd have to go "backwards" to actually reach the destination.

[@jeanvichier123]

This looks like a graphic in Neon Genesis Evangelion

[@yikebendan]

EVA vibes

[@Verbosal]

Amazing visualization! One small issue though. The map isn't real

[@majormiller493]

Could you tell us where the points are located ? I can tell the northern one is near the subway station Jaurès but not that much idea for the southern one

[@joaoruiz2577]

from the looks of it, might be from one of the entrances to the parc de buttes chaumont to the paris expo à porte de versailles.

[@MPSpecial]

southwest point is in front of pavilion 7 of the Porte de Versailles exhibition centre. northeast point is at 31, rue Manin

[@majormiller493]

@@MPSpecial merci chef

[@majormiller493]

@@joaoruiz2577 thanks chef

[@bustlinValorant-nm3tc]

What was used for the production of this video?

[@YouTubeAccount-qk9fg]

slavery

[@bustlinValorant-nm3tc]

@@KZbinAccount-qk9fg very helpful and insightful.

[@pdcoronado]

Habrá algún tutorial ?

[@hikari1690]

No mentioned but this looks like a bidirectional breadth first search for those interested

[@angulinhiduje6093]

is it better then a-star?

[@hikari1690]

@@angulinhiduje6093 I think it's case by case. With a bad heuristic, A* behaves like BFS/djisktra(can never spell this right...) anyways so bi-directional BFS will be faster because the search happens from both ends and meets at the middle so the time should be O(b^(d/2)) vs O(b^d) where b is breath and d is depth. With a good heuristic, my instinct is A* will be faster because although it needs to cover twice the depth, it doesn't need to explore as many branches as BFS would. But this is just gut feeling, I don't have the maths to back it up.

[@hikari1690]

@@angulinhiduje6093 oh, but A* ensures the result you get is optimal while bi-directional bfs might not if the cost isn't uniform. Bidirectional BFS is also a pain to implement

[@olocuilta456]

1st sucriber from north korea

[@JkaBG]

wut??

[@afadeevz]

Is that you Kim?

[@olocuilta456]

@@afadeevz yes

[@OfficialDaveChannel]

Wild guess but maybe ur from el salvador idk

[@olocuilta456]

@@OfficialDaveChannel how you know that

[@overcookedsquid8400]

Ghost in the shell type algo

[@ficolas2]

no heuristic?

[@PhenixArcher]

would love to see a download for this

[@thomasb.8808]

Shortest path, but definitely not the quickest...

[@DrifterXx22]

is this breadth first search?

[@wlockuz4467]

Looks like two way breadth first search.

[@genesisreaper2113]

this makes me wonder. whats the optimal amount of starting points for the quickest search, and where would we place them?

[@ritzkid76]

i don’t think there’s any optimal way to place any additional search points past the start and end since no place you put the median searcher would be guaranteed to be connected. you could however use double ended A* to get a faster result than the one in the video :)

[@genesisreaper2113]

@@ritzkid76 well if you had a premade uniform point map, and then layered it over another actual map (maybe have the points auto snap to the nearest node), sometimes that would be more fast than just 2 nodes. Say, an x shape for example with 5 nodes, layered onto a normal map. I'd think that would be faster than going from specific point a to specific point b. It would obviously depend, if the distance was nextdoor it would be less efficient, but the longer the distance is the more effective it would be. At least in theory, idk.

[@awfulunicorn]

This is basically the idea of Transit node routing. For example: you precompute the routes between the highway exits of all major cities and then only find the paths between those exits and the actual start/destination. en.m.wikipedia.org/wiki/Transit_node_routing#:~:text=In%20applied%20mathematics%2C%20transit%20node,relevant%20to%20long%2Ddistance%20travel.

[@genesisreaper2113]

@@awfulunicorn ooh very cool, thank you

[@TestTest-tj4nt]

Very romantic.

[@kyr...]

Why did that felt kinda romantic?

[@ciaotiziocaius4899]

Looks like something from Evangelion

[@PVMChannel]

is it slowed down? if yes, show much?

[@user-zu6kt1gq2m]

Я 73 подписчик из сибири!!! Закончилась водка и я сегодня узнал что есть yoytube

[@alanbrierton5450]

Now add realtime traffic congestion.

[@ethribin4188]

This is also how lightning works by the way.

[@OfficialDaveChannel]

Well, lightning looks for the path of least resistance idk if it could rlly be compared to an algorithm

[@j-twd930]

Is there a music name?

[@mrshibli]

Good Video !! Remember me, I'm one of your first 5 subscribers.

[@neznh]

he will forget you

[@Xevion]

Kinda lame that there's no heuristic. Pretty, but I think it'd be cooler and more honest if there was weighting on the nearest unsearched points.

[@Bobany]

but same speed, the first one to connect must therefor be the shortest route. but maybe you mean this that weights on "non-obvious direction" to direct processing power in more likely directions?

[@SliceOfFish]

Do it with A*

[@MaryMary-sh5ge]

Noi umani non dobbiamo saperlo

[@SoonEnough]

8th from Syria lol

[@phuripatkongsakban8580]

What algorithms is used in this clip? Dijkstra?

[@realprodigious]

rip cpu

[@YayzayMc]

who's in paris?

[@lappelduvide2445]

wait so it's just an algorithm that finds the path? It hought it was unpaid interns at google....

[@Nicogs]

The reason your map looks stretched out is because you didn’t correctly convert longitude and latitude to x y pixel coordinates

[@simonkovacic2585]

I think it might just be a 3d view?

[@OfficialDaveChannel]

tilted perspective attempting to look 3D-ish

[@Nicogs]

@@OfficialDaveChannelIt is the exact mistake that creates this kind of transformation, seems a little bit more plausible than someone creating a visualisation in Blender, a 3D engine, to then render it sideways with a camera set to isometric, at the exact angle that the very common mistake of converting lat as long with the same unit would make…

[@deafharp8944]

15th subscriber from Palestine!

[@arsiarskila]

Imagine

[@deafharp8944]

@@arsiarskila ?

[@real31iger]

For this humans exists

[@theastuteangler]

shortest path is not the fastest path

[@mehmetoguzyardimci8598]

This only works if the distance from A to B is (or can be assumed) equal to the distance from B to A. Also, the animation is not correct.

[@user-hf6os1qb2w]

Weak not optimised for going in totally opposite direction

[@gregboi183]

Wtfdym bro France isn't "real"

[@alvinhoklk]

Nazis didn't have this and still took france in about two days L france

[@RussianStyleZV]

D DAY

[@alvinhoklk]

@@RussianStyleZV took you guys that + half of the russian population just to take on germans on horseback. horrible performance

[@sans_hw187]

6 weeks ≠ 2 days

[@alvinhoklk]

@@sans_hw187 hyperbole... Ever heard about it?

[@sans_hw187]

@@alvinhoklk 80,000 French people died during the invasion of their country, including 20,000 civilians. That’s more than the entirety of American casualties in the Vietnam war that lasted for 20 years, yet Americans see Vietnam as a “national tragedy”. In 6 weeks that’s an insane death rate so imagine if it had happened in 2 days. Respect… ever heard about of it?

[@Marc83Aus]

Hilariously inefficient when you look at it this way.

[@ryant3204]

eww bfs

[@nickst2797]

Really useful for Illegal Immigrants.