Design Snake Game

Problem Statement

The goal is to design a "Snake Game" typically found on older cell phones and simple gaming consoles, programmed to run on a device with a defined screen size labeled by its width and height. Initially, the game places a snake of unit length at the upper left corner of the screen. As the game progresses, pieces of food, specified by coordinates within the food array, appear on the screen one after another. Each time the snake consumes a piece of food, its length increases by one unit, as does the player's score.

However, the game imposes a natural limit to the snake's unfettered eating: food pieces will never appear on a block currently occupied by the snake's body. The gameplay continues with the snake moving in specified directions until it either exits the boundary of the play area or collides into itself, at which point the game concludes.

The functionality for this game is encapsulated in the SnakeGame class, which initializes the game setting with the specified screen and food positions and processes the movement commands, returning the current score or indicating the game's end.

Examples

Example 1

Input

["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]

Output

[null, 0, 0, 1, 1, 2, -1]

Explanation

SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // return 0
snakeGame.move("D"); // return 0
snakeGame.move("R"); // return 1, snake eats the first piece of food. The second piece of food appears at (0, 1).
snakeGame.move("U"); // return 1
snakeGame.move("L"); // return 2, snake eats the second food. No more food appears.
snakeGame.move("U"); // return -1, game over because snake collides with border

Constraints

• 1 <= width, height <= 104
• 1 <= food.length <= 50
• food[i].length == 2
• 0 <= ri < height
• 0 <= ci < width
• direction.length == 1
• direction is 'U', 'D', 'L', or 'R'.
• At most 104 calls will be made to move.

Approach and Intuition

In approaching the design of the Snake Game, it's helpful to understand both the operational mechanics provided in the problem statement and the game’s structure from common gameplay experiences:

1. Initialization:

   • The SnakeGame object is initialized with width, height, and the food coordinates.
   • The snake starts at position (0,0) with an initial length of 1.

2. Game Mechanics:

   • The game accepts a move command, which specifies the direction of the snake's next move (one of 'U' for up, 'D' for down, 'L' for left, and 'R' for right).
   • The snake moves one block per command in the specified direction.

3. Food Consumption and Growth:

   • If the snake's new head position after a move matches the location of the next piece of food, the snake grows in length by one unit and the corresponding piece of food is considered eaten. The next piece will then appear according to the sequence provided in the food array.
   • The game keeps track of how many pieces of food have been eaten using an index that gets incremented with each consumed piece.

4. Checking Game Termination Conditions:

   • If the snake attempts to move outside the confines of the screen's width or height, the game ends.
   • If the snake moves into any part of its own body, the game also ends.
   • The move method returns -1 if the game is over; otherwise, it returns the current score, which equates to the number of food items eaten.

5. Example Walkthrough:

   • Consider the given example with initial settings and a series of moves.
   • Track the snake’s head, ensure it does not collide with the wall or itself, manage food consumption accurately, and update the game state and score accordingly.

This strategy ensures the accurate simulation of the Snake Game, providing clear rules for movement, growth, and game-ending scenarios.

Solutions

class GameOfSnake {
    
HashMap<Pair<Integer, Integer>, Boolean> snakePositionMap;
Deque<Pair<Integer, Integer>> snakeBody;
int[][] foodItems;
int foodPointer;
int maxWidth;
int maxHeight;
    
public GameOfSnake(int maxWidth, int maxHeight, int[][] foodItems) {
    this.maxWidth = maxWidth;
    this.maxHeight = maxHeight;
    this.foodItems = foodItems;
    this.snakePositionMap = new HashMap<Pair<Integer, Integer>, Boolean>();
    this.snakePositionMap.put(new Pair<Integer, Integer>(0,0), true);
    this.snakeBody = new LinkedList<Pair<Integer, Integer>>();
    this.snakeBody.offerLast(new Pair<Integer, Integer>(0,0));
}
    
public int adjustSnake(String direction) {
    
    Pair<Integer, Integer> headCell = this.snakeBody.peekFirst();
    int nextRow = headCell.getKey();
    int nextCol = headCell.getValue();
    
    switch (direction) {
    case "U":
        nextRow--;
        break;
    case "D":
        nextRow++;
        break;
    case "L":
        nextCol--;
        break;
    case "R":
        nextCol++;
        break;
    }
    
    Pair<Integer, Integer> newHeadPosition = new Pair<Integer, Integer>(nextRow, nextCol);
    Pair<Integer, Integer> tailCell = this.snakeBody.peekLast();
    
    boolean hitsBoundary = nextRow < 0 || nextRow >= this.maxHeight || nextCol < 0 || nextCol >= this.maxWidth;
    boolean selfCollision = this.snakePositionMap.containsKey(newHeadPosition) && !(newHeadPosition.getKey() == tailCell.getKey() && newHeadPosition.getValue() == tailCell.getValue());
    
    if (hitsBoundary || selfCollision) {
        return -1;
    }
    
    if ((this.foodPointer < this.foodItems.length)
        && (this.foodItems[this.foodPointer][0] == nextRow)
        && (this.foodItems[this.foodPointer][1] == nextCol)) {
        this.foodPointer++;
    } else {
        this.snakeBody.pollLast();
        this.snakePositionMap.remove(tailCell);
    }
    
    this.snakeBody.addFirst(newHeadPosition);
    this.snakePositionMap.put(newHeadPosition, true);
    
    return this.snakeBody.size() - 1;
}
        
}