First, find all
articulation points,
i.e. fields that, when taken, separate the remaining empty fields,
shown in green, lighter green for those articulation points which we can
reach directly (without going through another articulation point first).
This is done using graph.h,
graph.cc,
based on
Graph Algorithms: Applications.
We decide on which articulation point to take using the
maxsteps function. Here, the
one at the bottom left is the best choice.
First, we build the shortest path from the current
position to the destination, which is obtained cheaply with
a
breadth-first search, implemented with a queue to avoid
recursion.
Now comes the "stretching rubber-band" algorithm
(expand.h,
expand.cc): given a path (shown in pink)
from source (our current position) to destination,
try to expand that path to fill more adjacent empty fields.
We start with the first two fields of our path, and check if both
adjacent fields to the right or left are still free.
Here, only the fields on the left (from the perspecitive of the bot
walking the path) are free (shown in purple).
In this case, the initial path is SSSSWWNNW. We can expand the beginning SS into SESW and keep the remaining path, filling two more fields and gaining two more steps to walk.
We keep repeating this, as long as we find two free adjacent fields
along the path.
This produces a quite recognizable fill pattern, which is visible here, for example (click on image to view interactively):
I also wrote a more complex version of the expand function which not only tries to expand into two adjacent free fields along the path, but also finds longer connections between two adjacent free fields. This finds expansions around obstacles. It turned out to be quite a bit slower, though, and it made a difference only on very few maps (where I was isolated in an area with only narrow ways around obstacles). You can view this version here.