Basically the maze exploration algorithm that includes breadth-first search (flood fill) works like this.
1. Initilialise a maze with only the outside walls, and the walls you know from the start cell. All other walls are assumed to be absent at this point.
2. Perform a flood fill to find a path from the current cell to the finish. Until more walls are learned, this will produce an optimistic path that may not be completely valid, but the 1st node in the path will always be valid.
3. Move to the next adjacent cell indicated from the path found in step 2.
4. Learn the walls in the new cell.
5. If the current cell is not the finish, go back to step 2 again.
6. Finished... the mouse is now at the finish cell.
I don't have any simple code for flood fill in C++ to hand, but I do have some that's in Python. Perhaps it will be enough to illustrate Step 2 from the above list:
def flood( from, curDir, toList ):
# flood fill to find costs to accessible areas
SIZE = 16 * 16
MAX_COST = 9999
cost = [MAX_COST for pos in range(SIZE)]
edge = toList
for pos in edge:
if pos != from:
cost[pos] = 0
while len(edge) != 0 and cost[from] == MAX_COST:
newEdge = set()
for pos1 in edge:
for dir in range(4):
if not isWall(pos1, dir):
pos2 = nextPos(pos1, dir)
if pos2 and cost[pos2] > cost[pos1] + 1:
newEdge.add( pos2 )
cost[pos2] = cost[pos1] + 1
edge = newEdge
# backtrack path
path = 
while cost[from] != 0:
bestCost = MAX_COST
for dir in range(4):
if not isWall(from, dir):
pos2 = nextPos(from, dir)
if pos2 != None and bestCost > cost[pos2]:
bestCost = cost[pos2]
bestPos = pos2
from = bestPos
path.append( from )
Hopefully the two functions referenced (but not supplied above), isWall() and nextPos(), will be fairly self explanitory. The to parameter toList is a list as all 4 locations are used when searching for the centre.
So not only does the code need to 'flood' the maze, it also needs to backtrack to extract the path for the robot to follow.
NOTE THAT: This code actually 'floods' from the destination to the start, so that the backtracking produces the final output path in start to finish order.