Generating loops

The first major algorithm problem is how to generate loops. Here is what I came up with.

The algorithm in summary is as follows.

  1. Choose a starting point, giving preference to hexes with fewer free edges. Initially this will pick the rim corners.
  2. Make an outward leg, again selecting hexes with fewer free edges. This will tend to hug the rim.
  3. At each step use A* search to make sure there is a way back home.
  4. 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!

This entry was posted in Arcopoly. Bookmark the permalink.

Leave a Reply
