State Over Time

Tic-Tac-Toe changed only when you clicked. Most programs people enjoy don't wait: a game moves every fraction of a second, a download bar creeps forward, a chart scrolls as data arrives. This lesson is about programs whose state changes on a clock, and about keeping that state correct while two things — time and the player — both want to change it.

The worked example here is a tiny brick-breaker. The lab builds Snake, then asks you to plan a new simulation on your own.

State is data you can print

Everything the game needs to remember between two moments goes in one place:

state = {
    "ball": (4, 6),          # (col, row) on a grid
    "velocity": (1, -1),     # one column right, one row up per tick
    "bricks": {(3, 1), (4, 1), (5, 1), (6, 1)},
    "paddle": 4,             # column of the paddle's centre
    "score": 0,
}

Nothing about the game lives in the picture. The picture is drawn from state every time something changes, so if the picture looks wrong, you print state and the bug is in front of you. This separation — a model you can inspect, and a view drawn from it — is the same one Tic-Tac-Toe used with its list of nine cells.

Positions are grid cells, not pixels. A cell becomes pixels only when it is drawn (col * 20, row * 20 on a 20-pixel grid), so the rules of the game never mention pixels at all.

Two kinds of event

A clock-driven program has two sources of change:

• The tick. Every 150 milliseconds or so, the program advances the world one step.
• The player. A key press can arrive at any moment, including twice between two ticks.

The mistake almost everyone makes first is to let a key change the world immediately. Then the world changes at two different rates, and the rules that the tick enforces — no moving through walls, no turning back on yourself — can be skipped by pressing keys faster than the clock. Snake is the classic victim: two quick presses between ticks can add up to a turn the game should never allow.

The fix is to let a key record a wish, and let the tick commit it. For the brick-breaker's paddle:

game = {"paddle": 4, "wish": 0, "width": 10}

def key(name):
    # A key only records what the player wants.
    game["wish"] = {"left": -1, "right": 1}.get(name, 0)

def tick():
    # The tick is the only place the world changes, and it applies the rules.
    moved = game["paddle"] + game["wish"]
    game["paddle"] = min(game["width"] - 1, max(0, moved))    # stay on the board

key("left")
key("right")          # two quick presses: only the latest wish is kept
tick()
assert game["paddle"] == 5

Because only tick changes paddle, the rule "stay on the board" lives in one place and cannot be bypassed, however fast the keys arrive. In the lab you will write the rule for Snake's turns yourself. The question to settle before you code: when a key arrives, which direction should it be compared with — the one the player last asked for, or the one the snake last actually moved?

Decide, then change

A tick has an order, and the order is the whole game. For the brick-breaker:

1. Work out where the ball would go.
2. Decide what that means: a wall, a brick, the paddle, or empty space.
3. Only then change state.

def step(state, width=10):
    col, row = state["ball"]
    dc, dr = state["velocity"]
    target = (col + dc, row + dr)
    if not 0 <= target[0] < width:          # side wall: bounce sideways
        dc = -dc
        target = (col + dc, row + dr)
    if target in state["bricks"]:           # brick: remove it and bounce back
        state["bricks"].remove(target)
        state["score"] += 1
        dr = -dr
        target = (col + dc, row + dr)
    state["velocity"] = (dc, dr)
    state["ball"] = target

state = {"ball": (4, 2), "velocity": (1, -1),
         "bricks": {(3, 1), (4, 1), (5, 1), (6, 1)}, "paddle": 4, "score": 0}
step(state)
assert state["bricks"] == {(3, 1), (4, 1), (6, 1)} and state["score"] == 1
assert state["velocity"] == (1, 1) and state["ball"] == (5, 3)

If step moved the ball first and asked questions afterwards, the ball would sit inside a brick for one frame and the collision rule would have to undo a move. Deciding first keeps every state the program ever shows a legal one.

Snake adds a twist you will meet in the lab: the head arrives in the same tick that the tail leaves, so moving onto the cell your tail occupies right now is safe — unless the snake is growing this tick.

The invariant

An invariant is something that is true every time you look. For a clock-driven game the useful one is:

Between ticks, state describes a legal position, and it was produced only by ticks.

Key handlers never break it, because they only write wishes. Ticks never break it, because they decide before they change. When a bug appears, the invariant tells you where to look: something changed the world outside a tick, or a tick changed it before deciding.

Lists or sets: the cost of asking

The brick-breaker asks one question over and over: is there a brick at this cell? How long that takes depends on how the bricks are stored.

bricks_list = [(col, 1) for col in range(1000)]
bricks_set = set(bricks_list)

target = (999, 1)
assert target in bricks_list     # walks the list until it finds a match
assert target in bricks_set      # jumps straight to where the cell would be

in on a list checks items one by one: with 1,000 bricks, a miss costs 1,000 comparisons. in on a set hashes the cell and looks in one place, whatever the size. We write these as O(n) and O(1): the first grows with the number of items, the second does not.

Build the set once, when the state is created, and keep it up to date as bricks disappear. Rebuilding set(bricks_list) inside every tick would cost O(n) again and throw the advantage away.

The same reasoning applies to Snake's body. The body is a list, because order matters — the head is at index 0 and the tail at the end — but "is this cell part of the body?" is a set question.

What moving costs

Anything that moves by gaining a front and losing a back — a trail behind the ball, a list of the last few scores, Snake's body — pays for where it adds and removes. A list of recent ball positions, newest first:

trail = [(5, 3), (4, 2), (3, 1)]
trail.insert(0, (6, 4))    # the newest position goes in front: every item shifts
trail.pop()                # the oldest leaves from the end: nothing shifts
assert trail == [(6, 4), (5, 3), (4, 2)]

pop() from the end is O(1). insert(0, ...) is O(n): every other item shifts one place to make room. For a snake of a few hundred cells that is invisible. Module 8 introduces collections.deque, whose appendleft adds at the front in O(1) — a good example of choosing a structure for the operations you do most, not the ones that are most familiar.

Where it goes wrong

• Changing state in a key handler. Two quick keys reverse the snake. Record wishes; commit on the tick.
• Moving before checking. The object is briefly inside a wall, and the collision code has to undo a move. Decide first.
• Updating a grid in place while reading it. When every cell's next value depends on its neighbours' current values, changing cells as you go means later cells see a mixture of old and new. Build the next state separately, then replace the old one.
• Rebuilding a lookup set every tick. It works, and it quietly turns O(1) questions back into O(n) ones.

In the lab

The lab builds Snake in four steps: drawing a snake from coordinates, moving it by inserting a head and removing a tail, deciding whether a move crashes (with a lookup microscope that counts the work a list and a set do), and the full game with keys and a clock. It ends with a mastery challenge that names no technique: a simulation you plan yourself, answering four questions about the plan, the invariant, the cost, and the alternative before you write it.