Skip to content

Spanning trees

A spanning tree connects every character to its neighbors without loops, like a maze carved through the text. Revealing characters in the order a tree links them makes the text grow outward in branches, and walking the finished tree from its root sends a pulse down those branches. Built-in effects that use spanning trees include Burn, Laseretch, and Smoke.

The Grow example

Grow builds a spanning tree over the text, reveals the characters in the order the tree linked them, and then runs a pulse from the tree's root out along its branches. Save it as grow.py in your community effects directory:

grow.py
"""Grow: the text grows along a spanning tree, then a pulse runs back along the tree's branches.

An Effect Guide example for the Spanning trees pattern.
"""

from __future__ import annotations

import typing
from dataclasses import dataclass

from terminaltexteffects import Color, ColorPair, EffectCharacter, Gradient
from terminaltexteffects.engine.base_config import BaseConfig
from terminaltexteffects.engine.base_effect import BaseEffect, BaseEffectIterator
from terminaltexteffects.utils import argutils
from terminaltexteffects.utils.spanningtree.algo.aldousbroder import AldousBroder
from terminaltexteffects.utils.spanningtree.algo.breadthfirst import BreadthFirst
from terminaltexteffects.utils.spanningtree.algo.primssimple import PrimsSimple
from terminaltexteffects.utils.spanningtree.algo.recursivebacktracker import RecursiveBacktracker

ALGORITHMS = {
    "prims_simple": PrimsSimple,
    "recursive_backtracker": RecursiveBacktracker,
    "aldous_broder": AldousBroder,
}
GROWN_COLOR = ColorPair(fg=Color("#3a7a3a"))
PULSE = Gradient(Color("#ffffff"), Color("#80ff80"), steps=8)
LINKS_PER_TICK = 3


def get_effect_resources() -> tuple[str, type[BaseEffect], type[BaseConfig]]:
    """Return the command name, effect class, and configuration class TTE registers."""
    return "grow", Grow, GrowConfig


@dataclass
class GrowConfig(BaseConfig):
    """Configuration for the Grow effect."""

    parser_spec = argutils.ParserSpec(
        name="grow",
        help="The text grows along a spanning tree, then a pulse runs along the tree's branches.",
        description="grow | The text grows along a spanning tree, then a pulse runs along the tree's branches.",
        epilog="Example: tte grow --algorithm recursive_backtracker",
    )
    algorithm: typing.Literal["prims_simple", "recursive_backtracker", "aldous_broder"] = argutils.ArgSpec(
        name="--algorithm",
        default="prims_simple",
        choices=list(ALGORITHMS),
        help="Algorithm that builds the spanning tree.",
    )  # pyright: ignore[reportAssignmentType]
    "typing.Literal['prims_simple', 'recursive_backtracker', 'aldous_broder'] : Algorithm that builds the tree."


class GrowIterator(BaseEffectIterator[GrowConfig]):
    """Produce the frames of the Grow effect."""

    def __init__(self, effect: Grow) -> None:
        """Build the whole spanning tree up front, and prepare the pulse that follows it."""
        super().__init__(effect)
        tree = ALGORITHMS[self.config.algorithm](self.terminal, limit_to_text_boundary=True)
        while not tree.complete:
            tree.step()
        self.link_order = [character for character in tree.char_link_order if not character.is_fill_character]
        self.link_order.reverse()  # So pop() takes the first character linked.
        self.root = tree.char_link_order[0]
        self.pulse = BreadthFirst(self.terminal, self.root)
        for character in self.terminal.get_characters():
            character.animation.set_appearance(character.input_symbol, GROWN_COLOR)
            scene = character.animation.new_scene(scene_id="pulse")
            scene.apply_gradient_to_symbols(character.input_symbol, 2, fg_gradient=PULSE)

    def start_pulse(self, character: EffectCharacter) -> None:
        """Play the pulse scene on a character the pulse has just reached."""
        if not character.is_fill_character:
            character.animation.activate_scene("pulse")
            self.active_characters.add(character)

    def __next__(self) -> str:
        """Grow a few characters per tick; once all have grown, advance the pulse one layer per tick."""
        if self.link_order:
            for _ in range(LINKS_PER_TICK):
                if self.link_order:
                    self.terminal.set_character_visibility(self.link_order.pop(), is_visible=True)
        elif not self.pulse.complete:
            if not self.pulse.char_explore_order:  # The first pulse tick: start at the root.
                self.start_pulse(self.root)
            self.pulse.step()
            for character in self.pulse.explored_last_step:
                self.start_pulse(character)
        elif not self.active_characters:
            raise StopIteration
        self.update()
        return self.frame


class Grow(BaseEffect[GrowConfig]):
    """The text grows along a spanning tree, then a pulse runs along the tree's branches."""

    @property
    def _config_cls(self) -> type[GrowConfig]:
        return GrowConfig

    @property
    def _iterator_cls(self) -> type[GrowIterator]:
        return GrowIterator

The algorithm that builds the tree decides the shape of the growth:

tte --input-file concept_input.txt grow --algorithm prims_simple

The text grows outward from a random point in a ragged blob, then a white pulse spreads from that point

Prim's algorithm links a random character on the edge of the tree each step, so the tree grows outward evenly from its root.

tte --input-file concept_input.txt grow --algorithm recursive_backtracker

The text grows in long winding corridors, then a pulse follows those corridors

The recursive backtracker follows one branch as far as it can before backing up, so the tree has long corridors and the pulse takes winding routes.

tte --input-file concept_input.txt grow --algorithm aldous_broder

The text grows in scattered patches that join up, then a pulse spreads through them

Aldous-Broder wanders at random and links each character the first time it visits it, so growth appears in patches and slows down as fewer unvisited characters remain.

Building the tree

The generators are in terminaltexteffects.utils.spanningtree.algo. Each one takes the terminal and, optionally, a starting character:

tree = PrimsSimple(self.terminal, limit_to_text_boundary=True)
while not tree.complete:
    tree.step()

Each step() links at most one more character. You can step a generator once per frame to animate the tree as it is built, or, as Grow does, build the whole tree during setup and replay char_link_order, the characters in the order they were linked. Building up front keeps __next__ simple and lets you change the reveal rate freely.

Without a starting character, the generator picks a random one, inside the text bounds with limit_to_text_boundary=True. That option also keeps the tree from linking characters outside the text.

Fill characters

Trees link neighboring cells, and spaces inside the text are cells too. The engine fills them with fill characters, so a tree can pass between words (see Fill characters). Fill characters have is_fill_character set and a space as their symbol. Grow skips them when revealing and pulsing.

A generator records the tree in each character's links, the set of neighbors it is linked to. A character that already has links can't be part of a new tree: the generators raise ValueError. Build one tree per effect run.

Walking the tree

BreadthFirst(terminal, starting_char) traverses a tree that is already built. Each step() moves one layer out from the start, and explored_last_step lists the characters reached by that step. Grow starts a pulse scene on those characters each tick, so the pulse moves one link per tick along every branch at once. The traversal is complete when a step finds no new characters.

Where to go next