← Labs

Coverage Wars

Drop robots on a floor plan and watch them divide it into fair territories — Voronoi coverage control, the math behind multi-robot area partitioning.

How to use

The floor loads pre-seeded with a handful of robots already relaxing into a stable partition — no input needed. Each robot owns a Voronoi cell: the region of the floor closer to it than to any other robot. Every frame the partition rebalances, and the cells breathe toward an even division of space.

  • Click empty floor to drop a new robot. Its territory carves out of its neighbors and everyone re-settles.
  • Drag a robot to move its seed; the partition re-flows under your cursor in real time.
  • Right-click a robot (or switch to Remove robot mode and click) to kill it. The survivors expand to re-cover the area it left behind.
  • The relaxation gain slider sets how aggressively each robot steps toward its cell centroid each frame — low is a slow, calm settle; high snaps to convergence.
  • Toggle the obstacle to drop a no-go rectangle the territories must flow around — no cell is allowed to claim it. Drag the rectangle’s body to reposition it, or drag a corner handle to resize it, and watch the partition re-flow around the new shape.
  • The convergence meter plots total robot travel per step. It falls toward zero as the layout settles: that decay is the optimization, made visible.

Pause stops the relaxation; while it is stopped — or if your system has reduced-motion enabled — the Step button advances the partition one relaxation iteration at a time, so you can walk it toward convergence and watch each move. Step is disabled while the animation is running, since the loop is already stepping every frame.

What you are watching

This is coverage control — the problem of spreading a team of robots so that every point of an area is as close as possible to some robot. It is the question behind warehouse fleet zoning, decentralized cleaning or inspection robots, and sensor-network placement: given N agents and a space, how do they divide it fairly, and how do they re-divide it the instant one is added or fails?

The classic answer is a centroidal Voronoi tessellation (CVT). Partition the space into Voronoi cells, one per robot. A partition is optimal (it minimizes the average distance from any point to its nearest robot) exactly when every robot sits at the centroid of its own cell. Lloyd’s algorithm reaches that fixed point by iterating two cheap steps:

  1. Partition — recompute the Voronoi diagram of the current robot positions.
  2. Relax — move each robot a fraction of the way toward its cell’s centroid.

Repeat, and the seeds drift until each one is centered in its territory. That is the breathing you see; the convergence meter is the total step distance, which shrinks as the system approaches the CVT fixed point.

Why it is built this way

A few decisions that make the demo honest rather than just pretty:

The Voronoi diagram is clipped to the floor, and the obstacle is a hard exclusion. Each cell is carved around the obstacle rectangle — its territory is the Voronoi cell minus the no-go zone — and a robot’s centroid is computed over that free area only, so no robot ever tries to center itself inside a wall. Kill a robot next to the obstacle and the neighbors flow around it, never across it.

It degrades gracefully. A single robot owns the whole floor (the Voronoi diagram is undefined for one point, so that case is handled explicitly). Drag a robot onto another and the partition stays valid. There is a hard cap of 40 robots — recomputing the diagram is cheap well below that, and the cap is surfaced in the UI rather than silently swallowing your clicks.

It is the decentralized version of real work. In the field this same partition is computed without a central planner: each robot knows only its neighbors, computes its own Voronoi cell from their positions, and steps toward its local centroid. The global CVT emerges from purely local rules — which is exactly why it survives a robot dropping out mid-shift. This lab runs it centrally for legibility, but the math is identical to the decentralized control law that makes it useful on a warehouse floor.

The geometry runs on plain Canvas 2D with d3-delaunay for the Voronoi computation — no WebGL, no heavy dependencies. The render loop pauses when the canvas scrolls offscreen or the tab is hidden, and all colors come from the site’s theme tokens, so it follows light and dark themes automatically.