Maze Solving - Computerphile

Putting search algorithms into practice. Dr Mike Pound reveals he likes nothing more in his spare time, than sitting in front of the TV coding.
EXTRA BITS: • EXTRA BITS - Maze Solv...
Mike's Code: bit.ly/MikesMarvellousMazes
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

[@mrfreezy7457]

"Each of these squares is a square, and I'll hear nothing more said about that". I love the idea of a maze made out of parker squares.

[@omikronweapon]

Parker maze?

[@rewrose2838]

That would be an amazing collab, team Parker Pound

[@liminos]

It's so awesome that all nerds (counting me in) are somehow the same kind of broken 😂😂 I already hear my colleages, after presenting my ideas, say "We'll, why is it all made of squares?", "What's the path/obstacle ratio of the squares you generated?", "How does it behave if..", "Why haven't you implemented ...?" 😂😂😂

[@luisa.machado6595]

😂😂😂

[@MattMcConaha]

This guy is my favorite on the Computerphile channel. I think that the algorithms he talks about are the most interesting to me, and I've even coincidentally researched a lot of them on my own before seeing his videos. There are some other interesting algorithms for maze solving that I would recommend looking into if you are interested in this video.

which other interesting algorithms? i really like them

[@LucaDiCarlo-LDC]

Is there one where you would grid the maze as he has done in the video, but you just delete all nodes with only one connection that is not beginning or end of the maze over and over until the last node of this kind ? I was wondering about this algorithm while watching the video. Would it be performant ? (he may have used that in the video and I didn't understand everything, because of my english)

[@DatMilu2K]

Matt McConaha Yeah I like him too. Just after watching the Video about the "Slow Loris" attack, i implemented it myself in Delphi :D

do you like delphi?

[@DatMilu2K]

András Gyarmati Yeah, its very efficient in coding and running speed while being a lot easier than C++ ("power of C++, convinient like C#", i code(ed) in all three) but its a little bit outdated and too expensive which results in a very small community. I use it only for GUI applications on Windows, Linux and Android as there arent any modern libraries for 3D programming and many other things aswell as not having all the C/C++ compiling options for other platforms such as Arduino.

[@Hambrack]

Not a programmer myself, but one "improvement" I'd make is to treat every white square with 2 adjacent white squares "not a node", and make every other square a node. This because a turn is no different from a corridor. You can still only go one way.

[@en7998]

Just thought of that while watching and immediately thought that someone alse must have stumbled upon this. It becomes more apparent when you use an actual graph that doesnt use the grid, though. To extend on this idea, one could then use this graph and start deleting nodes with only one neighbor (that are not start or finish)

[@ericlee6029]

The idea is that given this maze structure that already is given to you in this "each square is a node" form, compressing the maze as you say would involve traveling through the entire maze once, which would be slower than just solving the maze in the first place. If you delete the node, you have to have the two next to it connect, etc. But yes, if we could store it as an adjacency matrix as you suggest, then it would be more efficient. This is more of a simplified version where we define connections as "touching squares" compared to adding an extra step of parsing out the entire maze to cut out nodes.

[@cerebralm]

"Each of these squares IS a square, and I'll hear nothing more said about it then that!" Non-Euclidean geometry I see :P

[@garychap8384]

All MY squares have three sides - more efficient.

[@startrek0336]

@@garychap8384 They're on spheres, right?

[@garychap8384]

@@startrek0336 of course... all the best squares are! ; )

[@vegardpig8634]

what does that mean lol

[@rinzhler6922]

Yeah it is a square cause there are only four orthogonal directions of movement in maze like the 4 edges of square

[@joshuasy10]

I just noticed the at the start and the at the end, very nice

[@nickwoodward819]

love how excited Mike looks when he gets asked, or says something nerdy. comes across as a great guy

[@KarlosSacramento]

1. open MS Paint 2. Load maze image 3. use "fill" tool 4. click 5. maze solved.

[@baronvonbasscat]

Sweet algorithm homie!

[@proxy1035]

honestly wondering how the fill algorithm works

[@AdoobII25]

It's as he described his initial solution at the beginning, the fill algorithm checks around the clicked pixel for neighbour pixels of the same colour values. You can't solve a maze using MS paint all the time because the main path will be branching which will result in a root-like path, and in a very large maze it would be hard to track the solution because paths might overlap.

[@deziograff]

That would only really show the areas where the user cannot access

[@ctbully]

This is why you arent a programmer

[@RikuJako]

*camera man gets bored* "So what was in tv?" ;)

[@burrytellam]

Riku Jako I thought he was expecting an answer like "The Crystal Maze".

[@Volvith]

"Something that doesn't require much attention and isn't complicated..." So, which of the Transformer movies was it? :)

[@josgeerink9434]

OOOOOH

[@BuggSmasher]

Terminator ?

[@eoghanbarry1432]

Mazerunner!

[@skyfog_]

I was really having a bad day, with really dark thoughts, when i decided to educate myself a little, to keep my mind busy from making those thoughts. I stumbled upon Computerphile channel and started to watch Dr. Pound's videos. Gotta admit that the way he is explaining things is so soothing. I actually calmed down a lot watching him explain image analysis and steganography. Thank you Dr. Pound. You are a great teacher and you also appear to be a great person as well.

[@heh2393]

Get well soon mate! A deep breath and a hug always help!

[@mantaz3068]

Hey mate, hope you're doing better! Both computerphile and numberphile are great channels. They bring us a entertaining education without making it superficial.

[@mastod0n1]

I hope you are doing even the slightest bit better because every step forward is a mile even if every step back is a foot. For me personally, Computerphile, Numberphile, Sixty Symbols, SciShow, SciShow Space, Minute Physics, vSauce, Tom Scott, Fermi Lab, PBS Eons, PBS Space Time, and other channels that I regret that I can't remember off the top of my head, have helped me process some of my mental health issues because they help me fall asleep while my brain wants to race off to dangerous places and I feel like I'm actually learning stuff.

[@igniteflow]

Mike would simply walk right through any interview. An Effortless, engaging and fun communicator. Great stuff

[@hellterminator]

Fun fact: You can use GIMP/Photoshop to solve mazes as long as the image is simple enough. The path through the maze splits the walls into two distinct parts, so all you have to do is use the fuzzy select tool/magic wand on any of the walls, create a new layer, expand the selection by a couple pixels (so it becomes continuous and covers part of the path between the walls), fill it in with some color, shrink it by couple pixels and delete it. You'll be left with a nice clear path going through the maze.

[@indjev99]

No. You could have walls not connected to the outside walls.

[@hellterminator]

indjev99 Alright, let me revise my previous statement: The maze is split in _at least_ two distinct parts. The method still works.

[@indjev99]

Yes.

[@RustyTube]

Where’s the fun in that?

[@omikronweapon]

you could also just take a pencil and draw it by hand. but the point of the video is to write a program to do it, and learn/practice writing code while doing it. So why would you use photoshop?

[@Sachin-at]

I m going to kill KZbin for not suggesting this channel to me years back

[@AureliusR]

Have you not seen the sister channels, Numberphile, Periodic Videos, Objectivity? You're welcome.

[@Jako1987]

"This guy seems very familiar.", "Oh yes I have subscribed to this channel."

[@WarrenGarabrandt]

Careful, KZbin will demonetize your comment for language like that. :)

[@anandsuralkar2947]

Dan

[@jadenmax679]

same

[@DontTalkShite]

Brilliant practical example that implements the techniques taught in his last couple of videos. Love this guys way of teaching.

[@youvebeensubbedto8009]

12:29 "I've got a very technical question for you." " :) "

[@vertxxyz]

I like the idea of pruning the graph when you reach a dead end (a node with 3 walls) as you create your graph.

[@digivince]

The default windows 10 app for viewing images is really shitty for viewing small images because it blurs the image in an attempt at removing jagged edges. If you use the older windows photo viewer program, you won't get that. It's still built into W10.

[@whuzzzup]

Just use IrfanView.

[@luckymouse1988]

digivince - Came here just to say this.

[@abcdefghilihgfedcba]

I personally use Honeyview… idk how it compares to others.

[@RealCadde]

"shitty" depends on what you are after. Viewing photographs like this is better than viewing them pixelated. It's called linear or bicubic interpolation and there are videos on those subjects on this channel. It's actually slower to view images in that way when zooming in. Or rather, more operations takes place. So if you really wanna be picky about it (which i will), Windows 10's viewer is BETTER than a viewer without the feature. The only thing that's missing is a switch to turn the effect on or off. One more thing. All that processing for interpolation takes place on the GPU anyways. So it doesn't run much slower than without the filter.

[@luckymouse1988]

You know what's also missing from the Windows 10 Photo's application? Proper levels of zoom. the Windows Photo Viewer is able to zoom in to a factor of 20, whereas the Photo's application is only able to zoom in to a factor of 4. Tested on a 10x10 red .png file, maximum zoom on Windows Photo Viewer yields a 200x200 red square, whereas the Photo's application yields a 40x40 red square. Aside from blurring things up, the Photo's application is inadequate when trying to display small images because it can't scale them past 400%. Unless I'm missing something, that is.

[@trankaz]

Really love the videos with Mike, he and tom scott is the reason i started watching computerphile

[@realGBx64]

I really like Tom Scott, I am just not convinced that he really has any experties in anything he's talking about :D

[@Omnifarious0]

Several people mentioned parts of the idea I'm about to mention, and I thought of them too when watching the video, but I don't think anybody's combined it all. So, it's obvious that squares that only have two adjacent white neighbors are pointless to have as nodes. But, as you're trying to track the node representation of the maze to the maze, nodes for any bend (even a bend you'd be forced to take anyway) are very useful. So, build the nodes the way he originally did. Then take a pass through them all and eliminate any nodes that have two connections to their neighbors. You replace each with an edge that has the weight of the two combined edges that used to lead to and from the node you're eliminating. This reduces memory use and greatly reduces the number of nodes you have to consider. You could also eliminate all nodes that have only one edge (except start and end) completely, but then you have to go to the node you connect to and see if you just eliminated enough edges that it only has one or two and so on. By then you're basically solving your maze.

[@Darticus42]

Eric Hopper it's much more efficient, yes, but it would probably make displaying the path difficult, since you lose info about where the corner was. Adding a separate x weight and y weight could do the trick, summing for the shortest path algorithms I like the idea of continuously pruning the tree of redundant nodes until you solve the maze though. I wonder if an algorithm exists for that yet (probably)

[@alfredwarnsater3099]

These kind of vidoes where Mike codes something and then talks about it and shares it with us are really educational and I hope to see more of this!

[@VincentVegas64]

I was given this task in school in 1980. At that time there were no graphics, we realized it with # in a text file, which had to be created manually. The task was not only to find a way, but the shortest way. The computer had an 8080 CPU or something similar. Operating system was EUMEL, programming language was ELAN, both developed in Germany. Later I thought things backwards and wrote a program that created mazes, since there was nothing like that before, as my teacher told me. Still later I developed probably the first 3D game in which you could run around in the maze and shoot a monster. You could also shoot through the walls. If you hit an outer wall, you lost. By switching to a different terminal after each move, the other people could see the player running through the maze from above - and make fun of him. The construction of the views was realized by loading text parts consisting of /, \ and #. Only the differences to the previous picture were loaded because the construction of a whole page with 80 x 24 characters took several seconds. By reloading only the changed parts, a fluid display was possible.

[@waasar]

I really enjoy playing around with this kind of little programs. Thanks for sharing this with us.

[@JonSebastianF]

LOL... the auto-subtitles at 1:24 _"so I thought to started by coming up with some rules that my maid have to follow"_

[@guitarloser07]

I like that you didn't include the code in your video as it could distract from the logic demonstration. What you've included in this video is the most fun part of programming (problem solving). Great fun in this one!

[@suvetar]

Still fascinating to watch, even in 2021! Thank you Computerphilers!

[@AnimilesYT]

15:43 almost at the start, where the red part is above the blue part it has a straight line going between them. So you're right, there is a silly little thing that could've made the path way shorter.

[@soupisfornoobs4081]

Thanks English caption author, for your humourous misinterpretations of what they were saying. Very useful for someone trying to actually use the captions to enjoy the video. All the hearing-impaired in the world are bowing down to you.

[@Benjamin-mj1ck]

From looking at them I would guess they were auto-generated. There are a lot of subtle mistakes which a human wouldn't make.

[@crooksandcrafts3262]

Yeah, this guy is the best at illustrating and explaining his concepts. I think the others make too many assumptions about the general knowledge of their viewers. That being said, I think even those who are computer scientists can enjoy these videos, which is why his approach is so refreshing.

[@bluegiant13]

My favourite episode on Computerphile so far!

[@timothymclean]

It strikes me that the nodes at corners are kind of redundant. I'm not sure how the code implementation works, but it seems like you'd only need nodes if the pixel had three or four possible exits. Though getting it to connect would probably be tricky... Maybe something could be set up after the initial node-net is created that makes a pathfinding node-net and "cleans up" those nodes? I'm not sure if that would result in a net computing profit, though.

[@SosirisTseng]

Probably he wants to keep the links straight for easier tracing.

[@ten.seconds]

It's not going to be that much slower, but if I want to get rid of this inefficiency, I would add two changes like this, then it would probably work: 1. If the pixel has 2 connections only, flag the corner during the object creation (In programming terms: I'll have CornerNode extend Node, or maybe I'll have a nodeType variable in the object, or even have some kind of "node in construction" object) 2. If we are trying to add a second connection to a node with the flag, the program deletes the node and merges the connection. (There'll be more than just 2 changes to the code (at least one more place, after a glance at the program), but the gist is these two)

[@Kartaal]

You could check the corner nodes and push the connections to the connected nodes. So A connects to B connects to C and B is a corner node. Just say that A connects to C and C connects to A in reverse. For step count and such, you could just use the one on C, possibly with a noted direction for colouring in the path and a check for "Oh, I hit a wall and this has to be a corner, take the other exit until next node"

[@KohuGaly]

probably not. To remove the corner nodes you have to iterate through all nodes once, then search for the path in this collapsed array. When you pathfind through the full array you are not bound to iterate through all of the nodes, so it should take less time.

[@AleBian1996]

You don't need those corner nodes at all, the computer could skip diagonally to the next one, he probably left them there 'cause the solution tracing system would be a pain otherwise... Or at least that's what I thought

[@MacoveiVlad]

At 14:14 i think he meant to say "2 million nodes" not "2 thousand nodes". Nice video!

[@9999rav]

Macovei Vlad I was going to write this :D

[@redbaron3555]

Unbelievable how much I like to listen to Dr. Mike Pound, super interesting and funny and so easy to understand. Thank you!!

[@soccer7901]

This is epic, Dr. Mike always has fun stuff to present.

[@GolembladeMC]

This captures the essence of programming perfectly

[@code-dredd]

Do a video on the fact that the SHA-1 cryptohashing algorithm got cracked recently by Google researchers.

[@z1k1c1321]

Coding something simple like that and seeing the result can be the most amazing feeling.

[@tendividedbysix4835]

Kind of makes you marvel how the IT guys manage to get the robots to open doors and stuff, if even programming the simple tiny maze concept was this complicated. Well done computer programmer folks, you're the bomb.

[@slipperynickels]

Semicolons in your Python code? Blasphemy, I say.

[@potatoonastick2239]

He's probably too used to C/C++

[@hiddencactus4855]

Or Java

[@mayube9292]

As a C#/JS/PHP programmer by trade, it took a while for me to get used to not using semicolons in python, and I still use them sometimes if I'm the only one who'll ever see the code (ie for quick scripts)

[@serenityrahn5656]

i use semicolons all the time to set variables etc... helps hold the line count down

[@oroville12345]

Ness is that you?

[@Toobula]

Mike, here is a fun one to solve that might get your interest: Imagine a game played on a grid. Player one starts in the center cell on the left side, player two in the right center.The players move alternately, each stepping from the square they are on to an adjacent square (up, down, left, right). Each time a player enters a square, it becomes "wall" in the sense of your mazes. Very simply, play continues until a player cannot move, in which case he loses. Is there an optimal strategy? Code it. This game is similar to "Light Cycle" but in fact was implemented a coin game well before Tron. I cannot remember the name, but it also allowed diagonal moves which were traced as two moves, one in the direction last traveled, followed by one to the side. You might want to code for that rule. (A nice feature was that the 16 directional moves - eight each player - were mapped to the notes of a lovely minor mode scale, so as you played, you were making up little fugues.)

[@HiddenLotus9]

Toobula sounds interesting, I'll have a go

[@boggers]

Check out the board game / mobile app Quoridor, not exactly the same as your idea (you can either move or place a wall anywhere each turn) but still a great game.

[@marlonmarcello]

Great fun video, I hope Dr. Mike keep up with the television/coding so we can have some more.

[@sabriath]

You can mark any dead-end nodes during the 1-pass algorithm in a separate list; afterward, you can go through this list and prune off all nodes connected to it that don't have multiple choices. This will reduce the amount of work for the search algorithm. What's neat about that is if multiple dead ends meet at an intersection, it doesn't matter what order they are pruned, the entire intersection will be reduced as well (in the 8x8 grid in the video, the entire bottom left part of the maze is cleared).

[@adhamuhajier]

Maybe do a video on SHA-1and its collision attack. Its successor SHA-2, its variations etc.

[@jpchevron]

And Tom Scott needs to do it.

[@Falcrist]

Motion seconded. All in favor say "Aye".

[@pablowestphalen]

Falcrist Aye

[@MiChAeLoKGB]

Yep, and I want him to also do the video about CloudBleed.

[@chicken6180]

Goodwine I think that the topic is complicated enough where it can be 2 parts, part 1: Intro to cryptography, asymmetric encryption, what are collisions, etc. P2 when Google explains is a dumbed down version of Google's method

[@ryanlapchynski1542]

You'd only need nodes on white spaces with more than 2 adjacent (not diagonal) white spaces. At any white space with 2 adjacent spaces, there's no decision to be made, and any with 1 adjacent space would be a dead end, and you wouldn't want to go there anyway.

[@vonkruel]

After finding a solution it may be a bit more work to trace the path, but that seems insignificant compared to all the cache misses as "extra" nodes are traversed over & over during the search. Actually in C++ (and C) you could store a 2-bit "direction" value in the lowest-order bits of a Node* because a Node* will always be at least 4-byte aligned. The direction says which way to go (up/down/left/right) in order to reach the connected node, so when you're tracing the path after finding a solution, you start out in that direction and then take _the only possible path_ from there to reach the connected node. Makes sense to me?? I'm a bit sleep-deprived though. _Yeah, never mind the direction data.. Since there's 3 or 4 connected nodes, just store the pointers in order by direction. I just need the UPS guy to show up and then I can sleep._

[@binarin]

Since he is drawing the result path he needs to know the positions of the corners it passed.

[@kelpsie]

True, but you can store the path between nodes as part of the connection, then use that to draw the final solution. It would increase memory overhead, but decrease solve time drastically on large mazes. Granted, memory overhead is probably more important. Another type of node that can be removed is one with only two UNIQUE connected neighbours, like the two nodes that make up the loop on the left of the sample maze. You'd have to do a bit of intermediary pathfinding to store the shorter path, though.

[@philrod1]

He talks about Dijkstra's algorithm, so he must store edge data somewhere (cost). You could also store the physical path on the edge, too. The corner nodes are redundant when turning the maze into a weighted graph.

[@keeyan2166]

Binarin I don't think it does. The path can easily be recreated after solving the maze by just following the white spaces between the 2 nodes that need to be connected.

[@chadestioco]

Incidentally, I am currently studying Jump Point Search. Got a bit excited when he mentioned making a graph out of the grid based on corridors as it is similar to one of the basic ideas behind JPS. Shame he did not go fully in to that.

[@lulairenoroub3869]

Every time he said depth first search, I thought he was saying breakfast search, and it was completely believable to me that it was just called that, and there was some plausibly interesting anecdote about why this particular algorithm had been given the name of breakfast search, to which I was simply not yet privy.

[@BrutalHellfire]

Great stuff Mike. But you can save some more nodes by rejection those which has exactly two open sides. You have given me a weekend project. Thanks 😊

[@Dusk-MTG]

After a day at work spent programming, Mike Pound gets home and "feels like doing some programming in front the TV". Damn man, that's some real passion over here.

[@theperson101ful]

Mike Pound is my favorite on Computerphile! Keep up the awesome videos :)

[@marcusk7855]

I implemented these at University(Depth. Breadth, A* search and Dijkstra's algorithm). The people that came up with them were very clever.

[@Booskop.]

Nice ghostcube!

[@fredwalker3765]

i'm currently working on a sokoban solver, you really should try it that's pretty interesting... if you're getting bored in front of your TV again, you can think about it

[@cgdilley]

Maze solving is really cool! I implemented something very similar this a number of years ago after I first learned about A*. I also had it render it processing in real-time, showing all the nodes it of the maze it had considered (if running on slow mode... could also tell it to just forgo rendering and just run as fast as possible to time it). Don't want to link videos in comments, but it's literally the only video on my channel, if anyone wants to take a look. It's super mesmerizing watching it work!

[@styleisaweapon]

The "left turn algorithm" is best described as "Run with your left hand on the wall" - back in the early days of robotic maze solvers this was the best possible algorithm because all decisions had to be local. It is only when gobs of memory was available that the bots could build a decent model of the maze while it was solving it and thus intelligently skip areas.

[@ScrapMek]

I can't wait to write my own! This is inspiring.

[@bamless95]

I did this as an assignment the fist year of university. I didn't create an explicit graph but treated the image as an implicit graph in wich every node was a pixel. This way i didn't have the need of storing extra informations, saving a lot of memory.

[@jasperh6618]

i love this guy, he's great to listen to

[@lasseibsen2942]

Strangely, this clip has entered the zone of "Series and episodes you put on when you just want something cozy on the 2. screen" - Must be the 10. time i watch it now

[@Hyuts]

4:28 lol that editing though.

[@benoitb.3679]

"One of the cool things about being able to program is, if you think 'ooh, I wonder if I can write something that will solve mazes?', you can then immediately go and do that." Truer words, never.

[@Rx7man]

It's really interesting to find the "gotchas" in what seems to be a simple problem to solve, and then find ways to work around them

[@x-seronis-x]

Never thought of doing a maze solver with nodes like this which makes me feel like i've overlooked such a beautiful solution for soo many years. But coming up with rules at a glance to determine if a given square needs to be a node or a path: S = square being analized A = square above S B = square below S L = square left of S R = square right of S Square state can either be Wall or Empty. Square type can be node or path if( A.state == B.state && L.state == R.state && A.state != L.state ) S.type = path else S.type = node Using this criteria you never have to care what the type (node/path) of any other square is when figuring out what the current one. Because all 'paths' are straight lines with walls on each side and the above two equalities and one difference proves this. Everything else is a node. Now we need to make connections between nodes. While examining each node on each of its 4 sides there will either immediately be a wall, immediately be another node, or be a path that leads to a node in that straight line direction. If we have each 'connection' object record the number of square until we reach the next node then we can not only find the path through the maze, but by comparing all connections we can also find the SHORTEST path through the maze quite quickly since we only look at the nodes and not every pixel of the maze.

[@SosirisTseng]

I was only able to solve the maze problem by recursion (or stack). This video is very helpful!

[@benjaminbrady2385]

You'll want to make sure the end is always a node in case there are no junctions between the start and end

[@frankmalenfant2828]

I probably means handling more nodes but I'd find if fun to get all possible solution by recursively removing dead end nodes until there is none.

[@9999rav]

Frank Malenfant you would be left with loops

[@spiritlevelup1036]

Look up pruning it is a real thing and is used to reduce memory overhead, it doesn't increase it

[@NoriMori1992]

The coloured maze solutions reminded me a lot of a clip in hackerdashery's "P vs NP" video that shows a graphic of a maze being solved by a computer. It looked a bit similar, but you could actually see it searching different paths.

[@samtukua4508]

I am so happy to know that the programmer I look up to chose, of all the programming interfaces, the same sublime text that I use.

[@Nickgowans]

as someone who's programming ability includes "hello world" and cnc machine centre programming, most of this video was "blablablablablablablablablabla" but I did find it incredibly fascinating :)

[@Rx7man]

I really ought to learn g code, but my lathe and milling machine are both digitally controlled in the older sense of the word.. Controlled with MY digits!

[@semnet3217]

3:01 ''each of this squares is a square and i will not say anything about it other than that'' Wow

[@ethanarrowood7454]

I found my new favorite channel on youtube.

[@tumvoodoo]

Really enjoyed this video. Thank you very much!

[@BIGWUNuvDbunch]

Delete all nodes with only 2 connections

[@iAmTheSquidThing]

You have to add weights to the connections then though. Because you're trying to find the shortest path.

[@BIGWUNuvDbunch]

nodes with only 2 connections are equivalent to a connection: i.e. you only have one choice of where to go

[@joshuamckinney2281]

Yeah but then it would be harder to color the maze after the fact with the path you would have to undo your deletions

[@Djorgal]

@@joshuamckinney2281 Yeah. Why not? Keep the initial graph with all the connections in memory, solve the maze using the simplified graph then map the solution onto the first graph to, then, draw it.

[@joshuamckinney2281]

@@Djorgal sure that would work. I guess you would just have to run it to see which tactic would save the most memory so that bigger mazes could be solved

[@TheScabbage]

You'll get 8 times more pixels if you stored it as a byte array instead of a boolean array, and used the individual bits.

[@Ludix147]

Scabbage does a single boolean value take up a whole byte?

[@pH7oslo]

Depends on the programming language, and then it's often implementation-defined (it's usually either 1 or 4 bytes in c/c++ for instance). AFAIK, in Python it's a sub-class of integer, which uses 24(!) bytes for its representation. However, given that there are only two possible boolean values, you use pointers to a static instance of either true or false. Which takes up either 4 or 8 bytes of memory, for 32bit and 64bit respectively (the platform-specific size of a pointer). There are ways to get Python to store bools as bytes, or even in bit-maps, but unless you're actively taking advantage of these representations chances are it will just slow down your code.

[@TheScabbage]

+Ludix147 The smallest addressable memory size on modern hardware is one byte, unless you're working with some incredibly small, unconventional and basic hardware. Typically no one worries about it in most cases because memory capacity per dollar has gotten so large, but if he's having memory issues it'd be better to store all his bits in a byte array and use bit masks to address individual bits (at the cost of a small performance hit like +pH7oslo said) instead.

[@hellterminator]

+pH7oslo Actually in C/C++ bool is a typecast of char, so it is 1 byte (of course depending on aligning on stack or in structures, the following 1 to 7 bytes might be unused). If you make an array of bools, it will be 1 byte per bool, _however_ vector has a template specialization for bool that actually uses a bitfield, so you only use 1 bit per bool.

[@AureliusR]

Yes, but in C it's also very easy to specify the number of bits you want a variable to use.

[@axelBr1]

Just came across this channel; can't believe that, that printer paper is still available!

[@TheDXPower]

I love the ghost cube in the background. :D

[@petarmilic9729]

clearing deadend nodes would save memory but increase time i presume?

[@PongoXBongo]

Climb the wall, and walk on top of the walls to the nearest edge. ;)

[@SteveLEKORodrigue]

Really liked your video. I would have liked to see the SPF bad path tree on the maze. Seeing all the paths it considered but discarded.

[@koz_iorus1954]

I really like that the animations are slightly in 3D

[@bpark10001]

What happens to your algorithm is a corridor is more then 1 pixel wide? Say there was a 50 x 50 white square in the middle of the maze?

[@9999rav]

Brian Park it would probably create new node on every pixel

[@Droobilicious]

Nodes with only only 2 connections should be eliminated for the solution calculation

[@charlieangkor8649]

calculate the solution with a GAXIO calculator.

[@rabidbigdog]

When I was a lad (ha!) we used to use Z80s with 1KB ram and a wheeled maze robot, mine were made of Mecano and have competitions in a built box maze.

[@shikhanshu]

this was so much fun to watch!

[@Pfaeff]

Why not use a proper image viewing program?

[@NightHawker258]

memory issues ;)

[@imveryangryitsnotbutter]

What if you made an algorithm that tries to solve the maze beginning from the entrance and exit simultaneously? In one step, it tests a node from the entrance path, and in the next step, it tests a node from the exit path, and it continues alternating in this way until the two paths meet in the middle somewhere. Also, each time the algorithm deduces that a node is definitely on the correct path, it updates the destination node for the other path. So the two paths are not each searching for their corresponding entrances, but rather each aiming for the head of the other path. This would be useful in a maze with a start and exit at the top, connected by a very long U-path that touches the bottom. Initially the pathfinding will stumble as they try to cut directly sideways, but as the heads of the confirmed paths move ever downward, they'll start aiming towards the bottom more and more, where they'll eventually meet and complete the solution.

[@the_brutal_king4314]

This is a viable solution, but requires more memory. You also have to check when both sides have met.

[@yngve1993]

You mentioned python not being quick, but have you tested out cython? Profile your code, find bottlenecks, write that in cython, have it translated into C, compile and import it into python as if it was python code. Absolutely amazing!

[@TheCandoRailfan]

This video inspired me to make a program in the BASIC language QB64, where you can create mazes using text (either manually or by the computer) save them, and have the computer solve them. It doesn't do the quickest possible route, unless it does by luck or there's only 1 route, it just wanders randomly, never repeating the same spot twice, and when there are no possible moves, it will go to previous curves or intersections until there is a move. My code probably isn't great, and probably could be better, but it works. The maximum size is 80 * 55, including edge.

[@philrod1]

This was OK, but *generating* mazes is *way* more fun. I know, because I did it. I wrote three different maze generation algorithms (should have been 4, but I never did get Eller's algorithm to work) and a bunch of solvers (A* being best, naturally). The rules for a perfect maze are that there must be one, and only one, path between any two points in the maze (using the same up, down, left, right grid system as i the video). I'm actually tempted to make a video about it myself; I already have the code, and it is animated so you can watch it work.

[@serenityrahn5656]

if you already have the code and the animation, you should upload and show/teach us!

[@joeytje50]

please don't do the stretching of the video to "make it look better..." I'd much rather just stretch it in my head, with the original image. If you want it to be clear, use the animation, if you want to show his fingers, show a regular view like 8:48 or something. The stretched thing really makes me a bit dizzy.

[@philiptkd1]

joeytje50 +

[@Sir_ClickALot]

It took a little effort to ignore the distorted hand but after I managed that I really think the 'corrected' image looked fine and helped to show what he was actually pointing at. If it's something that really does bother a lot of people then I'd suggest animating that part of the video as well, but it's a lot of extra effort and personally I like this solution. For me at least it's better than having to do a perspective transformation in my head, way more annoying.

[@BlakeJPhoenix]

Unnecessary nitpick

[@aNaGrMa]

Great video. And amazing to find a comment section spewing with constructive criticism instead of hate.

[@stevensexton5801]

Your library is missing 'The C Programming Language' by Brian W. Kernighan and 'Code Complete: A Practical Handbook of Software Construction' by Steve McConnell

[@atrumluminarium]

So we have algorithms that solve mazes... What about algorithms that create them? By create I mean the output should be solvable (preferably uniquely).

[@Theasstasticvillain]

I think he used a program to output those huge ones, I doubt he made a 6k by 6k pixel maze :S

[@atrumluminarium]

Eli Tzar It would be nice if they show it some time

[@moilui1664]

that's the only thing i was thinking about during this video, thanks for not making me feel alone lol

[@atrumluminarium]

Moi Lui you're welcome :D

[@T0ly113]

Look up maze generation algorithms on Wikipedia. There's at least one really simple one to recreate and maybe learn a thing or two!

[@kevnar]

I once coded a maze in PERL that was a million squares by a million, and then I got the algorithm to solve it. It found the exit. The only trouble was, the maze was so big, I had to just take the program's word for it. I couldn't actually display it on screen. I knew it worked, though because I began with a 10x10 maze and drew it in ascii characters, with the solution. But when I upped it to 1,000,000 x 1,000,000, I just had to turn the drawing function off.

[@beanthemachine3675]

You know that even if each square is just 1 byte, a maze that big would take up an entire terabyte of memory? I'm curious how you supposedly went about handling that

[@iIiWARHEADiIi]

@@beanthemachine3675 most probaly vector lines. They contain start and end points only

[@milan.stankovic]

Please do more videos like this !!!

[@pitronetor]

thanks for the code, last year I did something similar! when I have time I will compare mine to yours. cheers!

[@jeffreyblack666]

The first maze you used wasn't a perfect maze. It had 3 possible solutions, 1 of which is shorter than the other 2 which are equal. Is there a reason you didn't simplify the nodes further (even as an intermediate structure) where if a node is just connected to 2 other nodes you remove it and link those 2 nodes directly; rather than just doing that when the nodes are collinear? That simplification could also remove nodes which only connect to one other node, and it could all be done in the first simplification if it keeps track of connections rather than just making them. Also, if you are using nodes, you aren't finding the shortest path but the "simplest". A simple example of that would be a maze where you enter top left and exit bottom left. The simplest path could be a loop around the outside, while the shortest could be a zigzag along the left 2 columns.

[@HauppiLP]

420 views. nice.

[@442277100]

Hannes Hauptmann nice meme

[@notfavoritemartian]

On 5:30 I thought I was watching The Office beaucse the way the camara zooms in. Great video, helped a lot!

[@Ceelvain]

I did something like this in the end of 2015. Except it was written in D, made to handle photos, and you could draw on it to add walls. I was also very focused on the performance.

[@MazeFrame]

You rang? Not that I actually solve mazes, just the name.

[@justinward3679]

Well, I guess we can run the algorithm on you.

[@silicalnz]

Kinky

[@myntdragon9578]

....

[@josgeerink9434]

Edited?

[@omikronweapon]

how did this get 127+ likes? just for having the keyword in his username...

[@Nyhilo]

Looks like he codes in SublimeText :)

[@blueghost3649]

Yep

[@douglasmennella4525]

One optimization is to run a second pass over the graph removing nodes which only have two edges connected to them since they're not actual choice points. A third pass could remove multiple edges between the same two nodes (and/or don't add them in the first place.)

[@Eikenhorst]

I like the algorithm for turning the grid into a graph. I would probably do another few passes to remove nodes on this graph that have only 1 or 2 edges connecting to that node. If it has only 1 edge connected (and not start or end) it is a death end, so remove. If it has only 2 edges, it can be removed as there is no decision to be made at this node. This graph simplification can be done extremely fast and hugely simplifies the graph