Maze Solving - Computerphile

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

😂😂😂

[@joshuasy10]

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

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

[@nickwoodward819]

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

[@igniteflow]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[@nine.ties6]

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

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

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

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

[@z1k1c1321]

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

[@GolembladeMC]

This captures the essence of programming perfectly

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

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

[@DontTalkShite]

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

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

[@code-dredd]

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

[@suvetar]

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

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

[@marcusk7855]

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

[@waasar]

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

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

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

[@axelBr1]

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

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

[@7th_CAV_Trooper]

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

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

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

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

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

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

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

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

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

[@ScrapMek]

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

[@bluegiant13]

My favourite episode on Computerphile so far!

[@benjaminbrady2385]

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

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

[@Booskop.]

Nice ghostcube!

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

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

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

[@semnet3217]

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

[@antonw6455]

This is a great way to get people to start thinking about the difficulties of searching! You may want to revisit how the problem was solved by introducing the limitation of visibility. Specifically, as an individual at the start, you can't see the entire maze at one time, you can only see and gather information about the immediately adjacent corridors. Maybe a problem for extra credit?

[@Ghorda9]

Look up A* (A star)

[@Hyuts]

4:28 lol that editing though.

[@kefler187]

I play a game where I needed to solve a max maze size of 12x12 cells but to explore the nodes, you have to actually move to them so I didn't have the luxury of just relying on code jumps to do a breadth first search, A * or any any algo that sequentially expand nodes between possible potential depths/paths. I settled on a depth first search because... well it's the easiest to code when you physically have to move through a maze and minimized the travel distance thus time to solve. For those that don't follow, in any sort of flood fill style algorithm such as A * or breadth first(even with a weighted graph to a lesser extent) for mazes you have to physically traverse to check the node, you end up with an n**(length of path)-1? movement for every possible path up to the shortest path distance through the maze if we're talking breadth first search, less for A * because A * won't check each potential path to it's depth upto the point it finds the exit/goal in one of the paths. Make no mistake, everything Dr. Mike has said in the video about the algorithms is true, if you're solving a maze programmatically(which he clearly states). Things only change if you have to physically traverse the maze to do them.

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

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

[@petarmilic9729]

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

[@sdmarlow3926]

You are going across a line at a time, but still looking at the rows above and below, AND, something you did not explain, but surely implemented, was to take the idea of a white pixel after a black one as being the start of a row, also being tested to see if it might be the start of a column. It's the only way to explain how there was no node at 1,2 (0,0 as traditional upper left) because it was part of the column above, rather than a new row. It also explains how you get 1,7 and 3,7 and 8,7 as the start of columns since they were not classified as the start of new rows. It should be stated that having access to the entire map at once is a bit of a cheat.

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

[@ethanarrowood7454]

I found my new favorite channel on youtube.

[@Pfaeff]

Why not use a proper image viewing program?

[@NightHawker258]

memory issues ;)

[@redbaron3555]

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

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

[@soccer7901]

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

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

[@CattleRustlerOCN]

At 12:37 my question would be why is there no real-time graphical representation running on screen for this. I might try this in Javascript using real 2d objects and collision for the player object to feel and figure its way out based on it knowing where its been and being able to back track its way out of dead ends

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

[@destrierofdark_]

If this chooses the shortest path by node count, I see a *huge* problem with this from the get go. In the first maze, if there was a clear path along one wall, that would be five nodes in length, but the actual distance covered is larger than the nine step route that was actually demonstrated. So, if each node stores the distance to the next node (or a -1 if it is not yet connected), not only are you more thoroughly (and accurately) looking for the shortest path, you open yourself up to optimizations and not actually requiring a scan of the black squares, thus potentially resulting in a faster algorithm also.

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

[@williambillemeyling5647]

I am no expert, but from an algorithmic standpoint the time complexity and space complexity of the algorithm used will always have a minimum boundary of O(N*M) since the image has to be loaded into memory in the first place, where N and M are the dimensions of the image, which is also the complexity of BFS and DFS. Now dijkstra and A* on the other hand would run O(N*M*log(N*M)) on the raw image and O(T * log(T)) on your compressed maze (with nodes), where T is the number of nodes. However T might potentially be equal the the number of non-wall pixels and therefore the big-O time complexity, O(T * log(T)) is worse than O(N*M). Nevertheless a very interesting approach with the graph build :)

[@Droobilicious]

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

[@charlieangkor8649]

calculate the solution with a GAXIO calculator.

[@FBuilding]

I don't know why but this thumbnail just does it for me 👑

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

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

[@PongoXBongo]

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

[@SamvitAgarwal]

Wouldn't it not make sense to use Djikstra's or A* for a perfect maze, since only one possible path exists? In that case, wouldn't something like DFS or BFS give you a solution faster?

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

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

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

[@eatbolt42]

This guy is easily the best presenter.

[@Nyhilo]

Looks like he codes in SublimeText :)

[@blueghost3649]

Yep

[@aNaGrMa]

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

[@hanneshauptmann]

420 views. nice.

[@442277100]

Hannes Hauptmann nice meme

[@trevdawg9182able]

You dont have to create nodes at every corner, just as the ones that have 1 or >=3 white squares around it. I understand you did this so you can know whether its in "line of sight" with another node, though. You can keep your method, but then iterate through and remove nodes that are connected to 2 nodes, and connect the pair it is chaining together

[@RobertT1999]

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.

[@gasquakestudios]

Robert Tucker - (shadykillar123) What was the point of this comment? Haha

[@RobertT1999]

I just thought someone might have a little interest in what I was saying but I guess I was wrong.

[@gasquakestudios]

Robert Tucker - (shadykillar123) It's cool dude, if I'm being honest I'm just a little "salty" over not being in college yet to have more time to do what I love.

[@RobertT1999]

+gasquakee That's weird. I actually read your comment thinking that you didn't like to read that I was studying something you wanted to. Don't worry, I understand why you feel like this. When you are in college, it'll be great. Just think, you will be enjoying yourself doing something that I won't be doing in a few months time because I will have finished A level by then. I wish I could go back to the same position you are in and do it all over again. I hope whatever the reason for you not being in college goes away soon so you can actually do what you love.

[@gasquakestudios]

Robert Tucker - (shadykillar123) Finishing highschool is the barrier! So how was your experience of college; do you feel you're leaving with a better mind?

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

[@dyld921]

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

[@alandouglas2789]

Dylan Dang wtf? lol

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

[@gchinmayvarma9030]

Wtf just use the paint bucket tool

[@MumboJ]

I wonder if the node graph could be simplified by removing corners. Technically a corner is not a decision, at least no more than a corridor. You just keep following the path until you reach a junction. Mechanically speaking, in this case a junction would be defined as a pixel with 3 or 4 adjacent white spaces. The nodes are simply the junctions plus the start and end points. It does lessen the connection to the visual display, but I don't know if that's a deal breaker. It might well be, in which case nevermind. But if possible it would significantly reduce the number of nodes and therefore the amount of space the graph takes up.