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

New issue

Open

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 method to find a path through BSP leaf nodes based on shared walls, enabling "longest path" corridor generation.

Problem Statement

The BSP tree structure represents containment, not adjacency:

Parent nodes CONTAIN their children
Traversing the tree doesn't give a path through rooms
For corridor generation, we need the adjacency graph of leaf nodes

Two leaf nodes are adjacent if they share a wall segment (not just a corner).

Proposed Specification

def find_path(self, start: BSPNode, end: BSPNode) -> tuple[BSPNode, ...]

Find a sequence of adjacent leaf nodes connecting start to end.

def leaf_neighbors(self, node: BSPNode) -> tuple[BSPNode, ...]

Get all leaf nodes that share a wall with the given node.

Example Use Case

bsp = mcrfpy.BSP(bounds=((0, 0), (100, 100)))
bsp.split_recursive(depth=5, min_size=(8, 8))

leaves = list(bsp.leaves())

# Find rooms at opposite corners for entrance/exit
start = min(leaves, key=lambda n: n.center[0] + n.center[1])
end = max(leaves, key=lambda n: n.center[0] + n.center[1])

# Get path through rooms
path = bsp.find_path(start, end)

# Connect rooms along path
for i in range(len(path) - 1):
    connect_rooms(path[i], path[i+1])

Design Questions

Adjacency Definition: How to detect shared walls?
- Option A: Two nodes share a wall if their bounds overlap on one axis and are adjacent (differ by 0 or 1) on the other
- Option B: Calculate actual wall segments and check for overlap
Pathfinding Algorithm:
- BFS for shortest path?
- Or provide the adjacency graph and let users pathfind?
Edge Cases:
- What if no path exists? (Return empty tuple or raise?)
- What about diagonal adjacency? (Probably no - corners don't share walls)

Implementation Approach

Build adjacency graph of all leaves:

For each pair of leaves (A, B):
    If A.bounds and B.bounds share a wall segment:
        Add edge A <-> B

BFS/DFS from start to end on adjacency graph
Cache adjacency graph on BSP (invalidate on split/clear)

Alternative: Expose Adjacency Only

Instead of find_path, just expose the adjacency information:

def adjacent_leaves(self) -> dict[BSPNode, tuple[BSPNode, ...]]

Then users can implement their own pathfinding (A*, longest path, etc.)

Acceptance Criteria

Design decision made on adjacency definition
Design decision made on API (find_path vs adjacency graph)
Implementation handles all edge cases
Works correctly 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 method to find a path through BSP leaf nodes based on shared walls, enabling "longest path" corridor generation. ## Problem Statement The BSP tree structure represents containment, not adjacency: - Parent nodes CONTAIN their children - Traversing the tree doesn't give a path through rooms - For corridor generation, we need the **adjacency graph** of leaf nodes Two leaf nodes are adjacent if they share a wall segment (not just a corner). ## Proposed Specification ```python def find_path(self, start: BSPNode, end: BSPNode) -> tuple[BSPNode, ...] ``` Find a sequence of adjacent leaf nodes connecting start to end. ```python def leaf_neighbors(self, node: BSPNode) -> tuple[BSPNode, ...] ``` Get all leaf nodes that share a wall with the given node. ### Example Use Case ```python bsp = mcrfpy.BSP(bounds=((0, 0), (100, 100))) bsp.split_recursive(depth=5, min_size=(8, 8)) leaves = list(bsp.leaves()) # Find rooms at opposite corners for entrance/exit start = min(leaves, key=lambda n: n.center[0] + n.center[1]) end = max(leaves, key=lambda n: n.center[0] + n.center[1]) # Get path through rooms path = bsp.find_path(start, end) # Connect rooms along path for i in range(len(path) - 1): connect_rooms(path[i], path[i+1]) ``` ## Design Questions 1. **Adjacency Definition**: How to detect shared walls? - Option A: Two nodes share a wall if their bounds overlap on one axis and are adjacent (differ by 0 or 1) on the other - Option B: Calculate actual wall segments and check for overlap 2. **Pathfinding Algorithm**: - BFS for shortest path? - Or provide the adjacency graph and let users pathfind? 3. **Edge Cases**: - What if no path exists? (Return empty tuple or raise?) - What about diagonal adjacency? (Probably no - corners don't share walls) ## Implementation Approach 1. Build adjacency graph of all leaves: ``` For each pair of leaves (A, B): If A.bounds and B.bounds share a wall segment: Add edge A <-> B ``` 2. BFS/DFS from start to end on adjacency graph 3. Cache adjacency graph on BSP (invalidate on split/clear) ## Alternative: Expose Adjacency Only Instead of `find_path`, just expose the adjacency information: ```python def adjacent_leaves(self) -> dict[BSPNode, tuple[BSPNode, ...]] ``` Then users can implement their own pathfinding (A*, longest path, etc.) ## Acceptance Criteria - [ ] Design decision made on adjacency definition - [ ] Design decision made on API (find_path vs adjacency graph) - [ ] Implementation handles all edge cases - [ ] Works correctly for various BSP configurations - [ ] Example corridor generation in tests/demo