Snake Game (Object-Oriented Design)

0) Problem Restatement

Amazon asked: design the classic Snake game with clean object-oriented design. The snake moves on a grid in a direction (up, down, left, right). When it eats food, it grows by one and the score increases, and new food appears on a random free cell. The game ends if the snake hits a wall or itself.

1) Classes

classDiagram
    class Game {
        -Board board
        -Snake snake
        -Food food
        -int score
        -bool over
        +changeDirection(dir) void
        +tick() void
    }
    class Board {
        +int width
        +int height
        +inside(cell) bool
    }
    class Snake {
        -deque body
        -set occupied
        -Direction dir
        +head() Cell
        +move(newHead, grow) void
        +occupies(cell) bool
    }
    class Food {
        +Cell position
    }
    Game --> Board
    Game --> Snake
    Game --> Food

• Snake body = a deque of cells (head at the front). Moving = add a new head and remove the tail (unless growing). Both are O(1).
• Occupied set = a hash set of body cells for O(1) self-collision checks (instead of scanning the whole body).

2) Code (Python)

import random
from collections import deque

DIRS = {"UP": (-1, 0), "DOWN": (1, 0), "LEFT": (0, -1), "RIGHT": (0, 1)}
OPPOSITE = {"UP": "DOWN", "DOWN": "UP", "LEFT": "RIGHT", "RIGHT": "LEFT"}

class SnakeGame:
    def __init__(self, width, height, seed=None):
        self.w, self.h = width, height
        self.rng = random.Random(seed)                 # seeded -> reproducible tests
        start = (height // 2, width // 2)
        self.body = deque([start])                     # head is body[0]
        self.occupied = {start}
        self.dir = "RIGHT"
        self.score, self.over = 0, False
        self.food = self._spawn_food()

    def change_direction(self, d):
        if d in DIRS and d != OPPOSITE[self.dir]:      # can't reverse into itself
            self.dir = d

    def _spawn_food(self):
        free = [(r, c) for r in range(self.h) for c in range(self.w) if (r, c) not in self.occupied]
        return self.rng.choice(free) if free else None # None = board full (win)

    def tick(self):
        if self.over:
            return
        dr, dc = DIRS[self.dir]
        hr, hc = self.body[0]
        new_head = (hr + dr, hc + dc)
        grow = new_head == self.food
        if not grow:                                   # the tail moves away this tick
            tail = self.body.pop()
            self.occupied.discard(tail)
        if not (0 <= new_head[0] < self.h and 0 <= new_head[1] < self.w) or new_head in self.occupied:
            self.over = True                           # wall or self collision
            return
        self.body.appendleft(new_head)
        self.occupied.add(new_head)
        if grow:
            self.score += 1
            self.food = self._spawn_food()
            if self.food is None:
                self.over = True                       # filled the board

3) Game Loop and Separation

• The game loop calls tick() at a fixed rate (e.g., every 150 ms), speeding up as the score grows.
• Rendering (terminal, canvas, mobile) is separate: it reads the state (body, food, score) and draws. The same SnakeGame class works with any UI.
• Input events call change_direction(). Only one direction change per tick is applied, to avoid a quick double-turn into itself.

4) Extensions

• Obstacles / levels: the board holds wall cells, checked like collisions.
• Wrap-around mode: take positions modulo width and height instead of hitting walls.
• Multiplayer: multiple Snake objects, checking head collisions with every snake's occupied set.
• Food spawn at scale: for huge boards, keep a list of free cells (with swap-remove) so spawning is O(1) instead of scanning.

5) Wrap-Up

Model Game, Board, Snake and Food. The snake is a deque of cells (O(1) head add and tail remove) plus a hash set for O(1) collision checks. Each tick computes the new head, removes the tail unless eating (so moving into the vacated tail cell is legal), checks walls and self-collision, grows and scores on food, and spawns food on a random free cell with a seeded generator. Keep the game logic separate from rendering and input for testability and extensions.