IRACST – Engineering Science and Technology: An International Journal (ESTIJ), ISSN: 2250-3498,

Vol.3, No.4, August 2013

Optimization of Flood fill algorithm using

Look-Ahead Technique

Garima Vipul Aggarwal

Deptt. Of CSE Deptt. Of CSE
BPIT, Delhi, India BPIT, Delhi, India

Abstract— In this paper further optimization of Flood fill (shortest) path which will allow the mouse to run in the shortest
algorithm is proposed. Our aim is to reach the center of the possible time. [7]
maze with shortest distance and in fastest time possible. With MicroMouse applies the knowledge from different fields, such as
the present work, a Micromouse traverses a maze of unknown computer science, computer engineering, electrical engineering,
dimensions by travelling the shortest path, irrespective of and mechanical engineering. It is a great opportunity to utilize
looking the path that exists beyond it, thereby increasing time interdisciplinary theoretical fundamentals to create a physical
complexity. Combining Flood Fill algorithm with Look Ahead project. [7] The contributions to this paper are thus twofold.
technique, time optimization is achieved by not allowing the Firstly, to design and develop the optimizing techniques (time and
Micromouse to travel those paths beyond which no further distance) for Flood fill algorithm and secondly to integrate Look
route(s) exist. A performance comparison has been done with Ahead technique with flood-fill algorithm as it will help in
normal flood fill execution, line follower algorithm, and look optimization of distance traveled and time taken. This paper spans
ahead alone. The results show that it can significantly span across two major searching techniques, i.e. Look-Ahead
improve the performance which in turn will help in technique and Flood-Fill algorithm. The concept has been coined
improving the performance of flood fill algorithm. as Flood-Ahead Algorithm.
This paper is organized as follows. In the first section, brief
introduction about the motivations for the research and
Keywords- flood-fill algorithm; flood-ahead algorithm, IR
development of MicroMouse optimization is presented. In the
sensors.
second section literature review of earlier proposed techniques are
shown. The third section comprises of the framework that we
have proposed for our entire Micromouse system to optimize the
I. INTRODUCTION time complexity. In section four, details about the dataset used i.e.
------ is explained. In section five and six the experiments
The micromouse is a miniature robot designed to race inside a conducted and subsequent performance evaluation are shown.
maze from a starting point to the destination. A maze is a tour Finally, at the end of this paper we conclude and give suggestions
puzzle in the form of a complex branching passage through which for future work in this field.
the solver must find a route. Along the way, there are walls and
rooms with hedges that micromouse has to go through and decide
the shortest and fastest way the reach the destination. The II. RELATED WORK
destination is at the centre of the maze. [7]
In order to make the micromouse navigate properly to reach the Many researchers have contributed in the field of Artificial
destination inside the maze, it must be equipped with at least Intelligence optimizing the flood fill algorithm. The core
sensors, microcontrollers and motors. The most important algorithm was given by Lee [1]. After analyzing it, we saw that it
equipment inside the micromouse is controller that must be was a Breadth First Search (BFS) algorithm; an application to
programmed with software to ensure micromouse making wise Dijkstra’s algorithm. But its drawback was that it suffered from
decision and navigating smoothly. What determines micromouse huge memory requirements and slow performance. Many other
is making wise decision using software algorithm inside the authors have contributed in this area. In [2], the authors tried to
microcontroller. Developing algorithm for the micromouse improvise the Ackers [3] algorithm in which a two bit encoding
ultimately controls the autonomy positioning of the robot. [8] To technique was used per cell instead of saving the real distance.
accomplish this task, the micromouse needs to map the maze The authors proceeded in two phases: The filling phase: here they
through intelligent exploration, and then track the optimal filled the neighboring cells to the starting point (S) with a one; the
next cells were marked with two (these values are the distance of
each cell from the source). They repeated this till they reached the

670
 IRACST – Engineering Science and Technology: An International Journal (ESTIJ), ISSN: 2250-3498,
Vol.3, No.4, August 2013

target point (T). Retrace phase: If the target was reached in step I, It is divided into two phases:
they traced their way back by going to the cell with value I-1. A. Initial Framework
They repeated this till they reached the starting point S. But this B. Proposed Framework
algorithm did not provide viable results for every maze. Hence,
lead to its drawback. Consequently, an update procedure is used A. INITIAL FRAMEWORK
to modify the last search without re-starting. This technique is
known as the Modified Flood Fill algorithm [4], which again is Here we throw light on the existing techniques and algorithms
widely used by micromouse contesters. In [5], the authors used being used contemporarily, i.e. Flood Fill algorithm and Look
three approaches primarily. The wall follower logic: This worked Ahead algorithm.
on the rule of following either left wall or right wall continuously
until it lead to the center. The micro mouse sensed the wall on the 1.) FLOOD FILL ALGORITHM
left or right, and followed it to wherever it lead until the center
was reached. This simple logic used for solving the maze. Flood fill, also called seed fill, is an algorithm
Mathematical approach: Here, they had an array of 16 rows and that determines the area connected to a given node in a multi-
16 columns. If the array was denoted by M, then each cell was dimensional array. It is based on Bellmen- Ford algorithm. The
represented by M[R][C]. They assumed the present position of flood fill algorithm is one of the most popular algorithms used for
array as M2 [R2] [C2], the previous position as M1 [R1] [C1], maze solving. It combines both solution speed and easy handling
and the next position as M3 [R3][C3]. Now they proceeded as of locations to give a quick solution to the maze concerned. The
follows: basic idea behind the algorithm is to imagine one pouring water
down the destination cell and to follow the path of flow of the
If R2-R1>0, then it is currently moving straight, upwards through stream. The water will flow and cover all cells one by one until it
the maze array. reaches the destination cell. The solution is the path of water from
If R2-R1<0, then it is currently moving straight, downwards the source to the destination. The algorithm works as follows:
through the maze array.
If C2-C1>0, then it is currently moving rightwards, through the 1.1 Each cell is assigned a value which indicates its distance
maze array. from the destination cell. Thus the destination cell is assigned a
If C2-C1<0, then it is currently moving leftwards, through the value 0.
maze array. 1.2 Any open neighbor to the destination cell is assigned a
value 1. Similarly, all the open neighbors to the current set of
Depth-First algorithm: Depth- First search was an intuitive open neighbors are assigned a value 2 and so on.
algorithm for searching a maze in which the mouse first started 1.3 The value of the cell therefore is an indication of how far we
moving forward and randomly chose a path when it came to an are from the destination. Any cell will have at least one adjacent
intersection. If that path leads to a dead end, the mouse returned cell holding a value one less than the current value.
to the intersection and chose another path. This algorithm forced 1.4 To find the solution one has to simply follow the path
the mouse to explore each possible path within the maze, and by of decreasing values from their current position, it is assured
exploring every cell, the mouse eventually found the center. It that they will reach the destination. This has been taken from
was called “depth first” [6] because if the maze was considered a [2].
spanning tree, the full depth of one branch was searched before
moving onto the next branch. The relative advantage of this Dynamic flood fill algorithm: It is the basic method to flood fills a
method was that the micromouse always found the route. maze. If we have all the wall information, then all we need to do
Unfortunately the major drawback was that the mouse did not is follow the numbers from the current value till machine reaches
necessarily find the shortest or quickest route and it wasted too zero. Let’s say we start from 10, then jump to the neighboring cell
much time exploring the entire maze. that has value 9, and then to 8 and so on. But when we start our
Different researchers have tried in the area of optimization of machine for the first time it has no information of walls and its
various algorithms of micromouse. But if their technique were memory is completely clean. Assume there are no walls. Now
simple, the time complexity of the algorithm was too large and if flood fills the maze. Jump to the neighboring cell with one value
the time complexity was minimal, then the technique used was less than the current cell. Use sensors to read the walls and update
not practically possible. Till date the best algorithm to execute the the maze. Again flood fill and jump to the neighboring cell with
program of micromouse has been the flood fill algorithm. In our one value less than the current cell. Go on doing this till we reach
paper we have tried to further optimize the flood fill algorithm to the destination. By this method we need not follow the shortest
provide better results. We have proposed a framework in which a path when we run the machine for the first time. Repeat the steps
cell looks ahead (for the cells with and without walls) every time and come back to start position. Again follow these steps. But this
it follows the flood-fill path. It helps the MicroMouse o eliminate time we have more wall information and so we will go by a
those nodes where dead end exists and thereby optimizing the different path (this too may not be the shortest). Eventually may
distance travelled and the time taken. be in 3rd - 4th run) we will have enough wall information (need
not have all wall information) and we will follow shortest path.

III. FRAMEWORK 2.) LOOK-AHEAD ALGORITHM

671
 IRACST – Engineering Science and Technology: An International Journal (ESTIJ), ISSN: 2250-3498,
Vol.3, No.4, August 2013

In backtracking algorithms, look ahead is the generic term for 14. Compare the values in the unblocked neighboring cells of
a sub-procedure that attempts to foresee the effects of choosing (X, Y).
a branching variable to evaluate or one of its values. The two 15. Move micromouse to the cell which has the minimum value
main aims of look-ahead are to choose a variable to evaluate next and is closest to the centre i.e. (0, 0).
and the order of values to assign to it. Look Ahead algorithm 16. Repeat these steps until micromouse reaches at the centre
incurs extra cost for assigning values as it needs to propagate of the maze.
constraints. Look ahead algorithm; helps to restrict the search
space significantly as it remove values from future domains
which does not suit the context. Look Ahead algorithm has no
change on worst case performance but it can significantly reduce
the amount of path traversed by the MicroMouse in best case.

B. PROPOSED FRAMEWORK

In our proposed framework we have combined Look Ahead

algorithm with the existing Flood Fill algorithm to achieve
optimization of distance and time. Modified version of Flood Fill
algorithm helps us to put a constraint forward to check whether
another variable can take a consistent value. In other words, it
first extends the current partial solution with the tentative value
for the considered variable. By combining the above two
algorithms we aim to evaluate nodes ahead of the current node
where MicroMouse has to (will) travel. In our framework, nodes
with walls (sensed through IR sensors) ahead of them will be
eliminated and it will lead to optimum path utilization.
Figure 1 indicates the working of flood-ahead algorithm. It shows
that how the micromouse when kept at the starting of the maze
reaches at the center using most optimum path and in minimum
time. It uses the flood-ahead technique wherein each cell does not
look only for its neighboring cell but also the cells of its
neighbors to get the most optimum path.

ALGORITHM OF FLOOD-AHEAD

1. Set micromouse at the starting of the maze, say (X, Y).

2. Check if cell (X+1, Y) is blocked. If yes, then ignore this
path.
3. If no, then check if the neighbors of this cell are blocked. If
yes, then ignore this path.
4. If no, then go to step 14.
5. Check if cell (X, Y-1) is blocked. If yes, then ignore this
path.
6. If no, then check if the neighbors of this cell are blocked. If
yes, then ignore this path.
7. If no, then go to step 14.
8. Check if cell (X, Y-1) is blocked. If yes, then ignore this
path.
9. If no, then check if the neighbors of this cell are blocked. If
yes, then ignore this path.
10. If no, then go to step 14.
11. Check if cell (X, Y-1) is blocked. If yes, then ignore this
path.
12. If no, then check if the neighbors of this cell are blocked. If
yes, then ignore this path.
13. If no, then go to step 14.

672
 IRACST – Engineering Science and Technology: An International Journal (ESTIJ), ISSN: 2250-3498,
Vol.3, No.4, August 2013

The electronic design centers on a Microchip processor. The

PIC16F877 has 5 ports that make our interface with external
hardwareseasier.PIC could be interfaced with external EEPROM
memory to facilitate extensive programming. To keep the
hardware small and compact, the inbuilt EEPROM code memory
of 8k was used for programming and the data memory of 256
bytes were used for runtime memory map storage. Other data
storage requirements are implemented on the 256 byte RAM. The
processor is the only onboard programmable chip, other
peripherals included a Schmitt trigger IC 74HC14N.the voltage
levels from the sensors were a change from 1.45v to 0.25 volts
when an obstacle was detected. The inverting Schmitt trigger was
interface to bring the detecting signal to TTL logic.

B. STEPPER MOTOR
A defining characteristic of a stepper motor is that, under normal
circumstances, it is made to take up and hold one of a number of
fixed positions. Movement from one of these positions to another
is only by stepping it through a series of intermediate positions. A
typical stepper motor might have 200 such positions in a single,
complete rotation of the drive shaft. With little effort, this can be
increased, on the same motor, to 400 steps. [8]

C. IR SENSORS
A defining characteristic of a stepper motor is that, under normal
circumstances, it is made to take up and hold one of a number of
fixed positions. Movement from one of these positions to another
is only by stepping it through a series of intermediate positions. A
typical stepper motor might have 200 such positions in a single,
complete rotation of the drive shaft. With little effort, this can be
increased, on the same motor, to 400 steps. [8]

V. PERFORMANCE EVALUATION

Performance evaluation is the key aspect of undertaking any

research work. So we have evaluated our work and finally
concluded by elaborating the efficiency of our work. But before
discussing our execution, we first give an overview of the work
done and then its relevant efficiency.
The existing framework makes the MicroMouse move towards
centre from the starting point. The maze is number in an
increasing order as we move from centre to the outside of the
maze. The MicroMouse then observes the neighborhood cells and
the number assigned to them to move forward in the maze.
However, it does not intelligently scan the neighboring cells to
move forward and hence produces ambiguity in obtaining the
most optimal path.
Optimizing the given problem statement means applying and
integrating the exiting techniques with other techniques to
produce more optimal results. An optimized e of solution has
been presented in this section.
Figure1: Flow chart of flood ahead algorithm [9]
The following snapshots are from the earlier execution of
MicroMouse using flood-fill algorithm:

IV. DATASET

A. MICROPROCESSOR

673
 IRACST – Engineering Science and Technology: An International Journal (ESTIJ), ISSN: 2250-3498,
Vol.3, No.4, August 2013

Figure 2(a): Execution of flood fill Figure 3(a): Execution of flood ahead

Figure 3(b): Simulation of flood ahead

Figure 2(b): Simulation of flood fill
Clearly, flood-ahead algorithm results in lesser number of steps
the MicroMouse has to travel. Also, as distance is directly
In the above snapshots we can clearly see the ambiguities arising proportional to time, MicroMouse will take lesser time to reach
wherein the MicroMouse has to travel extra distance to reach the the destination, thereby reducing time complexity as well.
centre. The working of flood-ahead algorithm in the above snapshot, in
place of ambiguity is explained as follows:
On applying flood-ahead algorithm, not only we helped in saving
the distance travelled by MicroMouse but also saved the time to
reach the centre (destination). The following screen shots show
the execution of flood-ahead algorithm:

674
 IRACST – Engineering Science and Technology: An International Journal (ESTIJ), ISSN: 2250-3498,
Vol.3, No.4, August 2013

problem is given to the decision maker, he not only looks out

for the possible steps which can be taken, but also the possible
solutions in the second level of the problem. That is why it is
called look ahead i.e., to look ahead for the best possible path.
On the other hand, in flood ahead algorithm, the micromouse
makes an intelligent and decisive choice by not only
considering the second level solution of the problem, but also
ensuring that the first level solution is the cell having the
minimum value and at least one neighbor of that cell should
not be blocked further and should be closer to the center of the
maze.
Figure 4: Ambiguity resolution through flood ahead

In the above figure as the MicroMouse travel from cell 23 to 25,

i.e. towards the centre it follows the wrong path as there is a dead The flood-ahead algorithm integrates the Flood fill algorithm and
end ahead of it. In the proposed flood-ahead algorithm the the look-ahead condition. Like in Flood fill algorithm, it
MicroMouse will follow the natural steps of Flood-Filling compares the cell values of the neighboring cells. But before
algorithm but will travel lesser steps. The MicroMouse halts at going any further, it estimates whether the path beyond the
cell 26 and look ahead for a clear path ahead. On receiving false neighboring cells is available or not. It also uses the look ahead
Boolean value, as there is a wall (sensed by IR sensors) head of
condition wherein its decision making also depends on the
cell 29, it will not traverse the additional four steps it would have
traversed earlier (26-27-29-27-26). Hence, saving the time and condition that which cell is closer to the center of the maze.
minimizing the distance the MicroMouse will have to travel.
Flood-Ahead algorithm optimizes the distance, by eliminating the
miscalculated steps; the MicroMouse has to travel to reach its CONCLUSION AND FUTURE WORK
destination.
In this paper, we have proposed an efficient way to optimize the
path micromouse has to travel to reach the center of the maze.
VI. PERFORMANCE COMPARISON The experimental results obtained in the above figures showed
that the proposed work decreased the distance micromouse
Now the performance comparison between various execution travelled. Also, the time taken by micromouse to reach the center
techniques is given below for easy understanding: was less compared to other algorithms. With the proposed work,
the effectiveness of optimization has been studied carefully.
A. LINE FOLLOWER AND FLOOD AHEAD Further investigation to the topic reveals that flood-ahead
algorithm can give good results. The concept has been worked out
In line follower algorithm, the micromouse blindly moves and can be used in future with flood fill algorithm.
forward in a straight line in the maze without using any
intelligence. This algorithm has a large time complexity as the
micromouse does not foresee what is coming in its way. Whereas, ACKNOWLEDGEMENT
in flood-ahead algorithm, the micromouse intelligently and
cautiously moves forward while calculating the minimum We take this opportunity to express our sincere thanks and deep
distance it has to traverse to reach the center gratitude to all those who extended their wholehearted
cooperation and have helped us in completing this work
B. FLOOD FILL AND FLOOD AHEAD successfully. We express our sincere thanks to Mr. Suyash Gupta
ALGORITHM (DTU) for his encouragement and valuable suggestions
In flood fill algorithm, the micromouse intelligently moves
forward without estimating whether there is a path ahead or not. It
compares the cell values of the neighboring cells and moves to REFERENCES
the cell with the least value. On the other hand, the flood-ahead
[1] Lee, C.Y., "An Algorithm for Path Connection and its
algorithm not only compares the value of neighboring cells, but it Applications", IRE Transactions on Electronics Computers, 1961.
also foresees whether there is path available ahead or not.
[2] Ahmed N. Mosa Ayman M. Saad Moustafa A. Mohamed,
C. LOOK AHEAD AND FLOOD AHEAD "MicroMouse: An Intelligent Maze Solver Robot" IEEE Egypt
ALGORITHM section, September 2005.

Flood-ahead is an algorithm whereas, look ahead is a [3] Akers, S.B., "A Modification of Lee's Path Connection
Algorithm", IEEE Transactions of Electronics Computers,
condition. According to the look-ahead condition, whenever a
February 1967.

675
 IRACST – Engineering Science and Technology: An International Journal (ESTIJ), ISSN: 2250-3498,
Vol.3, No.4, August 2013

[4]http://www.micromouseinfo.com/introduction/mfloodfill.html[
accessed on July 2013]

[5] Sandeep Yadav, Kamal Kumar Verma, Swetamadhab

Mahanta, "The Maze Problem Solved by Micro mouse",
International Journal of Engineering and Advanced Technology
(IJEAT)
ISSN: 2249 – 8958, Volume-1, Issue-4, April 2012.

[6] Gorden Mc Comb, Myke Predko,“Robot Builder’s Bonanza”,

Mc-Graw Hill, 2006 [accessed on July 2013]

[7] Work in Progress – Undergraduate Interdisciplinary Research

– IEEE Micromouse Competition, Robert D. Milos, Allan J. Hall,
Neal Shine, Kyle D. See, Tyler R. Bednarz, Yonglian Wang;
Department of Electrical and Computer Engineering and
Computer Science Ohio Northern University[accessed on July
2013]

[8]http://www.google.com/url?q=http%3A%2F%2Fmadan.wordp
ress.com%2F2006%2F07%2F24%2Fmicromouse-maze-solving-
algorithm%2F&sa=D&sntz=1&usg=AFQjCNF0x7vp7y7STl2vZ-
PVHlyu4f6fcQ

[9] http://en.wikipedia.org/wiki/Micromouse [accessed on July

2013]

AUTHORS PROFILE

Garima was born in 1991 in New Delhi, India. She has

completed her B.Tech in Computer Science and Engineering from
Bhagwan Parshuram Institute of Technology, IP University,
Delhi, India. Her areas of interests include Artificial Intelligence,
Digital forensics and Data mining.

Vipul Aggarwal was born in 1991 in New Delhi, India. He has

completed her B.Tech in Computer Science and Engineering from
Bhagwan Parshuram Institute of Technology, IP University,
Delhi, India. His areas of interests include Artificial Intelligence,
Data warehousing and C++Programming.

676