Source code for tcod.bsp

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"]