Upon first look Microsoft paint and the classic game of Minesweeper don’t have any similarities. But theres the same important algorithm behind both programs: Flood fill.
I recently made a minesweeper clone and had to do a bit of fumbling around this algorithm before i really understood it. So hopefully I can save you a bit of fumbling by taking a deeper dive into the algorithm here.
In minesweeper the flood fill is specifically used for when you click on an empty square. Maybe you’ve noticed that instead of one square being revealed you get a whole section of empty squares surrounded by numbered squares. This is accomplished by the flood fill algorithm.
Now let’s talk about the algorithm itself. It works by checking neighboring cells and then recursively doing the same thing to that square until the parameters are met. for example:
Ok so what are we looking at here? Well I apologize for my crude drawing but when you're first learning the algorithm there is a lot to follow so I think color coding will help. Right now we have a grid of squares and we will be starting the algorithm on the red square. We also have 3 arrays to the right (the returned array, the queue, and the visited). We will be representing which squares are in which array with the colors assigned.
So first thing that happens when we start the algorithm is this:
Ok WOAH! What just happened? well let’s start with red. The squares surrounding the starting square were added to the returned array and the queue of squares to be checked next. meanwhile the square we just checked is added to an array(or given a property that identifies it as visited). This is where recursion comes into play. We have gone thru the process once so now we will take the first square in our queue array (which for our purposes will be the top square)and run the function on it as well. Lets see what happens:
So at first glance this makes sense. We see that the squares to the left, right, and above the new square are added to the queue and the returned squares but based on what happened last time the original square should also be added to the queue. However we as humans can see thats worthless because we have already checked that square so we have no need to check it again(which is why we have the visited array). We should also note that the square currently being checked was removed from the queue and since it has now been added to the visited square so it wont be added to the queue again in future iterations of the function.
OK thats a lot of info but now that we’ve covered the basics lets jump in and write some pseudo-code for the algorithm!
Although this isn’t working code it gives a good idea of what our code would need to look like and if you can understand the pseudo-code here then you definitely understand the algorithm and can write it on your own!
something to think about is that theres two problems with this algorithm how its currently written in our pseudo-code:
1st: Our code doesn’t account for edge cases and will run into problems when we get to the edge of our board.
2nd: Our code wont reveal the corners of our “flooded” space which we need it to do for minesweeper, so instead of the 4 surrounding nodes it actually needs to check the 8 surrounding nodes.
Hopefully I’ve left you with a better understanding of the flood-fill algorithm and also some challenges to work out on your own!