# How Munder Difflin Implements Agent Pathfinding on the Office Floor: A BFS-Based Navigation System

> Discover how Munder Difflin uses BFS for agent pathfinding on the office floor. Learn about their tile-based navigation system routing agents around obstacles.

- Repository: [Chaitanya Giri/munder-difflin](https://github.com/chaitanyagiri/munder-difflin)
- Tags: architecture
- Published: 2026-08-28

---

**Munder Difflin uses a lightweight Breadth-First Search (BFS) algorithm operating on a tile-based walkability grid to route agents around office obstacles and furniture.**

The open-source office simulation project `chaitanyagiri/munder-difflin` implements deterministic agent navigation through a three-layer architecture: map parsing, pathfinding engine, and character integration. This design ensures agents can reliably traverse desks, PCs, and walls while maintaining predictable, efficient movement patterns.

## Building the Walkability Grid from Tiled Map Data

The foundation of agent pathfinding starts with **TiledMapRenderer**, which transforms the visual office map into a binary navigation mesh.

In [`src/renderer/src/scene/office/TiledMapRenderer.ts`](https://github.com/chaitanyagiri/munder-difflin/blob/main/src/renderer/src/scene/office/TiledMapRenderer.ts), the `parseCollisionLayer` method reads the *collision* layer from the Tiled map format. It constructs a boolean `walkabilityGrid` where `true` indicates a tile agents may occupy and `false` marks blocked terrain including walls and permanent furniture.

```typescript
// TiledMapRenderer ensures spawn points remain traversable
markWalkableSpawnPoints(spawns: SpawnPoint[]): void

```

The `markWalkableSpawnPoints` function explicitly overrides grid cells containing interactive objects—desks, PCs, and other workstations—to remain walkable. Without this step, agents could never reach their assigned destinations. The public `isWalkable(x, y)` method then provides constant-time lookups for the pathfinding engine.

## The BFS Pathfinding Engine in pathfinding.ts

The core **agent pathfinding** algorithm lives in [`src/renderer/src/scene/office/pathfinding.ts`](https://github.com/chaitanyagiri/munder-difflin/blob/main/src/renderer/src/scene/office/pathfinding.ts). The `findPath` function implements classic BFS optimized for grid-based movement with four-directional connectivity.

```typescript
export function findPath(
  map: Walkable, 
  start: Point, 
  goal: Point
): Point[] | null

```

The algorithm proceeds through these deterministic stages:

- **Trivial case handling** — Returns empty path if start equals goal, or `null` if the goal tile itself is blocked
- **Queue-based exploration** — Dequeues the current tile, examines four orthogonal neighbors (up, down, left, right via `DIRECTIONS` constant)
- **Walkability filtering** — Skips visited tiles and non-walkable cells using `map.isWalkable()`
- **Parent tracking** — Records predecessor relationships in a `Map<string, Point>` for path reconstruction
- **Goal detection** — Triggers `reconstructPath()` immediately upon reaching the destination

The `reconstructPath` helper walks parent links backward from goal to start, reversing the sequence to yield the forward path. If the queue exhausts without reaching the goal, the function returns `null` indicating no valid route exists.

BFS guarantees **shortest path in unweighted grids**—critical for natural-looking agent movement where detours appear irrational.

## Character Integration: From Path to Animation

The `Character` class in [`src/renderer/src/scene/office/Character.ts`](https://github.com/chaitanyagiri/munder-difflin/blob/main/src/renderer/src/scene/office/Character.ts) bridges pathfinding results to on-screen movement. Two primary methods initiate navigation:

```typescript
// Direct movement request
moveTo(target: Point): void

// Movement with completion callback
walkToAndThen(target: Point, onArrive: () => void): void

```

Both methods follow identical internal flow:

1. **Coordinate translation** — Converts the character's pixel position to tile coordinates
2. **Path computation** — Calls `findPath(this.mapRenderer, startTile, goalTile)`
3. **State transition** — Stores the resulting tile array and switches animation state to "walk"
4. **Frame-by-frame execution** — The rendering loop advances through stored path tiles, updating sprite position each frame

The separation between **path calculation** (synchronous, immediate) and **path execution** (asynchronous, frame-driven) allows the simulation to maintain responsive UI while agents traverse arbitrarily long routes.

## Complete Pathfinding Workflow Example

```typescript
// Request agent to navigate to desk at tile (5, 3)
character.moveTo({ x: 5, y: 3 });

// Navigate to meeting room and trigger interaction
character.walkToAndThen({ x: 10, y: 7 }, () => {
  console.log('Agent arrived—starting presentation');
});

```

Behind these simple APIs, the full BFS execution unfolds: grid validation, neighbor expansion, parent mapping, and path reversal—executing in milliseconds even for large office layouts.

## Summary

- **TiledMapRenderer.ts** builds and queries the boolean `walkabilityGrid`, forcing spawn points walkable for accessibility
- **pathfinding.ts** implements BFS through `findPath()` with orthogonal expansion and parent-based reconstruction
- **Character.ts** translates pixel positions to tiles, caches paths, and drives frame-by-frame animation
- The system guarantees shortest paths on unweighted grids with deterministic, reproducible behavior
- All navigation respects static obstacles while permitting agent interaction with designated workstations

## Frequently Asked Questions

### Why does Munder Difflin use BFS instead of A* for pathfinding?

BFS provides optimal shortest paths on unweighted grids without the heuristic overhead of A*. For the uniform movement costs in Munder Difflin's tile system—where each cardinal step has identical travel time—BFS achieves equivalent path quality with simpler implementation. The algorithm's guaranteed completeness and optimality suit the office simulation's predictable, relatively small map sizes.

### How does the walkability grid handle interactive objects like desks?

The `markWalkableSpawnPoints` method in [`TiledMapRenderer.ts`](https://github.com/chaitanyagiri/munder-difflin/blob/main/TiledMapRenderer.ts) explicitly sets grid cells containing desks, PCs, and other interactables to `true`, overriding any collision layer defaults. This ensures agents can path onto these tiles to perform work actions while still blocking movement through walls and permanent furniture.

### What happens when no valid path exists between two points?

The `findPath` function returns `null`, which `Character` implementations must handle. The current codebase typically leaves the agent idle at its current position; callers of `walkToAndThen` will never see their completion callback executed. This silent failure mode prevents runtime crashes while signaling unreachable destinations.

### Can agents move diagonally between tiles?

No—Munder Difflin's pathfinding uses strict four-directional movement via the `DIRECTIONS` constant (up, down, left, right). Diagonal traversal would require modifying the neighbor expansion loop in [`pathfinding.ts`](https://github.com/chaitanyagiri/munder-difflin/blob/main/pathfinding.ts) to include the four diagonal offsets, though this would also demand updates to collision detection for corner-cutting scenarios.