# Multiplayer Snake (WebTransport) - Project Plan

## Overview
- Goal: Build a real-time, networked multiplayer Snake game with a Python 3 authoritative server and a web client using WebTransport datagrams for low-latency updates.
- Gameplay: Continuous, persistent world (no rounds). Players can join/leave anytime. Display each snake's current length; the longest snake is the momentary leader.
- Field: Default 60x40 grid; protocol supports 3x3 up to 255x255.
- Networking: Unreliable, unordered datagrams with sequence numbers and wraparound handling. Compression and packet partitioning to fit MTU (~1280-1500 bytes).

## Core Mechanics
- Collision handling: If the head would hit an obstacle (wall, self, other snake), the head stays in place (blocked) and the tail shrinks by 1 per tick until the player turns to a free direction.
- Self-collision: Temporary; tail shrink can clear the blocking segment.
- Other-snake collision: Clears when the other snake moves or shrinks away.
- Minimum length: A snake cannot be shorter than its head; minimum length is 1.
- Turning rules:
  - Length > 1: 180-degree turns are invalid and ignored at consumption time.
  - Length = 1 (only head left): 180-degree turns are valid.
- Apples and scoring:
  - Replace score display with current snake length.
  - Eating an apple grows snake by 1 immediately.
  - When 0 players remain connected, pre-populate field with exactly 3 apples.
- Colors: Assign a color when a client connects and keep it stable for that session.
- Spectator join: On initial connection, show current gameplay and overlay "press space to join".

## Input Buffer Rules
- Maintain a small buffer of up to 3 upcoming direction changes.
- If the new input is directly opposite to the last buffered direction, replace the last buffered entry instead of appending.
- Drop repeats: Do not add consecutive duplicates to the buffer.
- Overflow policy: If buffer is full, replace the last element with the new input.
- At each tick, before moving:
  - Consume at most one input from the buffer.
  - If length > 1 and it is a 180-degree turn, ignore it and immediately try the next buffered input; if none valid, keep current direction.

## Server Architecture (Python 3)
- Runtime: Python 3 with asyncio.
- Transport: WebTransport (HTTP/3 datagrams). Candidate library: aioquic for server-side H3 and datagrams.
 - Model:
   - Authoritative simulation on the server with a fixed tick rate (default 10 TPS). Tick rate is reconfigurable at runtime by the server operator and changes are broadcast to clients.
  - Each tick: process inputs, update snakes, resolve collisions (blocked/shrink), manage apples, generate state deltas.
- Entities:
  - Field: width, height, random seed, apple set.
  - Snake: id, name (<=16 chars), color id (0-31), deque of cells (head-first), current direction, input buffer, blocked flag, last-move tick, last-known client seq.
  - Player session: transport bindings, last-received input seq per player, anti-spam counters.
 - Spawn:
   - New snake spawns at a random free cell with a random legal starting direction.
   - Initial length policy: try to allocate a 3-cell straight strip (head + two body cells) in a legal direction; if not possible, spawn with length 1.
   - If the field appears full, temporarily ignore apples as obstacles for the purpose of finding space. If no free single cell exists, deny the join and inform the client to wait.
  - On apple eat: grow by 1; spawn a replacement apple at a free cell.
- Disconnect: Immediately remove snake and its length; apples persist. If all disconnect, ensure field contains 3 apples.
- Rate limiting: Cap input datagrams per second and buffer growth per client.

## Client Architecture (Web)
- Tech: Browser WebTransport (H3 datagrams), Canvas/WebGL rendering, minimal UI framework.
- Modes:
  - Spectator: Render world, show overlay "press space to join".
  - Player: Capture keyboard, build input buffer client-side, send inputs with sequence numbers; predict local movement for smoothness and reconcile to server.
- Rendering:
  - Gridless pixel or cell-based canvas.
  - Colors: 32-color predefined palette; deterministic mapping from player id to color id.
  - HUD: Current length; leaderboard (top N by length).
- Opponent prediction: When server state updates are late, step other snakes using server input broadcasts from their last known state; maintain mirrored per-opponent buffers and reconcile on the next authoritative update.

## Networking & Protocol
Constraints and goals:
- Use datagrams (unreliable, unordered). Include a packet sequence number for late-packet discard with wraparound handling.
- Keep payloads <=1280 bytes to avoid fragmentation; prefer a safety budget of ~1200 bytes post-compression when partitioning.
- Support up to 32 concurrent players; names limited to 16 bytes UTF-8.

Header (all packets):
- ver (u8): protocol version.
- type (u8): packet type (join, join_ack, join_deny, input, input_broadcast, state_delta, state_full, part, config_update, ping, pong, error).
- flags (u8): bit flags (compression, is_last_part, etc.).
- seq (u16): sender's monotonically incrementing sequence number (wraps at 65535). Newer-than logic uses half-range window.
- Optional tick (u16): simulation tick the packet refers to (on server updates).

Handshake (join -> join_ack | join_deny):
- Client sends: desired name (<=16), optional preferred color id.
- Server replies (join_ack): assigned player id (u8), color id (u8), field size (width u8, height u8), tick rate (u8), wrap_edges (bool), apples_per_snake (u8), apples_cap (u8 up to 255), compression_mode (enum: none|deflate), random seed (u32), palette, and initial full snapshot.
- Server can reply (join_deny) with a reason (e.g., no free cell; please wait).

Inputs (client -> server):
- Packet input includes: last-acknowledged server seq (u16), local input_seq (u16), one or more direction events with timestamps or relative tick offsets. Client pre-filters per buffer rules.

Input broadcast (server -> clients):
- Upon receiving a player's input, the server immediately relays those input events to all other clients as input_broadcast packets.
- Contents:
  - player_id (u8), the player's input_seq (u16)
  - base_tick (u16): server tick for alignment (typically current_tick)
  - events: one or more direction changes, each with rel_tick_offset (u8/varint) from base_tick
  - apply_at_tick (u16): optional absolute apply tick for convenience (both provided; clients may use either)
- Purpose: Enable client-side opponent prediction during late or lost state updates. Broadcasts are small; apply rate limits if needed.

State updates (server -> client):
- Types:
  - state_full: rare (on join or periodic recovery); includes all snakes and apples.
  - state_delta: frequent; contains only changed snakes (head move, tail shrink/grow) and apple changes since last acked tick.
- Per-snake encoding (compressed):
  - Header fields: `id` (u8), `len` (u16), `head` `(x,y)` (u8,u8).
  - Body TLV framing:
    - Type (T): QUIC varint. Values: 0=body_2bit, 1=body_rle, 0x10=body_2bit_chunk, 0x11=body_rle_chunk.
    - Length (L): QUIC varint; byte size of the Value.
    - Value (V): payload depends on Type (see below). TLV enables easy skipping and robust validation.
  - 2-bit body (T=0): direction stream from head toward tail using 2 bits per step: up=00, right=01, down=10, left=11. Total bits = (len-1)*2. Pack LSB-first within bytes; pad the last byte with zeros. Expected body bytes = ceil(((len-1)*2)/8).
    - Decoder: read exactly `len-1` directions; verify body size matches expectation and padding bits are zero.
  - RLE body (T=1): sequence of runs describing straight segments from head toward tail.
    - Each run: `dir` (u8: 0=up,1=right,2=down,3=left), `count` (QUIC varint, number of steps, >=1).
    - Decoder: accumulate counts until total equals `len-1`; reject if over/under.
  - Chunked variants (T=0x10, 0x11): used only when a single snake must be split.
    - Prefix V with `start_index` (u16, first direction offset from head) and `dirs_in_chunk` (u16); then the encoding for that range (2-bit or RLE respectively).
    - Client buffers chunks by `(update_id, snake_id)` and assembles when the full [0..len-2] range is present; then applies.
  - Selection: server chooses per snake whichever TLV (2-bit or RLE) yields fewer bytes.

Compression:
- Primary: domain-specific packing (bits + RLE for segments and apples).
- Optional global DEFLATE mode (server-configured): when enabled, server may set flags.compressed=1 and apply DEFLATE to payloads; this mode is negotiated in join_ack and is not changed on the fly (server restart required; clients must reconnect).
- Client decompresses if set; otherwise reads packed structs directly.

Packet partitioning (if >~1200–1280 bytes after compression):
- Apply to state_full (join and periodic recovery) and large state_delta updates.
- Goal: avoid IP fragmentation. Ensure each compressed datagram payload is <1280 bytes (use ~1200 target for headroom).
- Strategy (whole-snake first):
  - Sort snakes by estimated compressed size (head + body TLV) descending.
  - Greedily pack one or more complete snakes per packet while keeping the compressed payload <1280 bytes.
  - If a snake does not fit with others, send it alone if it fits <1280 bytes.
  - If a single snake still exceeds 1280 bytes by itself, split that snake into multiple similar-sized chunks using the chunked TLV types.
- Framing:
  - Each PART carries `update_id` (u16), `part_index` (u8), `parts_total` (u8), and `inner_type` (u8: STATE_FULL or STATE_DELTA) followed by the chunk payload.
  - For STATE_FULL: the chunk payload is `snakes_count + [per-snake records] + apples`. Include apples only in the first part; clients merge across parts using `update_id`.
  - For STATE_DELTA: the chunk payload is a subset of per-snake changes; include `apples_added/removed` only in the first part; clients merge across parts using `update_id`.
  - Clients apply complete per-snake TLVs immediately. Chunk TLVs are buffered and assembled by `(update_id, snake_id)` using `start_index` and `dirs_in_chunk` before applying.

Sequence wrap & ordering:
- Define is_newer(a, b) using signed 16-bit difference: ((a - b) & 0xFFFF) < 0x8000.
- Clients ignore updates older-than last applied per-sender.
- For input_broadcast, deduplicate per (player_id, input_seq) and apply in order per player; if apply_at_tick is in the past, apply immediately up to current tick.

Live config updates (server -> clients):
- Packet type: config_update, sent on change and periodically (low frequency).
- Fields: tick_rate (u8), wrap_edges (bool), apples_per_snake (u8), apples_cap (u8 up to 255).
- Clients apply changes at the next tick boundary. Compression mode is not changed via config_update (handshake-only).

## Simulation Details
- Tick order per tick:
  1) Incorporate at most one valid buffered input per snake (with 180-degree rule).
  2) Compute intended head step; if blocked, set blocked=true and keep head stationary.
  3) If blocked=true: shrink tail by 1 (to min length 1). If the blocking cell becomes free (due to own shrink or others moving), the next tick's step in current direction proceeds.
  4) If moving into an apple: grow by 1 (do not shrink tail that tick) and respawn an apple.
  5) Emit per-snake delta (move, grow, or shrink) and global apple changes.
 - Blocking detection: walls (0..width-1, 0..height-1), any occupied snake cell (including heads and tails that are not about to vacate this tick). Wrap-around rules are applied only to the head; if wrap_edges is turned off while a body segment is mid-edge traversal, allow the body to continue, but prevent the head from crossing walls thereafter.
- 180-degree turn allowance when length == 1 only.

### Client-side Opponent Prediction Heuristics
- Use last authoritative state per opponent as baseline; apply input_broadcast events at apply_at_tick boundaries.
- Apply the same input buffer rules and 180-degree constraints as the server.
- Approximate blocking: if predicted head step hits an occupied cell in the last known occupancy, mark blocked and simulate tail shrink until an alternate direction arrives; reconciliation will correct drift.

## Data Model & Structures
- Field cells: Represent coordinates as (x:u8, y:u8).
- Snakes: Deque of cells or segment list; store length as deque.size() and maintain head index.
- Apples: Hash set of cells for O(1) lookup; spawn on empty cells only.
- Occupancy: Sparse set/map from cell -> (snake_id, index) for O(1) collision checks.

## Limits & Config
- Players: max 32 (ids 0..31); deny joins beyond capacity.
- Names: UTF-8, truncate to 16 bytes; filter control chars.
- Field: default 60x40; min 3x3; max 255x255; provided by server in join_ack.
- Tick rate: default 10 TPS; server-controlled, reconfigurable on the fly via config_update (reasonable range 5-30 TPS).
- Apples per snake: default 1; server-controlled, reconfigurable on the fly; min 1/snake, max 12/snake; total apples capped at 255.
- Wrap-around edges: default off (walls are blocking); server-controlled, reconfigurable on the fly; head obeys current rule; legacy body traversal allowed during transitions.
- Compression (DEFLATE): global mode negotiated at join; requires server restart to change; clients must reconnect; when enabled server may set flags.compressed=1.
- Browser targets: must work on latest Firefox; latest Chrome is optional but desirable; others optional.

## Error Handling & Resilience
- Invalid packets: drop and optionally send error with code.
- Flooding: server-side rate limits and strike-based disconnects.
- Out-of-order: discard using is_newer check.
- Desync recovery: server sends state_full periodically or when client reports large gaps.

## Testing Strategy
- Unit tests: input buffer rules, 180-degree logic, blocking/shrink, collision resolution, sequence wrap comparison.
- Property tests: snake movement invariants (no duplicates in body except expected at head on block), apple placement safety.
- Soak tests: bot clients sending random but rate-limited inputs; measure packet size and latency.
- Prediction tests: delayed/missing state updates with input_broadcast streams; assert bounded drift and successful reconciliation.

## Milestones
1) Protocol draft and wire structs (this plan).
2) Server skeleton: tick loop, entities, occupancy, apples, basic WebTransport datagrams.
3) Input handling: buffer logic and per-tick consumption; collision/blocking/shrink rules.
4) Input relay and opponent prediction: server input_broadcast and client prediction + reconciliation.
5) State encoding: deltas, compression, and partitioning; client renderer (spectator).
6) Player flow: join overlay, name/color, spawn, HUD and leaderboard.
7) Performance pass: packet size tuning, RLE, optional DEFLATE, rate limits.
8) Polishing: error messages, reconnect, telemetry/logging, Docker/dev scripts.

## Open Questions
- Interpolation/smoothing specifics on client for variable tick rates.
- Any additional anti-cheat measures for input_broadcast misuse.
- Exact UI/UX for join denial when field is full (messaging/timing).

## Next Steps
- Validate the protocol choices and mechanics with stakeholders.
- Decide on tick rate and initial lengths.
- Confirm library choices (aioquic server; client-side WebTransport API usage).
- Begin Milestone 2: implement server skeleton and simulation core.