Python Breadth First Search Maze solving program

this is a demonstration of a maze solving program using the breadth first search algorithm this is one of the more effective algorithms because it searches all the paths at the same time unlike the depth-first search whose only searches one path our time once he has identified all the cells in the maze it will start up backtrack using the most efficient route as you can see here okay so what is breadth first search well if I just close the program and rerun it but this time a slightly slower speed might give you an idea of how it how it actually works so programs constructing the maze at the moment so we're gonna do this is responses starting musician it all start to search to the right up and down so every branch it binds he creates another path and does another search so he got maybe four five six searches going on maybe seven eight now no caring like that every tight sees a branch it will split and start to search that branch of same time as it searches all the others this makes it a very very efficient algorithm when it gets back to this spot here this purple spot will use the most effective route back to the red spot which I think will see the starting position there we go yep so before I run through the program I thought it might be a good idea if I just show you the algorithm that I use to create this program the program uses written in Python Python 3 so I've got this little PowerPoint presentation that I'll explain how the break first search algorithm works so I've got it's a little grid here a very minute very mini maze so you've really got three or four branches and I'm using two lists a frontier list and a visited list to store the information and a variable called content in fact there is actually another list called solution Bala come under that in a minute that creates the backtracking to find the actual solution but for this part I'm gonna concentrate on two lists the frontier list and the visited list and the variable current so let's start top here place starts in the frontier where I'm going to use my starting position as number one so therefore I'm going to place starts in the frontier list I place one in there then I move down to is the frontier empty well now I've just put something in it so the frontier isn't empty so I come across to this site here set the current cell to be the frontier so the current cell at the moment is empty so I need to be set to the same variables as in frontier so it's one and come down here and he says move to the frontier so it's here so I'll highlight that in red so we can keep track right move down it's the cell to the left visited in the visited list or a wall will sell to left this here so it's in the wall okay so come down to the next part the algorithm is the cell to the right in the visited list or in a wall or this is the cell so I write certainly not in a war but it's not in a visited list either so therefore I move across to this branch here place the cell in the frontier cube so I placed a cell this cell number 2 into the frontier Q so in frontier now has two items in it cell one and cell su now move back it's a cell up in the visited list or a wall so the cell up so you set up is in it is in a wall and a cell down is in a wall so ignore that ignore that and I place the current cell in the visitors list so number one goes in the visited lists now I have to DQ the frontier which basically means I have to remove the first entry in the frontier list in Python that's called pop left I then move back around the loop again is the frontier lists empty no frontiers could have got something in it so put the current cell in a frontier list so the current cell is one it now needs to be two and I move to the frontier so highlight that in red is the cell to the left in visited list or a wall a cell to the left is this one here and it is in a visted list so I moved down yes it's in the listed list is the cell to the right in a visited in the visited list or a wall this is cell to right to my right and it's not in a visited list so therefore I moved here place cell in a frontier Q so frontier Q s cell 3 and I move down to here it's a cell up in the visted list or in a wall it's in the wall and so is the one down so I can really jump down to place the current cell nervous this list so they can't cell which is 2 goes in the visited list and I do leak DQ the frontier I'll take you out to wrap around is the frontier empty no it's got well item in it still and I make the current seal the frontier so it becomes a 3 cell 3 move to a frontier so I'll highlight it I'll goes red so we know we've been there is this cell to the left a wall always had been visited well it's been visited so I move down is this cell to write a wall or has it been visited well it's not walk but it and it's not been visited so therefore and move across right here and I place that cell in a frontier queue so in the 4 goes into a frontier queue it's now this is interesting now is a cell in a sum up in a wall or in viscid list list not in the world is not in viscid list so therefore I move to the right place the cell in the frontier queue so frantic you new house three entries in there is the cell down in a wall or visted list oh it's not the wall when it's not in the visitors list so move to the right place a cell in a frontier Q so frontier Q now has four items in it seven place the current cell and a vist its list so the can't CL was three that needs to go into the visited list DQ the frontier so take out three now no longer required move around is the frontier empty no it's not make the current cell at the frontier so the can't sell so you can't see ok the frontier so the frontier is 7 so it needs to be at 7 so it can't sell is four that needs to be 4 move to the frontier move to the frontier here's a cell to the left so I needed a high like that denied is the cell to the left in viscid or a wall cell to the left has been visited so I move down he says cell to the right a wall or visited cell to the right is a wall the set up is a wall cell down as a wall I place the current cell invested list so 4 goes into vassilis into the visited list I kick you the frontier you move for from the list go up and around is the frontier list empty no it's not make the currency of the frontier list so I can't sell so in frontier is 5 so that needs to be 5 move to frontier so I'm now going up to here to 5 and I'll highlight that I'm gonna move to now now it's the cell to the left a wall or a nervousness so it's a war so I moved down here is the cell to the right a wall it is here's the cell a barbed up a wall or nervously list and cell is not a wall and it's not in the visit list so therefore I moved to right place that cell in frontier qs6 move down to here it's a cell down wall on a visited lists the cell down is already invested list so move away face the current cell in a visted list so 5 goes to visit this visited list ID q 4p q the frontier I removed five no longer required is the frontier empty no carousel comes frontier a little bit current cell equals frontier which is 7 moved to the frontier we looked at frontier and I'll highlight that so we know we've been there he's a cell to left a war it is I come down his itself to write a war it is so I come down he's a cell up up a wall or Anna visited list so it's not wall but it's been visited it's not come down is the cell down in a wall or visited on cell down is not in a wall it's not been visited so therefore I moved to the right place a cell in the frontier q so number 8 goes into the frontier q come down here place the current cell in the visited list number 7 bigger fancier remove certain from list background frontier list empty no it's not console equals frontier sorry frontier is six so for the current cell must know be six move to frontier later frontier and shall highlight it is a cell to the left in the wall it is is the self to the right a wall it is is a cell up in a wall or vistit well it's not wall but it has been visited he says cell down in the wall or visted and a sill down isn't a wall but it has been visited so therefore place the current cell in a visiting list so the current cell is six I place that into the visited list i DQ the frontier and go around one more time frontier is not empty still so the currency all week was the frontier so 60 replaced by eight move to the frontier I like that is the seltzer left in the visitors list a wall selten less left is not in the visi list and it's not in a wall so therefore place a cell in the frontier queue place nine in the frontier queue he's a cell to the right a wall or in visited list the cells right he's not a wall and it's not on the visitors list so therefore moved to right and place that cell in the frontier queue just 10 it's a set up a wall or visited set up is been visited is to sell down visit all settled down is a wall so we're here right now place the current cell in a visited list can itself which is 8 this is list and I think you the frontier background again he's the frontier empty no he still got two items in there make the currency of the frontier becomes nine and move to frontier nine he's a cell to left of his syllable cell to the left is a wall shelter-rite has been visit so he can't go there the setup is a wall so he can't go there the cell down as a wall so he can't go there so he placed the current cell and visited 9dq the frontier Laura moved 10 whoops move 10 back round again near the end now it's the frontier list empty no there's still one item in their place the current cell in the frontier very place that we have 10 move to the frontier you can see now that's the very last item so all cells have been checked and we notice they're all getting checked in at the same time it's a cell to lift this little wall cell to left is in the visited list the shelter right as a wall cell above as a wall the cell below is a wall so place that can't sell in visited so I can't sell just 10 goes in visited I DQ'd a frontier so now the frontier is empty move up here is the frontier empty yes it is and that ends the algorithm so you can see it's searched across here first when you got to number three it searched there there and there at the same time and then from there to five to six and then from seven to eight then from 80 search both these two paths so you see how it does on the breakthrough search works the algorithm is really efficient I do like you okay so let me minimize that okay so the first search algorithm explained how we were managed to search all the cells that are in the maze but he didn't explain how we got the backtracking part of the program working so I'm using a different algorithm now it's called a backtracking algorithm it's very very simple basically it uses a key feature of of pythons list which is called a dictionary dictionary Python dictionary which consists of two key elements so you have the solution which is the list name and you have two values you have a key and a value so you look up the key and it returns the value so I'm using this to identify the cell that I'm on and the cell that came from so for instance if I take cell and let's say cell 1 cell 1 started to starting so so say cell one came from cell 1 but cell 2 here is the current cell beta previously he came from cell 1 cell 3 came from cell to cell 4 came from cell 3 so five also came from cell 3 cell 6 came from five cell 7 came from three cell eight came from seven cell nine come for it came from eight and cell 10 came from AIDS so you got this list of the current cells and the previous cell so I'll just put this really basic algorithm together that allows me to create the backup tracking so first of all find starting key find the key the starting point now the starting point is the very last where you want it to backtrack from so in this case it's going to be nine because I want it to go from nine back to one so that's going to be my starting position and I wanted to go back in that direction to the beginning of the cell one so starting at nine I look that's my current cell read the value of the key so the value of the key is nine and the value is eight now make the values and make it new key and find the new key so if the key is nine the value is eight I now make eight the key which is there now find the value of that which is seven I make seven a new key and find the value of that is three I find the value of three so the key of three and the value of that is to now make that the new key that becomes two the value is one and that becomes a new key and that's one so it takes you back in this direction it's very simple to very simple algorithm but very effective okay just to prove the algorithm works from any cell let's take cell six this time so we say that the key value is six and the value is five and we convert from the value from five to the key of six that takes us to 3 and three takes us to two and two takes us to one so it works in that direction let's try 10 so 10 takes us to eight eight takes us to seven seven takes us to 3 three takes us to two and to Texas to one so the backtracking works in any permutation you can choose ok so let me now move on to the actual Python program I'll show you how to code it to give you the results of a breadth-first search by this is the Python program that I wrote to demonstrate the breadth first search or BFS as is sometimes called this first part of the program is used to set up the the turtle graphics now as you probably notice that the maze and all the animation using turtle graphics and these this first past piece of code is just defining just setting up the screen really so the walls that define this of white square dbfs search is defined as green square the blue square is the end points and the red square is a starting point and the yellow well that's the backtracking path so the first part really just defined just sets up the turtle graphics and then we come down here we have various grids I use when I've set it up and testing the program but the one that I used to demonstrate was grid one and this pro part the program here set up maze just really constructs the maze so if we look up here the maze is made up of ASCII characters and what the program does it examines each line and in each line examines each character and if it sees a cross then it knows it's a wall if it sees a s then it knows it's a starting point and puts in the Red Square if it's season E you knows it's the end point and puts in a Blue Square so that's basically what this part the program is doing here so he sees the character and it's a and it's across then it stamps it with a white square if it sees it as a they stamped of a Blue Square and so on now this part the program is the algorithm that I was going through earlier on now unfortunately turtle graphics doesn't use a nice convenient one two three four four it sells it uses a grid system so each cell has a X parameter and a Y parameter so if you look in here and this part the program here which says check in to the left it's X is the actual cell it seemed and it was checking left it's gonna go minus 24 in the x-axis to see if the cell to the left of it is in the path or as is in the wall so unfortunately can't be nice and convenient as in terms of home one two three four but it uses the grid system that's why I've seen a lot of X plus and minus 24 so that's searching left this is searching down this is searching to the right and this is searching up the code inside each of these bars is exactly the same as it was with the algorithm I showed earlier on this part of the code is the backtracking routine fairly straightforward not much to say about that I explained that earlier on these pieces of code are setting up the various lists and that we used the program and these are the three main routines that set up the mate and set up the main routine the search we've seen and the backtrack community now this code is available and get up if you want so there's a link below in the description please feel free to download it play around it do whatever you want with it so I think that's about all I wanted to say maybe I just run the program again just so get a feel for how it works one more time so quiet so the total of graphics are constructing the maze there's the BFS search going through and there we go there's our back path and just to prove that I'm not cheating let's um let's quickly change the star so to start seeing it smoother start to another location to say go here and let's move the end somewhere else as well to say yeah and I run the program again let's see weapons okay so our start is over here now well we did we put the end some around here isn't it yeah there's the end here okay so the ef-s is taken into various pop this time obviously because the start position is different but she's still create the most efficient backtracking path and it goes bang done so you see it will work in wherever you put the start and end points the program will work it's a really efficient algorithm okay thank you for listening I hope it was a fuse to you bye for now

Channel: Davis MT

Views: 16,439

Keywords: Sicence & Technology, python 3, maze solving, algorithms

Id: ZuHW4fS60pc

Length: 24min 40sec (1480 seconds)

Published: Tue Nov 27 2018