Abstract =>
This article will first discuss the Flood Fill algorithm, modified flood fill’s d
Abstract =>
This article will first discuss the Flood Fill algorithm, modified flood fill’s description and implementation will be built on that. After the boring theory session, the actual C implementation of the algorithm will be discussed and a sample simulator program is provided at the end of this article.
It should be noted that the algorithm and some of the pictures used in this article have been taken from ‘micromouseinfo’ website,
http://www.micromouseinfo.com/introduction/floodfill.html
http://www.micromouseinfo.com/introduction/mfloodfill.html
Prerequisites =>
This article requires the reader to have some basic knowledge and understanding about the following topics
- Basic logical constructs of C like if-then-else, while, for etc.
- Understanding of bitwise operators in C.
- Implementation of Stack using arrays.
- Simple 1D array manipulations.
- Writing subroutines in C and macros.
It is advised that before putting up any question on the forum regarding doubts about the software implementation of the Modified Flood fill algorithm, the reader goes through some C-language tutorial like the one given here,
http://www.lysator.liu.se/c/bwk-tutor.html
The Flood Fill Algorithm =>
The best way to understand the flood fill algorithm is the water-in-the-maze analogy. This is how it goes,
Suppose you start pouring water in the center square of the maze (I would love to know who actually tried it first). The water will ‘flood’ the center of the maze and then will start flowing in all the adjacent squares which are ‘not separated by a wall’. If I mark the first square, that is the center, as 0 and mark the next square(s) where the water goes as 1 and keep on increasing the number as the water ‘floods’ the maze, I’ll get something like this
The water is now flooding the maze, and I am numbering the squares in ascending order. That is, water reached the square numbered 4 before reaching the square numbered 5 or 6 or 7.
Done flooding, with water! (You got a dryer or something?)
Now taking the bottom left square as the starting point, if I follow the numbers in descending order, you can see that I will reach the center through the shortest path! Amazing….yes….hard to digest….YES!
This was my reaction when I first got the hang of flood fill.
Flood Fill can be understood in another manner, something that I call the ‘potential difference’ analogy. Water is still used here [:-)] !
Suppose there are two squares A and B. I put A at a higher potential than B and pour a glass of water in A. It is obvious that the water will reach the square B taking the shortest path, given there exists a path (i.e. no wall present) between A and B.
Above point is shown at a larger scale in the following picture and this should clear any doubts in your mind regarding this algorithm (hopefully).
It should be noted here that this illustration has no connection with the ones shown before. Here also, it is easy to see if squares are chosen in ascending order of their potential from the starting square, the center can be reached by the shortest path.
This algorithm has a relatively simple implementation in the software. Two arrays should be maintained in the memory, one for keeping the flood fill numbers and the other for keeping the wall information of the maze. Every time the mouse enters a new square, it stops and checks for the walls, runs the flood fill algorithm, decides where to go depending upon the information given by the flood fill and moves on till it finds the center. Needless to say, this is not a great approach, firstly because your mouse is stopping at every square and secondly, you are flooding the maze from the center every time. This is where the modified flood fill kicks in.
The Modified Flood Fill Algorithm =>
The modified form of flood fill is nothing different from the original one, just that we don’t flood the whole maze every time. It changes only those flood values which need to be changed. Have a look at the link given below,
http://www.micromouseinfo.com/introduction/algorithm.html
This is a very good demonstration of modified flood fill for maze solving.
Algorithm Formulation =>
Before I start describing the various parts of my modified flood fill simulator, we need to formulate the various parts of our algorithm in simple English language.
This part has been taken from micromouseinfo.com.
Whenever we enter a cell, we check for the walls and update the wall map accordingly.
Update the wall map:
Is the cell to the North separated by a wall?
Yes -> Turn on the “North” bit for the cell we are standing on and
No -> Do nothing
Is the cell to the East separated by a wall?
Yes -> Turn on the “East” bit for the cell we are standing on and
No -> Do nothing
Is the cell to the South separated by a wall?
Yes -> Turn on the “South” bit for the cell we are standing on and
No -> Do nothing
Is the cell to the West separated by a wall?
Yes -> Turn on the “West” bit for the cell we are standing on and
No -> Do nothing
Now we need to call the modified flood fill to flood only that part of the maze which is required. The cell values are updated according to the following rule,
If a cell is not the destination cell, its value should be
one plus the minimum value of its open neighbors.
When the cell values violate the above rule, they need to be updated.
Update the distance values (if necessary)
Make sure the stack is empty
Push the current cell (the one the robot is standing on) onto the stack
Repeat the following set of instructions until the stack is empty:
{
Pull a cell from the stack
Is the distance value of this cell = 1 + the minimum value of its open neighbors?
No -> Change the cell to 1 + the minimum value of its open neighbors and
push all of the cell’s open neighbors onto the stack to be checked
Yes -> Do nothing
}
The stack empty check is not required in the program presented in this article.
The wall map is updated, required part of the maze is also flooded now what? Guess we need to make the right move.
Decide which neighboring cell has the lowest distance value:
Is the cell to the North separated by a wall?
Yes -> Ignore the North cell
No -> Push the North cell onto the stack to be examined
Is the cell to the East separated by a wall?
Yes -> Ignore the East cell
No -> Push the East cell onto the stack to be examined
Is the cell to the South separated by a wall?
Yes -> Ignore the South cell
No -> Push the South cell onto the stack to be examined
Is the cell to the West separated by a wall?
Yes -> Ignore the West cell
No -> Push the West cell onto the stack to be examined
Pull all of the cells from the stack (The stack is now empty)
Sort the cells to determine which has the lowest distance value
Move to the neighboring cell with the lowest distance value.
After making the move, the above process is repeated again and again till the mouse reaches the center/runs out of gas/stops to say ‘Hi!’ to you/stops for a photograph/bangs into the wall!
The Modified Flood Fill Simulator =>
I know you were waiting for this, the ‘real thing’!
The simulator is divided into two parts, the ‘.c’ file which implements the algorithm and the header ‘.h’ file which provides the graphics and basic front, left and right movements. At this point you might think that the main program is the most important thing, but you must understand that the header file is a general purpose file which can be used to implement any higher level maze solving algorithms.
The main program file, ‘Modified Floodfill_TRI.c’ has three routines,
- The ‘main’ routine
- The ‘step’ routine
- The ‘floodfill’ routine
- The ‘main’ routine
This is where the action takes place. ‘main’ is responsible for maze mapping, calling the floodfill routine to flood the maze and then calling the step routine to make a move.
The maze is mapped according to the algorithm given above.
- The ‘step’ routine
This function is the implementation of the above ‘Decide which neighboring cell has the lowest distance value’ algorithm.
- The ‘floodfill’ routine
This is where modified flood fill takes place. It takes the maze’s cell number as an argument and floods the maze assuming that the given cell number is the destination.
The ‘MAZE.h’ header file deals only with the graphics and I must clearly state here that it has not been written by me. It has the following functions that you are supposed to know,
- void movestraight(int)
This function makes the mouse on screen go straight the number of squares mentioned in the argument when calling.
- void turnleft()
This makes the mouse point to its left direction. If you call the movestraight(1) function after calling turnleft(), the mouse will move into the square in its left.
- void turnright()
This makes the mouse point to its right direction. If you call the movestraight(1) function after calling turnright(), the mouse will move into the square in its right.
You should note that the left and right directions are relative to mouse and not yours’ left and right, don’t get confused.
- void show_maze()
Calling this function would display the maze on the screen. This should be done in the start of the main().
- int sense(int)
This function has three arguments, FRONT, LEFT and RIGHT. It returns a high(i.e. ‘1’) if there is a wall in the given direction. Basically this is the sensor of your virtual mouse on screen.
- int hori_walls[sizemaze+1][sizemaze] and int vert_walls[sizemaze][sizemaze+1]
These two variables contain the maze’s wall information. Putting a ‘1’ builds a wall, ‘0’ removes it. I have provided two actual competition mazes for you. One was used in a competition in the USA in 1982 and the other was used in Japan in 1991 (yes, we are far behind them). The design has been taken from Peter Harrison’s micromouse site,
http://micromouse.cannock.ac.uk/maze/samples.htm
Watch out for that Japanese maze, it is the best I have ever seen. Also, you can build your own test maze.
Before going through the simulator program, you need to understand a few things about this implementation,
- I have tried to make things as simple as possible(with few exceptions of course!), thus the implementation is not very efficient in terms of memory consumption and execution speed, mainly because of my 2.4Ghz machine with 1Gb RAM. You are probably going to implement this on a 16MHz 2Kb thingy (ATMega32), so take this program as a reference only.
- The maze has been mapped as a 1-dimensional array to maintain simplicity and has been visualized as shown below
In the implementation, cell number 119 has been taken as the destination cell. This happens to be the bottom left cell of the maze’s center.
- The directions have been taken like this
It is pretty evident that if the mouse is facing north in the cell number ‘x’ and it moves straight one cell, it will find itself in the cell number ‘x+16’.
If the mouse is facing west in the cell number ‘x’ and it moves one cell to its left, it will find itself in the cell number ‘x-16’. You can work out for other directions and movements in a similar way.
- The maze’s wall information is stored in the variable ‘wallmap[256]’. The maze’s dimensions is 16×16, representing it by a one dimensional array would require 256 memory locations.
- A single wall is represented in the following manner
[BIT7] |V| [BIT6] |0| [BIT5] |0| [BIT4] |0| [BIT3] |W| [BIT2] |S| [BIT1] |E| [BIT0] |N|
Here, V stands for visited. ‘1’, cell is visited, unvisited otherwise. W stands for the wall in cell’s west direction. Here, the west is the maze’s west not the mouse’s west. S, E and N have similar meanings.
- The current direction of the mouse is represented as follows
[BIT7] |0| [BIT6] |W| [BIT5] |0| [BIT4] |S| [BIT3] |0| [BIT2] |E| [BIT1] |0| [BIT0] |N|
These directions refer to the absolute maze’s directions. For example, if the mouse is facing east, i.e. the 2nd bit current direction is ‘1’, then the mouse’s left is maze’s north and its right is maze’s south.
You need to go through this direction part again and again until you get the hang of it otherwise you won’t be able to understand a major part of the program.
In this format when I change the direction of my mouse, I simply rotate the direction bit left or right. This is done every time after I make a move in the maze. See the program to get what I am trying to say.
7. The unsigned char wallflood[256] variable holds the flood fill numbers (or the potential values) of the squares. This variable is initialized with values assuming that there are no walls in the maze.
8. There is a variable in the program called cell_count, this variable was declared solely for debugging purposes and has no use in the current program. You can surely put it to some good use.
9. Rest of the code is very heavily commented (that’s my habit, a good one) and is pretty much self explanatory given you have gone through the theory part and you have a good command in C.
10. Please go through ‘Read Me.txt’ before running the simulator on your PC.
Final Remarks =>
First things first, flood fill algorithm of any kind is pretty inefficient. Your mouse will take a long time to reach the center and come back for a speed run. But yes, you will reach the center and complete the problem statement which might be enough for you to be the champion!
There is a reason why I like that Japan competition maze, the shortest path in it is not the fastest one! Yup, this is possible! Here, you will see, flood fill’s performance is horrible. Here, something you need to know about the pedigree of flood fill. Flood Fill Algorithm has been derived from Kruskal’s Algorithm which happens to be a kind of greedy algorithm. Kruskal’s Algorithm finds a minimum spanning tree (i.e. the shortest path in the maze) for a connected weighted graph (which is The Maze). I know I am speaking too much! It does not assigns costs to the paths, that is, a turn takes more time than a straight and hence, ‘costs’ more. Kruskal’s Algorithm doesn’t cares about this.
A simple idea to work around this problem could be like this,
1. After coming back to the start for a speed run, the mouse stops and calculates the fastest path.
2. Check all the cells that the mouse has visited.
3. Out of those cells, figure out how many paths lead to the center.
4. The path involving minimum turns will be the fastest path.
Here I have a made the important assumption that your mouse does not makes diagonal runs. If it does, then the problem is much more complex than you think and you better opt for A* (pronounce A star) or Dijkstra’s Algortihm (pronounce diaofoasdfsdfet [:-)] ).
All the Best for the Techfest 20xx…….and Happy microMousing!
Read Me
Maze.h
Modified Floodfill.c
