Introduction

Imagine a robot dropped into an unknown room. It cannot see. It has no map. All it can sense is whether it is touching an obstacle and which direction points toward the goal. Can it still guarantee reaching the goal?

The answer is yes — and the proof is surprisingly simple. A family of algorithms called bug algorithms (introduced by Lumelsky and Stepanov in 1987) show that touching obstacle boundaries and following a single rule is enough to reach any reachable goal in any finite environment. The robot behaves like a bug crawling along a wall: when the path is clear it walks straight; when it hits something it hugs the boundary until a well-chosen exit condition fires.

Bug algorithms are the foundation of minimal-sensor navigation — a branch of robotics that asks: what is the least information a moving agent needs to be complete? They are also a vivid illustration of the gap between having a complete algorithm and being efficient: Bug1 guarantees the goal but may trace every boundary; Bug2 is smarter; A* and its cousins are smarter still, but they demand a map.

Try It: Bug2 Escapes a Maze

The robot (green) starts at the top-left and must reach the goal (red star) at the bottom-right. It follows the Bug2 rule: move along the straight line from start to goal (the m-line) until you hit a wall, then hug the left side of the obstacle until you cross the m-line again at a point closer to the goal.

<!-- Bug2 maze demo — minimal-sensor navigation -->
<div class="hint-bar">Bug2 moves straight toward the goal along the <em>m-line</em> (blue cells). When it hits a wall it hugs the left boundary until it re-crosses the m-line closer to the goal — then resumes straight-line travel. No map needed.</div>
<canvas id="maze" width="360" height="300"></canvas>
<div class="status-row">
  <span id="status" class="status">Press Step or Run to start.</span>
</div>
<div class="btns">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run"  type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Styles for the Bug2 maze canvas demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint-bar { font-size: .85rem; color: #444; margin-bottom: .5rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; max-width: 100%; }
.status-row { min-height: 1.6em; margin: .4rem 0; }
.status { font-size: .95rem; font-weight: 600; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

/* Bug2 algorithm implementation */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Grid definition — 1=obstacle, 0=free */
const ROWS = 10, COLS = 12;
const CELL = 25; // pixels per cell
const PAD  = 5;  // canvas padding in pixels

/* Obstacle map — hand-crafted maze solvable by Bug2 */
// 1 = obstacle, 0 = free
const GRID = [
  [0,0,0,0,0,0,0,0,0,0,0,0],
  [0,0,0,1,1,1,1,0,0,0,0,0],
  [0,0,0,1,0,0,1,0,0,0,0,0],
  [0,0,0,1,0,0,1,0,1,1,0,0],
  [0,0,0,0,0,0,1,0,1,0,0,0],
  [0,0,0,0,0,0,1,0,1,0,0,0],
  [0,0,1,1,1,0,0,0,1,0,0,0],
  [0,0,1,0,0,0,0,0,0,0,0,0],
  [0,0,1,1,1,1,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0,0,0,0]
];

const START = {r:0, c:0};
const GOAL  = {r:9, c:11};

/* Movement directions — 4-connected grid */
// 4-connected movement: up, right, down, left
const DIRS = [[-1,0],[0,1],[1,0],[0,-1]];

/* Simulation state variables */
let pos, state, wallMode, hitPoint, steps, done, timer, running;

/* m-line helpers */
// The m-line connects START and GOAL.
// A cell (r,c) is "on or crossing" the m-line when the straight line from
// START to GOAL passes within half a cell of its centre.
function onMLine(r, c) {
  // perpendicular distance from point to the m-line
  const dr = GOAL.r - START.r, dc = GOAL.c - START.c;
  const len2 = dr*dr + dc*dc;
  if (len2 === 0) return r === GOAL.r && c === GOAL.c;
  const t = ((r - START.r)*dr + (c - START.c)*dc) / len2;
  const pr = START.r + t*dr, pc = START.c + t*dc;
  return (r-pr)*(r-pr) + (c-pc)*(c-pc) < 0.5*0.5;
}

function distToGoal(r, c) {
  const dr = GOAL.r - r, dc = GOAL.c - c;
  return dr*dr + dc*dc;
}

function isBlocked(r, c) {
  return r < 0 || r >= ROWS || c < 0 || c >= COLS || GRID[r][c] === 1;
}

/* Render the grid, path, robot and goal to canvas */
function draw(path) {
  const canvas = document.getElementById('maze');
  const ctx = canvas.getContext('2d');
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // Draw each grid cell
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      const x = PAD + c*CELL, y = PAD + r*CELL;
      if (GRID[r][c] === 1) {
        ctx.fillStyle = '#6b7280';
      } else if (onMLine(r, c)) {
        ctx.fillStyle = '#dbeafe';
      } else {
        ctx.fillStyle = '#f3f4f6';
      }
      ctx.fillRect(x, y, CELL-1, CELL-1);
    }
  }

  // Draw the robot's trail
  if (path && path.length > 1) {
    ctx.strokeStyle = '#93c5fd';
    ctx.lineWidth = 2;
    ctx.beginPath();
    path.forEach(({r,c}, i) => {
      const px = PAD + c*CELL + CELL/2, py = PAD + r*CELL + CELL/2;
      i === 0 ? ctx.moveTo(px, py) : ctx.lineTo(px, py);
    });
    ctx.stroke();
  }

  // Draw the goal star
  const gx = PAD + GOAL.c*CELL + CELL/2, gy = PAD + GOAL.r*CELL + CELL/2;
  ctx.fillStyle = '#dc2626';
  ctx.font = 'bold 16px sans-serif';
  ctx.textAlign = 'center';
  ctx.textBaseline = 'middle';
  ctx.fillText('★', gx, gy);

  // Draw the robot circle
  const rx = PAD + pos.c*CELL + CELL/2, ry = PAD + pos.r*CELL + CELL/2;
  ctx.fillStyle = '#16a34a';
  ctx.beginPath();
  ctx.arc(rx, ry, CELL/2 - 3, 0, 2*Math.PI);
  ctx.fill();
}

/* Bug2 simulation — step-by-step */
// Bug2 algorithm core: one step at a time.
// state = 'toward_goal' | 'follow_wall'
let path = [];

function initSim() {
  pos = {...START};
  state = 'toward_goal';
  wallMode = null;
  hitPoint = null;
  steps = 0;
  done = false;
  path = [{...START}];
}

/* Move directly toward the goal (m-line phase) */
// Move one step toward the goal: pick the 4-connected free neighbor closest to goal.
function greedyStep() {
  // Pick the free neighbor that minimises distance to goal
  let bestDir = null, bestDist = Infinity;
  for (const [dr, dc] of DIRS) {
    const nr = pos.r + dr, nc = pos.c + dc;
    if (!isBlocked(nr, nc)) {
      const d = distToGoal(nr, nc);
      if (d < bestDist) { bestDist = d; bestDir = [dr, dc]; }
    }
  }
  if (bestDir === null) return null; // all neighbors blocked
  pos = {r: pos.r + bestDir[0], c: pos.c + bestDir[1]};
  return bestDir;
}

// Choose initial wall-following direction toward goal
// Choose initial wall-following direction: the DIRS index pointing most toward goal.
function getInitialFacing() {
  let bestFacing = 1, bestDist = Infinity;
  for (let d = 0; d < 4; d++) {
    const [dr, dc] = DIRS[d];
    const dist = distToGoal(pos.r + dr, pos.c + dc);
    if (dist < bestDist) { bestDist = dist; bestFacing = d; }
  }
  return bestFacing;
}

/* Wall-following phase — left-hand rule */
// Follow the wall: keep the obstacle on the left.
// wallMode encodes the current facing direction index into DIRS.
function stepFollowWall() {
  // Left-hand rule turn priority
  // Left-hand rule: try to turn left first, then go straight, then right, then back.
  const leftOf  = (d) => (d + 3) % 4;
  const rightOf = (d) => (d + 1) % 4;

  let facing = wallMode;
  // Try turns in priority order
  for (let attempt = 0; attempt < 4; attempt++) {
    const tryDir = (attempt === 0) ? leftOf(facing)
                 : (attempt === 1) ? facing
                 : (attempt === 2) ? rightOf(facing)
                 : (facing + 2) % 4;
    const [dr, dc] = DIRS[tryDir];
    const nr = pos.r + dr, nc = pos.c + dc;
    if (!isBlocked(nr, nc)) {
      wallMode = tryDir;
      pos = {r: nr, c: nc};
      return 'moved';
    }
  }
  return 'stuck';
}

function setStatus(text, cls) {
  const el = document.getElementById('status');
  el.textContent = text;
  el.className = 'status ' + (cls || '');
}

function tick() {
  if (done) return;
  steps++;

  if (pos.r === GOAL.r && pos.c === GOAL.c) {
    done = true;
    setStatus(i18nFmt('Reached the goal in %steps% step(s)!', { steps: steps }), 'ok');
    draw(path);
    return;
  }

  if (steps > 2000) {
    // safety limit exceeded
    done = true;
    setStatus('Stuck — could not reach goal in 2000 steps.', 'bad');
    draw(path);
    return;
  }

  if (state === 'toward_goal') {
    // Try to move one step toward goal
    const moved = greedyStep();
    if (moved) {
      path.push({...pos});
    } else {
      // Hit a wall — switch to wall-following mode
      hitPoint = {r: pos.r, c: pos.c, dist: distToGoal(pos.r, pos.c)};
      state = 'follow_wall';
      // Set initial wall-following direction
      wallMode = getInitialFacing();
      stepFollowWall();
      path.push({...pos});
    }
  } else {
    // Wall-following mode
    stepFollowWall();
    path.push({...pos});

    // Check Bug2 exit condition
    // Bug2 exit: on m-line AND closer to goal than where we left it
    if (onMLine(pos.r, pos.c) && hitPoint &&
        distToGoal(pos.r, pos.c) < hitPoint.dist &&
        !(pos.r === hitPoint.r && pos.c === hitPoint.c)) {
      state = 'toward_goal';
      hitPoint = null;
    }
  }

  setStatus(i18nFmt('Step %steps%', { steps: steps }), 'info');
  draw(path);

  document.getElementById('btn-step').disabled = done;
}

function reset() {
  if (timer) { clearInterval(timer); timer = null; }
  running = false;
  document.getElementById('btn-run').textContent = 'Run';
  document.getElementById('btn-step').disabled = false;
  initSim();
  setStatus('Press Step or Run to start.', '');
  draw(path);
}

document.getElementById('btn-step').addEventListener('click', () => { if (!done) tick(); });

document.getElementById('btn-run').addEventListener('click', function() {
  if (done) return;
  if (running) {
    clearInterval(timer); timer = null; running = false;
    this.textContent = 'Run';
  } else {
    running = true;
    this.textContent = 'Pause';
    timer = setInterval(() => {
      tick();
      if (done) {
        clearInterval(timer); timer = null; running = false;
        document.getElementById('btn-run').textContent = 'Run';
      }
    }, 120);
  }
});

document.getElementById('btn-reset').addEventListener('click', reset);

reset();
Result
Console

Press Step to advance one move at a time, or Run to watch it complete automatically. Notice that the robot never needs a map — it only needs to know the goal direction and whether it is touching a wall. Press Reset to start over.

The Real Complexity

The bug family reveals a beautiful tradeoff between sensor requirements and path quality:

  • Bug0 — move toward goal; if blocked, follow the wall until unblocked, then head for the goal again. It uses zero memory but can loop forever in mazes where every exit leads back to the same wall.
  • Bug1 — on hitting a wall, trace the entire boundary once, remember the closest point to the goal, return there and leave. Always complete, but the path length can be O(n2)O(n^2) where nn is the total obstacle perimeter — the robot may trace every boundary it touches.
  • Bug2 — the robot carries an imaginary straight line (the m-line) from start to goal. On hitting a wall, hug it until you re-cross the m-line at a point strictly closer to the goal than where you left it. Path length is O(n⋅P)O(n \cdot P) where PP is the number of obstacles the m-line crosses.
  • Tangent Bug (1998) adds a thin ring sensor: the robot can see a short distance ahead. This removes wasted boundary tracing and brings the path length down to O(n)O(n) over the full journey.

The key theoretical result: Bug1 and Bug2 are complete — in any connected environment with finitely many polygonal obstacles they always reach the goal or correctly declare it unreachable. Bug0 is not complete. Tangent Bug is complete and more efficient. None of them produce the shortest path; that requires global map knowledge, as studied in Dijkstra's algorithm and its variants.

Where It Matters

The "feel the wall" strategy is not just a theoretical curiosity — it appears everywhere sensors are scarce or cheap:

  • Robot vacuums: early Roombas used a direct relative of Bug1, tracing room boundaries and returning to the nearest approach to the center. The sensor required is just a bump sensor.
  • Emergency robotics: in smoke-filled buildings or deep-sea wreckage where cameras fail, a robot that only needs to feel walls can still navigate to a known goal position.
  • Planetary rovers: when communication lags make remote mapping impractical, onboard completeness guarantees matter more than path optimality.
  • Swarm robotics: individual agents with cheap touch sensors can collectively explore an unknown environment without any agent needing a global map.
  • Teaching foundations: bug algorithms are the canonical entry point for the question "what is the minimum information needed to solve a navigation problem?" — the same question that motivates complexity theory more broadly.

Conclusion

Bug algorithms answer one of the most basic questions in robotics: how little can a robot know and still be guaranteed to reach its goal? The answer — just a compass and a bump sensor — is surprisingly small.

The insight that completeness and optimality are separate concerns runs deep. A bug robot always arrives; it just may take the long way around. Getting a shorter path costs information: you need a map, or at least a longer-range sensor. That tradeoff — more knowledge buys better paths — echoes through A*, Dijkstra, and every planning algorithm ever designed.

So the next time a robot vacuum bumps into your sofa and starts circling the room, do not dismiss it as primitive. It is running one of the most elegant completeness proofs in all of computer science.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bug-algorithms/Content licensed under CC BY-NC 4.0.