[Proc Gen] BSP.adjacency - Room connectivity graph #210

New issue

Closed

opened 2026-01-12 00:11:38 +00:00 by john · 0 comments

john commented

2026-01-12 00:11:38 +00:00

Owner

Parent Issue: #192
Depends On: #202 (BSP core), #203 (BSPNode), #204 (BSP iteration)
Priority: Lower - Nice to have for 7DRL, not blocking

Overview

Add leaf adjacency graph to BSP, enabling room connectivity analysis for corridor generation, critical path detection, and spatial reasoning.

Design Decisions (Settled)

1. Adjacency-Only API (no find_path)

Exposing the adjacency graph is more flexible than providing a specific pathfinding algorithm. Users can implement BFS (shortest), DFS with backtracking (longer paths), or domain-specific heuristics. "Longest path" is NP-hard anyway, and a "probably pretty long" path via simple heuristics is more fun than an optimal zig-zag.

2. Geometric Wall Segment Detection

Two leaves are adjacent if they share a wall segment (not just a corner). This is determined geometrically:

Horizontal adjacency: a.x + a.w == b.x AND y-ranges overlap (max(a.y, b.y) < min(a.y+a.h, b.y+b.h))
Vertical adjacency: a.y + a.h == b.y AND x-ranges overlap

3. Lazy Computation with Caching

The adjacency graph is computed on first access and cached. Cache is invalidated when generation changes (after clear() or split_recursive()). The O(n²) cost is acceptable for typical BSP sizes (depth 4-6 = 16-64 leaves) and happens during level generation where loading time is expected.

4. Leaf Indexing

Leaves are assigned stable indices 0..n-1 based on level-order traversal. These indices are used consistently across bsp.adjacency and node.adjacent_tiles. Modifying the tree invalidates the cache and may change indices - this is an acceptable tradeoff for the uncommon "iterative refinement" workflow.

API Specification

BSP.adjacency (property)

@property
def adjacency(self) -> Sequence[tuple[int, ...]]

Returns a sequence-like object where adjacency[i] gives the tuple of leaf indices adjacent to leaf i.

bsp = mcrfpy.BSP(pos=(0,0), size=(100,100))
bsp.split_recursive(depth=4, min_size=(8,8))

# Get neighbors of leaf 0
neighbors = bsp.adjacency[0]  # -> (2, 5) if leaf 0 borders leaves 2 and 5

# Iterate all adjacencies
for i, neighbors in enumerate(bsp.adjacency):
    print(f"Leaf {i} is adjacent to: {neighbors}")

BSPNode.leaf_index (property)

@property
def leaf_index(self) -> int | None

Returns this node's index in the leaf enumeration, or None if not a leaf.

leaves = list(bsp.leaves())
assert leaves[3].leaf_index == 3
assert bsp.root.leaf_index is None  # Not a leaf

BSPNode.adjacent_tiles (property)

@property  
def adjacent_tiles(self) -> Mapping[int, tuple[Vector, ...]]

Returns a dict-like object where adjacent_tiles[neighbor_index] gives the tuple of Vector coordinates representing wall tiles shared with that neighbor.

node = leaves[0]
neighbor_indices = bsp.adjacency[0]  # e.g., (2, 5)

# Get wall tiles between leaf 0 and leaf 2
wall = node.adjacent_tiles[2]  # -> (Vector(15, 10), Vector(15, 11), Vector(15, 12))
print(f"Wall length: {len(wall)} tiles")

# Accessing non-adjacent leaf raises KeyError
node.adjacent_tiles[1]  # KeyError if leaf 1 is not adjacent

Example Use Case

import mcrfpy

bsp = mcrfpy.BSP(pos=(0, 0), size=(80, 50))
bsp.split_recursive(depth=4, min_size=(8, 8))

leaves = list(bsp.leaves())

# Find entrance/exit at opposite corners
start = min(range(len(leaves)), key=lambda i: sum(leaves[i].center()))
end = max(range(len(leaves)), key=lambda i: sum(leaves[i].center()))

# Simple BFS for a path (user-implemented)
from collections import deque

def find_path(adjacency, start, end):
    visited = {start}
    queue = deque([(start, [start])])
    while queue:
        current, path = queue.popleft()
        if current == end:
            return path
        for neighbor in adjacency[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return []

path = find_path(bsp.adjacency, start, end)

# Connect rooms along path with corridors
for i in range(len(path) - 1):
    a, b = path[i], path[i + 1]
    wall_tiles = leaves[a].adjacent_tiles[b]
    # Place door at middle of shared wall
    door_pos = wall_tiles[len(wall_tiles) // 2]
    print(f"Door between rooms {a} and {b} at {door_pos}")

Implementation Notes

C++ Data Structures

// In PyBSPObject
struct AdjacencyCache {
    std::vector<std::vector<int>> graph;      // graph[i] = neighbors of leaf i
    std::vector<TCOD_bsp_t*> leaf_pointers;   // leaf_pointers[i] = TCOD node for leaf i
    uint64_t generation;                       // Generation when computed
};
AdjacencyCache* adjacency_cache;  // nullptr until first access

Wall Tile Calculation

For two adjacent leaves A and B:

Determine shared edge (which side of A touches B)
Calculate overlap range on the perpendicular axis
Generate Vector for each tile coordinate along the overlap

std::vector<sf::Vector2i> get_wall_tiles(TCOD_bsp_t* a, TCOD_bsp_t* b) {
    std::vector<sf::Vector2i> tiles;
    
    // Check if A is left of B (vertical wall)
    if (a->x + a->w == b->x) {
        int y_start = std::max(a->y, b->y);
        int y_end = std::min(a->y + a->h, b->y + b->h);
        int x = a->x + a->w - 1;  // Last column of A (or first of B)
        for (int y = y_start; y < y_end; y++) {
            tiles.push_back({x, y});
        }
    }
    // ... similar for other 3 directions
    
    return tiles;
}

Cache Invalidation

The existing generation field handles this. When adjacency is accessed:

if (!adjacency_cache || adjacency_cache->generation != self->generation) {
    rebuild_adjacency_cache(self);
}

Acceptance Criteria

BSP.adjacency property returns sequence of neighbor tuples
BSPNode.leaf_index returns stable index (0..n-1) or None
BSPNode.adjacent_tiles[i] returns wall tile Vectors
Adjacency computed lazily on first access
Cache invalidated correctly on clear() / split_recursive()
KeyError raised for non-adjacent leaf access in adjacent_tiles
Unit tests verify adjacency correctness for various BSP configurations
Example corridor generation in tests/demo

**Parent Issue:** #192 **Depends On:** #202 (BSP core), #203 (BSPNode), #204 (BSP iteration) **Priority:** Lower - Nice to have for 7DRL, not blocking ## Overview Add leaf adjacency graph to BSP, enabling room connectivity analysis for corridor generation, critical path detection, and spatial reasoning. ## Design Decisions (Settled) ### 1. Adjacency-Only API (no find_path) Exposing the adjacency graph is more flexible than providing a specific pathfinding algorithm. Users can implement BFS (shortest), DFS with backtracking (longer paths), or domain-specific heuristics. "Longest path" is NP-hard anyway, and a "probably pretty long" path via simple heuristics is more fun than an optimal zig-zag. ### 2. Geometric Wall Segment Detection Two leaves are adjacent if they share a **wall segment** (not just a corner). This is determined geometrically: - Horizontal adjacency: `a.x + a.w == b.x` AND y-ranges overlap (`max(a.y, b.y) < min(a.y+a.h, b.y+b.h)`) - Vertical adjacency: `a.y + a.h == b.y` AND x-ranges overlap ### 3. Lazy Computation with Caching The adjacency graph is computed on first access and cached. Cache is invalidated when generation changes (after `clear()` or `split_recursive()`). The O(n²) cost is acceptable for typical BSP sizes (depth 4-6 = 16-64 leaves) and happens during level generation where loading time is expected. ### 4. Leaf Indexing Leaves are assigned stable indices 0..n-1 based on level-order traversal. These indices are used consistently across `bsp.adjacency` and `node.adjacent_tiles`. Modifying the tree invalidates the cache and may change indices - this is an acceptable tradeoff for the uncommon "iterative refinement" workflow. ## API Specification ### BSP.adjacency (property) ```python @property def adjacency(self) -> Sequence[tuple[int, ...]] ``` Returns a sequence-like object where `adjacency[i]` gives the tuple of leaf indices adjacent to leaf `i`. ```python bsp = mcrfpy.BSP(pos=(0,0), size=(100,100)) bsp.split_recursive(depth=4, min_size=(8,8)) # Get neighbors of leaf 0 neighbors = bsp.adjacency[0] # -> (2, 5) if leaf 0 borders leaves 2 and 5 # Iterate all adjacencies for i, neighbors in enumerate(bsp.adjacency): print(f"Leaf {i} is adjacent to: {neighbors}") ``` ### BSPNode.leaf_index (property) ```python @property def leaf_index(self) -> int | None ``` Returns this node's index in the leaf enumeration, or `None` if not a leaf. ```python leaves = list(bsp.leaves()) assert leaves[3].leaf_index == 3 assert bsp.root.leaf_index is None # Not a leaf ``` ### BSPNode.adjacent_tiles (property) ```python @property def adjacent_tiles(self) -> Mapping[int, tuple[Vector, ...]] ``` Returns a dict-like object where `adjacent_tiles[neighbor_index]` gives the tuple of Vector coordinates representing wall tiles shared with that neighbor. ```python node = leaves[0] neighbor_indices = bsp.adjacency[0] # e.g., (2, 5) # Get wall tiles between leaf 0 and leaf 2 wall = node.adjacent_tiles[2] # -> (Vector(15, 10), Vector(15, 11), Vector(15, 12)) print(f"Wall length: {len(wall)} tiles") # Accessing non-adjacent leaf raises KeyError node.adjacent_tiles[1] # KeyError if leaf 1 is not adjacent ``` ## Example Use Case ```python import mcrfpy bsp = mcrfpy.BSP(pos=(0, 0), size=(80, 50)) bsp.split_recursive(depth=4, min_size=(8, 8)) leaves = list(bsp.leaves()) # Find entrance/exit at opposite corners start = min(range(len(leaves)), key=lambda i: sum(leaves[i].center())) end = max(range(len(leaves)), key=lambda i: sum(leaves[i].center())) # Simple BFS for a path (user-implemented) from collections import deque def find_path(adjacency, start, end): visited = {start} queue = deque([(start, [start])]) while queue: current, path = queue.popleft() if current == end: return path for neighbor in adjacency[current]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, path + [neighbor])) return [] path = find_path(bsp.adjacency, start, end) # Connect rooms along path with corridors for i in range(len(path) - 1): a, b = path[i], path[i + 1] wall_tiles = leaves[a].adjacent_tiles[b] # Place door at middle of shared wall door_pos = wall_tiles[len(wall_tiles) // 2] print(f"Door between rooms {a} and {b} at {door_pos}") ``` ## Implementation Notes ### C++ Data Structures ```cpp // In PyBSPObject struct AdjacencyCache { std::vector<std::vector<int>> graph; // graph[i] = neighbors of leaf i std::vector<TCOD_bsp_t*> leaf_pointers; // leaf_pointers[i] = TCOD node for leaf i uint64_t generation; // Generation when computed }; AdjacencyCache* adjacency_cache; // nullptr until first access ``` ### Wall Tile Calculation For two adjacent leaves A and B: 1. Determine shared edge (which side of A touches B) 2. Calculate overlap range on the perpendicular axis 3. Generate Vector for each tile coordinate along the overlap ```cpp std::vector<sf::Vector2i> get_wall_tiles(TCOD_bsp_t* a, TCOD_bsp_t* b) { std::vector<sf::Vector2i> tiles; // Check if A is left of B (vertical wall) if (a->x + a->w == b->x) { int y_start = std::max(a->y, b->y); int y_end = std::min(a->y + a->h, b->y + b->h); int x = a->x + a->w - 1; // Last column of A (or first of B) for (int y = y_start; y < y_end; y++) { tiles.push_back({x, y}); } } // ... similar for other 3 directions return tiles; } ``` ### Cache Invalidation The existing `generation` field handles this. When adjacency is accessed: ```cpp if (!adjacency_cache || adjacency_cache->generation != self->generation) { rebuild_adjacency_cache(self); } ``` ## Acceptance Criteria - [ ] `BSP.adjacency` property returns sequence of neighbor tuples - [ ] `BSPNode.leaf_index` returns stable index (0..n-1) or None - [ ] `BSPNode.adjacent_tiles[i]` returns wall tile Vectors - [ ] Adjacency computed lazily on first access - [ ] Cache invalidated correctly on `clear()` / `split_recursive()` - [ ] KeyError raised for non-adjacent leaf access in `adjacent_tiles` - [ ] Unit tests verify adjacency correctness for various BSP configurations - [ ] Example corridor generation in tests/demo