state_machine.py

"""
Branchless State Machine — State transitions without if/switch.

PATTERN: Table-Driven Transitions
    Instead of a switch/case or if/elif chain to decide what happens
    when an event occurs, we store ALL transitions in a 2D table:

        next_state = TRANSITION[current_state][event]
        action     = ACTIONS[current_state][event]

    This is a single array lookup — no branches, no matter how many
    states or events exist.

    Traditional (branching):
        if state == IDLE:
            if event == WALK:
                state = WALKING
                speed = 1
            elif event == JUMP:
                state = JUMPING
                velocity = 10
            ...

    Branchless (table-driven):
        state = TRANSITION[state][event]    # One lookup!
        action = ACTIONS[state][event]      # One lookup!

REAL-WORLD USES:
    - Game character controllers (this example)
    - Network protocol handlers (TCP state machine)
    - Lexers and parsers (tokenization)
    - UI navigation (screen flows)
    - Hardware controllers (elevator logic, traffic lights)
"""


# ──────────────────────────────────────────────
# State and Event Definitions
# ──────────────────────────────────────────────

# States — each is just an integer index into our tables
IDLE = 0
WALKING = 1
RUNNING = 2
JUMPING = 3
FALLING = 4
NUM_STATES = 5

# Events — also integer indices
EVT_NONE = 0  # No event (do nothing)
EVT_WALK = 1  # Start walking
EVT_RUN = 2   # Start running
EVT_JUMP = 3  # Jump
EVT_LAND = 4  # Land on ground
EVT_STOP = 5  # Stop movement
NUM_EVENTS = 6

# Human-readable names for display
STATE_NAMES = ["IDLE", "WALKING", "RUNNING", "JUMPING", "FALLING"]
EVENT_NAMES = ["NONE", "WALK", "RUN", "JUMP", "LAND", "STOP"]


# ──────────────────────────────────────────────
# Transition Table
# ──────────────────────────────────────────────
#
# HOW TO READ THIS TABLE:
#   Row = current state, Column = event
#   Value = next state
#
#   Example: TRANSITION[WALKING][EVT_JUMP] = JUMPING
#            "If we're WALKING and a JUMP event occurs, go to JUMPING"
#
#   Example: TRANSITION[JUMPING][EVT_WALK] = JUMPING
#            "If we're JUMPING and a WALK event occurs, stay JUMPING"
#            (can't start walking while in the air!)
#
#              Event:   NONE     WALK     RUN      JUMP     LAND     STOP
TRANSITION = [
    # IDLE:
    [IDLE,    WALKING, RUNNING, JUMPING, IDLE,    IDLE],
    # WALKING:
    [WALKING, WALKING, RUNNING, JUMPING, WALKING, IDLE],
    # RUNNING:
    [RUNNING, WALKING, RUNNING, JUMPING, RUNNING, IDLE],
    # JUMPING:
    [JUMPING, JUMPING, JUMPING, JUMPING, IDLE,    FALLING],
    # FALLING:
    [FALLING, FALLING, FALLING, FALLING, IDLE,    FALLING],
]


# ──────────────────────────────────────────────
# Action Functions
# ──────────────────────────────────────────────
# Each function returns a velocity value representing what happens
# during this transition.

def action_none(state, event):
    """No-op — nothing changes."""
    return 0

def action_start_walk(state, event):
    """Begin walking — set speed to 1."""
    return 1

def action_start_run(state, event):
    """Begin running — set speed to 3."""
    return 3

def action_jump(state, event):
    """Jump — set upward velocity to 10."""
    return 10

def action_land(state, event):
    """Land — reset velocity to 0."""
    return 0

def action_stop(state, event):
    """Stop — reset velocity to 0."""
    return 0


# ──────────────────────────────────────────────
# Action Table
# ──────────────────────────────────────────────
#
# Same structure as TRANSITION table, but stores functions instead of states.
# ACTIONS[current_state][event] = function_to_call
#
#           Event:  NONE          WALK             RUN              JUMP         LAND          STOP
ACTIONS = [
    # IDLE:
    [action_none, action_start_walk, action_start_run, action_jump, action_none, action_none],
    # WALKING:
    [action_none, action_none,       action_start_run, action_jump, action_none, action_stop],
    # RUNNING:
    [action_none, action_start_walk, action_none,      action_jump, action_none, action_stop],
    # JUMPING:
    [action_none, action_none,       action_none,      action_none, action_land, action_none],
    # FALLING:
    [action_none, action_none,       action_none,      action_none, action_land, action_none],
]


# ──────────────────────────────────────────────
# State Machine Class
# ──────────────────────────────────────────────

class BranchlessStateMachine:
    """
    A state machine that uses table lookups for ALL decisions.

    There are zero if/switch statements in the core logic.
    Adding new states or events just means adding rows/columns to the tables.
    """

    def __init__(self):
        self.state = IDLE
        self.velocity = 0

    def process_event(self, event):
        """
        Process an event: look up the action, execute it, transition state.

        This is the core of the branchless pattern:
            1. Validate input with arithmetic (no if)
            2. Look up action in table (no if)
            3. Look up next state in table (no if)

        Returns:
            (old_state, new_state, velocity) tuple
        """
        # Branchless bounds check: if event is out of range, treat as EVT_NONE (0)
        #   valid = 1 if 0 <= event < NUM_EVENTS, else 0
        #   event * valid = event if valid, 0 if invalid
        valid = int(0 <= event < NUM_EVENTS)
        safe_event = event * valid

        # Look up and execute the action — one table access, no branching
        action = ACTIONS[self.state][safe_event]
        result = action(self.state, safe_event)

        # Update velocity
        self.velocity = result

        # Transition state — one table access, no branching
        old_state = self.state
        self.state = TRANSITION[self.state][safe_event]

        return old_state, self.state, result

    def get_state_name(self):
        """Get human-readable name of current state."""
        return STATE_NAMES[self.state]


# ──────────────────────────────────────────────
# Helper: Branchless Event Priority Selection
# ──────────────────────────────────────────────

def branchless_event_priority(events):
    """
    Select the highest-priority event from a list, without branching.

    In games, multiple events can happen in one frame (e.g., player presses
    WALK and JUMP simultaneously). We need to pick the most important one.

    Priority order: JUMP (highest) > RUN > WALK > STOP > LAND > NONE (lowest)

    TRICK: Use a priority lookup table and branchless max selection.

    For each event, we check: is this event's priority higher than our best?
        is_better = int(priority > best_priority)
    Then use the 0/1 flag to conditionally update:
        best = new * is_better + old * (1 - is_better)
    """
    #                   NONE  WALK  RUN   JUMP  LAND  STOP
    priority_table =   [0,    3,    4,    5,    1,    2]

    best_event = EVT_NONE
    best_priority = 0

    for evt in events:
        evt_priority = priority_table[evt]

        # Branchless "if evt_priority > best_priority, update best"
        is_better = int(evt_priority > best_priority)
        best_event = evt * is_better + best_event * (1 - is_better)
        best_priority = evt_priority * is_better + best_priority * (1 - is_better)

    return best_event


# ──────────────────────────────────────────────
# Demo
# ──────────────────────────────────────────────

if __name__ == "__main__":
    print("Branchless State Machine Demo")
    print("=" * 55)

    sm = BranchlessStateMachine()

    # Simulate a sequence of game events
    events = [
        EVT_WALK,  # IDLE → WALKING
        EVT_RUN,   # WALKING → RUNNING
        EVT_JUMP,  # RUNNING → JUMPING
        EVT_LAND,  # JUMPING → IDLE
        EVT_WALK,  # IDLE → WALKING
        EVT_STOP,  # WALKING → IDLE
    ]

    print(f"\nInitial state: {sm.get_state_name()}")
    print(f"\n{'Event':<10} {'From':<10} {'To':<10} {'Velocity'}")
    print("-" * 45)

    for event in events:
        old, new, velocity = sm.process_event(event)
        print(f"  {EVENT_NAMES[event]:<8} {STATE_NAMES[old]:<10} → {STATE_NAMES[new]:<10} vel={velocity}")

    # Test event priority selection
    print(f"\n{'='*55}")
    print("Event Priority Selection (pick most important event):")

    test_sets = [
        [EVT_WALK, EVT_RUN],
        [EVT_STOP, EVT_JUMP, EVT_WALK],
        [EVT_NONE, EVT_LAND],
    ]

    for event_list in test_sets:
        names = [EVENT_NAMES[e] for e in event_list]
        selected = branchless_event_priority(event_list)
        print(f"  {names} → {EVENT_NAMES[selected]}")

    print()
    print("KEY TECHNIQUE: 2D lookup tables")
    print("  TRANSITION[state][event] = next_state")
    print("  ACTIONS[state][event]    = what_to_do")
    print("  → zero branches, easy to extend")