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:
- start is on the left side
- there is no obstacle in a distance of 2 from the start
- stop is on the right side
- there is at least one possible path
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
- Wavefront Sample Movie