MathCS - Robotics

Challenge: Wavefront Algorithm

The Wavefield Algorithm

An N x M board denotes a room where a X at position (x,y) indicates an obstacle. The algorithm finds a path avoiding the obstacles from point A to point B. For example, a room might look like this:

.  .  .  .  .  X  .  .  .  .  .  .  .  .  X  B
.  .  .  .  .  X  .  .  .  .  .  .  .  .  X  .
.  .  .  .  .  X  .  .  .  .  .  .  .  .  X  .
.  .  .  .  .  X  .  .  X  X  X  X  .  .  X  .
.  .  .  .  .  X  .  .  X  .  .  .  .  .  X  .
.  .  .  .  .  .  .  .  X  .  .  .  .  .  X  .
.  .  X  X  X  .  .  .  X  .  .  .  .  .  .  .
.  .  .  .  .  .  .  .  X  .  .  .  .  .  .  .
A  .  .  .  .  .  .  .  X  .  .  .  .  .  .  .

You may assume that:

The wavefront algorithm involves a breadth first search of the graph beginning at the destination point until it reaches the start point. First, obstacles are marked with a 1 and your goal point is marked with a 2. You can optionally surround the entire world with 1s as well to tell your robot to avoid those squares, and/or "expand" the size of the obstacles to avoid collisions due to dead-reckoning errors.

.  .  .  .  .  1  .  .  .  .  .  .  .  .  1  2
.  .  .  .  .  1  .  .  .  .  .  .  .  .  1  .
.  .  .  .  .  1  .  .  .  .  .  .  .  .  1  .
.  .  .  .  .  1  .  .  1  1  1  1  .  .  1  .
.  .  .  .  .  1  .  .  1  .  .  .  .  .  1  .
.  .  .  .  .  .  .  .  1  .  .  .  .  .  1  .
.  .  1  1  1  .  .  .  1  .  .  .  .  .  .  .
.  .  .  .  .  .  .  .  1  .  .  .  .  .  .  .
A  .  .  .  .  .  .  .  1  .  .  .  .  .  .  .

To create the "wave" of values, begin at the destination, and assign a distance of 3 to every empty square adjacent to the goal. Then assign a distance of 4 to every empty square adjacent to the squares of distance 3. Continue to do this until you reach the start point.

23 23 23 23 23  1 17 16 15 14 14 14 14 14  1  2
23 22 22 22 22  1 17 16 15 14 13 13 13 13  1  3
23 22 21 21 21  1 17 16 15 14 13 12 12 12  1  4
23 22 21 20 20  1 17 16  1  1  1  1 11 11  1  5
23 22 21 20 19  1 17 17  1 13 12 11 10 10  1  6
23 22 21 20 19 18 18 18  1 13 12 11 10  9  1  7
23 22  1  1  1 19 19 19  1 13 12 11 10  9  8  8
23 23 22 21 20 20 20 20  1 13 12 11 10  9  9  9
 A 23 22 21 21 21 21 21  1 13 12 11 10 10 10 10

Once this is complete, you can simply follow the numbers in reverse order until you reach the goal, avoiding any square with the value 1. Here is one possible path avoiding the obstacles (you may allow diagonal movement if you wish).

23 23 23 23 23  1 17 16 15 14 14 14 14 14  1  |
23 22 22 22 22  1 17 16 15 14 13 13 13 13  1  |
23 22 21 21 21  1 17  | -- -- -- -- -- 12  1  |
23 22 21 20 20  1  | --  1  1  1  1  | 11  1  |
23 22 21 20 19  1  | 17  1 13 12 11  | 10  1  |
23  | -- -- -- -- -- 18  1 13 12 11  | --  1  |
 | --  1  1  1 19 19 19  1 13 12 11 10   | -- --
 | 23 22 21 20 20 20 20  1 13 12 11 10  9  9  9
 A 23 22 21 21 21 21 21  1 13 12 11 10 10 10 10

To ensure your robot avoids the obstacles, in particular if you allow diagonal movement, you could extend them with additional 1's prior to running your algorithm.

Scoring:

Sample Movies