[Proc Gen] BSP - Iteration (leaves, traverse) #204

New issue

Open

opened 2026-01-12 00:10:02 +00:00 by john · 0 comments

john commented

2026-01-12 00:10:02 +00:00

Owner

Parent Issue: #192
Depends On: #202 (BSP core), #203 (BSPNode)

Overview

Add iteration methods to BSP for traversing the tree.

Specification

def leaves(self) -> Iterator[BSPNode]

Iterate all leaf nodes (the actual rooms).

def traverse(self, order: Traversal = Traversal.LEVEL_ORDER) -> Iterator[BSPNode]

Iterate all nodes in the specified order.

Traversal Enum

class Traversal(Enum):
    PRE_ORDER = "pre"           # Node, then left, then right
    IN_ORDER = "in"             # Left, then node, then right
    POST_ORDER = "post"         # Left, then right, then node
    LEVEL_ORDER = "level"       # Top to bottom, left to right
    INVERTED_LEVEL_ORDER = "level_inverted"  # Bottom to top, right to left

Example

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

# Iterate leaves (rooms)
for leaf in bsp.leaves():
    print(f"Room at {leaf.bounds}")

# Traverse all nodes
for node in bsp.traverse(mcrfpy.Traversal.POST_ORDER):
    if node.is_leaf:
        print(f"Leaf: {node.bounds}")

Implementation Notes

leaves() is equivalent to traverse() filtered to is_leaf
Maps to TCOD_bsp_traverse_* functions with callback
Consider implementing as Python generator for memory efficiency
Traversal enum should be exposed at module level: mcrfpy.Traversal

Acceptance Criteria

leaves() yields only leaf nodes
traverse() yields nodes in correct order for each traversal type
Iteration works with for loops
Can convert to list: list(bsp.leaves())
Unit tests verify traversal order

**Parent Issue:** #192 **Depends On:** #202 (BSP core), #203 (BSPNode) ## Overview Add iteration methods to BSP for traversing the tree. ## Specification ```python def leaves(self) -> Iterator[BSPNode] ``` Iterate all leaf nodes (the actual rooms). ```python def traverse(self, order: Traversal = Traversal.LEVEL_ORDER) -> Iterator[BSPNode] ``` Iterate all nodes in the specified order. ### Traversal Enum ```python class Traversal(Enum): PRE_ORDER = "pre" # Node, then left, then right IN_ORDER = "in" # Left, then node, then right POST_ORDER = "post" # Left, then right, then node LEVEL_ORDER = "level" # Top to bottom, left to right INVERTED_LEVEL_ORDER = "level_inverted" # Bottom to top, right to left ``` ### Example ```python bsp = mcrfpy.BSP(bounds=((0, 0), (100, 100))) bsp.split_recursive(depth=4, min_size=(8, 8)) # Iterate leaves (rooms) for leaf in bsp.leaves(): print(f"Room at {leaf.bounds}") # Traverse all nodes for node in bsp.traverse(mcrfpy.Traversal.POST_ORDER): if node.is_leaf: print(f"Leaf: {node.bounds}") ``` ## Implementation Notes - `leaves()` is equivalent to `traverse()` filtered to `is_leaf` - Maps to `TCOD_bsp_traverse_*` functions with callback - Consider implementing as Python generator for memory efficiency - `Traversal` enum should be exposed at module level: `mcrfpy.Traversal` ## Acceptance Criteria - [ ] `leaves()` yields only leaf nodes - [ ] `traverse()` yields nodes in correct order for each traversal type - [ ] Iteration works with for loops - [ ] Can convert to list: `list(bsp.leaves())` - [ ] Unit tests verify traversal order