Skip to content

Recursive Backtracker

Module: terminaltexteffects.utils.spanningtree.algo.recursivebacktracker

Recursive Backtracker minimum spanning tree algorithm.

This module provides the RecursiveBacktracker spanning tree generator implementation. The algorithm builds a spanning tree over a graph of EffectCharacter nodes using the depth-first recursive backtracker approach (implemented iteratively with an explicit stack).

The algorithm starts from a chosen starting character (or a random one from the terminal) and grows the tree by repeatedly linking to a randomly selected unvisited neighbor. Linked cells are added to the stack.

When a node has no unvisited neighbors the algorithm backtracks by popping the stack until it finds a node with unvisited neighbors.

RecursiveBacktracker

Bases: SpanningTreeGenerator

Recursive Backtracker tree generator algorithm.

Attributes:

Name Type Description
char_last_linked EffectCharacter | None

Character linked into the tree on the last step. None, if no character was linked during the last step.
char_link_order list[EffectCharacter]

Characters in linked order.
stack list[EffectCharacter]

Characters on the stack.
stack_last_popped EffectCharacter | None

Character popped off the stack on the last step. None if no character was popped during the last step.
complete bool

Whether the algorithm is complete.
Source code in terminaltexteffects/utils/spanningtree/algo/recursivebacktracker.py 
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class RecursiveBacktracker(SpanningTreeGenerator):
    """Recursive Backtracker tree generator algorithm.

    Attributes:
        char_last_linked (EffectCharacter | None): Character linked into the tree on the
            last step. None, if no character was linked during the last step.
        char_link_order (list[EffectCharacter]): Characters in linked order.
        stack (list[EffectCharacter]): Characters on the stack.
        stack_last_popped (EffectCharacter | None): Character popped off the stack on the
            last step. None if no character was popped during the last step.
        complete (bool): Whether the algorithm is complete.

    """

    def __init__(
        self,
        terminal: Terminal,
        starting_char: EffectCharacter | None = None,
        *,
        limit_to_text_boundary: bool = False,
    ) -> None:
        """Initialize the algorithm.

        Args:
            terminal (Terminal): TTE Terminal.
            starting_char (EffectCharacter | None, optional): Starting EffectCharacter. Defaults to None.
            limit_to_text_boundary (bool, optional): If True, the graph will not link to neighbors outside the text
                boundary.

        Raises:
            ValueError: Unable to find a starting character.

        """
        super().__init__(terminal)
        self.limit_to_text_boundary = limit_to_text_boundary
        starting_char = starting_char or terminal.get_character_by_input_coord(
            terminal.canvas.random_coord(within_text_boundary=limit_to_text_boundary),
        )
        if starting_char is None:
            msg = "Unable to find a starting character."
            raise ValueError(msg)
        self._current_char = starting_char
        self.char_last_linked: EffectCharacter | None = self._current_char
        self.char_link_order: list[EffectCharacter] = [self._current_char]
        self.stack: list[EffectCharacter] = [self._current_char]
        self.stack_last_popped: EffectCharacter | None = None
        self.complete = False

    def step(self) -> None:
        """Progress the algorithm by one step."""
        self.char_last_linked = None
        self.stack_last_popped = None
        if self.stack:
            unvisited_neighbors = self.get_neighbors(
                self._current_char,
                limit_to_text_boundary=self.limit_to_text_boundary,
            )
            if unvisited_neighbors:
                next_char = random.choice(unvisited_neighbors)
                self._current_char._link(next_char)
                self.char_link_order.append(next_char)
                self.char_last_linked = next_char
                self.stack.append(next_char)
                self._current_char = next_char
            else:
                self.stack_last_popped = self.stack.pop()
                if self.stack:
                    self._current_char = self.stack[-1]
        else:
            self.complete = True

__init__(terminal, starting_char=None, *, limit_to_text_boundary=False)

Initialize the algorithm.

Parameters:

Name Type Description Default
terminal Terminal

TTE Terminal.

 required
starting_char EffectCharacter | None

Starting EffectCharacter. Defaults to None.

 None
limit_to_text_boundary bool

If True, the graph will not link to neighbors outside the text boundary.

 False

Raises:

Type Description
ValueError

Unable to find a starting character.
Source code in terminaltexteffects/utils/spanningtree/algo/recursivebacktracker.py 
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
def __init__(
    self,
    terminal: Terminal,
    starting_char: EffectCharacter | None = None,
    *,
    limit_to_text_boundary: bool = False,
) -> None:
    """Initialize the algorithm.

    Args:
        terminal (Terminal): TTE Terminal.
        starting_char (EffectCharacter | None, optional): Starting EffectCharacter. Defaults to None.
        limit_to_text_boundary (bool, optional): If True, the graph will not link to neighbors outside the text
            boundary.

    Raises:
        ValueError: Unable to find a starting character.

    """
    super().__init__(terminal)
    self.limit_to_text_boundary = limit_to_text_boundary
    starting_char = starting_char or terminal.get_character_by_input_coord(
        terminal.canvas.random_coord(within_text_boundary=limit_to_text_boundary),
    )
    if starting_char is None:
        msg = "Unable to find a starting character."
        raise ValueError(msg)
    self._current_char = starting_char
    self.char_last_linked: EffectCharacter | None = self._current_char
    self.char_link_order: list[EffectCharacter] = [self._current_char]
    self.stack: list[EffectCharacter] = [self._current_char]
    self.stack_last_popped: EffectCharacter | None = None
    self.complete = False

step()

Progress the algorithm by one step.

Source code in terminaltexteffects/utils/spanningtree/algo/recursivebacktracker.py 
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
def step(self) -> None:
    """Progress the algorithm by one step."""
    self.char_last_linked = None
    self.stack_last_popped = None
    if self.stack:
        unvisited_neighbors = self.get_neighbors(
            self._current_char,
            limit_to_text_boundary=self.limit_to_text_boundary,
        )
        if unvisited_neighbors:
            next_char = random.choice(unvisited_neighbors)
            self._current_char._link(next_char)
            self.char_link_order.append(next_char)
            self.char_last_linked = next_char
            self.stack.append(next_char)
            self._current_char = next_char
        else:
            self.stack_last_popped = self.stack.pop()
            if self.stack:
                self._current_char = self.stack[-1]
    else:
        self.complete = True