The Lightning Algorithm - Numberphile

Matt Henderson is making lightning in mazes.
Check out www.kiwico.com... and get 50% off your first month of any subscription.
More links & stuff in full description below ↓↓↓
More videos with Matt: bit.ly/MattHen...
Follow his work on Twitter at: / matthen2
Maze solving on our sister channel, Computerphile: • Maze Solving - Compute...
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumb...
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoun...
And support from Math For America - www.mathforame...
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberph...
Videos by Brady Haran
Patreon: / numberphile
Numberphile T-Shirts and Merch: teespring.com/...
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanb...
Sign up for (occasional) emails: eepurl.com/YdjL9

[@numberphile]

Check out www.kiwico.com/Numberphile and get 50% off your first month of any subscription. Previous video with Matt (Chaotic Balls): kzbin.info/www/bejne/bKuXooWepad8r6M

[@scurvydog20]

You could make this simulate lightning more accurately by giving the grid squares different weights to represent conductivity.

[@jitgtij]

If you know both gates and approach from both sides, that will have even faster convergence.

[@Typical.Anomaly]

Have you guys ever heard of a game called "Plinko" on the US game show "The Price Is Right"? If so then you should know why I mentioned it lolol (Always remember to have your pets spayed or neutered!) 😁

[@picobyte]

Real lightning an actually branch out both at ground level and the clouds as main channel sets up, cascades of charge want to flow there, it's like kicking a huge bucket of charged capacitors resistors and coils.

[@alanthesuperhero]

Why did you put an amogus in the thumbnail???

[@Pulsar77]

Back in the day when we needed screen savers, this would've been really nice.

[@bretscofield]

My thought was this would be a great like Windows 95 or Windows 98 screensaver.

[@Pulsar77]

@@bretscofield Yep, brings back memories.

[@exod4]

Screen savers are gonna make a come back with oled monitors

[@xxgn]

As-is I don't think this would be a suitable screen-saver. This would risk burning in the walls since they're both high intensity and positioned inconsistently. Also, the middle of the monitor is exercised more than the left and right edges. Mind you, it wouldn't be hard to tweak this to remove those issues.

[@feandil666]

the CPU would have been at 20% all the time trying to do the calculation in a reasonable time :)

[@wouterlahousse9637]

Just watching numberphile not to miss out on the cat and dog cameos

[@vigilantcosmicpenguin8721]

The channel is made to feature mathematicians, but we know who the real special guests are.

[@hawsroy]

this looks like it should be in a science museum somewhere in high detail on a huge wall, accompanied by huge flashes. i’d pay to see that

[@gamen8209]

Make it!! And put it in a modern art Museum instead 🤩

[@mayabartolabac]

@@gamen8209 as much as i want to, those snobs will never appreciate art that actually took effort

[@t.c.bramblett617]

I'd like it to be a screensaver!

[@kingk2405]

Or in my shower .

[@SlampthChompth]

Dude that's genius. Have a continuous cycle of randomly generated mazes, and just have them keep going like that, and make it look even more like lightning. Just like a digital portrait on the wall that keeps going, producing lightning. And the occasional null ones would just amount to a few seconds of no lightning. Which would also emulate the incontinence of real world lightning strikes. Should also randomize the time between rolls. Dude build this I'll buy one.

[@onion013]

"This was done in Mathematica" - I was half-expecting the code to be something like PlotLightning2D[100, 100] given how extensive Mathematica's libraries are :)

[@PhilBoswell]

Give it a bit and it might well be ;-) Is there an open-source equivalent to Mathematica? I feel like there should be, and this should be part of it.

[@cybisz2883]

@@PhilBoswell GNU Octave is the closest thing I know of.

[@timseguine2]

@@PhilBoswell Sage is kind of like Mathematica. GNU Octave that was suggested is more like MATLAB.

[@gcewing]

There's probably a command for it in Emacs.

[@timseguine2]

@@combatcorgiofficial For what the guy in this video uses it for, I agree. But it is actually pretty great as a computer algebra system.

[@Arctic_Narwhal]

Animations of search algorithms are always so fun to watch

[@pvic6959]

I agree!!

[@GRAYgauss]

thats why i like doing acid

[@trinidad17]

Yeah and the hard part here is actually making the animation.

[@poppop-oj6by]

I like animations of sorting algorithms even more

[@florianlipp5452]

the effect of different values for p and q would have been interesting. Higher q values in particular might lead to more twisted paths, detours (going back up for some time) etc.

[@alpardal]

He did mention he uses different values for p and q to make it so vertical paths are more likely than horizontal ones

[@MrDoctorDen]

Should p+q = 1 tho?

[@faelyn5770]

@@MrDoctorDen No not at all, p and q are probability for two different things that are not really connected. p+q only needs to be one if p and q are probabilities for opposite events.

[@MrRyanroberson1]

Though you don't want the probability too high in total, so maybe p+q=1 is a nice constraint in the first place

[@gcewing]

An interesting challenge would be to find the probablity of the maze being unsolvable for a given p and q.

[@ciscoortega9789]

This looks amazing! Such simple ideas but the combination of them together is absolutely brilliant!

[@chris9012]

I'd love to see a version with hexagon-tiling.

[@R_V_]

Or 3D space tiling.

[@BooyahL]

He showed the code (maybe on his Twitter he even shared it!) so you can try it yourself :)

[@LittleKitBirkl]

You could try looking for A* pathfinding in hexagonal space. You might have some luck there. In essence (or rather in code) a hex grid is a square grid where every second row is offset by 1/2 (I think) and you have to then treat 6 cells as neighbours instead of just 2.

[@damien4197]

Well, they are the bestagons, after all.

[@FINALLYQQQQAVAILABLE]

@@LittleKitBirkl The same A* search algorithm works on any graph. Rectangular, hexagonal, 3D, whatever. A skilled programmer would write the search algorithm once and then just apply it for different kind of graphs.

[@sunongral5605]

I can't hardly explain how satisfying I find the animation! With that little sound! I'm a simple person, I see lighting and I'm hooked for as long as physically possible.

[@greatquux]

Perhaps a “tie” in the real world leads to forked lightning

[@OriginalPiMan]

Kinda. Because of how electrical resistance works, the energy will mostly travel on the shortest path (or rather, the path of least resistance), including splitting equally between equal paths, but energy will also follow less efficient paths albeit a lower magnitude of energy. In the end, the energy will follow every path to some degree, as long as the resistance is not too great such that the travel is impossible. (Or at least, that's what I remember from science classes and electronics classes years ago).

[@RFC-3514]

Doesn't have to be a tie; lightning isn't binary like in these animations (i.e., it doesn't follow a single path), some of it discharges into the air itself, and a lot of "side paths" never actually light up (there is always a lot of forking, most of it is just hard to see).

[@OriginalPiMan]

@@RFC-3514 Yeah, and even when two forks visibly hit something, there will usually be one brighter one and one dimmer one.

[@CallousCoder]

That’s true, electricity takes the path of least resistance. So when two paths are equal, the same amount of current goes left and right. If a path is more resistant, less current can- and will move through that path. When there’s no way to ground, there will be no current going that way.

[@EebstertheGreat]

Also, just in general, the physics of lightning are not very similar to the mathematics of maze solving by breadth-first search. This algorithm is really a demonstration of a breadth-first search, not of lightning, but it looks a bit like lightning so that makes for a catchy name. Lightning strikes are much more complicated and involve the formation of "leaders" connecting adjacent regions of different charge. For instance, a more negatively charged part of the cloud adjacent to a more positively charged part can form a leader between them, equalizing the charge. If the charge is still not equalized, these leaders can continue to spread, and to branch, repeatedly equalizing charges of adjacent areas. If the leader escapes the cloud and there is still a large charge separation, it can travel between the cloud and the ground. Usually, the leader comes down from the cloud and up from the ground at the same time. In some conditions, it can also form between the two in the lower troposphere. Once a connection is made between the ground and the cloud, air is so ionized that an extremely low-resistance channel is created, and a huge current is produced, which heats the air into a glowing plasma that looks like lightning. So it's a lot more chaotic than a breadth-first search, and it isn't just going from one end to the other. Lightning that strikes the ground is not branched (though branched lightning can get relatively close to the ground, so this isn't always obvious visibly). Typically, once the downward and upward streamers attach, a single connection is made and that's where you see the bolt. There are usually several flashes in close proximity (a couple tenths of a second), as the same ionized channel is used again and again to discharge different parts of the cloud. Until the ionized channel disperses, it will always be by far the lowest resistance path to the ground, and the current will follow it almost exclusively.

[@Veptis]

Learned about this guy through twitter. After I followed I searched for any features on Numberphile. And there were some in my watch later. Glad I am here now. Making beautiful maths visualizations is really something outstanding and that is the only piece that is missing from some of the lectures I have. Therefore for anything I present or teach - having a beautiful visualisation is something I strife for.

[@PW_Thorn]

To improve this algorithm (generating random map), instead of generating randomly a new map in case it is not solvable, you can just add holes, level by level, randomly. It will then end solvable in a deterministic way instead of crossing finger to avoid that bad luck appears continuously. And we can notice that a randomly generated map with random holes added is still a random map !

[@TheOcram2000]

I'm a chemist and this is fairly accurate actually. The electrical charge has to pick the oxygen molecules with the proper alignment of their double bonds (pi orbital) to create ozone and still reach the ground ASAP

[@ebrelus7687]

Quite educative comment for a komunist! Well done! Like communisation of the most individuals by fear while murdering as many on road as possible in shortest time!

[@ImaginaryMdA]

@@ebrelus7687 Have fun with your capitalist "healthcare". ;)

[@RFC-3514]

It's not _accurate_ at all. Real lightning forms a lot of forked paths, and starts discharging through all of them, at varying rates. The drop in resistance eventually causes one path (sometimes with some visible forking) to heat up, become dominant, and form plasma, but these animations aren't even trying to simulate that. Also, there are no hard barriers forming a predefined path in the air; the formation of the lightning strike itself rearranges the "maze" dynamically. It's a nice-looking approximation that gets across the point of "path of least resistance", but it doesn't even attempt to simulate the real-world mechanisms involved in lightning strikes, let alone do it accurately.

[@idkman-rr3bm]

Spoken like a true chemist..ry student.

[@Frosty-oj6hw]

It is actually surprisingly accurate in a few ways. Lightning doesn't just strike immediately, it has Leaders which kind of explore the environment much the same way as the code checking for the fastest route, many of them fork through the air finding a path from one pocket of charged ions to another (normally cloud to ground). The leader which connects a path first is where the full discharge actually travels. With one minor difference, when leaders get near pockets of opposite charges on the ground it causes leaders of opposite charge to actually leave the ground and travel up, where they eventually connect forming the whole path, and the full discharge happens along that path.

[@penny3577]

I can only assume CGP is somewhere screaming: "make them hexagons, not squares!"

[@spv420]

CGP*

[@HoSza1]

what is a cgp?

[@leadnitrate2194]

@@HoSza1youtuber cgp grey, he's a big fan of hexagons

[@spv420]

@@HoSza1 cgp grey

[@penny3577]

@@spv420 yep...thank you, didn't realise I spelt it wrong lol

[@mceajc]

Brady, I didn't even know how much I was missing hearing you speak to experts in their field until this moment. Thank you!

[@krakenwarrior3237]

They could have called this the "Following the Droplet Down the Car Window as a Child" Algorithm, but I guess it doesn't have the same ring to it.

[@realitant]

The droplet doesn't go up though

[@david203]

@@realitant It can if the car or the surrounding air is moving! Usually, all of the droplets move in a common path modified by an interesting randomness.

[@Just_a_user3]

Thank you for reminding me of this. I had forgotten how much I enjoyed watching the droplets slide down.

[@esquilax5563]

The droplet would use a greedy algorithm

[@david203]

@@esquilax5563 Are you referring to how moving droplets combine with stationary droplets to increase in size? Yes, that is interesting.

[@elraviv]

there is an algorithm to generate solvable mazes. you add random length lines one by one vertically and horizontally, but they can connect to other lines only at one point. so basically there are no blocking lines but the way around them can be long.

[@lonestarr1490]

Yes. But in such a maze a breadth-first search wouldn't look that interesting, I suppose.

[@reedplaysgames]

I could watch a bunch of these mazes for hours and not get bored

[@yobgodababua1862]

I'm surprised there was no mention of how A* (The king of pathfinding) basically combines naiive breadth-first with an arbitrary "fitness metric" (just like you used here to color the wavefront) to guide the selection of which border nodes to search next.

[@leeboehmer6793]

Eh?

[@MrRedwires]

I was really about to ask in what way this algorithm here is in any way special or interesting. It feels like the only thing they really added was a colouration of the search-front, but the algorithm itself is... Really the most basic thing they could've done, and to me it just felt like a more basic A*

[@MattMcConaha]

@@MrRedwires it wasn't A* at all, it was just a basic breadth first search. A* uses a heuristic measure to only continue searching down paths which have a chance at being the best. In this implementation, the code always follows every path (all paths are always at the same depth, and every instance of that depth is accounted for) and then just stops when one of them finishes. In A*, the heuristic measure would probably just be the height value, and a path would only be continued if its current depth plus height were less than the any other depth plus height combination. Or some similar calculation. Off the top of my head I'm not sure if A* is defined in such a way that the heuristic must result in the optimal solution or not, but the heuristic I described would guarantee it. The full breadth first search also guarantees optimality, though with less efficiency.

[@killerbee.13]

@@MattMcConaha A* works (it finds the shortest path) even with a bad heuristic, but it performs worse. In this example, that would mean it explores more of the maze before finding the end. From what I can tell it actually loses its performance guarantees entirely depending on just how bad the heuristic is, though I assume that such bad heuristics are pretty unlikely because one had to be deliberately constructed by computer scientists for their proof, because it had never come up in practice.

[@framegrace1]

​@@MattMcConaha A* guesses and backtracks if can't continue. This follows every path and stops when can't continue... Appart of that, I would say the heart of the algorithm is basically the same. A* doesn't guarantee optimal path, (doing it in linear time like A* would be a Nobel at least...:) )

[@31337flamer]

this is what i do everyday xD making sims that have no purpose but look satisfying :D trying out algorithms

[@bootje99]

thought you were talking about the Sims (the game) 😂

[@macronencer]

Can relate to this. I'd do that too if I had the time! I have a busy life, but sometimes I do get to play with code... I spent months on and off working on an algorithm to generate near-optimally-compact patterns that encode words (so basically steganography). In the end, I cracked it using simulated annealing, and it was so satisfying! I made a pattern for my own name and got Vistaprint to put it on a mug. Every time I use that mug I remember the feeling of solving the problem, and it's pretty nice.

[@asailijhijr]

@@bootje99 that is approximately the source of the name of (the (species of) characters in) that game. They were originally the inhabitants of the cities in a different game by the same publisher: Sim City.

[@Games_and_Music]

Powder, named after that 90s movie about that guy that got hit by lightning?

[@david203]

I used to get software jobs by entering a three-instruction program to simulate a waterfall by displaying a parabola with errors due to overflow.

[@Krebzonide]

I made a lightning simulation algorithm for a programming class in college. Basically it generated around 1000 "electrons" randomly placed, then connects a line between the top of the screen and the closest electron. It then continuously connects a line between whichever line is closest to an electron that hasn't been connected. Each time it draws a new line it increases the thickness of all the lines connecting to the top. When it hits the bottom that line's thickness is increased by more.

[@MorreskiBear]

I wonder... did that ever result in a loop-the-loop or other non-lightningish effect?

[@Krebzonide]

@@MorreskiBear I don't think I ever saw something like that. The main problem I saw was since it hit EVERY electron it occasionally forced itself to go up. I did add a small offset in the math to encourage it to go down which made it look better.

[@python-programming]

I love lightning and I love numbers, so this is basically my new jam.

[@ebrelus7687]

really jazzy

[@Games_and_Music]

Lightning by the numbers

[@strangeWaters]

I wonder if the lightning strikes end up normally distributed along the bottom

[@drakoz254]

This is a really interesting question. Seems like modelling the maze as a random graph is your best bet to approach a solution.

[@vezepheros3895]

My intuition tells me the points in the middle would be more likely to be the solution than the side points

[@krzysztofq7420]

I guess so

[@drakoz254]

The algorithm preferentially chooses the shortest path, right? So if we suppose that each "bottom" node is acessible with probability a, and in every round, the algorithm chooses the acessible node with the shortest distance to the top (and therefore, the node closest to the center on average), does that process lead to a normal distribution? Sure feels like it does, but we have abstracted away the maze in the middle here so maybe that plays a bigger role.

[@pyglik2296]

It may be binomial, just like in galton board, where at each level you're equally likely to turn left or right.

[@Stereotype3]

I absolutely love these videos with Matt Henderson! He's got such a nice way of speaking, I'm completely zen after watching

[@notmyname327]

I love Matt's maths visualisations

[@numberphile]

So do we

[@vanderkarl3927]

I click on the video, instantly there is a cat. I am satisfied with the content of the video.

[@seldom_bucket]

Glad it wasn't just me.

[@teleny2]

@@seldom_bucket It's the view of the cat as well. Showing his nether star, as it were.

[@JMUDoc]

Fantastic video - within the first ten seconds I understood the concept completely.

[@leumas75]

10:33 Thank you for the added thunderbolt sound effect on that last solution. I can’t believe @Matthen2 didn’t include this is the code, because it it ABSOLUTELY necessary.

[@najakwarkle]

I love Matt's enthusiasm!

[@nothingnewhere6551]

I like the examples this guy presents. Always something cool going on with you guys!

[@aikumaDK]

I love videos like this, because while I enjoy making the odd program here and there, I got bugger all idea what's going on in Matt's code.

[@Fiifufu]

Such an interesting character this one. Hope to see more of his stuff✌🏻

[@MarioRossi-sh4uk]

Math and science are just fantastic. Without them I could not survive.

[@muffinman2546]

I wonder how a hexagonal maze would turn out. Given the complexity of having more walls on more sides and given that it will never go straight horizontal and have lots of diagonals.

[@lonestarr1490]

I guess the lightnings would turn out like parts of a Sierpinski arrowhead.

[@TomasSab3D]

Thanks!

[@pcfilho425]

Numberphile and lightning, what a perfect combination. :)

[@JavierSalcedoC]

I thought this was about the lightning network for a second. Great video as usual

[@uncountablehey3346]

Not sure which is more beautiful, the mathematics or the cat.

[@kalidsaed8754]

This is really a deep meaning in life. Every person has a maze and then one needs a Lighting path to success and happy life. I like this work.

[@fundayswithfox6706]

Seems like the sidewinder algorithm would be helpful for maze generation, there is always at least 1 path that goes downwards so you never get stuck.

[@adamgray9212]

This is so cool! If you could get it to return all the shortest paths (in cases where there's a tie) that could create some nice forked lightning animations too...

[@diaz6874]

*Dude explains the beauty of the visuals created by the algorithm * Brady: *C A T*

[@RafalRzepecki]

Pretty cool! Lightning strikes actually grow similarly, but from both directions, bottom-up and top-down, and they strike when the traces meet.

[@jacklardner8229]

Matt, the Twitter legend. I remember seeing this one on Twitter

[@gerardmoran]

I've said this before - but Brady ALWAYS asks the questions that I'm wanting to ask. Brilliant host.

[@aukeholic1]

If this was interactive I would request the lightning to start again but in reverse; from its arrival point up and see wether it takes roughly the same route. And maybe iterate to find the optimal path. Really interesting!

[@tommy_svk]

You mean find the shortest path from bottom to the top? Shouldn't that find the exact same path though?

[@GRAYgauss]

@@tommy_svk yeah it's literally part of the definition of the algo.

[@andymcl92]

@@GRAYgauss Well it's slightly different. The starting point at the top is fixed as the middle square, but it wouldn't necessarily end there going bottom to top. Say, for example, one maze started top middle and ended bottom left. Then suppose the entire leftmost column was free of walls. The shortest path back up would be straight up the left column, ending top left. The reason for this difference is because the start point is fixed, but not the end point. Now what I'm wondering about is if you repeated this again and again, where each end point becomes the start of the return, would you ever get back to where you started? I suspect the answer is no, and you'd eventually settle on one route that is (locally) the fastest both forwards and backwards.

[@GRAYgauss]

@@andymcl92 Are you saying restart the whole algo in reverse? This isn't measuring shortest path, it's measuring shortest temporal path under a system of rules that effectively modify what a timestep means. If you inverted it and used the end point as origin, it'd still be the shortest temporal path assuming the rules are mirrorable. (I'm abusing time as a sort of metaphorish thing here sorry) I could be wrong but that's the immediate intuition without thinking about it. I also forgot the video so I'm just going off what I imagine the program would be like. Maybe it's not deterministic, but in the simplest case I'm imagining, I expect it to be.

[@andymcl92]

@@GRAYgauss Within the confines of the system, the shortest path and the shortest temporal path are the same thing. I'm saying if you work from top to bottom, then you take that endpoint and work from there upwards following the same rules, the route would not necessarily be the same because you could end up in a different spot on the top from the original start point. Imagine taking an n×n grid and filling in all the walls. Now imagine clearing a route that goes from the top middle along the top row to the left, then down the left column. The shortest route to the bottom (both my distance and time) is to go n/2 left, then n down. That's the only route. But now you start from there and go up again. The shortest route to the top is just to go n up. Once you're at the top corner, you're done. You don't need to go to the middle again. From there, the shortest route down would be straight down, and up would be straight up, and so on. You fall into a reversible path eventually.

[@GJames007]

I really like the videos made with this guy!

[@Ak47andre]

it didn't even freeze at 301 :D

[@awandererfromys1680]

Nice visualisation of the path of least resistance. Makes a cool animation. Would make for an awesome transition from one scene to the next where lightning suddenly strikes.

[@beirirangu]

If you've ever seen slow-motion footage of lightning, you'd see it's surprisingly similar

[@ZeedijkMike]

This is the coolest program I have seen for a very long time. Hypnotizing

[@seldom_bucket]

That cat was the most satisfying thing in this video.

[@matthenderson1672]

Summary: 1. A cat! Yes, a cat! I saw Mochi the cat! 2. Something about lightning

[@NickyHendersonArt]

Mochi is famous now!

[@jimparsons6803]

Ingenious. Reminds me, a little, of the programs used to generated etching patterns for printed circuit boards.

[@bigcountrymower4263]

"The cat helps MEOWt". Idk if that pun was intentional, but it was good.

[@Games_and_Music]

ha!

[@avadakedavra80]

Hahahahhaha 😂

[@KnakuanaRka]

^w^

[@cooleslaw]

I was recommended this right after thunderstorms in Southern Ontario. Nice.

[@mistertornado2303]

It's incredible that real lightning strikes can have tens of thousands of "steps" or potential target areas where charges have built up. Even more shocking that it determines its final location in milliseconds.

[@ShankarSivarajan]

If you think that's cool, you should check out the real-time large-scale fluid simulations.

[@RFC-3514]

The final location is a result of the local interactions, it's not "determined". Unlike these animations, real lighting isn't "goal-oriented", and doesn't follow a single path. You just end up seeing a main path (often with some forking) because that's the one that heats the air enough to form glowing plasma.

[@mistertornado2303]

@@RFC-3514 I know that - which is why I mentioned all the steps. A single bolt can have 50,000 potential paths (steps) which contributes to the zig-zag appearance of the bolt.

[@RFC-3514]

@@mistertornado2303 - To have 50 thousand "steps" the cloud would have to be really, really close to the ground. In the real world, every molecule between the cloud and the ground (along every possible path) is a "step".

[@ditrixgenesis781]

Breadth First Search is a practical application of a queue. In the detailed example, once 4 happens, there are two 5s. Both 5s are put in at the back of the queue, and this is what he meant by how he wrote the code. Then for the 6s, it adds the two 6s of the first 5 in the queue, then adds the two 6s for the second 5 in the queue. That way no numbers get lost and every step occurs completely before moving onto the next step.

[@user-iu1xg6jv6e]

Maybe giving each two adjacent boxes a weight to go from each to another, then find the path with the minimum weight! I don't know, but in my opinion it seems more likely to how lightning happens!

[@MrRyanroberson1]

With a large enough grid, it will take on that behavior, I'm pretty sure.

[@joseville]

To add some more context: Breadth first search (BFS) looks at all the length-1 paths first, then all the length-2 paths, then all the length-3 paths, etc. In the example at 5:40, BFS would have looked all the length-9 paths and found that no path so far reaches an objective. So it would then look at length-10 paths - maybe the first few length-10 paths that are considered don't reach the objective, but then BFS finally finds a path that reached an objective and can stop looking. Because BFS considers paths in order of increasing length, it always finds the shortest path to the/an objective. The order in which paths of a given length are considered can be arbitrary and is down to how BFS is implemented. Of course, you can also modify BFS, to find all paths to an objective or to tell you if there exists n-length path to the/an objective, or in many other ways.

[@4815162342o]

Нейроны места таким способом находят путь до целевой точки в пространстве. In the same way, the place cells find a way to the target point.

[@markbulla1851]

In watching all of the solved puzzles, I never saw one where the solution included going upwards for a step or more. I'm not sure if that's a glitch in the programming, or if the puzzles just ended up that way. Thanks for the fun vlog!

[@nowandtenofficial]

Well try making the same with a 3d labyrinth and thereby getting an actual lightening in a 3Dd space

[@Geuzenviking]

Cool visual and nice to see a fun use of algorithm.

[@stapler942]

So every time lightning *doesn't* strike the Earth, it's just because the air and charge distribution has been configured as an unsolvable maze...

[@official-obama]

That’s because the path is long, and the voltage wears off.

[@sleeptyper]

That or the algorithm became sentient and decided that it was better to solve between side boundaries (cloud to cloud).

[@pinaz993]

Nah. If you put enough electrons into a make like that, they stop respecting walls.

[@stetai352]

So basically weighted walls that need a higher number of ticks to be penetrated (to simulate higher resistance of air that could be overcome if the voltage was high enough)

[@framegrace1]

@@stetai352 Or start by a number proportional to the voltage and decrease it on every step instead of increasing it. When the number reaches 0 the search stops. More resistant air would be equivalent to a more complex maze.

[@jwilder2251]

Constructing an artificial maze to make a labyrinthine solution to an otherwise simple programming task sums up Mathematica perfectly

[@johnchessant3012]

Pretty sure I can do that in one line of Python after "import lightning" ;)

[@jansenart0]

Well you can, now.

[@DaveWhoa]

instead of traversing a maze you could simply select one of three random numbers for each iteration ... eg. 0 = left, 1 = down, 2 = right

[@mbrusyda9437]

@@DaveWhoa sounds like it'll get stuck

[@Alexander_Grant]

@@mbrusyda9437 Don't think it would be as pretty as this animation, but it wouldn't get stuck, it'd have a 1/3 chance to move down each time and wouldn't go back up.

[@mbrusyda9437]

@@Alexander_Grant that's the thing, if you get into a square like |__|, you need to go back up

[@LhwanPSilva]

OMG! I had this ideia to modeling a lightning years ago, but I never thought much about, just some sketches. Great video!

[@DaveWhoa]

instead of traversing a maze you could simply select one of three random numbers for each iteration ... eg. 0 = left, 1 = down, 2 = right

[@timothywaters8249]

In reality, the "maze" changes as lightning travels to ground. How would you solve it if the maze was also changing randomly at each step?

[@DaveWhoa]

instead of traversing a maze you could simply select one of three random numbers for each iteration ... eg. 0 = left, 1 = down, 2 = right

[@panteleimonnielsen225]

Very nifty - thanks, Matt & Numphile

[@ThreeEarRabbit]

This perfectly models how charged particles in the air would collide into other neutral particles, thus jumping the gap and breaking the insulation of the air.

[@ShabbaDabb]

I simply must have access to this program. Great stuff

[@ericvilas]

I mean it sounds pretty close to how lightning actually works, to be fair, if we consider each step of the process to have a probablility of its neighbors being ionized or not. The only thing that seems to need tweaking is the probabilities and maybe instead of a yes/no wall having something more continuous? But I'm not a meteorologist, so I'm not sure. Still, really interesting.

[@danielhenderson9719]

Thank you, Car, for helping him generate this.

[@buggs4350]

How is your video still froze on 301

[@EricTheCat]

Very interesting way to simulate lightning. Last winter I wrote a program to draw random lightning by calculating a branching tree fractal and drawing the path as soon as one of the branches got close enough to a randomly selected point near the bottom.

[@DaveWhoa]

instead of traversing a maze you could simply select one of three random numbers for each iteration ... eg. 0 = left, 1 = down, 2 = right

[@mho9296]

i’m here from the video 301

[@MorisonMs]

Starting from a full grid and gradualy and randomly removing walls until you can reach the bottom makes more sense specially if the generating part takes time (depends on the parametrs of course) . You can implement it with union find algoirhtm.

[@Cl0udWolf]

Even if it doesn’t work like real lightning, the randomness makes it look very believable and maybe someone might want to try this for a game to animate lightning, as the algorithm is fairly fast

[@DaveWhoa]

instead of traversing a maze you could simply select one of three random numbers for each iteration ... eg. 0 = left, 1 = down, 2 = right

[@Cl0udWolf]

@@DaveWhoa sure but that would probably have a tendance to go horizontally u would need to play with the probabilities

[@eldestisland4520]

It would be cool if it sent lightning for both paths in the case of a tie. Or if there were multiple semi-ends to the maze, which would result in mini-lightnings attatched to the main bolt. Great work! This was very interesting 👍

[@goatmeal5241]

Would've been cool to have some slo-mo lightning footage included to compare, because it really does look like the branching fronts of a lightning pre-strike.

[@yvesdelombaerde5909]

Highly interesting from both theoretical and practical points of view.

[@stephencurry_goldenstatewa6430]

I still remember 301 views

[@madisondampier3389]

This may not necessarily be predictive of lightning patterns in our atmosphere, but it would be interesting to discover the sorts of paths that a high current would "search" through in a sufficiently complicated maze before it finds the channel of least resistance

[@rinner2801]

FYI: It really should be going downwards towards the ground, then as it gets close some should start going upwards until they meet (based on charged density around certain areas). This might actually end up creating a slightly different result?

[@sydthegoat88]

Cool how slime mold manifests the same solutions to mazes, I think that is a model of how lightning works

[@valeriecoronado8713]

Pov: your here from the 301 yt vid

[@sussybawka9999]

This particular BFS algorithm is called Lee's algorithm iirc.

[@audio_collage]

hey 301 views guy)

[@williamrutherford553]

It's a very simplified way of showing lightning, mostly because the connections are "fully open" or "fully closed" so it's very binary. In reality there's small differences in the air, and the lightning wants to take the path of least resistance. The issue with simulating that is that the distances would no longer be whole numbers, which would add lots of complexity. But it definitely gives a great intuition for how lightning works, and I would also say it's a great way of showing the algorithm behind breadth first search!

[@adams3627]

Forgive the ignorance, but isn't it true that you can measure anything in whole numbers as long as your units are small enough?

[@sehr.geheim]

If this is how lightning actually works (he didn't claim it, but let's hypothecise) electricity isn't gnostic, how would it know the path?

[@millwrightrick1]

The same way a ball held in your hand knows where to fall when released. It is the lowest energy path.

[@sehr.geheim]

@@millwrightrick1 kinda makes sense, but I should probably go on r/AskScience to fully get it

[@OriginalPiMan]

Electricity follows every path that does not have too much resistance. So if three paths have resistances of 1000 Ω (ohm), 5000 Ω, and 1,000,000 Ω, then most of the energy will go down the 1000 path, some down the 5000 path, and likely none down the 1,000,000 path.

[@RFC-3514]

This is not how real lightning works, and electricity doesn't follow a single path anyway. If you look at super slow motion video of lightning strikes you'll see it follows a lot of different paths, and the reason why one becomes (a lot) brighter is that resistance starts to drop, making that path preferable.

[@Emily-fm7pt]

There are actually maze generation algorithms that ensure they are always solvable. In school, I created something sort of similar, but instead, it generated pseudo-random 3d puzzles of any shape, and it was P time complexity (The algorithm it had shown had a theoretical time complexity of infinity, meaning that in theory it could spend forever trying to generate a maze, but never get there because it was very "unlucky")

[@cosmo1248]

Bottom left of the thumbnail is sus

[@piyushv5739]

yo wtf how did u see it 😂

[@propername4830]

🤮🤮🤮🤮🤮🤮🤮BLEUUURRRGGGHHH

[@TheWiseTorsk]

I think the sentence "It should be, but it may not be" pretty much sums up probabilistics

[@Walking_Death]

Matt: This is how to model a lightening strike. Cat: Here is my butthole.

[@anieldayyanelday1771]

1:45 Helps with the animations? That's quite a brilliant cat.

[@craft_gamer5035]

301

[@K-o-R]

A related thing I'd love to see with these styles of maze is to imagine it's like an ant farm and water is being poured into the top. I want to see how each section fills up.

[@Truth-Spoken]

from "301 views" video