Maze Solving - Computerphile

try a little bit different today after we did the video on Dykstra I thought well you know sometimes I like to go home and sometimes do a bit of programming in front of the TV you know the person I am and one of the cool things that you about being other program is if you think all i wonder if i could write something that would solve mazes you can immediately go and actually do that that thing so that's what we're doing today I've come over a bit of a part of a small program not very complicated that fold mazes that you give it an image for you get amazed it worked his way through it and then output say the same picture made from red line on it is very exciting and but I've also actually implemented lot of different search approaches so I didn't go into depth and breadth first search and a star and Dykstra want to see the actual code those things then we'll make it available so other people can follow along tweak it maybe improve on what I've done it comes back down to date well for the implementation video doesn't it because there are so many ways you can program something that solves an image-based maze and how I've done it is okay it probably isn't the optimal I I had in mind i wanted to do really big mazes in fifteen thousand pixels by 15,000 pixel maybe bigger about around now so I can't go any bigger than that but so i'd love you to be most semi efficient at the very least you know not completely impractical and so I thought to started by coming up with some rules that my maid have to follow because yeah okay so I could I could give it any maze any picture made a photograph of amazed but then most of the time i'm going to be doing is now just trying to turn that into a structure in memory and that's what a job right you want to be there I mean yeah yeah and i'm just doing it in front of the TV you know I get carried away so what I said was I have a black and white pixel image that hopefully doesn't have jpeg compression on it because activex everything is a blackboard all the way around the outside that the wall and then any black pixels wall anyway pixels path and their intention to the top and an expert at the bottom that that was my boat my rules I almost the other boot made it don't follow the rules are going to work in myself where you can follow me to extend myself with how they're closed amazed if you want I've got a very small image here called tiny dot PNG which you can't see because windows does not like to expand these qualifies of images what you don't do is give it the 50,000 50,000 image first go because if you have any kind of problem you've no idea what we want my baby started a small image you can actually sort of debug what's going on in the code you could say well I was expecting this to happen and it didn't which means i made a mistake or something like this to start with a small cases and then work your way up to the bigger think hopefully once you've got to add overbust album that work for small limited on the mazes just get a big amazing should figure cross work first time we should think so i've taught amazed right that took ages to draw in video it but you know just giving all this in a little bit wayward here but you know each of these square in a square and I had enough nothing like that about it than that so my walls are that the outside is black apart from the top has one picture of light which is the entrance and the bottom have one picture of which is the exit those are my rules that have come up with now I said there are loads of ways we could solve that maze programmatically perhaps the first one I did and it's so in the most obvious one is just to put it into memory and then kind of freak pixel look at the neighbors and see if we can go there and then move there and if maybe we can go a bit further and so on so that with my credit first trial implementation what I did was like I copied it into memory or storage array and then I say that's my start position at not 123 naught but and I said we'll look where can I go from free not well well the left pixel to know is is black the color there and the next pixel across for North is black longer there but this one isn't this 31 is white so i'll go there and I'll continue my search from there and I think the same for the blue car looked at look left look like process and every pixel like this is basically a flat field but it's nothing smart about this and it does work in the sense that it will get into the end is loaded very quickly you have to have a small but says which nodes have been visited if you otherwise you're just going to go up and down up and down up and down up and down it and get yourself into a loop or here we got an actual loop we want to go around and mailed if we don't have any idea about where we've been so i created another a variety of the exact same size as this which was a true-or-false of a foodie the right and just if you've been visited you get that true and will ever go back there but because by definition we don't want to go backwards glue come from right but what if you get go to a dentist partially so the data structure that i'm using to do this breadth first search is it's one that keep a bit about our box to approach in our previous video keeps retractable windows that currently under consideration but haven't been invented yet so you know if it's been looking down here have this one and maybe this one maybe this one and when it gets to the end here we'll just go out and work out a little fall back to this one so it highly inherently allows itself to backtrack and if I love doing it as you said that as you sort of suggested which was I just kind of followed blindly then i'm going to be doing a lot of backtracking now I had actually implemented version of that was much aware that of life left turn version as well good luck Hardaway and implement a few different approaches the problem with what i did here by which is why i'm not showing the code of this particular version is that it's a beneficent like it's it's not massively inefficient in memory because the right don't take up a huge amount we even for a really big image you know you know we love these kind of images when we take high-resolution photographs and things so it's not inconceivable that you have that amount of memory the issue more is that over made of that kind of Sighs the amount of nose under consideration start to grow really quite rapidly that put the memory and computational overhead that we don't want and also if I'm walking down this path here let's say and I'm here like I can't let the right here called left or right here I called left to right here and I'm spending a lot of time going to this one adding it to the queue to this one and then and going down here i'm taking one two three four steps when we really want that with a surprise now spit at people interview at some point I'm going to have to travel down there but I don't want to store that information in memory just seems a bit inefficient so what i did was i wrote a a one-pass which means one look over the image out with them to turn this maze into a graph like that one too dr. video i have no idea is the optimal album for this probably not but it was not going to work and it extends quite reasonably two large mazes as well let's have a quick look at how that works let's go with our green pen if we do one part of them what we have to do is make all the decisions we want to make by just cutting process throughout medical office was and then across thrown across the rope and you could do it column wise but for the sake of argument I've got that the most obvious thing is once we get to the start we can slide that the start and that's good right so the first low we simply move along until we get to start and we create a node in that position that my note little have a little object in memory stored it and it will store any of these connections 20 neighbors but it can so that's RS in the dark shades RS yes but in in my implementation decision to somewhere in the array this is an actual tangible object in memory that has a north east and west connection that could have something connected to it in this case is not gonna have a lot of connection because you know not going to go anywhere so for the next row i came up with a number of rules that depending on whether you're looking at war on the flat part you do different things right so the first one for example is if you're on a wall don't do anything but you can't right now there you can't connect and he knows to that point it doesn't make any sense right so if you're on a wall but you do nothing right and it's reflected in the code if you're on a path and you were on a wall that means you want to start something new so we should create a node but it start to get a little bit confusing but I can basically I can't with different rules so in this one we talked their dad we can't go up we were already on the path that we do nothing this one we've got something about that we can connect to so we create a node here and we join them up and we've just created a note so we join them up like we know which is literally created on the left so we're tracking the ones above the ones to the left and we're going this way down always so microsoft way can I take a break in motion TV and then I come back the next day and and i'm going to ok so now but this node this goes into anything this doesn't do anything because awful down to glow decision to be made at this node is no point we make anything in memory for here here this is an obvious junction we can go down to this point so we created those and we connected back to the one we last saw on the left and then again we get to this one we're just in front of a wall at the end of the corridor that's so exciting we create a node and rejoined out by this now there's a few statements involved in that what you saw in your line think about the steps you have to take that each given position and what's going on at that position doesn't take very long to come up the steps you know if there is a war on the left is all the like is there a passel of those are the things we basically have to check and they will involve referencing the image and saying is it was all that pixel and the next one below by this one doesn't left her life so it's a path going downwards and don't do anything on this one alright this one the same this on the side on the next row this one is a junction so we created knows we connected to the last one is all about it which I stored in the list incidentally for those of you following along with my coach so we get to before mrs. that this is the end of the corridor we connect that in here we start one here because that's the beginning of a corridor end of the corridor connect them up this one take no action and you get the idea over time we start to fill in wherever there's an interesting junction anything to be done you see that this and we propagate this through until eventually we finish off our graph this unit I will actually finish it off because i went to all the trouble of doing out there we are but now it's my algorithm is correct all of these notes should exactly reflect are made and what we've got it insulated increase memory because these loads a slightly bigger objects in the underlying away which is just small numbers but we have to take many fewer steps to go across this late you know the step counts from here to here is one instead of 3 and so on and depending on the length of your corridors in your maze you can imagine that drastically decrease the number of nodes you have to be expanding into and so they want to did was I said well okay so i put this in the maze class so i go to class and object in memory that stores this maze have a start it happened and then I started writing other classes that their only task is to go to later be so i did that first search which expands all of them one after another remember next and the next and the flood fill that first search with his fans as far as to count one direction and then the next election and so on and then left her lonely which is where you with her less and you get stopped all the time and it with her left but it's a closed famous made solving album because if you're human and you can't see the whole maze it was quite well and then I also implemented Dykstra in a style as well so we'll see if it works so that's one of the command prompt soap in an ideal world I would have a name of the file read in from a command line parameters like I do actually have to do that apartment was a bit lazy and I hard-coded it so at the moment it was tiny dot PNG could have told me to and that's the only made it done so Python so dot pie there we are and so it creates the image didn't take long with this is not a big maze in fact it took no second to solve made it only got 23 knows let's see if that's true 123456789 10 12 14 efficient any more than 20 22 23 1 quite pleased actually because I could have been really embarrassing but it's that pile of debugging that I was doing early on and getting funny amount of nose and you think we're done wrong okay i must have not connected these popular something I've got a very technical question for you what was entirely while all this was going to wasn't le oh yeah good point arm something like that to cultural too hard it's got detailed plot is difficult for me to also do this community one thing that one it took six 10,000 for a second i think that is some fraction of a second to to actually find the path explored lighting know that means it looked at mind impossible cabin nodes and eventually found a path that would have length 94 here and if we look at the image which again it difficult to do on this screen so using the magic of editing this will now appear very large and extremely positive rather than that which has also been linearly interpolated which is exactly what I didn't want to happen on this pc my previous video on linear interpolation so I thought a pass in from glutamate which represents the start to the end let's see if we can do something a little bit more challenging like so here i have a 2000 by 2000 image which when you load up on my screen looks like a my patent now i use the program with Daedalus to generate this and you can generate very large mazes I'm taking it in some way on faith that there is a bachelor star island could you know it doesn't make a slightly different life program so i had to go in and start the end by partnumber why did on this one and so on so let's see if it work so this is called 2000rpm gee that's a hard-coded change right on that and it will take a little bit longer to creative ways maybe get coffee there we go light so it took a second to create the maid and it had 760,000 node now when you consider that amazing with two thousand pixels by 2000 pixels which is four million pixels and let's say half of them white on average then you would expect about 2,000 loads if you were doing it the bad way how about I try to save some money this way it's essentially what i'm doing it and then the actual the actual worm was it that further breadth-first search everyone i was breadth-first apparently punch my code it takes 15 seconds not no longer to get through that made and again using wizardry I will resume in on this and you can see it has found a path through so it looks like a general arcing path but if we zoom in you can see it's actually finding its way from quite complicated maze the last in class is that the two major i just put in that's open perfect mazes that means there's only one possible solution everything else is by definition a dead end now somebody's are like that like if you were to think of the Manhattan Bridge systems amazed then in some ways there's a lot of different parties could take and really what you want to do is find the shortest one tomato got here has multiple solutions to it and so for example if I want a depth-first search on it it will be going down the first part fine as far as possible and it may well not take the shortest path because it would just go down as part of our two cans and that part might lead to the exit it just might be very long so if i change my algorithm to this image and then get first right and we run it okay he didn't take long 6300 knows a hundredth of a second to actually calculate it but it found all kinds of super group through my mace and so calm down here and then up here again and back down here now the chances i probably just jumped across here or something silly it just didn't occur to in some sense because it was falling apart was on I mean they're searching better associated is two different problems like depending on the northern knows you want to expand but in this case suboptimal it would be the site is not not the optimal algorithm to use so I've also implemented better search and a star and Isis dices shortest path and so on if I turn turn it into Dykstra has a bit of overhead because you've got to set up your quality q which i'm using Fibonacci heat do that because if not he also in the code that reprogram yourself so if we run this so the path length that debt first found with a fountain world and the parkland dr establish will be the shortest path is 897 long they've been taking a bit longer to do it just could have many overhead mostly there we go about the actual shortest path through that maze which is significantly better than the last one yeah get download the code have a play around see if you couldn't work out what I've done and what I shouldn't have done that maybe you can fix it and then come up with a live album if you want to try to work your way through to make and depend on how much rather you have you can see what kind of that size have made it will handle and we look forward to seeing some more pictures yes but partner isn't as fast as doing this in depth they see something like that but it's not too bad and absolute speed is not important for this because i was just looking for fun and deceive see you know with work right so you know if you want to be implemented in a park language is not the point arithmetic and so on been you know go for it but

Channel: Computerphile

Views: 1,008,879

Rating: 4.9460483 out of 5

Keywords: computers, computerphile, computer, science, Dr Mike Pound, University of Nottingham, Path Finding, Maze Solving, Search Algorithms, Dijkstra, Computer Science

Id: rop0W4QDOUI

Length: 17min 14sec (1034 seconds)

Published: Fri Feb 24 2017

Reddit Comments

[u/Leadstripes]

Would it not only be necessary to create nodes on intersections and not on corners?

[u/adi1133]

Your username is too similar, this is awkward.

[u/_aidan]

Of course he wrote it in Python...