First, find all
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.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.