The Dumbest Way To Solve A Maze - Numberphile

[@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

[@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]

??

[@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.

[@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.

[@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.

[@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.

[@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."

[@DeenBoi]

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

[@moth.monster]

A different kind of -philia?

[@interbeamproductions]

numberphallic

[@thecakeredux]

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.

[@topilinkala1594]

No-one has mentioned it but the way only one sperm can enter the egg is that the instant it enters the electric charge on the surface of the egg changes to repel more sperm.

[@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

[@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

[@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

[@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 ;)

[@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.

[@punkdigerati]

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

[@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.

[@rg8766]

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

[@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!

[@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.

[@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

[@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.

[@jasminecruickshank2343]

I love “this one became a billionaire and wrote a biography about all the great decisions it made but really it was just random”

[@jasminecruickshank2343]

Shout out to the triggered capitalists

[@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.

[@marklonergan3898]

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

[@GeofreySanders]

Yeah I felt that one.

[@anon6514]

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

[@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.

[@user-pw5do6tu7i]

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

[@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!

[@NickCombs]

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

[@imallfordabulls]

The guests in Roller Coaster Tycoon mazes be like:

[@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.

[@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.

[@Joecoleman84]

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

[@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

[@FuncleChuck]

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

[@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.

[@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 ;-)

[@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.

[@Martial-Mat]

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.

[@MCLegoboy]

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

[@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.

[@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.

[@thiyagutenysen8058]

Does anyone know the github link to code presented in this video?

[@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.

[@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. 🙃

[@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.

[@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.

[@jadeyjung]

what if the title was "the dumbest way to be a billionaire" then you've got a billion views in the easiest way for sure

[@traywor]

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.

[@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.

[@HappyBeezerStudios]

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

[@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

[@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.

[@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.

[@U014B]

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

[@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.

[@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.

[@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. :)

[@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?

[@Martial-Mat]

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

[@Martial-Mat]

@@MaryamMaqdisi :)

[@peppybocan]

My question: how would the random walks differ if the length of the random step was bigger?

[@jursamaj]

Mathematically? Not much, until the step size gets comparable to the maze box size.

[@H0A0B123]

@@jursamaj you pulled that out of your ah without doing the math. didn't you?

[@landsgevaer]

If the step size becomes too big, it may never be solvable (if you always hit a wall). But as long as the step size is much smaller than the boxes, you would expect the number of required steps to increase quadratically with the reduction in step size: i.e. 10x smaller steps require 100x more steps, so the total length of the path becomes 10x longer too.

[@saavestro2154]

​@@landsgevaer isn't quadratically first order approx? my guess is larger step sizes would also increase the time spent on a deadend

[@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

[@gurgleblaster2282]

I could listen to him describe things for days lol.

[@JohnLeePettimoreIII]

dumbest way: smash it to powder with a hammer, then throw the maze-powder in the air while loudly declaring, _"I win!!"_

[@RoySchl]

wait a minute I could get payed for stuff I did for shits and giggles in 7th grade decades ago? damn

[@thecarman3693]

If a maze has no free walls (walls that do not touch the outer perimeter through continuous contact) it can always be solved by keeping (remaining in contact) to either wall from the entrance. I have also found that many mazes can be solved more easily by traveling through them in reverse.

[@CamAlert2]

this is more something akin to a computerphile video

[@handreieiacasa]

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

[@pepsalt]

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

[@pwhite2579]

also, check each room in order. if it has only one door, exit and close the door. repeat until you reach a room that has more than one door. go until the last room. if you closed no doors you are standing in the escape path. if at least one door was closed repeat.

[@RickJaeger]

2:39 You're telling me the dumbest way of solving a maze is farting at the entrance? Yeah, okay, I guess that comports.

[@nathanielmoreland5271]

I hope to see matt in another video he's so rad. Should bring him back again. and again.

[@randy7894]

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

[@robertmchugh2001]

Well done … thanks for walking through the code!

[@muhammadsiddiqui2244]

Simply beautiful.

[@EconAtheist]

You could've just *asked* me and I'd have immediately found the dumbest solution. 🤕 /it's a talent

[@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.

[@FransHenskens]

This would be a more accurate representation of "pressure" in a gas if the molecules stuck in a pathway gave an indication of how many other molecules are around them. Pressure increases as more molecules are constricted in a confined space. If you wanted to keep the pathing algorithm the same, you could have the update mechanism change the direction of travel of a particle enters a cell reactive to a pressure vector updated by its surrounding cells.

[@ferretyluv]

But then he’d have to incorporate rheology formulas.

[@komojo]

Is running the simulation for 1000 particles any more efficient than running a single particle 1000 times longer?

[@MrMarapro]

This simulation could be made to mimic the movement of gas molecules quite easily by checking the number of other molecules around it after each step and then determining the length of the next straight path based on the number of neighbours. The less neighbours, the longer path before the next change of direction.

[@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

[@zaco-km3su]

The maze has one issue. It's cut in half and there's one way through the dividing wall. That makes it easy to find a part of the right trail.

[@Jkauppa]

gas pressure simulation is fast, breadth first style propagation, or also electric current

[@Jkauppa]

if you have max 1 particle in cell pressure, you expand in new cells always, through known path

[@Jkauppa]

ironically most of your science is done this way you just demonstrated, rip

[@Jkauppa]

you claim to be smart but you are not, complex is not always better than simple, monte carlo random walk simulations is what you just demonstrated

[@Jkauppa]

ok so first construct a tree of all possible connections, then find the shortest path to the exit

[@Jkauppa]

cause of law is trash ways of doing things

[@erbro]

This is something I have been thinking about for some time. If you fill a maze with water, and you apply pressure at the entrance and an opening at the exit, the maze gets basically solved at the speed of sound. I have been thinking whether I could make a cellular automaton that does that. I mean, not linearily find a solution, but cell based, suited for parallel computing.

[@ultradarx]

Just add water in the top and when it comes out at the bottom add a dye to water to trace the solution path.

[@SaHaRaSquad]

The problem is that on a computer you need to simulate the water molecules, so it's never going to be all that fast. Much faster than the solution in this video, though, because the pressure reduces the randomness.

[@AppleGameification]

That's the lightning algorithm

[@ultradarx]

@@AppleGameification Thanks for the info. I'm more interested physical processes that solve the maze. Been thinking if the walls of the maze were mirrors would a light ray trace the path out?

[@rasowa2958]

Creating a maze with one solution is actually trivially easy. Just start with outside walls, and then keep adding new walls connecting one end to any existing wall. That's it!

[@redountilgreat]

Idea: Apply a value of zero to every square of a maze. Create pressure and sucktion on entry and exit at every iteration: Add one at the entry square and substrackt one at the exit square. Let both spread until they connect. Interesting? Wonna try? I can't code well enough. Have fun.

[@davidjohnston4240]

The maze was created with a tree. Presumably you could assign a probability of a particle taking a left or right or backwards path from nodes of the tree, multiply up the path probability for the winning solution from the start point to the end point and so compute the odds of a particle making it through the optimal path, without actually simulating it.

[@m3tro839]

This is related to the concept of first passage time of stochastic processes. By collecting the times taken to solve the maze for many many simulations, he could obtain a first passage time probability distribution and a mean first passage time. Each maze will have a different one.

[@LiamPilot120]

There’s a bug in his code, looks like molecules can cross walls.

[@zebfross]

Love this guy's stuff! Always fascinating

[@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?

[@johnchessant3012]

Love this guy!

[@sumantchopde9039]

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