Design Snake game


  • 0

    @1337c0d3r that's right, food is scarce in the real case. Ok, last question : how does snake grow up? Is it the case that the snake eats the food and its head moves to the food positions and body enlarges by 1 or somehow different?


  • 0

    @elmirap From my experience playing snake game, when the snake's head moves toward the food, the snake's tail does not move, which essentially grows the length by 1.


  • 0
    D
    class Snake {
    
        public static class Node {
            int x;
            int y;
            Node pre;
            public Node(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
    
        int len, foodIdx;
        Node[][] screen;
        List<int[][]> food;
        Node head;
        Node tail;
        boolean over;
    
        public Snake(int width, int height, List<int[][]> food) {
            this.food = food;
            screen = new Node[width + 1][height + 1];
            head = new Node(0, 0);
            screen[0][0] = head;
            tail = head;
            len = 1;
            foodIdx = 0;
            over = false;
        }
    
        /**
         * @param direction
         *            U = Up, L = Left, R = Right, D = Down
         * @return The game's score after the move. Return -1 if game over.
         */
        public int move(char direction) {
            int x = head.x;
            int y = head.y;
    
            if ('U' == direction) {
                y++;
            } else if ('L' == direction) {
                x--;
            } else if ('R' == direction) {
                x++;
            } else if ('D' == direction) {
                y--;
            }
    
            if (!check(x, y)) {
                over = true;
                return -1;
            }
    
            move(x, y);
            len += eat(x, y);
            return len - 1;
        }
    
        private int eat(int x, int y) {
            if (food != null && food.size() > foodIdx) {
                int[][] f = food.get(foodIdx);
                if (f[x][y] > 0) {
                    foodIdx++;
                    return 1;
                } else {
                    // delete tail node
                    Node tmp = tail;
                    tail = tail.pre;
                    screen[tmp.x][tmp.y] = null;
                }
            }
            return 0;
        }
    
        private boolean check(int x, int y) {
            return (!over && x >= 0 && y >= 0 && x < screen.length && y < screen[0].length && screen[x][y] == null);
        }
    
        private void move(int x, int y) {
            Node n = new Node(x, y);
            screen[x][y] = n;
            head.pre = n;
            head = n;
        }
    
        public void print() {
            int[][] f = null;
            if (food != null && food.size() > foodIdx) {
                f = food.get(foodIdx);
            }
    
            for (int i = 0; i < screen.length; i++) {
                for (int j = 0; j < screen[0].length; j++) {
                    if (f!=null && f.length > i && f[0].length > j && f[i][j] > 0) {
                        System.out.print("2");
                    } else {
                        if (screen[i][j] != null) {
                            System.out.print("1");
                        } else {
                            System.out.print("0");
                        }
                    }
                }
                System.out.println();
            }
    
        }
    }
    

  • 0
    Y

    @daffyang This solution looks very interesting!


  • 0
    D

    @yrxwin thank u
    i think it's an easy way to solve this problem ,but not the best.
    because it uses too much storage.


  • 0

    @daffyang Could you elaborate on what you meant by using too much storage? Any way to optimize it?


  • 0
    D

    @1337c0d3r
    I mean the matrix “screen”, it's like a Sparse Matrix . most of time the snake's size is far less than the matrix's size. I can use LinkedHashMap or LinkedHashSet store the snake.

    public class Screen {
    int width;
    int height;
    LinkedHashSet<Integer> set;

        Screen(int width, int height) {
            this.width = width;
            this.height = height;
            set = new LinkedHashSet<Integer>();
        }
    
        boolean isOccupied(int x, int y) {
            return set.contains(hash(x, y));
        }
    
        void add(int x, int y) {
            set.add(hash(x, y));
        }
    
        void delete(int x, int y) {
            set.remove(hash(x, y));
        }
    
        void deleteOldestNode() {
            Iterator<Integer> it = set.iterator();
            if (it.hasNext()) {
                set.remove(it.next());
            }
        }
    
        private int hash(int x, int y) {
            return y * width + x;
        }
    }

  • 0

    @daffyang here is my implementation :

    public class Snake {	
    	enum Direction {
    		Up,
    		Down,
    		Right,
    		Left
    	}	
    	
    	private Queue<int[]> foodList;
    	private LinkedList<int[]> body;
    	private Set<Integer> bodyIndex;
    	private int width;
    	private int height;	
    	private int score;
    	
    	public Snake(int w, int h , List<int[]> food) {
    		foodList = new LinkedList<>(food);
    		width = w;
    		height = h;
    		body = new LinkedList<>();
    		bodyIndex = new HashSet<>();
    		body.add(new int[] {0,0});
    		bodyIndex.add(0);
    	}
    	
    	private int[] moveToCell(Direction dir, int[] head) {		
    		int res[]  = Arrays.copyOf(head, 2);
    		switch (dir) {
    			case Up : res[0]--; break; 
    			case Down : res[0]++; break; 
    			case Left : res[1]--; break; 
    			case Right : res[1]++; break; 
    		}
    		return res;
    	}
    	
    	int move(Direction dir) {
    		if (foodList.isEmpty())
    			return  score;
    		else {
    			int[] currFood = foodList.peek();
    			int[] next = moveToCell(dir, body.getFirst());	
    			if ((next[0] == width) || (next[0] < 0) || (next[1] == height) || (next[1] < 0))
    				return -1;
    			int index = next[0] * width + next[1];
    			if(bodyIndex.contains(index))
    				return -1;
    			if (next[0] != currFood[0] || next[1] != currFood[1]) {
    				int[] tail = body.removeLast();
    				bodyIndex.remove(tail[0] * width + tail[1]);				
    			}
    			else
    			{
    				foodList.remove();	
    				score++;		
    			}
    			body.addFirst(next);
    			bodyIndex.add(index);	
    						
    			return score;
    		}
    	}
    }

  • 0

    @nixed By the way I think the food should not appear in any block that is occupied by the Snake. To see why this is so, imagine the food appear at (0,0) right at where the Snake is initially positioned. Since the Snake eats the food by default, in which direction does the Snake's tail grow?


  • 0
    N

    @1337c0d3r Good point. You are right, in this case there will be ambiguity in where the tail grows.


  • 0

    maybe should be generated on a field not occupied by the snake


  • 0

    @elmirap Yes I agree. Are you able to simplify your code with this constraint?


  • 0

    @1337c0d3r I can change function "move" to check if the snake moves in cell occupied by its body only when this cell is not occupied by food.
    I also think that if the player avoid moving to snakes body cells, the game will return -1 only when the snake tail is so large as the whole grid

    int move(Direction dir) {
    		if (foodList.isEmpty())
    			return score;
    		else {
    			int[] currFood = foodList.peek();
    			int[] next = moveToCell(dir, body.getFirst());	
    			if ((next[0] == width) || (next[0] < 0) || (next[1] == height) || (next[1] < 0))
    				return -1;
    			int index = next[0] * width + next[1];
    			if (next[0] != currFood[0] || next[1] != currFood[1]) {
    				if(bodyIndex.contains(index))
    					return -1;
    				int[] tail = body.removeLast();
    				bodyIndex.remove(tail[0] * width + tail[1]);				
    			}
    			else
    			{
    				foodList.remove();	
    				score++;		
    			}
    			body.addFirst(next);
    			bodyIndex.add(index);	
    			return score;
    		}
    	}

  • 0

    @elmirap When you eat the food, the tail does not move. Otherwise you check if it touches the body (not including the tail/head). Then update the snake by removing the tail and insert it into the head.


  • 0

    @1337c0d3r yes, right. In my code forgot to check if my next step is tail


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.