S 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 G

The algorithm consists of a breadth-first search (BFS) on the graph induced by the neighborhood connectivity (adjacency) of cells, starting at G, which is assigned the value 2 at the beginning. As BFS traverses the space, each cell is assigned a value which corresponds to the number of moves required for the shortest path from that cell to the goal.

The **von Neumann neighborhood** of a cell C consists of its 4 neighbors
adjacent to the faces of the cell square:

1 4 C 2 3There are therefore 4 possible moves out of C, and C has 4 children in the graph induced by the von Neumann connectivity.

The **Moore neighborhood** of a cell C consists of its 8 neighbors
adjacent to both the faces and the corners of the cell square:

8 1 2 7 C 3 6 5 4There are therefore 8 possible moves out of C (including 4 diagnoal moves) and C has 8 children in the graph induced by the Moore connectivity.

Here is the general pseudo-code for a BFS algorithm. Note that implementations of the fringe and visited list can differ depending on what exactly you are trying to do. For example, in the wavefront planner, you can use the values of your space cells: any value > 0 has automatically been visited.

initialize: graph := {nodes}, {edges} fringe := {root} visited := empty breadth-first-search (graph, fringe, visited): while fringe not empty node := first element of fringe if node is what we are searching for return success endif //do whatever you need to do to node here children := find children of node in graph add children not in visited to back of fringe add node to visited remove node from fringe end while return failureMore on BFS (including iterative implementations) on Wikipedia and on kirupa.com.

The Wavefront planner for Lab 4 is simpler than general BFS, and should be implemented in the simplest possible way. For example, we are not searching for any particular node, but labelling the entire graph with values.

S 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 0 0 0 0 0 0 0 0 0 0 3 2The "wave" then propagates out one more step to the children of the cells marked "3", which have not already been assigned a positive value:

S 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 4 4 4 0 0 0 0 0 0 0 0 0 4 3 3 0 0 0 0 0 0 0 0 0 4 3 2And so on, until there are no more children to explore. At that point, only unreachable parts of the space (if any) will still be assigned the value of 0. The example space looks like this:

14 13 12 11 10 9 8 7 7 7 7 7 13 13 12 11 10 9 8 7 6 6 6 6 13 12 12 1 1 1 1 1 1 5 5 5 13 12 11 1 1 1 1 1 1 4 4 4 13 12 11 10 9 8 7 6 5 4 3 3 13 12 11 10 9 8 7 6 5 4 3 2In this graph, the starting position has value 14, and the goal has value 2. To plan an optimal path, you start at the goal, and at every point, until you've reached the goal, you pick the next cell that has the minimum value of all adjacent cells. For example, one good path from S to G (with each cell represented by its x,y Cartesian coordinates, starting at 0,0 in the lower-left corner):

(0,5)->(1,5)->(2,5)->(3,5)->(4,5)->(5,5)->(6,5)->(7,4)->(8,4)->(9,3)->(9,2)->(10,1)->(11,0)In principle, all choices among adjacent cells with equal values are equivalent. In practice, you may want to choose to go in a straight line over turning to prevent accumulation of angular error.

Paulina Varshavskaya, paulina [at] cs.tufts.edu