HTML5 game publishing

Territory Capture in JavaScript: Flood Fill to Claim a Loop

Grid of owners, trails, and a flood fill from the outside that claims whatever the loop encloses. Bounding boxes, 4-neighbour leaks, stealing land and the tests worth writing.

PlayKovo Team5 min read
Games currently available on PlayKovo. Open a title to see its current listing.

In a territory-capture game, a player leaves their land, draws a trail, comes back, and everything inside the loop becomes theirs. The moment of closing the loop is the whole game, and it is a small algorithmic problem with a couple of traps. This post explains how to compute "what is inside the loop" on a grid, how to make it fast enough for large maps, and the edge cases that cause the strangest bugs in these games.

Model the map as a grid of owners

Use a flat array where each cell holds an owner id, 0 for nobody. Keep trails separate from territory, since a trail cell belongs to a player's current path rather than to their land:

const W = 200, H = 200;
const owner = new Uint8Array(W * H);   // 0 = free, 1..N = player
const trail = new Uint8Array(W * H);   // 0 = none, 1..N = player's trail

const idx = (x, y) => y * W + x;

Typed arrays are compact and cache-friendly, which matters when you may process tens of thousands of cells in a frame. A 200 by 200 map is only 40,000 cells per array.

The trail leaves and returns

Each frame, the player moves one cell (or a fractional amount that you map to cells). Three cases:

  • The player is on their own land. No trail is drawn. If they were drawing one, this is the moment they close it.
  • The player is on free or enemy land. Mark the cell as part of their trail.
  • The player touches a trail. If it is their own, they are eliminated. If it is another player's, that player is eliminated.

Decide up front whether collisions are tested per cell or per fractional position, because mixing the two produces players who survive "through" a trail by moving fast. At high speed, test every cell the player crossed this frame, not only the one they ended on.

Filling the loop: flood fill from the outside

When the loop closes, the cells inside are those you cannot reach from the outside without crossing the trail or the player's own land. The cleanest way to compute that is to fill from the outside, then claim everything that was not reached:

  1. Treat the trail cells and the player's own territory as walls.
  2. Start a flood fill at every border cell of the bounding box that is not a wall.
  3. Mark everything reached as "outside".
  4. Every cell inside the bounding box that is not a wall and not outside is enclosed. Claim it.
  5. Convert the trail cells to territory.
function closeLoop(p, minX, minY, maxX, maxY) {
  const outside = new Uint8Array(W * H);
  const stack = [];
  const blocked = i => trail[i] === p || owner[i] === p;

  const push = (x, y) => {
    const i = idx(x, y);
    if (!outside[i] && !blocked(i)) { outside[i] = 1; stack.push(i); }
  };
  for (let x = minX; x <= maxX; x++) { push(x, minY); push(x, maxY); }
  for (let y = minY; y <= maxY; y++) { push(minX, y); push(maxX, y); }

  while (stack.length) {
    const i = stack.pop();
    const x = i % W, y = (i / W) | 0;
    if (x > minX) push(x - 1, y);
    if (x < maxX) push(x + 1, y);
    if (y > minY) push(x, y - 1);
    if (y < maxY) push(x, y + 1);
  }
  for (let y = minY; y <= maxY; y++)
    for (let x = minX; x <= maxX; x++) {
      const i = idx(x, y);
      if (!outside[i]) { owner[i] = p; trail[i] = 0; }
    }
}

The bounding box is the key optimization. You only scan the rectangle that contains the trail and the land it touches, not the whole map. For a typical loop that is a small fraction of 40,000 cells. Use a 4-neighbour fill. An 8-neighbour fill would leak through diagonal gaps in a trail, which is a classic bug.

Make sure the bounding box includes a one-cell margin around the trail, so there is always a free ring to start the fill from. Otherwise a loop that touches the box edge can seal itself and the fill finds no outside.

Stealing land from other players

Capturing includes enemy land inside the loop. Because the fill treats only the player's own cells as walls, enemy territory inside the loop is not marked outside, so it becomes yours automatically. Their cells change owner and you decrement their score. If you want a rule such as "you cannot take someone's last cell", enforce it after the fill.

Two harder cases:

  • A loop that cuts an enemy's trail. Eliminate that player, clear their trail, and decide whether their land stays on the map or disappears. Games differ, and both are valid.
  • Two loops closing in the same frame. Process players in a fixed order, or use a rule such as "larger area wins". Pick one and test it, since an arbitrary order produces unfair deaths.

Performance on busy maps

  • Do the fill only when a loop closes, not every frame. It is event-driven.
  • Reuse the outside buffer. Allocating a fresh array each closure creates garbage. Keep one and clear only the bounding box. See garbage collection and memory leaks in JavaScript games.
  • Use an explicit stack, not recursion. A recursive fill overflows the call stack on large regions.
  • Move heavy fills off the main thread if maps are huge. See Web Workers for heavy game logic.
  • Render only changed cells. Keep a dirty list rather than redrawing the whole grid.

Rendering the result

A pop-in animation, where newly claimed cells rise from the ground, is a small touch that makes closure feel rewarding. Store the claim time per cell and animate over a few hundred milliseconds. Avoid doing the animation inside the fill itself. The logic should finish instantly, and the animation should be a separate visual layer. For more on feedback like this, see game feel and juice.

Test cases worth writing

  1. A simple rectangle loop. All inside cells are claimed, none outside.
  2. A loop with a thin diagonal gap. Confirm it does not leak.
  3. A loop that encloses an enemy's whole territory.
  4. A loop that touches the map edge.
  5. A loop where the trail crosses itself. The player should be eliminated, not rewarded.

If you want to see how the genre plays from the other side, our guide to territory capture games covers five of them.

We use optional cookies for site analytics and site advertising. You can change your choice later. Privacy policy.