Design Snake Game
Design a Snake game that is played on a device with screen size height x width. Play the game online if you are not familiar with the game.
The snake is initially positioned at the top left corner (0, 0) with a length of 1 unit.
You are given an array food where food[i] = (ri, ci) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game's score both increase by 1.
Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.
When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.
The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).
Implement the SnakeGame class:
- SnakeGame(int width, int height, int[][] food) Initializes the object with a screen of size height x width and the positions of the food.
- int move(String direction) Returns the score of the game after applying one direction move by the snake. If the game is over, return -1.
Example 1:
Input:
Output:
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: The dimensions of the game grid.
- 1 ≤ food.length ≤ 50: The number of food items in the game.
- food[i].length == 2: Each food item has two values (row and column).
- 0 ≤ ri < height: The row index of the food is between 0 and height-1.
- 0 ≤ ci < width: The column index of the food is between 0 and width-1.
- direction.length == 1: The direction of the snake's move is a single character.
- direction is 'U', 'D', 'L', or 'R': The snake's direction is one of the following: 'U' (up), 'D' (down), 'L' (left), or 'R' (right).
- At most 104 calls will be made to move: There will be a maximum of 10,000 moves made.
Solution:
Solution: A Design Problem Explained
The Classic Snake Game: Let's go over the details in the problem statement once:
-
Grid Dimensions: We're given the width and height of the grid over which the snake moves.
-
Food Items: Additionally, we are also given the list of grid positions where the food will appear one after the other.
Just like the traditional snake, the next food item only appears once the current one is consumed.
-
Snake Growth: Consuming a piece of food increases the length of the snake by one.
In terms of our problem statement, the length of the snake increases by one more cell on the grid, with each cell being of unit length and width.
-
Snake Movement: The snake can move in four directions: Up (U), Down (D), Left (L), and Right (R).
Every time the snake has to be moved, the
move()function is called. This is the only function we need to focus on in this question. -
Game Over Conditions: The game ends when any of the following conditions happen:
-
The snake becomes too long to potentially fit inside the grid.
-
The snake hits one of the boundaries, which would happen in the previous case as well.
-
The snake bites itself, i.e., when the head of the snake collides with its body in the next move.
-
The Snake Game: A Design Challenge
Designing the Snake game requires careful consideration of the game mechanics and user experience.
Let's delve into the various aspects that need to be taken into account:
1. Grid Setup
The first step is to create a grid with the given width and height dimensions.
The grid will act as the playing field for the snake.
Each cell in the grid represents a position where the snake or food can be present.
Conclusion
The Snake game is a classic that has entertained generations of gamers.
Its simplicity and addictive gameplay make it an enduring favorite.
Designing the game requires thoughtful consideration of grid setup, snake movement, food placement, collision detection, and game over conditions.
The infinite wall mode adds an extra layer of complexity, allowing the snake to move across boundaries.
So, let's relive the nostalgia and dive into the world of the Snake game once again!
FAQs
-
Can the Snake game be played on modern smartphones?
Yes, the Snake game can be played on modern smartphones. There are numerous mobile apps and online versions available that provide an updated take on the classic game.
-
How can I control the movement of the snake in the game?
The movement of the snake can be controlled using various input mechanisms. On smartphones, you can typically control the snake's direction using swipe gestures. On computers, arrow keys or WASD keys are commonly used.
-
What happens when the snake collides with a wall? In the traditional Snake game, when the snake collides with a wall, it's considered a collision, and the game ends. However, in the infinite wall mode, the snake moves across the boundaries, reappearing on the opposite side.
-
Is the Snake game suitable for players of all ages?
Yes, the Snake game is suitable for players of all ages. Its simple mechanics and easy-to-understand gameplay make it accessible to both young and old players.
-
Are there any advanced versions of the Snake game available?
Yes, there are advanced versions of the Snake game available that introduce additional features and challenges. These versions often include power-ups, different game modes, and visually enhanced graphics to provide a more immersive gaming experience.
class SnakeGame {
HashMap, Boolean> snakeMap;
Deque> snake;
int[][] food;
int foodIndex;
int width;
int height;
/**
* Initialize your data structure here.
*
* @param width - screen width
* @param height - screen height
* @param food - A list of food positions E.g food = [[1,1], [1,0]] means the first food is
* positioned at [1,1], the second is at [1,0].
*/
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.food = food;
this.snakeMap = new HashMap, Boolean>();
this.snakeMap.put(new Pair(0, 0), true); // intially at [0][0]
this.snake = new LinkedList>();
this.snake.offerLast(new Pair(0, 0));
}
/**
* Moves the snake.
*
* @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
* @return The game's score after the move. Return -1 if game over. Game over when snake crosses
* the screen boundary or bites its body.
*/
public int move(String direction) {
Pair snakeCell = this.snake.peekFirst();
int newHeadRow = snakeCell.getKey();
int newHeadColumn = snakeCell.getValue();
switch (direction) {
case "U":
newHeadRow--;
break;
case "D":
newHeadRow++;
break;
case "L":
newHeadColumn--;
break;
case "R":
newHeadColumn++;
break;
}
Pair newHead = new Pair(newHeadRow, newHeadColumn);
Pair currentTail = this.snake.peekLast();
// Boundary conditions.
boolean crossesBoundary1 = newHeadRow < 0 || newHeadRow >= this.height;
boolean crossesBoundary2 = newHeadColumn < 0 || newHeadColumn >= this.width;
// Checking if the snake bites itself.
boolean bitesItself = this.snakeMap.containsKey(newHead) && !(newHead.getKey() == currentTail.getKey() && newHead.getValue() == currentTail.getValue());
// If any of the terminal conditions are satisfied, then we exit with rcode -1.
if (crossesBoundary1 || crossesBoundary2 || bitesItself) {
return -1;
}
// If there's an available food item and it is on the cell occupied by the snake after the move,
// eat it.
if ((this.foodIndex < this.food.length)
&& (this.food[this.foodIndex][0] == newHeadRow)
&& (this.food[this.foodIndex][1] == newHeadColumn)) {
this.foodIndex++;
} else {
this.snake.pollLast();
this.snakeMap.remove(currentTail);
}
// A new head always gets added
this.snake.addFirst(newHead);
// Also add the head to the set
this.snakeMap.put(newHead, true);
return this.snake.size() - 1;
}
}
/**
* Your SnakeGame object will be instantiated and called as such:
* SnakeGame obj = new SnakeGame(width, height, food);
* int param_1 = obj.move(direction);
*/
Approach: Queue and Hash Set
Intuition:
Let's start by thinking about how we want to store the snake.
In terms of the grid, a snake is just an ordered collection of cells.
We can technically use an array to store the cells representing the snake.
However, we would need to instantiate an array the size of width * height of the grid.
This would be necessary since a snake can occupy all the cells in the grid in the worst case, forming a spiral-like shape. But this scenario is highly unlikely due to the random nature of food items appearing on the grid.
Despite the unlikely scenario, we would still need an array the size of the grid to accommodate the snake in case this happens.
The main problem with using an array arises when we need to move the snake from one position to another.
Let’s consider a snake occupying 4 cells in the grid:
Snake's cells: [(1,1), (1,2), (1,3), (2,3)]
If the snake moves to the right (direction 'R'), its new positions will be:
New Snake's cells: [(1,2), (1,3), (2,3), (2,4)]
To achieve this with an array, we would have to move all the cells around per move, which is not ideal. Although we could develop a more complex logic for handling movement in an array, it would be inefficient due to the fixed space requirement of the array.
Let’s see which data structure would naturally fit our requirements for managing the snake.
We need a structure that allows us to:
- Dynamically add new cells to the snake's body and move the snake efficiently.
- Move the snake in constant time across the grid.
Now, let’s examine the snake's movement in detail:
Move with No Food:
Before the move, the snake occupies the following cells: (1,1), (1,2), (1,3), (2,3)
After the snake moves right, the cells are: (1,2), (1,3), (2,3), (2,4)
This can be seen as a "sliding window" where the tail (1,1) is removed and the new head (2,4) is added.
Move with Food Consumption:
Now, let’s look at the case where the snake consumes a food item and grows in length.
Suppose the snake moves right to (2,4), and there is food at this position. The snake now grows from 4 to 5 cells:
Before the move, the snake occupies: (1,1), (1,2), (1,3), (2,3)
After the move (and consuming food): (1,1), (1,2), (1,3), (2,3), (2,4)
Here, the snake's tail remains the same, but a new head is added.
These are the two main types of moves that happen in the game, aside from the termination conditions.
Required Operations:
The data structure we choose must support the following operations efficiently:
- Dynamic growth in size (the snake grows when it eats food, but it never shrinks).
- Maintaining an ordered list of cells to represent the snake.
- Extracting the tail and adding a new head to the ordered list after each move.
The Queue data structure fits these requirements perfectly. We need quick access to both the first and last elements in an ordered list, which is exactly what a queue provides. A queue can be implemented using an array or a linked list. Since we need dynamic resizing, we use a linked list-based implementation.
Algorithm:
Algorithm to solve the problem:
1. Initialize a queue containing a single cell (0,0), the initial position of the snake.
Note that this initialization is done in the constructor, not the move function.
2. In the move function, compute the new head based on the direction of the move.
The new head is essential to check if the snake hits a boundary and ends the game.
Termination Conditions:
1. If the snake crosses the grid boundaries, the game ends. This is checked by ensuring that the new head satisfies:
new_head[0] < 0 or new_head[0] > height or new_head[1] < 0 or new_head[1] > width
2. If the snake bites itself, the game ends. The tail of the snake is not considered part of the body, so the check is done by verifying if the new head already exists in the queue.
To make this check efficient, we use a dictionary to track the positions of the snake.
3. If neither condition is met, we update the queue with the new head and possibly remove the tail.
If the new head lands on a food position, we add the new head to the queue without removing the tail, since the snake grows in size.
Finally, we return the length of the snake if the move is valid, or -1 if the game is over.
class SnakeGame {
HashMap, Boolean> snakeMap;
Deque> snake;
int[][] food;
int foodIndex;
int width;
int height;
/**
* Initialize your data structure here.
*
* @param width - screen width
* @param height - screen height
* @param food - A list of food positions E.g food = [[1,1], [1,0]] means the first food is
* positioned at [1,1], the second is at [1,0].
*/
public SnakeGame(int width, int height, int[][] food) {
this.width = width;
this.height = height;
this.food = food;
this.snakeMap = new HashMap, Boolean>();
this.snakeMap.put(new Pair(0, 0), true); // intially at [0][0]
this.snake = new LinkedList>();
this.snake.offerLast(new Pair(0, 0));
}
/**
* Moves the snake.
*
* @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
* @return The game's score after the move. Return -1 if game over. Game over when snake crosses
* the screen boundary or bites its body.
*/
public int move(String direction) {
Pair snakeCell = this.snake.peekFirst();
int newHeadRow = snakeCell.getKey();
int newHeadColumn = snakeCell.getValue();
switch (direction) {
case "U":
newHeadRow--;
break;
case "D":
newHeadRow++;
break;
case "L":
newHeadColumn--;
break;
case "R":
newHeadColumn++;
break;
}
Pair newHead = new Pair(newHeadRow, newHeadColumn);
Pair currentTail = this.snake.peekLast();
// Boundary conditions.
boolean crossesBoundary1 = newHeadRow < 0 || newHeadRow >= this.height;
boolean crossesBoundary2 = newHeadColumn < 0 || newHeadColumn >= this.width;
// Checking if the snake bites itself.
boolean bitesItself = this.snakeMap.containsKey(newHead) && !(newHead.getKey() == currentTail.getKey() && newHead.getValue() == currentTail.getValue());
// If any of the terminal conditions are satisfied, then we exit with rcode -1.
if (crossesBoundary1 || crossesBoundary2 || bitesItself) {
return -1;
}
// If there's an available food item and it is on the cell occupied by the snake after the move,
// eat it.
if ((this.foodIndex < this.food.length)
&& (this.food[this.foodIndex][0] == newHeadRow)
&& (this.food[this.foodIndex][1] == newHeadColumn)) {
this.foodIndex++;
} else {
this.snake.pollLast();
this.snakeMap.remove(currentTail);
}
// A new head always gets added
this.snake.addFirst(newHead);
// Also add the head to the set
this.snakeMap.put(newHead, true);
return this.snake.size() - 1;
}
}
/**
* Your SnakeGame object will be instantiated and called as such:
* SnakeGame obj = new SnakeGame(width, height, food);
* int param_1 = obj.move(direction);
*/
Complexity Analysis
Let W represent the width of the grid, H represent the height of the grid, and N represent the number of food items in the list.
Time Complexity:
The time complexity of the move function is O(1).
This is because:
- Checking if the snake bites itself takes constant time, as we use a dictionary to search for the element.
- Adding or removing an element from the queue is done in constant time.
Space Complexity:
The space complexity is O(W × H + N).
This consists of:
- O(N) for the food data structure.
- O(W × H) for the snake and the
snake_setdata structures, where the snake may occupy up to all the cells in the grid.
In the worst case, the snake can occupy all the cells of the grid, as explained earlier in the article.
