Maze Solving - Computerphile 

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

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.

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.

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

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

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.

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

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

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

I m going to kill RU-vid for not suggesting this channel to me years back

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

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

<a href="#" class="seekto" data-time="749">12:29</a> "I've got a very technical question for you." " :) "

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.

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.

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

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.

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

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!

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

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

LOL... the auto-subtitles at <a href="#" class="seekto" data-time="84">1:24</a> _"so I thought to started by coming up with some rules that my maid have to follow"_

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

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

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.

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.

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!

At <a href="#" class="seekto" data-time="854">14:14</a> i think he meant to say "2 million nodes" not "2 thousand nodes". Nice video!

This captures the essence of programming perfectly

Semicolons in your Python code? Blasphemy, I say.

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.

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.

<a href="#" class="seekto" data-time="943">15:43</a> 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.

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.

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

My favourite episode on Computerphile so far!

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.

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

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

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.

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

Nice ghostcube!

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

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

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 😊

<a href="#" class="seekto" data-time="268">4:28</a> lol that editing though.

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

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.

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.

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

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.

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).

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.)

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 :)

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

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

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

Delete all nodes with only 2 connections

I found my new favorite channel on youtube.

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.

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.

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.

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

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!

<a href="#" class="seekto" data-time="181">3:01</a> ''each of this squares is a square and i will not say anything about it other than that'' Wow

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

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

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.

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?

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 <a href="#" class="seekto" data-time="528">8:48</a> or something. The stretched thing really makes me a bit dizzy.

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.

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

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

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.

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.

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.

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

Why not use a proper image viewing program?

I love the ghost cube in the background. :D

"it'll take longer" and then a youtube ad kicks off. lol

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.

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

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

When computing straight paths, you could collapse bent corridors into a straight path as well. So would it be an advantage to treat nodes with 2 edges as paths as well, instead of only 2-edge nodes where the edges are opposite?

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.

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.

I really like that the animations are slightly in 3D

Please do more videos like this !!!

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

420 views. nice.

Really enjoyed this video. Thank you very much!

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

Looks like he codes in SublimeText :)

I love this channel. Being an A level Computer Science student, just looking at the title allowed me to know that this video was about algorithm searching. Personally, I would create a boolean data type 2D array with the X and Y indexes being the same as the X and Y pixels of the image. I would scan each pixel of the image and if the pixel was white, it would assign true to the index in the array that is the same as the pixel position. That is probably the only thing I would do differently but I haven't actually thought about the rest of it. Too busy revising for my Computer Science PPEs next week.

On <a href="#" class="seekto" data-time="330">5:30</a> I thought I was watching The Office beaucse the way the camara zooms in. Great video, helped a lot!

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.

Dr. Pound is seriously attractive. I wonder if he's ever had any sexual innuendos made about his name.

Wtf just use the paint bucket tool

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.

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!