The Dumbest Way To Solve A Maze - Numberphile

Featuring Matt Henderson. Check brilliant.org/numberphile for Brilliant and get 20% off their premium service (episode sponsor)
More links & stuff in full description below ↓↓↓
Matt Henderson on Twitter (he posts lovely animations there): / matthen2
Matt Henderson Numberphile Playlist: bit.ly/MattHendersonPlaylist
Computerphile: / computerphile
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from The Akamai Foundation - dedicated to encouraging the next generation of technology innovators and equitable access to STEM education - www.akamai.com/company/corpor...
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Patreon: / numberphile
Numberphile T-Shirts and Merch: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9

[@numberphile]

Check Brilliant (episode sponsor): brilliant.org/numberphile Matt Henderson on Twitter (he posts super animations there): twitter.com/matthen2 Matt Henderson Numberphile Playlist: bit.ly/MattHendersonPlaylist

[@jamescollier3]

Make pressure, so they go the right way slightly more often than the wrong way each loop

[@MichaelMantion]

Who imports numpy as numpy. Everyone I know imports numpy as np. He might want to use numba to speed up his code.

[@Anonymous-df8it]

It would still work with only one particle... if you want an even dumber way!

[@chrisvandermerwe8321]

L

[@diegofrota]

What programming languages are Matt Henderson using to produce those beatiful animations? Can anyone tell me?

[@KasranFox]

finally, the maze-solving equivalent of bogosort

[@WinterDew.Studio]

This is the first thing which came to my mind

[@rewanthnayak2972]

What mught be the sorting equivalent of lightning maze solver??🤔

[@HyperHrishiHD]

Since you were first to say it then you get likes

[@yuvalne]

+

[@dagothur8037]

now throw a NEAT instead of pure randomness and now its NEATboggosolver!

[@superscatboy]

I once made a "rat with a terrible memory" maze-solving AI: It could do perfect A-star, but it only knew about walls it had "seen" (had a line of sight with), and at random it could forget a wall that it previously knew about.

[@HappyBeezerStudios]

That sounds intriguing. I'd love to see the results.

[@wolfmoz2232]

2. that

[@PC_Simo]

@@wolfmoz2232 3. that.

[@aaroncroft7514]

4. that

[@wojtekburzynski654]

" A-star, but it only knew about walls it had "seen" "so kinda like D-star?

[@MuJoeTheMean]

Interestingly, this concept actually has real world application in the world of mechanical engineering. Labyrinth seals are a type of seal in which a fluid is contained simply by making the leak path very long and torturous for the fluid particle to escape out of. This simulation is a pretty good demonstration of how surprisingly difficult it can be for a particle to escape when it just has random collisions to guide it. You can imagine that if designed to be intentionally difficult (narrow, long passages with lots of turns), a maze like this could do an excellent job at stopping leaks. They are most commonly used to seal spinning axels, where a normal seal may not be suitable due to friction or durability concerns. In these applications, the path usually makes many trips to and away from the axle so that centrifugal motion of the fluid can help prevent any leakage as well.

[@jasonrubik]

Now, that's a fun fact !

[@NickACrowley]

Is that the same principle used in a Tesla valve?

[@Kwauhn.]

@@NickACrowley That's the first thing I thought of! Is there a telsa valve such that particles escaping through it at a specific initial preassure is statistically impossible?

[@MuJoeTheMean]

@@NickACrowley It's similar. In a Tesla valve, the side path ways reverse the momentum of some fluid and then send it back into the main stream, so it's like you're subtracting the velocities from each other (that's not strictly true in a physics sense, but it's the right idea). The end result is fluid flow with an average velocity much closer to 0. Labyrinth seals rely much more on random chance instead of intentionally 'subtracting' velocity.

[@finnaustin4002]

@@Kwauhn. no, Labyrinth seals mostly used for high viscosity fluids like grease. All they do is make the path much longer and higher friction than a straight path

[@hamjudo]

Long ago, my robotics club had a maze solving competition for small autonomous robots. Before the contest began, I put a toy into the maze. It was a battery powered sphere with a picture of Santa Claus on it. There was a motor driven offset weight inside the Santa Ball. The Santa Ball would roll in a straight-ish line until it hit an obstacle. Then it would bounce in a random direction and continue on. The actual robots moved much more slowly. Even though they didn't ever retrace their path, they were much slower. Fortunately, the Santa Ball was disqualified. It was store bought, not built by a contestant. Thus one of the robot builders got the official first place prize.

[@bobson_dugnutt]

A local engineering competition had a remote controlled robot challenge. You got points for completing various tasks. Then some points for time. The year before I participated, the team from my school just made basically a RC car and went straight for the finish without doing any of the tasks. They got first place. Needless to say they changed the scoring grid for the following year.

[@Triantalex]

??

[@donaldasayers]

I have a 3D cube maze, it's in the form of a 5x5x5 cube, transparent and you roll a ball through it. But if you blow through it, the correct path steams up. This is exactly the same method.

[@DaedalusYoung]

Similar, in your cube there is air. If you blow through it, the air in the 'wrong' path can't escape, you're pushing it into a dead end. Your breath will take the path of least resistance. Since this model doesn't simulate air pressure, or any interaction between the molecules, there is the same resistance going into a dead end as there is following the correct path (none at all), where in the real world there is a difference in resistance. That makes your real world example more efficient than this model.

[@oddlyspecificmath]

So basically if I'm ever trapped in a huge cube, follow the breeze, or perhaps the condensation...

[@thekingoffailure9967]

@@oddlyspecificmath light some incense

[@jeffreydemattos5619]

I like your idea of solving a maze with gas pressure. this is mathematically very simple to simulate, and even a bad simulation would be very fast. For example, you could assign a fixed pressure of 1 to the maze entrance and zero to the maze exit. All the other cells start with zero pressure. Then iteratively calculate the pressure for every cell as the average of the pressures of adjacent connected cells. The length of the shortest path is simply the number of iterations it takes for the cell adjacent to the exit to get some non-zero pressure. And the shortest path would simply be from the beginning to the cell with the next highest pressure for each step and so forth. For larger mazes, processing time could be saved by keeping a list of all the cells with some positive pressure and in each iteration, add to the list the cells adjacent to the ones that have already been calculated at least once. Unfortunately this is not much different than simply enumerating the entire maze search, with the exception that you only have to store one value (the pressure) for each cell.

[@TheEternalVortex42]

This is basically the Bellman-Ford algorithm for finding shortest paths.

[@DeenBoi]

I didn't expect the word 'sperm' being mentioned in a Numberphile video

[@moth.monster]

A different kind of -philia?

[@interbeamproductions]

numberphallic

[@trevorgreenough6141]

Is simulating a molecule hard or easy? Yes, it is hard or easy.

[@recompile]

As they did in this video? Very easy. Though it looks like he over-complicated things quite a bit...

[@eragonawesome]

"that depends, do you want the big effects or the really tiny ones?"

[@Triantalex]

??

[@shohamsen8986]

This problem of maze solving screams calculus of variation. The function that minimizes the distance between the beginning and the end point subject to the wall constraints. I would model the walls as lines (some thickness) of infinite potential. So that functions intersecting the walls have answer infinite. Im sure someone must have thought about it (it would be a shame if nobody tried this tool with 500 years of research backing it up).

[@leodarkk]

One of our professor at the university made us code exactly this, while of course also explaining the mathematics. It was 10 years ago and still one of my favorite algorithm, I was kind of blown away by it. As far as I remember, it also gives a very beautiful visual representation of the answer as a gradient (?), with as you said, the walls with value infinite. So yes, you are not the first to think about it, but it is indeed an awesome idea!

[@shohamsen8986]

@@leodarkk sounds about right. I would sincerely hope I'm not the first person to come up with this idea. like i said there is 500 years of research behind these subjects.

[@frankfahrenheit9537]

Like letting an electric current flow through the maze. Pour carbon power onto the floor, same conductance everywhere, except walls which are modelled as conductors with zero conductance. Solve poisson equation of the electric field with boundary condition entry maze=1V, exit maze=0V, constant conductance everywhere except where wall present.

[@SgtSupaman]

2:24 Well, by definition, the dumbest way to solve a maze has to work because it would have to solve it, so this could still be the dumbest way. On the other hand, the dumbest approach to a maze would be to just stand still. That, however, can't be called the dumbest way to solve a maze, because it never solves the maze.

[@jasonrubik]

Semantics to the rescue ! In the best way possible ! :)

[@TheJunky228]

turn around and exit at the entrance! 4d chess solution to a maze

[@jasonrubik]

@@TheJunky228 that's a big brain move

[@JimBalter]

It depends on what "way" means. Not all ways to solve a problem work.

[@DqwertyC]

It's like the Jack Sparrow meme: "This is, without a doubt, the worst way to solve a maze!" "Ah, but it does solve the maze."

[@cyndicorinne]

This approach to solving problems is quite effective as it is interesting. In computer science there are many algorithms which emulate physical processes. It is always a pleasure watching Numberphile because of its closeness to the field. Thank you 🙏 for another awesome video!

[@philippelepilote7946]

30 years ago, I had the idea to "inflate" a grid of walls with random strength in order to create a "simply connected" maze. I eventually wrote the algorithm in Visual Basic for Excel, associated to the "follow-the-right-hand-wall" solver. So happy to discover that somebody else finally blew into a maze !

[@valovanonym]

Je serais intéressé par les détails de ton algorithme!

[@philippelepilote7946]

@@valovanonym My algo is very basic. Hereafter is its pseudo-code. Unfortunately YT prevents me from giving a link in the comment so that I cannot share the Excel file. // First assign a random number to the walls of each cell For each cell in the grid assign a random value to the right and bottom walls // and taking care of grid borders Do some init While all cells have not been inflated // Loop until all cells are inflated, and each time, explode the less resistant wall on the border of the already inflated cells Do some init For each inflated cell in the grid // Find the cell whose wall (left, top, right or bottom) is the less resistant if its left/top/right/bottom cell is not inflated yet // and taking care of grid borders if the left/top/right/bottom wall is the less resistant already seen // the cell is a candidate to explode one of its walls if none of the walls already seen had the same strength remember the current cell else // Bring a little randomness randomly choose between the current cell and the other already remembered cell and remember it end end end end //for // all inflated cells have been visited : explode the less resistant wall delete the left/top/right/bottom wall of the remembered cell mark the new left/top/right/bottom cell as inflated continue end //while Bon amusement

[@martincohen8991]

Considering that each particle has to keep track of its path, this would require a tremendous amount of storage.

[@thumper8684]

If the simulation is deterministic you can recover all the data from the initial conditions.

[@cyndicorinne]

A-maze-ing demonstration of this physical approach to problem solving, which for me as a computer scientist is always cool to see.

[@johndododoe1411]

If you were an actual CS, you would know how entirely bogus the arguments are.

[@Muhahahahaz]

@@johndododoe1411 if you were an actual human, you would have kept this to yourself

[@felixmerz6229]

I love the merge between logic and programming and creativity. It's how I conceptualized creating code forever, but this illuminates that intersection so well. I'm amazed.

[@PlayerSalt]

I thought I was stupid for always turning left , which surprisingly would have got me out of this maze fairly quickly , at least quickly enough

[@Aaron-cs3xl]

So long as you don't run into a loop, which shouldn't be possible if the exits are on the outside of the maze, it will always get you through the maze.

[@lonestarr1490]

@@Aaron-cs3xl And the maze is purely 2-D without "wormholes".

[@kindoflame]

That is called the Left-Hand Rule, and it actually works very well. If the maze is simply-connected, meaning all the walls touch one another, then you are guaranteed to eventually reach the exit.

[@George4943]

@@kindoflame And, of course, the Right-Hand-Rule works equally well in such mazes.

[@NLGeebee]

@@George4943 only for British mazes ;)

[@redryder3721]

It would be interesting to see what sort of maze design results in the Brownian motion taking the longest time to reach the exit. Would it simply be a zigzag path using 100% of the area of the maze or would it look more like a Tesla valve?

[@freshrockpapa-e7799]

A Tesla valve wouldn't be anything interesting since the particles don't interact with each other.

[@dmitryrybin7831]

Heuristically longer path means longer exit time, hence you want your maze tree to be a path, which results in zig-zag path maze (the zig-zag pattern can be altered aswell).

[@glenneric1]

I'm thinking zig zag with as few straight-aways as possible. Though maybe a succession of ever smaller chambers with a single entry and exit for each. Would be interesting I agree.

[@landsgevaer]

@@glenneric1 Maybe as many straight-aways as possible, since on a diagonal you can reach the next box with an average step size of sqrt(1/2), whereas on a straight path the required distance is 1. Atoms don't have memory regarding their direction, and straight alleys doesn't allow you to cut corners, so to say.

[@mitchellsteindler]

A particle could never reach the exit... so forever

[@HappyBeezerStudios]

How they are stuck in the first third and the density becomes progressively lower reminds me of mazes in Roller Coaster Tycoon. The way the pathfinding works causes the guests to practically get stuck (and walk back) on specific layouts with a very slim chance to move further.

[@anon6514]

Matt has the best job. I love making simulations like this.

[@scottbarrie1279]

I would love to see how adding more molecules decreases the average time of the fastest exit

[@jvdw843]

+ as a function of the length of the shortest exiting path.

[@charleslivingston2256]

Since he has the molecules just doing a random walk, doubling the number of molecules would cut the average time in half. If he were using pressure, I would expect the average time to drop more than that. [Edit: not true. See responses]

[@jursamaj]

@@charleslivingston2256 Can't be just the inverse of the number of molecules. There is a non-zero minimum to cross the maze. Rather, I'd expect it to exponentially decay towards the minimum.

[@mitchellsteindler]

@@jursamaj yes

[@landsgevaer]

@@charleslivingston2256 It doesn't work like that, I fear. That would mean you could find an arbitrarily quick/short path by having an arbitrarily large number of atoms, but the shortest path doesn't have length zero. It even doesn't qualitatively scale like that when you have few atoms. Unimpeded brownian motion spreads according to a gaussian bell curve; twice as many samples doesn't get you twice as far then.

[@lucassippel7516]

Looks like they get halfway quite quickly. You could also diffuse gas from the exit and then check pairwise between particles from opposite ends for line of sight. Then stitch a forward path and backward path together for a complete solution. Pairwise checking might be inefficient so you could limit it to particles which are past some predefined halfway - like a vertical line down the middle of the maze. This is the sort of thing that is only obvious when you have an appropriate visualization. Always love watching these animations!

[@rianantony]

If you wanted to find the dumbest way, it'd be fun to wait for every single molecule gets out. And then highlight the path taken by the single last one to find the exit

[@user-pw5do6tu7i]

Interviewer: i see you made a maze solver, did you use AStar? This guy: *I wrote a physics engine*

[@Joecoleman84]

It's hard to explain, but brain feels refreshed by this.

[@alienmoonstalker]

Great content! I am now motivated to try the fluid dynamics method to solving the maze.

[@velsni]

just done, it works nicely with CFD

[@kilimanjarocruz660]

It's lovely that this 'demonstrates' both the pressure drop that a gas would have in such a flow and the statistical origin of the ideal gas law. Awesome.

[@invisibules]

Or we could build the maze out of copper strips, and connect a battery between the start and end point. Use a magnetic compass to find the path, or turn the current up and watch it glow. This would even work if there were loops, like the air blowing method.

[@CharlesVanNoland]

While it *is* random if people become successful, the odds become more in their favor the more they act on opportunities - and the trick to opportunities is recognizing them when they are there, which most people don't.

[@NickCombs]

Often with optimization problems, it's a good idea to start with the dumbest solution as a sort of sanity check.

[@phileo_ss]

This video reminded me of a friend who, thirty years ago, wrote a computer programme that made random seven-storey mazes in which you can walk around in and collect various items to earn points or maps to help you solve the maze.

[@imallfordabulls]

The guests in Roller Coaster Tycoon mazes be like:

[@matbroomfield]

You could add an evolutionary "movement with purpose" parameter to this. On a grid with right angled cells, you can immediately simplify by limiting the movements to 45 degree increments, and by eliminating "back on yourself" as an option, you could speed up the solution by 12.5%. If rather than adding a wind modifier, you added a weak suction modifier, you could refine still further.

[@pepsalt]

been following this guy on twitter for so long, nice to see he made it :D

[@MCLegoboy]

1:06 Oh... I mean it's apt, but your enthusiasm is on a whole other level there. XD

[@dominiquelaurain6427]

Random waks in the plane is an amazing subject. I like that "physic view" of the problem, because it is local to every particle (with its path as only memory data). I will qualify the idea more like "the blindest way" to solve a maze because same as many people in a maze with no light (bumping to a wall, and maybe another people, is the only information). There are less blind ways, if you imagine people has a lamp ligntening to the random direction, people can accelerate to the next lightened wall. Another extension is for the random step : you can imagine a lattice drawn over the maze and people are only at vertices.

[@U014B]

This is even more brute force than brute force, and I'm all for it.

[@djayers]

Love it. How can you not go "wheeee!" at the start, "go on, go on..." towards the end :)

[@djayers]

I would think the bouncing-ball/gas approach could be an efficient solution (hard to prove), and probably isomorphic to the fluid dynamics approach

[@gedstrom]

I still remember a maze generation program that I coded in Basic back in 1978...45 years ago! I had a lot of fun with it in my very first personal computer.

[@robertmchugh2001]

Well done … thanks for walking through the code!

[@blindleader42]

I like how the automatic captions deal with Matt's accent and translates his "Brownian motion" as "brainy in motion"...🤔 Hmmm. Maybe the machine is on to something. 🙃

[@giddyjigga]

I'd love to see all the paths overlayed to see how densely some areas were explored while other areas were only superficially discovered.

[@zebfross]

Love this guy's stuff! Always fascinating

[@squatty9994]

turn those paths into wall sized art, they are really awesome.

[@cbuchner1]

How to solve a maze with a fart

[@yoxnod]

This video reminded a paper by Bennett of 1982 where he described concept of Brownian computer which solves problems by random motion, and most interestingly, he argued that RNA is basically a natural Brownian computer

[@gurgleblaster2282]

I could listen to him describe things for days lol.

[@randy7894]

Cool thing about Matt is that he also sees art in algorythms.

[@Novalarke]

The best (but slow) way to solve a maze: pick a wall, follow it. You will never get lost.

[@theblinkingbrownie4654]

But what if _3D_

[@Hermaniac8]

(as long as the maze doesn't have loops)

[@andvil01]

@@Hermaniac8 No. You can only be stuck in the loop If you follow the inner wall of the loop. If you stick to one wall in the beginning you will never touch the inner wall off the loop. The outer wall must have an opening to the end.

[@Novalarke]

Actually, I don't think that matters, as any wall loop would have to be free floating in the maze matrix, and thus defined by the outer housing which will have to be a left or right wall. But if you have a link to a maze that beats the "choose a wall" method, I'd totally dig that.

[@Novalarke]

@@andvil01 - exactly, that's what I thought as well.

[@Drachenbauer]

what program is used here for that code window, that generated stuff directly in between the code-lines?

[@johnchessant3012]

Love this guy!

[@xapemanx]

I confirmed this simulation; i created the same maze in a liquid and then placed my sperm on one end. amazing

[@flleaf]

i love the internet

[@flamencoprof]

Sorry to burst your bubble, but that solution is not forthcoming. Sperm are attracted to progesterone, which is secreted from the egg's companion cells. Sperm are not randomly swimming in every direction.

[@marklonergan3898]

"...or i could do it in the dumbest way... So i switched over to python..." Shots fired!

[@GeofreySanders]

Yeah I felt that one.

[@traywor1615]

You could increase the random direction moving, the more molecules are nearby, to simulate pressure, while, when the pressure drops, it keeps going more often until it hits a wall.

[@MrLoukizz]

The hair dryer approach is actually the exact same as the gas approach because the hair moves (just like the expanding gas) to the point of lowest pressure. But to simulate pressure you would need to simulate particle collision with each other or calculate the local gas density in any other fashion and map it onto the labyrinth (for example counting the number of particles per square). However this approach might still fail because of turbulences ;-)

[@azyfloof]

Now we just need Steve Mold to built a maze out of clear perspex and blow smoke through it to see if the smoke "solves" the maze :D

[@nhillery1]

Brady - I’m surprised you didn’t ask about the particle that finished second (or closest, since I guess the simulation stopped before it could finish). We could only dream of being the winner, but it feels so much more realistic that we finish close.

[@handreieiacasa]

Great, now we know that in order to escape backrooms we just need to turn ourselves into a gas

[@PetraKann]

If the simulation ran infinitely, would all the particles find their way out of the maze?

[@itismethatguy]

Yeah i guess unless there's a place they can get stuck and keep going in cycles

[@MKVideoful]

Do not forget, some infinities can be bigger than other infinities.

[@MKVideoful]

You will end up with infinity amount of success particles and also with infinity amount of failed particles. The failed infinity amount will be bigger.

[@dontbothertoreply9755]

Yes, as all paths will be taken.

[@charleslivingston2256]

If there exists a path through the maze, every random walk will eventually exit

[@V1ctoria00]

Collision physics is in so many video games. Look at "oxygen not included" great example of a game where you could literally use gas to fill a maze.

[@PunmasterSTP]

That was…a-maze-Ing. 😎

[@boelwerkr]

forget "bumping" in each others. Make a repelling force. If the molecule go below a defined distance a repelling force dependent of their distance is applied (you could also make it an attraction force beyond that "0-point" to hold the cloud together). This way you can use "wrong" but much faster distance/repelling calculation. It works really great for "emulating" pressure dispersion.

[@vsikifi]

Long ago I wrote a program that generated similar mazes but with a somewhat different algorithm: I started with a rectangular grid with all the possible walls present. I picked a random cell and then I did a random walk starting from that cell that knocked down the walls along the route it traversed, This random walk avoided going to already visited cells. When it ended up in a situation where it couldn't move into any direction without hitting a visited cell of maze edge, I picked a new random unvisited cell and started a new random walk from there but avoiding only cells visited by that walk. When it hit a cell visited by an earlier walk, it knocked down that wall and stopped. Then I repeated this until there was no more unvisited cells. The end result was a similar maze with unique routes between every cell pair but no loops.

[@TaohRihze]

11:30 and around it, the maze does not seem to match the particles. If you notice the lower left part and the upper left is separated, yet there is a LOT of molecules going down into the area.

[@valj137]

I checked! The particles are following the maze that's shown at the very beginning of the video 0:09, NOT the maze that is at 11:30. I think that's just one of the other mazes he had simulated. But for the particles' paths he showed the beginning maze. :)

[@sumantchopde9039]

Just today I had a test where I had to simulate maze-solving using Monte-Carlo simulations. This algorithm is quite cool too!

[@honeybee9455]

Instead of moving in a random 360 direction per tick, why doesn't it move in a random cardinal direction?( Per tick moving up, down, left or right and not some random theta). Would this be less computationally taxing?

[@franzperdido]

The paths look really interesting. Would be cool on a T-Shirt or something like that.

[@subliminalvibes]

I remember the old Windows screensaver always solved the maze by ONLY TURNING LEFT... 👍😎

[@mustelidify]

I'm interested in letting all the molecules escape and looking at the path of the LAST molecule to escape and what proportion of the maze area it traversed.

[@sleepib]

I wonder what the best strategy is for picking a simulation depth. If you cut off the simulation early you have more chances to get lucky, but you also risk cutting whatever path gives you the best result so far, or in extreme cases might never find a solution.

[@George4943]

There ought to be a quantum computer solution to maze solving which does "all the paths" at once.

[@GGoAwayy]

If you can represent the problem as a quadratic unconstrained binary optimization

[@liweicai2796]

It isn't going to be faster, since you nonetheless have to obtain information of the whole map, the complexity can't be lower than linear to the size of the map, which classical computers can already do.

[@johndododoe1411]

Quantum computers should not be allowed to exist. No honest person should forward the research into their creation and use.

[@mrosskne]

@@johndododoe1411 Why?

[@johndododoe1411]

@@mrosskne Currently, quantum computer algorithms exist that will break even encryption and signature tech widely deployed. We need to hold back quantum computer creation until everyone has non-NSA post-quantum encryption protecting everything they've done since birth. Which won't be this century.

[@punkdigerati]

You've described survivorship bias with the random billionaire biography bit.

[@Noobinski]

Mazing!

[@jonathanw1106]

Really interesting, I don't know if they mentioned this but will every molecule eventually reach the end given enough time? If so is that mathematically provable?

[@matbroomfield]

Given enough time, EVERY molecule would eventually get out by sheer random chance. Imagine if you were betting on a particular molecule and it randomly got all the way to the exit cell, before bouncing off a wall and working all the way back to the start position!

[@MaryamMaqdisi]

That’s hilarious to me fsr

[@matbroomfield]

@@MaryamMaqdisi :)

[@mekkler]

Maybe that concept could be applied to the traveling salesman problem.

[@FuncleChuck]

Oh so that’s how my city’s roads and utilities were planned! I always wondered.

[@caparn100]

3:50 I think the example of putting a fan to create wind is really just the same as adding a lot more molecules to the maze.

[@longleaf1217]

only if you program in the collisions between each of the molecules which would have the same effect of creating higher pressure where there are more molecules. He mentioned the he has it programmed now each molecule just ignores all the others like they aren't there. so there is no pressure in the system. all adding more molecules might do is find the solution faster purely as a result of it being more likely you have a lucky molecule. the point of having a fan is just to create high and low pressure, which is the same effect you would get with the collisions.

[@jursamaj]

No, the way he has it implemented, the molecules have no effect on each other, so more molecules doesn't actually matter. The wind would change the distribution of the random steps, making each molecule more likely to step towards the exit.

[@caparn100]

@@longleaf1217 That sounds like a much more lengthy running and complicated program. It would be much simpler if each particle, for each move, just picked a random adjacent cell to the one it's in that it hadn't been in before and doesn't have a wall along the side then to get the result just select the particle that exists the maze first.

[@ChrisLee-yr7tz]

@@jursamaj What would the 'wind' be and how would it interact with the molecules? What would makes the wind different to the path finding molecules? Surely the whole idea of a wind is just having the molecules interact and flood the maze with more of them?

[@bable6314]

@@ChrisLee-yr7tz The wind would literally just be a net force in the direction of the exit that gets weaker as a particle gets further from the start.

[@HappyBeezerStudios]

"Every batch will eventually have a winner" I'd go so far to say every particle eventually finds the exit, given enough time.

[@markkaidy8741]

Program a maze to solve for large prime numbers (one path to the prime) and then use it for solving unknown primes. This method may be invaluable.

[@saxxx78]

Great video, a question: why the distribution at the end do not spread to all the maze? Isn't it like molecules know of each other? maybe I am just bised looking for somenthing in randomness. Thanks if someone can help me.

[@rg8766]

"...or I could, you know, solve the maze in the dumbest way. So I switched over to Python..." :)

[@6DAMMK9]

I thought it should be a computerphile video (solving maze?), and then I'm pleased with an extra dumb brownian motion INSIDE the maze.

[@cmuller1441]

This is exactly what you do when you make coffee with a percolator...

[@kevnar]

I wonder if it would be better or worse if particles repelled each other. They would expand down the maze, filling every path until one of them got to the exit.

[@JaydenLitolff]

Need to do one that solves the maze with softbody physics now

[@Spencer0616Gaming]

you could improve this by giving each particle a radius and allowing particle collision, it seems the current method doesn't use a realistic gas particle as they do not interact with one another. This could possibly increase the variation in trajectories of the particles thus acting much more like a high-low density situation and possibly speeding up the solution time. As it stands you may as well use one particle with a minutely curved taken path. Given one particle or a set number I would assume that there will always exist some maze that can effectively capture every particle in an infinite loop, the curve on the trajectory for a perfect maze finder is questionable but would be interesting to learn more about. Supposing every maze has a specific curve that makes it solve the maze the fastest. Thank you for the videos

[@WhiteSpatula]

If you had a maze where every wall was a mirror, and you shone a laser into it from the starting point, sweeping around to test all possible angles of entry, I wonder what sort of correlations would manifest between successfully exiting the maze and the maze’s key attributes such as block size (vs laser width), overall dimensions, and complexity. I think it might also be fun to see a geometry wiz or a billiards pro venture some guesses beforehand.

[@b.a.r.c.l.a.y]

i wanna know this too i imagined more like a circle, with its circumference made of infinite points, and all of them bouncing around the walls until it reaches the end i wonder what the pattern of the circle would look like if every point that went to the exit was colored differently

[@GodwynDi]

Didn't they do a similar video on that already? The illumination problem is the one I was thinking of. Box where it is impossible for light to reach all of it from a single source.

[@fractal_lynn]

I bet you could assemble a bunch of line signed distance functions into the shape of the maze and check this composition of said lines for the closest the point is to the maze, and then only move some point within a uniform disk with a radius of such :)

[@pvictormesquita]

which IDE did he use to program this?

This is great, really enjoy the video! ♥♥

[@hurktang]

you could have round the x,y position of the particle before and after the move to the nearest cell. And just if and only if the 2 x,y coordonate differ, if there is a wall between those 2 coordonate. I assume that just that would have made your code run about 10x faster, because the collision detection here is clearly the most math intentive part of each particle loop.

[@Krebzonide]

The is kinda like that thing the action lab did like 2 years ago where water flows through a maze and by adding die to it you can see the path.

[@aveenmahabal]

pick a direction (left or right) always make that turn and follow to the end and exit

[@dovos8572]

doesn't work in every maze (it depends on what/where the goal is)

[@Math.Bandit]

That fails if there is a loop though, right?

[@dovos8572]

@@Math.Bandit if the maze is from outside to outside then it works even with loops. it can fail if the goal or start is somewhere isnide the maze and all starting walls aren't connected to the outside wall.

[@Math.Bandit]

@@dovos8572 Even if it's from outside to outside, wouldn't it fail to a very simple "around a block" type of loop, where you're making the same four left (or right) turns around a single area over and over again?

[@JobvanderZwan]

Meanwhile, Rohan Sahwney and Keenan Crane have been taking this random-walk stuff and turned into one of the *smartest* ways to solve complex geometry using Monte Carlo methods like Walk-On-Spheres.

[@utkarshgupta137]

A man of culture still using Atom.

[@TheJunky228]

reminds me of using electricity (connect start and end and it will find path of least resistance) or another analog method of solving these sorts of puzzles

[@Veptis]

what about a random Fourier series? As a cyclist. I often plan my routes not to be the shortest or "fastest" but with the least or no traffic lights so I don't have to stop. It's a navigation problem which is finding the optimal path through a graph. But all nodes (road intersections) with traffic lights get removed.

[@LIA-52]

9:23 Nice word choice, seeing how you're guessing with a gas simulation.

[@kirylbah]

It looks nice and interesting but very inefficient in term of consumed resources. I was in school around Intel 8080 CPU and less than 64 of RAM. Same type of task. Just array to store each cell of maze that you are filling with numbers incrementally and had to scan array to find empty cell near with cell that already have numbers. It might sound complex but it was simple program that works on very very slow CPU and you had to use assembler almost always. The second option was Basic