1 files changed, 95 insertions, 0 deletions
diff --git a/internal/world/grid.go b/internal/world/grid.go
new file mode 100644
index 0000000..837f737
--- /dev/null
+++ b/internal/world/grid.go
@@ -0,0 +1,95 @@
+package world
+
+// GridConflict describes a layout conflict found while embedding rooms onto a
+// 3D grid via their exit deltas.
+//
+//   - "twist":   one room is forced onto two different grid cells (it was already
+//     placed at Existing but a later exit wants it at Want).
+//   - "overlap": two distinct rooms want the same grid cell (Occupier already
+//     holds Want).
+type GridConflict struct {
+	Kind     string  // "twist" or "overlap"
+	From     int     // room whose exit produced the conflict
+	Dir      ExitDir // exit direction taken from From
+	Target   int     // room being placed
+	Want     [3]int  // grid cell Target was assigned
+	Existing [3]int  // where Target was already placed (twist only)
+	Occupier int     // room already at Want (overlap only)
+}
+
+// RoomGrid is the embedding of one connected component onto a 3D grid.
+type RoomGrid struct {
+	Coord  map[int][3]int // room -> grid coordinate
+	RoomAt map[[3]int]int // grid coordinate -> room
+	Dist   map[int]int    // room -> BFS hop distance from the seed
+}
+
+// BuildGrid lays out the rooms reachable from seed onto a 3D grid, assigning
+// each room a coordinate by accumulating per-exit DirectionDeltas3D offsets in
+// BFS order. The seed sits at the origin (0,0,0).
+//
+//   - load returns a room and false to skip one that cannot be read; its exits
+//     are then not followed, but any coordinate already assigned to it stands.
+//   - include, when non-nil, restricts placement to targets for which it returns
+//     true (pass nil to place every reachable target).
+//   - onConflict, when non-nil, is called for each twist/overlap encountered.
+//
+// The first assignment to a room or cell always wins; conflicting placements are
+// skipped. In a world that passes grid validation there are no conflicts, so the
+// layout is unambiguous.
+func BuildGrid(seed int, load func(int) (*Room, bool), include func(int) bool, onConflict func(GridConflict)) RoomGrid {
+	g := RoomGrid{
+		Coord:  map[int][3]int{seed: {0, 0, 0}},
+		RoomAt: map[[3]int]int{{0, 0, 0}: seed},
+		Dist:   map[int]int{seed: 0},
+	}
+	queue := []int{seed}
+
+	for len(queue) > 0 {
+		rid := queue[0]
+		queue = queue[1:]
+		room, ok := load(rid)
+		if !ok {
+			continue
+		}
+		c := g.Coord[rid]
+		for _, dir := range ExitOrder {
+			exit, ok := room.Exits[dir]
+			if !ok || exit.Room <= 0 {
+				continue
+			}
+			target := exit.Room
+			if include != nil && !include(target) {
+				continue
+			}
+			d := DirectionDeltas3D[dir]
+			want := [3]int{c[0] + d[0], c[1] + d[1], c[2] + d[2]}
+
+			if existing, seen := g.Coord[target]; seen {
+				if existing != want && onConflict != nil {
+					onConflict(GridConflict{
+						Kind: "twist", From: rid, Dir: dir,
+						Target: target, Want: want, Existing: existing,
+					})
+				}
+				continue
+			}
+			if occupier, used := g.RoomAt[want]; used && occupier != target {
+				if onConflict != nil {
+					onConflict(GridConflict{
+						Kind: "overlap", From: rid, Dir: dir,
+						Target: target, Want: want, Occupier: occupier,
+					})
+				}
+				continue
+			}
+
+			g.Coord[target] = want
+			g.RoomAt[want] = target
+			g.Dist[target] = g.Dist[rid] + 1
+			queue = append(queue, target)
+		}
+	}
+
+	return g
+}