Snake Game

Overview

Snake game implementation using a queue is a classic problem that demonstrates how queues can represent sequential, ordered data structures. In the snake game, the snake's body is naturally represented as a queue where new segments are added to the rear (when eating food) and old segments are removed from the front (when moving).

The queue perfectly models the snake because:

• FIFO order - Head moves first, tail follows
• Growth - New segments added to rear when eating
• Movement - Old tail removed from front when moving
• Order preservation - Maintains body segment order

Key characteristics:

• Queue representation - Snake body as queue of positions
• Head and tail - Head is rear, tail is front of queue
• Growth mechanism - Enqueue when eating food
• Movement - Dequeue tail, enqueue new head
• Collision detection - Check head against body/walls

How Snake Game Works with Queue

The snake game uses a queue to represent the snake's body:

1. Initialization - Start with queue containing initial snake positions
2. Movement - Remove tail (dequeue front), add new head (enqueue rear)
3. Food consumption - When eating food, don't remove tail (snake grows)
4. Collision detection - Check if new head collides with body or walls
5. Game over - If collision detected, game ends

The queue maintains the order of body segments naturally.

Basic Snake Game Implementation

Simple snake game using queue:

class SnakeGame {
  private snake: [number, number][] = [];
  private width: number;
  private height: number;
  private food: [number, number][] = [];
  private foodIndex = 0;
  private score = 0;
  
  constructor(width: number, height: number, food: [number, number][]) {
    this.width = width;
    this.height = height;
    this.food = food;
    // Initialize snake at center
    this.snake.push([height / 2, width / 2]);
  }
  
  move(direction: string): number {
    const [headR, headC] = this.snake[this.snake.length - 1];
    let newHeadR = headR;
    let newHeadC = headC;
    
    // Calculate new head position
    switch (direction) {
      case 'U': newHeadR--; break;
      case 'D': newHeadR++; break;
      case 'L': newHeadC--; break;
      case 'R': newHeadC++; break;
    }
    
    // Check wall collision
    if (
      newHeadR < 0 || newHeadR >= this.height ||
      newHeadC < 0 || newHeadC >= this.width
    ) {
      return -1; // Game over
    }
    
    // Check self collision (check if new head in body)
    const newHead: [number, number] = [newHeadR, newHeadC];
    for (let i = 0; i < this.snake.length - 1; i++) {
      if (this.snake[i][0] === newHeadR && this.snake[i][1] === newHeadC) {
        return -1; // Game over
      }
    }
    
    // Add new head
    this.snake.push(newHead);
    
    // Check if food eaten
    if (
      this.foodIndex < this.food.length &&
      newHeadR === this.food[this.foodIndex][0] &&
      newHeadC === this.food[this.foodIndex][1]
    ) {
      // Food eaten: don't remove tail (snake grows)
      this.score++;
      this.foodIndex++;
    } else {
      // No food: remove tail (snake moves)
      this.snake.shift();
    }
    
    return this.score;
  }
}

Time: O(n) for collision check, Space: O(n) where n is snake length

Key insight: Queue naturally represents snake body with head at rear, tail at front.

Pattern 1: LeetCode - Design Snake Game

LeetCode problem implementation:

class SnakeGame {
  private snake: [number, number][] = [];
  private width: number;
  private height: number;
  private food: [number, number][] = [];
  private foodIndex = 0;
  private score = 0;
  
  constructor(width: number, height: number, food: [number, number][]) {
    this.width = width;
    this.height = height;
    this.food = food;
    // Start at (0, 0)
    this.snake.push([0, 0]);
  }
  
  move(direction: string): number {
    const head = this.snake[this.snake.length - 1];
    const [headR, headC] = head;
    
    let newR = headR;
    let newC = headC;
    
    switch (direction) {
      case 'U': newR--; break;
      case 'D': newR++; break;
      case 'L': newC--; break;
      case 'R': newC++; break;
    }
    
    // Check boundaries
    if (newR < 0 || newR >= this.height || newC < 0 || newC >= this.width) {
      return -1;
    }
    
    // Check self collision (excluding tail since it will move)
    const newHead: [number, number] = [newR, newC];
    for (let i = 0; i < this.snake.length - 1; i++) {
      if (this.snake[i][0] === newR && this.snake[i][1] === newC) {
        return -1;
      }
    }
    
    // Add new head
    this.snake.push(newHead);
    
    // Check food
    if (
      this.foodIndex < this.food.length &&
      newR === this.food[this.foodIndex][0] &&
      newC === this.food[this.foodIndex][1]
    ) {
      this.score++;
      this.foodIndex++;
    } else {
      // Remove tail
      this.snake.shift();
    }
    
    return this.score;
  }
}

Time: O(n) per move, Space: O(n)

Key insight: Use queue to represent snake body segments.

Pattern 2: Optimized Snake Game with Set

Using set for O(1) collision detection:

class OptimizedSnakeGame {
  private snake: [number, number][] = [];
  private bodySet = new Set<string>();
  private width: number;
  private height: number;
  private food: [number, number][] = [];
  private foodIndex = 0;
  private score = 0;
  
  constructor(width: number, height: number, food: [number, number][]) {
    this.width = width;
    this.height = height;
    this.food = food;
    this.snake.push([0, 0]);
    this.bodySet.add('0,0');
  }
  
  move(direction: string): number {
    const head = this.snake[this.snake.length - 1];
    const [headR, headC] = head;
    
    let newR = headR;
    let newC = headC;
    
    switch (direction) {
      case 'U': newR--; break;
      case 'D': newR++; break;
      case 'L': newC--; break;
      case 'R': newC++; break;
    }
    
    // Check boundaries
    if (newR < 0 || newR >= this.height || newC < 0 || newC >= this.width) {
      return -1;
    }
    
    const newHeadKey = `${newR},${newC}`;
    
    // Check self collision (excluding tail)
    const tail = this.snake[0];
    const tailKey = `${tail[0]},${tail[1]}`;
    
    // Remove tail from set (will be removed unless food eaten)
    this.bodySet.delete(tailKey);
    
    if (this.bodySet.has(newHeadKey)) {
      return -1; // Collision
    }
    
    // Add new head
    this.snake.push([newR, newC]);
    this.bodySet.add(newHeadKey);
    
    // Check food
    if (
      this.foodIndex < this.food.length &&
      newR === this.food[this.foodIndex][0] &&
      newC === this.food[this.foodIndex][1]
    ) {
      this.score++;
      this.foodIndex++;
      // Don't remove tail (snake grows)
      this.bodySet.add(tailKey); // Add tail back
    } else {
      // Remove tail
      this.snake.shift();
    }
    
    return this.score;
  }
}

Time: O(1) collision check, Space: O(n)

Key optimization: Use set for O(1) collision detection.

Pattern 3: Snake Game with Direction Queue

Queue of directions for smooth movement:

class SnakeGameWithDirections {
  private snake: [number, number][] = [];
  private directionQueue: string[] = [];
  private currentDirection = 'R';
  private width: number;
  private height: number;
  private food: [number, number][] = [];
  private foodIndex = 0;
  private score = 0;
  
  constructor(width: number, height: number, food: [number, number][]) {
    this.width = width;
    this.height = height;
    this.food = food;
    this.snake.push([0, 0]);
  }
  
  changeDirection(direction: string): void {
    // Prevent reverse direction
    const opposites: Record<string, string> = {
      'U': 'D', 'D': 'U', 'L': 'R', 'R': 'L'
    };
    
    if (direction !== opposites[this.currentDirection]) {
      this.directionQueue.push(direction);
    }
  }
  
  move(): number {
    // Process next direction from queue
    if (this.directionQueue.length > 0) {
      this.currentDirection = this.directionQueue.shift()!;
    }
    
    const head = this.snake[this.snake.length - 1];
    const [headR, headC] = head;
    
    let newR = headR;
    let newC = headC;
    
    switch (this.currentDirection) {
      case 'U': newR--; break;
      case 'D': newR++; break;
      case 'L': newC--; break;
      case 'R': newC++; break;
    }
    
    // Check boundaries
    if (newR < 0 || newR >= this.height || newC < 0 || newC >= this.width) {
      return -1;
    }
    
    // Check self collision
    const newHead: [number, number] = [newR, newC];
    for (let i = 0; i < this.snake.length - 1; i++) {
      if (this.snake[i][0] === newR && this.snake[i][1] === newC) {
        return -1;
      }
    }
    
    // Add new head
    this.snake.push(newHead);
    
    // Check food
    if (
      this.foodIndex < this.food.length &&
      newR === this.food[this.foodIndex][0] &&
      newC === this.food[this.foodIndex][1]
    ) {
      this.score++;
      this.foodIndex++;
    } else {
      this.snake.shift();
    }
    
    return this.score;
  }
}

Time: O(1) per move, Space: O(n + m) where m is direction queue size

Key insight: Queue directions for buffered input handling.

Pattern 4: Multiplayer Snake Game

Multiple snakes using separate queues:

class MultiplayerSnakeGame {
  private snakes: Map<number, [number, number][]> = new Map();
  private width: number;
  private height: number;
  private food: [number, number][] = [];
  private foodIndex = 0;
  
  constructor(width: number, height: number, food: [number, number][]) {
    this.width = width;
    this.height = height;
    this.food = food;
  }
  
  addPlayer(playerId: number, startPos: [number, number]): void {
    this.snakes.set(playerId, [startPos]);
  }
  
  move(playerId: number, direction: string): number {
    const snake = this.snakes.get(playerId);
    if (!snake) return -1;
    
    const head = snake[snake.length - 1];
    const [headR, headC] = head;
    
    let newR = headR;
    let newC = headC;
    
    switch (direction) {
      case 'U': newR--; break;
      case 'D': newR++; break;
      case 'L': newC--; break;
      case 'R': newC++; break;
    }
    
    // Check boundaries
    if (newR < 0 || newR >= this.height || newC < 0 || newC >= this.width) {
      this.snakes.delete(playerId);
      return -1;
    }
    
    // Check collisions with all snakes
    const newHead: [number, number] = [newR, newC];
    for (const [id, otherSnake] of this.snakes) {
      const excludeTail = id === playerId ? 1 : 0;
      for (let i = 0; i < otherSnake.length - excludeTail; i++) {
        if (otherSnake[i][0] === newR && otherSnake[i][1] === newC) {
          this.snakes.delete(playerId);
          return -1;
        }
      }
    }
    
    // Add new head
    snake.push(newHead);
    
    // Check food
    if (
      this.foodIndex < this.food.length &&
      newR === this.food[this.foodIndex][0] &&
      newC === this.food[this.foodIndex][1]
    ) {
      this.foodIndex++;
    } else {
      snake.shift();
    }
    
    return snake.length - 1; // Score is length - 1
  }
}

Time: O(n × players), Space: O(n × players)

Key insight: Each player has their own snake queue.

Pattern 5: Snake Game with Obstacles

Snake game with obstacles on the board:

class SnakeGameWithObstacles {
  private snake: [number, number][] = [];
  private obstacles: Set<string> = new Set();
  private width: number;
  private height: number;
  private food: [number, number][] = [];
  private foodIndex = 0;
  private score = 0;
  
  constructor(
    width: number,
    height: number,
    food: [number, number][],
    obstacles: [number, number][]
  ) {
    this.width = width;
    this.height = height;
    this.food = food;
    for (const [r, c] of obstacles) {
      this.obstacles.add(`${r},${c}`);
    }
    this.snake.push([0, 0]);
  }
  
  move(direction: string): number {
    const head = this.snake[this.snake.length - 1];
    const [headR, headC] = head;
    
    let newR = headR;
    let newC = headC;
    
    switch (direction) {
      case 'U': newR--; break;
      case 'D': newR++; break;
      case 'L': newC--; break;
      case 'R': newC++; break;
    }
    
    // Check boundaries
    if (newR < 0 || newR >= this.height || newC < 0 || newC >= this.width) {
      return -1;
    }
    
    // Check obstacles
    if (this.obstacles.has(`${newR},${newC}`)) {
      return -1;
    }
    
    // Check self collision
    const newHead: [number, number] = [newR, newC];
    for (let i = 0; i < this.snake.length - 1; i++) {
      if (this.snake[i][0] === newR && this.snake[i][1] === newC) {
        return -1;
      }
    }
    
    // Add new head
    this.snake.push(newHead);
    
    // Check food
    if (
      this.foodIndex < this.food.length &&
      newR === this.food[this.foodIndex][0] &&
      newC === this.food[this.foodIndex][1]
    ) {
      this.score++;
      this.foodIndex++;
    } else {
      this.snake.shift();
    }
    
    return this.score;
  }
}

Time: O(n) per move, Space: O(n + obstacles)

Key insight: Check obstacles in addition to boundaries and self.

When to Use Queue for Snake Game

Use queue to represent snake when you see:

• "Snake game" - Classic snake game implementation
• "Sequential body" - Body segments in order
• "Growth mechanism" - Adding segments when eating
• "Movement" - Removing tail, adding head
• "Order preservation" - Maintain segment order
• "FIFO behavior" - Tail follows head naturally

Key distinction:

• Queue - Perfect for snake body (FIFO order)
• Array - Can work but queue is more semantic
• Linked List - Overkill for simple snake game

Queue vs Other Structures for Snake

| Structure | Pros | Cons | Use Case |

|-----------|------|------|----------|

| Queue | Natural FIFO, semantic | O(n) collision check | Snake body |

| Array | Simple, indexed access | Less semantic | Simple implementations |

| Set + Queue | O(1) collision check | Extra space | Optimized snake |

| Linked List | True O(1) operations | More complex | Advanced implementations |

Remember:

• Queue for natural snake body representation
• Set + Queue for optimized collision detection

Template (Basic Snake Game)

class SnakeGameTemplate {
  private snake: [number, number][] = [];
  private width: number;
  private height: number;
  private food: [number, number][] = [];
  private foodIndex = 0;
  private score = 0;
  
  constructor(width: number, height: number, food: [number, number][]) {
    this.width = width;
    this.height = height;
    this.food = food;
    this.snake.push([0, 0]);
  }
  
  move(direction: string): number {
    const head = this.snake[this.snake.length - 1];
    const [headR, headC] = head;
    
    // Calculate new head position
    let newR = headR;
    let newC = headC;
    switch (direction) {
      case 'U': newR--; break;
      case 'D': newR++; break;
      case 'L': newC--; break;
      case 'R': newC++; break;
    }
    
    // Check boundaries
    if (newR < 0 || newR >= this.height || newC < 0 || newC >= this.width) {
      return -1;
    }
    
    // Check self collision
    const newHead: [number, number] = [newR, newC];
    for (let i = 0; i < this.snake.length - 1; i++) {
      if (this.snake[i][0] === newR && this.snake[i][1] === newC) {
        return -1;
      }
    }
    
    // Add new head
    this.snake.push(newHead);
    
    // Check food
    if (
      this.foodIndex < this.food.length &&
      newR === this.food[this.foodIndex][0] &&
      newC === this.food[this.foodIndex][1]
    ) {
      this.score++;
      this.foodIndex++;
    } else {
      this.snake.shift(); // Remove tail
    }
    
    return this.score;
  }
}

Time and Space Complexity

Basic Snake Game

• move: O(n) where n is snake length (collision check)
• Space: O(n) for snake queue

Optimized with Set

• move: O(1) collision check
• Space: O(n) for snake queue + set

Multiplayer Snake

• move: O(n × players) for collision checks
• Space: O(n × players)

Note: Collision check is the bottleneck, optimized with set.

Practice Tips

1. Use queue - Queue naturally represents snake body
2. Head at rear - Head is last element (rear of queue)
3. Tail at front - Tail is first element (front of queue)
4. Growth - Don't remove tail when eating food
5. Movement - Remove tail, add new head
6. Collision optimization - Use set for O(1) collision check
7. Boundary check - Always check boundaries first

Common Mistakes

1. Wrong order - Confusing head and tail positions
2. Not removing tail - Forgetting to remove tail when moving
3. Removing tail when eating - Removing tail when food eaten (snake should grow)
4. Collision with tail - Checking collision with tail that will move
5. Boundary errors - Off-by-one errors in boundary checks
6. Direction handling - Not preventing reverse direction
7. Food check order - Checking food before collision

Real-World Applications

Snake game concepts are used in:

• Game Development - Classic snake game implementation
• Path Following - AI pathfinding with constraints
• Animation - Sequential animation frames
• Data Structures - Demonstrating queue usage
• Algorithm Teaching - Teaching queue concepts
• Mobile Games - Simple mobile game development
• Educational Tools - Teaching programming concepts

Related Concepts

• Queue - Data structure for snake body
• Set - For optimized collision detection
• Game Development - Game loop, collision detection
• Path Following - Sequential movement patterns
• FIFO - First in, first out principle

Summary

Snake game using queue demonstrates:

• Queue representation - Snake body as queue of positions
• FIFO order - Head at rear, tail at front
• Growth mechanism - Enqueue when eating, don't dequeue
• Movement - Dequeue tail, enqueue new head
• Collision detection - Check head against body/walls

Key takeaways:

• Queue perfectly represents snake body
• Head is rear of queue, tail is front
• Don't remove tail when eating food (snake grows)
• Use set for O(1) collision detection optimization
• Essential for understanding queue applications

Mastering snake game with queue will help you understand queue applications, implement game logic, and solve problems involving sequential, ordered data structures in coding interviews.