The first major algorithm problem is how to generate loops. Here is what I came up with.
The algorithm in summary is as follows.
- Choose a starting point, giving preference to hexes with fewer free edges. Initially this will pick the rim corners.
- Make an outward leg, again selecting hexes with fewer free edges. This will tend to hug the rim.
- At each step use A* search to make sure there is a way back home.
- After reaching the desired path length, use the A* search to head for home and close the loop.
The final result looks like this.
At this point I found a major bug. Occasionally it looks like this.
Why? It turns out that this implementation of the A* algorithm has no protection against paths that cross themselves.
Think about the Fedex algorithm: assuming trucks that drive on the right, Fedex found that it is cheaper to make three right turns rather than one left. If you set up a movement cost based on that rule it will generate paths that cross and break this implementation of the algorithm. Back to the drawing board!