Let me try explaining flood-fill...
In this method you need to have an array(say ff[][]) that stores the floodfill values which represent distances from the goal.
define a flood function that does the following steps:
1.Initialize all ff[][] to 255
2. Say your target cordinates be TX,TY. Then assign ff[TX][TY]=0
3. Implement a
queue. Push the target co-ordinates into the queue.
Repeat the following steps untill the queue is empty.
4.Pop an element from the queue.Say its co-ordinates be RX,RY.
5.Now look for cells that are accesible from RX,RY using the wall information.
If the flood-fill value of that cell is 255 then assign ( ff[RX][RY]+1 ) as the new flood-fill value and also push that cell into the queu.
now i wanna ask suppose the maze is completely unknown then how do u navigate the maze
*In the beginning, you don't have any wall information. You only know the target co-ordinates.
*Assume that there are no walls. Now flood the maze using the above algorithm.
*Find the cells that are accessible from the cell your bot is currently present.
Move to that cell that has the minimum flood-fill values among these cells. If there are more than one cell with minimum value, give preference to your front cell, left cell, right cell and then the behind cell.
*Upon reaching the new cell, you may have find new walls. Update your wall information, and again flood the maze using the new wall information and follow the above method to choose the next cell.
*Do the above procedure until you reach your target cell.
Based on your present wall information, the shortest path as calculated can have some cells that are unvisited. Your strategy should be to visit these cells, before you make your fast run. You can also develop other strategies.
See this page. It describes the flood-fill and some other algos:
http://www.micromouseinfo.com/introduction/software.html
