Micromouse Maze Solving: Flood Fill Algorithm Lecture

[00:00:02]all right hey guys welcome to our fifth micromast lecture today we're going to be talking about maze solving uh very exciting before before we get to that we have a couple announcements for you guys yeah first off great job everyone on your pcbs those are currently being manufactured so kind of gonna assemble those over spring break and get them shipped out to you so you should hopefully have them at the start of spring quarter i'm personally really excited to see all of them i hope you guys are too because they're they're pretty solid um also just heads up there's for just a reminder that there's all these gb takeovers happening so this weekend it's is it prom or prom i don't know it's definitely chrome chrome yeah you should pull up if you want to um there's the rsvp forms and more info on the ieee discord yeah don't worry if you don't have a date they're uh they're grouping they're doing groups of three or triodes or whatever i don't know what they're doing all electrical and computer engineers and other so uh chances of other people also having a date are on the lower end bradley did you really i'm just i'm just putting it out there it's like all right well anyways moving on let's uh let's get to the lecture so today we'll be talking first introducing a couple uh basic may solving algorithms and then uh the fancy one that we use a micro mouse uh flood fill so next oh that's the fun okay cool so let's see so the whole point of the end goal of micro mouse is to get your little robot to uh get find the center of a maze typically it's a 16 by 16 maze this this year uh that's a lot of cardboard but um uh yeah so you need it needs to get to the center of maze and all it has to work with are has its internal memory on the microcontroller and the ir sensors uh that will be uh in the form of your ir breakout boards coming soon so task is use some smart algorithms to make it happen so first there's a there's a couple here so what you guys implemented during the ir assignment and for the rock competition is more officially named dead reckoning it goes until it hits a wall and then it turns appropriately um it's really good at not hitting stuff but uh that's about it so that's dead reckoning there's another one called wall following uh this one this one's a little more interesting so right now i have the what the animation is showing is a left wall follower so it's just going to always it's going to follow along the left wall as the name implies so for simple mazes like where all the walls are connected like in this this maze if there's a connection right here so everything's connected together and the start and end points are along the edges then this algorithm will 100 of the time solve the maze so not necessarily with the shortest path but uh for micro mouse the mazes get a little more complicated you can see here since they're it's not a simple maze where everything's connected it never gets to the center point so we need something that can overcome these challenges that's where floodville comes in wanna talk about bradley all right flood fill is a slightly more complicated algorithm um this just finds the shortest path between a goal and an endpoint and continually updates as you learn more about the maze uh if you want to think about it just from the start um it's called flood fill because you can imagine in the same way if you put a drop of water and then let it flood out and fill um fill up the maze [Laughter] um it'll naturally like lower in height and decrease and like it'll form a slope based on how the water spreads out going farther and farther away from where you want to go and you can think of it as like you want to you follow basically follow that slope as you navigate around the maze um so yeah intuitively like you take the shortest path which is just following the nicest slope that left most point since there's a wall in the way the water has to flow around it so you can see it gets to that point last so um yeah and then putting a little bit more of a mathematical sense to what we like to just instead of saying water flowing down we can introduce this kind of more this more mathematical way of thinking about distances in a maze uh because this is the distances in a maze aren't just like euclidean distance from start to finish so like the hypotenuse of travel you have to think about actual distance you're going to travel so we call that manhattan distance which is the distance um going like say like i'm gonna go forward forward left forward forward turn and like if you think about it also is like if you're walking through a street from like one place to one place you're going to follow the streets and not just walk straight through the middle of a block yes there's buildings yeah we're not like vision we can't just walk through walls for those of you who have been getting into one division lately um but yeah so basically we can use manhattan distance which calculates our effective distance going through the maze um and you can see in the diagram out right we have manhattan distance for each cell relative to that center cell which is marked zero and this map also keeps into account the the barrier in there too so the effective distance having to navigate around that barrier of your distance from that endpoint yeah and then it's the last point it's it's the number of moves it takes to get from a certain cell to the goal so so if we start uh say right here number four so forward move forward down down down left that's four moves that will apply for all these so it's another way to think of it that's helpful all right let's talk about what this has to do with flood fill okay so um well your uh mouse is not an amorphous solid or a fluid that can flow through the maze in all directions so it can start at one point and it doesn't know anything about the maze so let's start there so kind of like on the previous slide where we assumed we dropped water out and it we kind of put numbers representing the order in which the water got to the different cells let's uh pretend there are no walls uh ignore the blue walls assume those are unknown so zero one two will expand out evenly in all directions and our mouse is gonna start down here so um if the maze looked like this then the fastest way to get to the center if you're at four just go straight three two turn right one zero now you're at the center um so basically uh if you if you start with these manhattan distances this is the maze then if you always travel towards the decreasing numbers you'll end up at the at your goal in the shortest amount of steps so let's let's kind of take a look at how this works so we start with the rat in the bottom left and uh the sensors pick up the that first wall on the to its right then next obvious step as it goes forwards and now sees another wall but nothing exciting happens yet goes forward again turns right then goes forward and just a side note with all of these you can see that it's going from a higher number to a low number each step yeah and that's uh that's what makes these moves easy yeah so now we're here and uh the rat wants to go forwards one more to zero right that's that's where it's trying to get to uh but there's a little problem there's a wall in the way so racket's stuck here and uh so there's a wall in front can't go forwards towards the lower cell and it's surrounded by cells that are higher in value so that valid that violates the rule where it always has to go towards a lower number right so essentially the mouse has just learned some more information off the maze it's learned that there's a wall there so if we imagine okay we know these walls are here so what's the that's the actual path so imagine if you poured water yeah my laser pointer all right so if you poured water from this cell um it wouldn't be able to flow here so it'd flow up one two then down three flow around this wall then go in here to be four or five six so if we uh ignoring the mathematical and the algorithm how to actually do this just imagine okay we learned there's wall there pour some water there simulate that and figure out what the new distance should be then uh they'll end up look the number new manhattan distances will be like this and then once you have your new manhattan distances uh now now it can keep going you can go up to two or down to one zero now it knows how to get around the wall so does that make sense uh does that make sense um how we encounter a wall and then we're stuck so we kind of re-simulate what what if we poured water from zero what would happen so anyone have any questions about that before we continue on to uh now let's see all right so let's keep going so let's talk about how to implement this and code so um i'm going to switch over to a tablet in a sec but first i'll uh let's see yeah i'm gonna switch over to that's why there's two of tyler's joined into the meeting while tyler's doing that i'll just give a quick intro to some terminology so we're going to be talking about a queue here um for those of you who haven't taken cs32 i think that's where they introduce it um a queue is essentially a data structure that it's like if you can think of it as waiting in a line you basically put things into the queue and then you take stuff from the front of the queue and basically you build up a queue of things that need to be done and then you execute them or process them or do something with them in order so it's like if you're um you can think of it just like waiting in line first for its first person in first person is the first person out and you just work your way through the tasks you put line up um yeah for yourself later on you'll kind of see it here as we work through an example of how it works so the goal is so we can intuitively see how the how our what poured out water would flow but how do we get the get a computer to get to produce those same numbers so this is how we do it so um so where do we start so we started the mouse was right here and it was stuck right so let's uh let's go through this algorithm we i have outlined on the left so first step is to add the first current cell which is l here to the q so my q is i should just have it shown down here i'm gonna write l okay cool that's the first step okay great uh second step so while the cue isn't empty uh take the front cell out for consideration okay so let's uh put him right here let's let's look at him oh okay right right here yeah so next step is get this front cells or so we just took out minimum get the minimum value of its accessible neighbors what i mean by accessible is zero doesn't count because there's a wall in the way so can someone tell me what the minimum value of its neighbors is are it's not a trick question the minimum value is two is two there you go thanks jonathan that's incredible yeah so there's two two and two what's the smallest number there it's two okay so small so minimum equals two okay so now we're on this step uh if if this if l's value which is the one we're looking at what one is less than or equal to two which it is uh okay now we need to set the current cell's value to the minimum plus one so hey this is not a trick question either what is two plus one three great tyler you made it too easy for them how do we know that they know the answer all right there we go uh so we set the three and then uh last and then also part of this we need to add all the accessible neighbors to so someone someone tell me what to add to the queue which cells i'm looking for some letters here g k and q perfect um good job m there we go so let's do uh for for fun reasons uh i'm gonna put it in this order but it could be any order side note um if you think about the order of the queue tyler correct me if i'm wrong but i i believe the way the order in which you drew them is the opposite in which you i guess you they just keep in mind that the things in the queue are coming from the right side and then moving to the left side um when you actually fill this up all right put g in first then put q in then i put k in okay so um okay so now let's run through this so uh okay all right let's go uh we're so back to the top of the while loop step eight uh take the front cell out for consideration that's g so uh let's uh let's look at let's look at g then uh then then i then how the q works you take the first element out and everything else moves up one spot in line cool okay step two get its minimum value so uh g has four neighbors uh f b h and l so the minimum value is one which is cell h so one half is um one is less than the g's value which is two so we're good to go so awesome ignore that okay um all right so now we go back to the top of the while loop take the front cell out it's cue i'm not going to draw that tell us does someone want to tell us what's going to happen with q before we go over it we're just gonna get rid of q and why is that because it's three neighboring cells the minimum is one and one is less than the value of our current cell which is two perfect easy and i do like how you said three accessible neighbors because that is true because p is not an accessible neighbor all right let's get to the let's get to the uh the spicy case okay there's one more item in our queue so let's uh all right what happens someone here want to volunteer and give us an idea of what they think is going to happen okay um which okay so we have two neighbors right okay two accessible neighbors so we've got l we've got pew alright so their minimum value so we have three and three so minimum of those two is three uh two is less than three so we're going to do this step and change this value to 3 plus 1 which is 4 and add the neighbors to the queue so i had l p okay all right i'm gonna do one more iteration of this and then i think you'll you'll get the idea so uh so just like what happened with q that jonathan said earlier um the same thing's gonna happen with l let me take it out because l has a valid neighbor that's less than it has g and q are both less than three okay go through the loop again back to the top all right p does not have a lower neighbor so you increase its value by one or take the minimum value which is four add one that's five someone guess what uh what you what's going to happen when we do q or our duet you should just change use value to six yeah precisely and uh that's uh this is exactly what we had on the other side so when we said like oh what should happen if we were to uh for the poor bucket of water here it should flow out one two three four five six it takes six steps to get from this cell to the target okay so how yeah how are people feeling about this do a thumbs up if you're feeling good um yeah or anything else if you're not feeling good okay i think that's a pretty good sign yeah so as far as uh like oh if if it's yeah this algorithm here you don't have to understand like why does this make flood fill work um the point is like this is here and then when you're doing your assignment you just implement this exact structure a while loop a cue these these steps in the form of if statements and whatnot and if you do this then it's going to successfully perform flood fill and correct the values so this used to be one speed two three four now you can see they've all changed to what they should be okay also just random quick side note there is an alternate way to implement this with recursion but we won't subject you to that if you're curious you can do this recursively but don't sweat it if that is a lot i personally like recursion more because it's just prettier to me but um the queue is definitely easier and it's a better way to teach it to uh okay i could okay i don't want to get too far on tangent but i want to say that uh recursions epic but on microcontrollers they have limited uh they have a limited call stack and limited memory and uh recursion basically will if you don't know what requisition is ignore this discussion but it'll it'll use up more resources than if you do it iteratively and with a small queue so um yeah so but both are both give you valid uh flood fill implementations so yep yeah for those of you who have taken wait is it cs30 is it cs31 or cs32 when you do all this stuff i think it's 32 32. yeah basically there's this is like a homework assignment in 32 i think and you can pretty much see how this plays out okay so you can see from the oh from the previous slide you saw like okay intuitively this is what we should get and that's and we after stepping through this algorithm that's in fact what we got okay so that's that's all there is to say about the blood fill guys like uh that that's it um i'll just hammer it in one more time okay i i don't know if we need to do that honestly okay follow the follow the number trail then if you get stuck run the algorithm we just told you and keep doing that and eventually you will find your way to the center that's it okay yeah that's pretty much it just follow it until you find something illogical which means you need to update your map update then update your map and continue following the trail yeah okay ready um i got this there's this epic maze simulator thing that uh you guys will be using so uh on we have an assignment document which has more instructions how to get it and set it up and everything so the goal here is uh you're going to implement and test out your maze solver on mazes that are more complicated than this one uh so on so this will be on like uh micro mouse mazes from previous competitions so if you're able to solve these then you will be able to succeed in micro mouse um let's do uh quite a bit from now so you have plenty of time but um yeah don't take that as an excuse to put it off for a long time i know saying that will make a difference but uh yeah we're giving you a long time because i mean at this point we're just waiting for pcbs to come but um like there's no reason to wait the quarter this is the monday of spring break for those of you who are curious okay all right uh bradley you had a yeah cool um just a few tips we talked about flood fill at a pretty high level of like you have a queue and you put stuff into the queue um so just like some tips to help figure out the nitty-gritty details of that you're going to need a coordinate system to note each um maze in the cell probably just an x and y coordinate and you're going to have to keep in mind that you're going to have to pick a reference point in your maze probably like one of the corners to have b zero zero um another way that might help keep this more organized is if you define a struct like of just like an x coordinate and a y coordinate so you can easily put in coordinates into a queue um and then you also need a location or a way to store all the data you currently have about your maze this will be your horizontal walls your vertical walls and the manhattan distances i would personally recommend having a 2d array for each of your vertical walls and your horizontal walls because then you can just usually say like left and right ir sensors and like top and bottom um i don't know that that's the way i would do it um and lastly just if you need help with debugging a great way to do that is to just use the printf statement um just because uh like well you you have to you run this simulator through a terminal so it'll print out stuff in the terminal and you can see what your maze what you you can have it tell you what your mouse is thinking at each step of the way eric to answer your question it's a good it's a good question how do you know when your mouse is done um in a standard micromast competition you always know the goal is to get to the center and that's your target so if you keep track of your mouse's coordinates so every time you go straight y increments by one you move over oneself you can keep track of where it is if your mouse's coordinates match up with the coordinates of uh your end goal then that's it let's see does the rat know how big the maze is beforehand yes and uh it doesn't let's see i don't remember if that is or is not a requirement for flood fill to work um it has to be for when you define the size of your of your coordinate structs um yeah um but the thing is with the with the may solving simulator you have the option to create a maze with the specified length so if you want to start debugging it on smaller bases you have that option i would just recommend going with the 16 by 16 from the start yeah i think why not um any other questions um can you talk more about the arrays necessary that you'd recommend for storing like the position of the walls that we find yeah sure um let's see well okay let's okay let's wrap with the lecture and then we can discuss it like uh like right so all right wearing other questions that's all for today but uh i'll bradley and i can stick around for a little bit and answer questions like that okay so um yeah so you basically if you think about it if you take all your vertical walls if you have a 16 by 16 maze you'll have like two walls on each side um of each cell which means and then you'll have 16 walls going up the maze so if for your vertical walls you'll have 17 columns and 16 rows of walls and to store like whether or not there is a wall you can just like have a one or a zero actually a better way to do this would probably be to have a 15 by 16 because you know that the edges of the maze are going to all be ones so you can store the center walls in an array um and then just say like if it's equal to one then there's a wall if there's not if there's no wall then it's equal to zero and you can initialize all of these values to be zero as you're assuming an empty maze and then you fill in the walls as you go using the ir sensors 4x4 um yeah we can start with the 4x4 and the same logic would apply with the vertical walls or wait sorry i was saying horizontal the whole time i was backwards but um yeah what tyler's drawing is a way you could think of the mace you can see it's going to be like three by four or four by three we already know there's always a border wall so you don't really need to keep track of it it's kind of if it makes your algorithm easier then feel free like you have a lot of flexibility with how you implement this but um for actually so you can see that vertical walls we're gonna have so four four by four we have uh so we're doing uh yeah so it's three so it's four tall and then 3 3 wide i'm writing this this way because this is how you would index the array it's a little confusing but for the horizontal so pretty cool so basically just store like one or zero if it's a zero then there's no wall there if it's a one there's a there's a wall there um or something there's a lot of different ways to go this is just one suggestion horizontal so an index array there's one two three four that's four wide and three you know what i mean three tall so three by four so um that's uh that's that now for manhattan distances um you just have a four by four uh yeah just a four by four array that could store all your uh all the distances in each cell one catch is you need to initialize the maze uh with manhattan distances in it in order to work properly the nice thing with that though is you're gonna initialize everything the same thing every time so that's something that'll be constant between all runs of the maze and what you do at the start is you just again you assume no walls um center the goal is that center cell or in a 16 by 16 maze it's it's the group of four in the center of the maze yeah and then you uh sorry uh and then you just fill outwards from there and there's different ways you could do that you could either just like define a starting array to have all these values you could write a function to calculate manhattan distance um go through each cell put the manhattan distance you or like if you want to take advantage of symmetry you know that at the start it's going to be symmetrical in all four directions because there's no there's no walls so you can calculate one but also simultaneously fill in all like calculate one quarter like the bottom left corner for example and then like mirror that on all things to initialize it there's there's a lot of ways to do this this would be a good leap code question or something like uh yeah oh given given this this array like a transform it in all four quadrants or something i don't know yeah so uh how bradley our yeah how we did it last year when we were doing this assignment um we just i i just had a function that initial when the program was starting that just went through populated it with the right values and uh use some absolute values it's just math to figure out of what each cell should have initially um got any more questions about how flood fill works um i haven't done queues in c plus plus before i've done them in java um but is there like a specific library that we use or do we have to implement them ourselves or what i would love to answer this question so much you have no idea how much i want to answer this question oh boy go for it tyler let's see um we so c plus plus and java are object oriented languages and uh so it they and they also the way their cues work um they well every time you want to add an item they'll allocate some memory to store their objects and it's like a it's a list but for microcontroller and for our purposes that's a bit overkill um because that the microcontrollers don't have a capped amount of memory um so the way we'd recommend implementing quasi-q thing is just as an array so um let's see so let's say we have an array here let's give it okay so let's say i want to add and and this was the this was index zero one two three four five okay so let's say i want to queue up the number three right so i cue it and i stick it and i have a variable keeping track of where the front is front's right there backs right there now i add the number seven and i keep going but then when i and then now the back changes so let's add nine one more okay so this is start end okay so then whenever i dequeue an item like let's say take three off instead of dealing with mixing pointers around and doing all this uh pointer manipulation um you could just say all right i took one item off so the start is gonna shift up one all right now i'm here and then uh that's supposed to say start trust me um okay then uh yeah circular array that's right derek so then keep going let's pretend we put in a bunch of random values so ends over here and okay then we can pop off values and then start we'll our start thing will shift over and then uh now when we try to add one more it's uh we do what's there's a little trick that's uh it's called a circular array right so um now we we say we want to add one more so then we have like a little bit of code it's like oh n should shift so it's at five our thing is size five so now it should become zero so next time we add something let's add it here then we'll add it here next etc and then once your end catches back up to start that's when you know it's full and you should uh you know you made your thing too small or whatever yeah um let's see sir no stl version we can even see uh oh so no okay i would like to this is i had a lecture on this actually on wednesday oh yesterday basically if you think about like the names of c plus plus versus c c plus plus is just c with a bunch of fun really nice things added on to it one of those nice things is having all these standardized libraries that you can call like having templates having objects having a standard library those are not available to you in c c is just all the base code so short answer no because there's no templates like templates just aren't a feature of the c language and because of that it can't you physically can't make stl library stands for standard template library so you can't make it you can't you can't make a library for a generic type like you could if you define your own chord coordinate struct and you want to make a cue for that like but the feature to use use some generic code to process the uh thing doesn't doesn't work is it is there a way to copy the cute implementation from c plus plus and just paste it into our project um well let's see in sequence post i think it's defined as a template isn't it yeah well in the standard template library it is yeah um so that that won't work what you could do is uh you could copy and paste the code for a um so you could you could just replace the word template in their thing with uh whatever you're trying to stuff into your queue so it's a coordinate struct for example a chord okay um [Laughter] let's see you can uh so i'd so the right way to make a cue that's infinitely expandable is using dynamic allocation or use malik and free and see uh that's good but you shouldn't be using those things on a microcontroller because um see memory is a lot smaller okay so you just set aside decide how much you need and then stick to that so you need like a statically defined size uh there so dynamic allocation is a little more interesting um what i'm trying to say is don't don't make uh you don't have to implement like a fancy cue like just do the array a circular array like just mentioned yeah um okay good questions um yeah these are all important things bradley i'm pretty sure more will come up make sure to post on piazza if questions come up um because other people probably have the same questions and will benefit from seeing what you have to say um even just your questions may help other people think more too and just simplify things going down the line we also there's a chance we may add more functionality to the simulator depending on more than probably more than a chance yeah so just glad yeah we'll uh we'll keep you posted on that just fun little features to add yeah all right let's see any other questions james turn your camera on see ya why are you pulling me out like this if he's like in his pajamas or something what if he's not wearing a shirt that's even that's even more reasons tournament right i'm kidding wait i've been recording our shoe i have to cut that out okay guys goodbye