# tcod.bsp - Binary Space Partitioning¶

The following example shows how to traverse the BSP tree using Python. This assumes create_room and connect_rooms will be replaced by custom code.

Example:

```import tcod

bsp = tcod.bsp.BSP(x=0, y=0, width=80, height=60)
bsp.split_recursive(
depth=5,
min_width=3,
min_height=3,
max_horizontal_ratio=1.5,
max_vertical_ratio=1.5,
)

# In pre order, leaf nodes are visited before the nodes that connect them.
for node in bsp.pre_order():
if node.children:
node1, node2 = node.children
print('Connect the rooms:\n%s\n%s' % (node1, node2))
else:
print('Dig a room for %s.' % node)
```
class `tcod.bsp.``BSP`(x: int, y: int, width: int, height: int)[source]

A binary space partitioning tree which can be used for simple dungeon generation.

`x`

Rectangle left coordinate.

Type: int
`y`

Rectangle top coordinate.

Type: int
`width`

Rectangle width.

Type: int
`height`

Rectangle height.

Type: int
`level`

This nodes depth.

Type: int
`position`

The integer of where the node was split.

Type: int
`horizontal`

This nodes split orientation.

Type: bool
`parent`

This nodes parent or None

Type: Optional[BSP]
`children`

A tuple of (left, right) BSP instances, or an empty tuple if this BSP has no children.

Type: Union[Tuple[()], Tuple[BSP, BSP]]
Parameters: x (int) – Rectangle left coordinate. y (int) – Rectangle top coordinate. width (int) – Rectangle width. height (int) – Rectangle height.
`__str__`() → str[source]

Provide a useful readout when printed.

`contains`(x: int, y: int) → bool[source]

Returns True if this node contains these coordinates.

Parameters: x (int) – X position to check. y (int) – Y position to check. True if this node contains these coordinates. Otherwise False. bool
`find_node`(x: int, y: int) → Optional[tcod.bsp.BSP][source]

Return the deepest node which contains these coordinates.

Returns: BSP object or None. Optional[BSP]
`in_order`() → Iterator[tcod.bsp.BSP][source]

Iterate over this BSP’s hierarchy in order.

New in version 8.3.

`inverted_level_order`() → Iterator[tcod.bsp.BSP][source]

Iterate over this BSP’s hierarchy in inverse level order.

New in version 8.3.

`level_order`() → Iterator[tcod.bsp.BSP][source]

Iterate over this BSP’s hierarchy in level order.

New in version 8.3.

`post_order`() → Iterator[tcod.bsp.BSP][source]

Iterate over this BSP’s hierarchy in post order.

New in version 8.3.

`pre_order`() → Iterator[tcod.bsp.BSP][source]

Iterate over this BSP’s hierarchy in pre order.

New in version 8.3.

`split_once`(horizontal: bool, position: int) → None[source]

Split this partition into 2 sub-partitions.

Parameters: horizontal (bool) – position (int) –
`split_recursive`(depth: int, min_width: int, min_height: int, max_horizontal_ratio: float, max_vertical_ratio: float, seed: Optional[tcod.random.Random] = None) → None[source]

Divide this partition recursively.

Parameters: depth (int) – The maximum depth to divide this object recursively. min_width (int) – The minimum width of any individual partition. min_height (int) – The minimum height of any individual partition. max_horizontal_ratio (float) – Prevent creating a horizontal ratio more extreme than this. max_vertical_ratio (float) – Prevent creating a vertical ratio more extreme than this. seed (Optional[tcod.random.Random]) – The random number generator to use.
`walk`() → Iterator[tcod.bsp.BSP][source]

Iterate over this BSP’s hierarchy in pre order.

Deprecated since version 2.3: Use `pre_order` instead.