floodfill algorithm
May be this is the most famous or
easiest algorithm for maze solving . Cells are assigned distance
values indicating how far they are from the destination.
Click here for my source code MM4.cpp,
compile this file with Turbo C++. Sample maze is put in the main()
code itself, make changes in it to create your own maze.
basic floodfill steps
1). Give 0 value to the destination (
in our case the centre cells )
2). Give 1 value to all the cells neighboring 0 to which mouse can
move if it is at 0
3). Now give value 2 to all cells neighboring 1s, and similarly fill
up all the cells
Dynamic floodfill algorithm
That was the basic method how you
floodfill a maze. If you have all the wall info then all you need to
do is follow the numbers from the current value till machine reaches
zero. Lets say you start from 10, then jump to the neighboring cell
that has value 9, and then to 8 and so on.
But when you start your machine for
the first time it has no information of walls and its memory is
completely clean.
Assume there are no walls. Now floodfill the maze. Jump to the neighboring cell with one value less than the current cell. Use sensors to read the walls and update the maze. Again floodfill and jump to the neighboring cell with one value less than the current cell. Go on doing this till you reach the destination. By this method you need not follow the shortest path when you run the machine for the first time. Repeat the steps and come back to start position. Again follow these steps. but this time you have more wall information and so you will go by a different path ( this too may not be the shortest ). Eventually ( may be in 3rd - 4th run ) you will have enough wall information ( need not have all wall information ) and you will follow shortest path.
