Zone of Control pathfinding

 from Red Blob Games
17 May 2019

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:

  1. The hexes adjacent to an enemy are controlled by it.
  2. 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

Email me , or tweet @redblobgames, or comment: