Author Topic: Implement breadth-first in C++  (Read 7450 times)

0 Members and 1 Guest are viewing this topic.

2easy4sam

  • Newbie
  • Posts: 4
Implement breadth-first in C++
« on: 06 January, 2013, 07:07:51 PM »
Hi all,

I am new to maze-solving and currently self-learning C++. I'm working on a project that requires coding in C++ for the Finch robot (http://www.finchrobot.com/) so that it knows how to find its way out of a maze.
So far, I have programmed the wall follower and the random algorithm, since these are the two easiest ones, and I would like to implement the breadth-first algorithm as well, though I'm not sure how I should go about it. I have read that breadth-first is a strategy for searching in a graph (http://en.wikipedia.org/wiki/Breadth-first_search), and I assume that my robot will need to know the following (correct me if I'm wrong):

1) where the start and end cells are
2) the cells it has visited and their accessible neighbours
3) its current coordinate in the maze (treat the maze as a matrix I'd imagine)

Now, suppose I have a 6*6 maze like this:


at the start, my robot knows nothing but the coordinates of S and F. With breadth-first, what would it do when it's in the centre cell (row 4, col 3), i.e. the one that has 4 neighbours (I'm not considering diagonal adjacency)?

Can someone give me a sample code snippet of breadth-first in C++? Many thanks in advance!

timfoden

  • phpBB Member
  • *****
  • Posts: 37
Re: Implement breadth-first in C++
« Reply #1 on: 07 January, 2013, 09:44:43 AM »
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:

Code: [Select]
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 )
return path

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.

Cheers, Tim.

2easy4sam

  • Newbie
  • Posts: 4
Re: Implement breadth-first in C++
« Reply #2 on: 08 January, 2013, 03:57:33 PM »
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:

Code: [Select]
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 )
return path

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.

Cheers, Tim.

Thank you Tim! it surely helps me a lot :)

Micromouseonline Forum

Re: Implement breadth-first in C++
« Reply #2 on: 08 January, 2013, 03:57:33 PM »