Someone asked me about pathfinding for Civ V's zone of control. I looked through the examples on this guide[1] and tried to implement something. Place the enemies, and see where your player can move.
The rules are:
- The hexes adjacent to an enemy are controlled by it.
- If you step into a hex controlled by some enemy, and then you step into another hex controlled by that same enemy, you can't move anymore.
In the initial example map, there's a gap in the north where you can step from one enemy's zone of control into another's. There's a gap in the south where you can make the step but you lose all your remaining movement points.
The algorithm is two phases. First, we run breadth first search N-1 steps. The graph edges are (a) free → free, (b) free → controlled, (c) controlled → not controlled by the same enemy (this could be either free, or controlled by someone else). Then the second step is to run 1 final round of breadth first search, but allow any movement, without the zone-of-control restrictions. Source: zone-of-control-paths.js