r"""Libtcod's 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
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)
"""
from __future__ import annotations
from typing import Any, Iterator
import tcod.random
from tcod._internal import deprecate
from tcod.cffi import ffi, lib
[docs]
class BSP:
"""A binary space partitioning tree which can be used for simple dungeon generation.
Attributes:
x (int): Rectangle left coordinate.
y (int): Rectangle top coordinate.
width (int): Rectangle width.
height (int): Rectangle height.
level (int): This nodes depth.
position (int): The integer of where the node was split.
horizontal (bool): This nodes split orientation.
parent (Optional[BSP]): This nodes parent or None
children (Union[Tuple[()], Tuple[BSP, BSP]]):
A tuple of (left, right) BSP instances, or
an empty tuple if this BSP has no children.
Args:
x (int): Rectangle left coordinate.
y (int): Rectangle top coordinate.
width (int): Rectangle width.
height (int): Rectangle height.
"""
def __init__(self, x: int, y: int, width: int, height: int) -> None:
"""Initialize a root node of a BSP tree."""
self.x = x
self.y = y
self.width = width
self.height = height
self.level = 0
self.position = 0
self.horizontal = False
self.parent: BSP | None = None
self.children: tuple[()] | tuple[BSP, BSP] = ()
@property
@deprecate("This attribute has been renamed to `width`.", FutureWarning)
def w(self) -> int: # noqa: D102
return self.width
@w.setter
def w(self, value: int) -> None:
self.width = value
@property
@deprecate("This attribute has been renamed to `height`.", FutureWarning)
def h(self) -> int: # noqa: D102
return self.height
@h.setter
def h(self, value: int) -> None:
self.height = value
def _as_cdata(self) -> Any: # noqa: ANN401
cdata = ffi.gc(
lib.TCOD_bsp_new_with_size(self.x, self.y, self.width, self.height),
lib.TCOD_bsp_delete,
)
cdata.level = self.level
return cdata
[docs]
def __repr__(self) -> str:
"""Provide a useful readout when printed."""
status = "leaf"
if self.children:
status = "split at position=%i,horizontal=%r" % (
self.position,
self.horizontal,
)
return "<%s(x=%i,y=%i,width=%i,height=%i) level=%i %s>" % (
self.__class__.__name__,
self.x,
self.y,
self.width,
self.height,
self.level,
status,
)
def _unpack_bsp_tree(self, cdata: Any) -> None: # noqa: ANN401
self.x = cdata.x
self.y = cdata.y
self.width = cdata.w
self.height = cdata.h
self.level = cdata.level
self.position = cdata.position
self.horizontal = bool(cdata.horizontal)
if lib.TCOD_bsp_is_leaf(cdata):
return
self.children = (BSP(0, 0, 0, 0), BSP(0, 0, 0, 0))
self.children[0].parent = self
self.children[0]._unpack_bsp_tree(lib.TCOD_bsp_left(cdata))
self.children[1].parent = self
self.children[1]._unpack_bsp_tree(lib.TCOD_bsp_right(cdata))
[docs]
def split_once(self, horizontal: bool, position: int) -> None:
"""Split this partition into 2 sub-partitions.
Args:
horizontal (bool): If True then the sub-partition is split into an upper and bottom half.
position (int): The position of where to put the divider relative to the current node.
"""
cdata = self._as_cdata()
lib.TCOD_bsp_split_once(cdata, horizontal, position)
self._unpack_bsp_tree(cdata)
[docs]
def split_recursive( # noqa: PLR0913
self,
depth: int,
min_width: int,
min_height: int,
max_horizontal_ratio: float,
max_vertical_ratio: float,
seed: tcod.random.Random | None = None,
) -> None:
"""Divide this partition recursively.
Args:
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.
"""
cdata = self._as_cdata()
lib.TCOD_bsp_split_recursive(
cdata,
seed or ffi.NULL,
depth,
min_width,
min_height,
max_horizontal_ratio,
max_vertical_ratio,
)
self._unpack_bsp_tree(cdata)
[docs]
@deprecate("Use pre_order method instead of walk.")
def walk(self) -> Iterator[BSP]:
"""Iterate over this BSP's hierarchy in pre order.
.. deprecated:: 2.3
Use :any:`pre_order` instead.
"""
return self.post_order()
[docs]
def pre_order(self) -> Iterator[BSP]:
"""Iterate over this BSP's hierarchy in pre order.
.. versionadded:: 8.3
"""
yield self
for child in self.children:
yield from child.pre_order()
[docs]
def in_order(self) -> Iterator[BSP]:
"""Iterate over this BSP's hierarchy in order.
.. versionadded:: 8.3
"""
if self.children:
yield from self.children[0].in_order()
yield self
yield from self.children[1].in_order()
else:
yield self
[docs]
def post_order(self) -> Iterator[BSP]:
"""Iterate over this BSP's hierarchy in post order.
.. versionadded:: 8.3
"""
for child in self.children:
yield from child.post_order()
yield self
[docs]
def level_order(self) -> Iterator[BSP]:
"""Iterate over this BSP's hierarchy in level order.
.. versionadded:: 8.3
"""
next = [self]
while next:
level = next
next = []
yield from level
for node in level:
next.extend(node.children)
[docs]
def inverted_level_order(self) -> Iterator[BSP]:
"""Iterate over this BSP's hierarchy in inverse level order.
.. versionadded:: 8.3
"""
levels: list[list[BSP]] = []
next = [self]
while next:
levels.append(next)
level = next
next = []
for node in level:
next.extend(node.children)
while levels:
yield from levels.pop()
[docs]
def contains(self, x: int, y: int) -> bool:
"""Return True if this node contains these coordinates.
Args:
x (int): X position to check.
y (int): Y position to check.
Returns:
bool: True if this node contains these coordinates.
Otherwise False.
"""
return self.x <= x < self.x + self.width and self.y <= y < self.y + self.height
[docs]
def find_node(self, x: int, y: int) -> BSP | None:
"""Return the deepest node which contains these coordinates.
Returns:
BSP object or None.
"""
if not self.contains(x, y):
return None
for child in self.children:
found = child.find_node(x, y)
if found:
return found
return self
__all__ = ["BSP"]