import java.util.*;
import java.awt.*;

public class Game {
	final Point OFFSET;
	final Dimension BOARD;
	final int SIZE;
	final int[] DX = new int[] {-1, 0, 1, 0};
	final int[] DY = new int[] {0, -1, 0, 1};
	LinkedList<Point> snake;
	/* lines keeps track of which lines were already draw. this is to prevent */
	/* lines being draw on top of each other and ruining the desired effect. */
	/* each line is designated a number based on its position and its orientation. */
	/* a tree set is used because it is implemented as a red black tree, ensuring */
	/* queries are in logn time. This helps, as there can potentially be hundreds */
	/* of lines being drawn per frame. */
	TreeSet<Integer> lines;
	Point food;
	int direction, newDirection, score;
	boolean grow;
	
	public Game(int w, int h, int s, int ox, int oy) {
		OFFSET = new Point(ox, oy);
		BOARD = new Dimension(w, h);
		SIZE = s;
		snake = new LinkedList<Point>();
		/* add the first three segments of the initial snake */
		snake.add(new Point(BOARD.width-3, BOARD.height/2));
		snake.add(new Point(BOARD.width-2, BOARD.height/2));
		snake.add(new Point(BOARD.width-1, BOARD.height/2));
		/* set the direction to left and reset the score*/
		direction = newDirection = score = 0;
		grow = false;
		addFood();
	}
	
	/* returns the polar angle of the line from (x1, y1) to (x2, y2) */
	public double whatAngle(double x1, double y1, double x2, double y2) {
		if (x1 == x2) return y1 > y2 ? 1.5*Math.PI : 0.5*Math.PI;
		return Math.atan((y2-y1)/(x2-x1)) + (x1 > x2 ? Math.PI : 0);
	}
	
	/* draws a squiggly line from (x1, y1) to (x2, y2) */
	public void squiggle(double x1, double y1, double x2, double y2, Graphics2D g2d) {
		/* how big of an increment the line will be drawn by */
		final double INC = 7;
		/* delta angle. the amount the angle can change by for every incremental drawing of the line */
		final double DANG = 28;
		/* last x/y and next x/y as well as the current angle */
		double lx, ly, nx, ny, angle;
		lx = x1; ly = y1;
		
		/* while the end point of the drawn line isn't within INC of the desired endpoint... */
		while((x2-lx)*(x2-lx) + (y2-ly)*(y2-ly) > INC*INC) {
			/* use a derivative of brownian motion to generate the line. */
			/* change the old direction to a random new one within DANG degrees of the old one */
			angle = Math.random()*(Math.PI*DANG/180) - Math.PI*DANG/360;
			/* move the line forward in the dew direction */
			nx = lx + Math.cos(whatAngle(lx,ly,x2,y2) + angle)*INC;
			ny = ly + Math.sin(whatAngle(lx,ly,x2,y2) + angle)*INC;
			g2d.drawLine((int)lx + OFFSET.x, (int)ly + OFFSET.y, (int)nx + OFFSET.x, (int)ny + OFFSET.y);
			/* update the current endpoint */
			lx = nx;
			ly = ny;
		}
		/* once we are within INC of the endpoint, we can draw a line directly to it */
		g2d.drawLine((int)lx + OFFSET.x, (int)ly + OFFSET.y, (int)x2 + OFFSET.x, (int)y2 + OFFSET.y);
	}
	
	/* drawing the board consists of drawing the border, the food and the snake. */
	void drawBoard(Graphics2D g2d) {
		Iterator<Point> it = snake.iterator();
		/* previous, current and next segment of the snake */
		Point p, c, n;
		p = null;
		c = it.next();
		n = it.next();
		/* prepare the drawn line set */
		lines = new TreeSet<Integer>();
		/* draw the top and bottom portions of the border. we know no lines */
		/* have been drawn yet, so we don't perform any checks. */
		for (int i = 0; i < BOARD.width; i++) {
			squiggle(i*SIZE, 0, i*SIZE + SIZE, 0, g2d);
			squiggle(i*SIZE, BOARD.height*SIZE, i*SIZE + SIZE, BOARD.height*SIZE, g2d);
			lines.add(i);
			lines.add(BOARD.height*BOARD.width + i);
		}
		/* draw the left and right portions of the border. we know no vertical */
		/* lines have been drawn yet, so we don't perform any checks. */
		for (int i = 0; i < BOARD.height; i++) {
			squiggle(0, i*SIZE, 0, i*SIZE + SIZE, g2d);
			squiggle(BOARD.width*SIZE, i*SIZE, BOARD.width*SIZE, i*SIZE + SIZE, g2d);
			lines.add(i*BOARD.width + BOARD.width*(BOARD.height + 1));
			lines.add(i*BOARD.width + BOARD.width + BOARD.width*(BOARD.height + 1));
		}
		/* draw the peice of food. check whether each of the four sides */
		/* is touching a border */
		if (!lines.contains(food.y*BOARD.width + food.x)) {
			lines.add(food.y*BOARD.width + food.x);
			squiggle(food.x*SIZE, food.y*SIZE, food.x*SIZE + SIZE, food.y*SIZE, g2d);
		}
		if (!lines.contains((food.y + 1)*BOARD.width + food.x)) {
			lines.add((food.y + 1)*BOARD.width + food.x);
			squiggle(food.x*SIZE, food.y*SIZE + SIZE, food.x*SIZE + SIZE, food.y*SIZE + SIZE, g2d);
		}
		if (!lines.contains(food.y*BOARD.width + food.x + BOARD.width*(BOARD.height + 1))) {
			lines.add(food.y*BOARD.width + food.x + BOARD.width*(BOARD.height + 1));
			squiggle(food.x*SIZE, food.y*SIZE, food.x*SIZE, food.y*SIZE + SIZE, g2d);
		}
		if (!lines.contains(food.y*BOARD.width + food.x + BOARD.width*(BOARD.height + 1) + 1)) {
			lines.add(food.y*BOARD.width + food.x + BOARD.width*(BOARD.height + 1) + 1);
			squiggle(food.x*SIZE + SIZE, food.y*SIZE, food.x*SIZE + SIZE, food.y*SIZE + SIZE, g2d);
		}
		/* draw each segment of the snake keeping track of the next and previous */
		/* segments in order to determine which lines need to be drawn. */
		do {
			drawSegment(p, c, n, g2d);
			p = c;
			c = n;
			n = it.hasNext() ? it.next() : null;
		} while(c != null);
	}
	
	/* draws a segment of the snake, where a segment is one of the small squares */
	/* which the snake is comprised of. there are four cases where the side of a */
	/* segement wont be drawn, namely when the side is connected to another segment */
	/* or wall. when a line is draw, it is added to the set of drawn lines so that */
	/* it is not draw again. */
	void drawSegment(Point p, Point c, Point n, Graphics2D g2d) {
		/* check if its ok to draw the top line of the segment */
		if ((p == null || p.x != c.x || (p.x == c.x && p.y > c.y)) &&
			(n == null || n.x != c.x || (n.x == c.x && n.y > c.y)) &&
			!lines.contains(c.y*BOARD.width + c.x)) {
				lines.add(c.y*BOARD.width + c.x);
				squiggle(c.x*SIZE, c.y*SIZE, c.x*SIZE + SIZE, c.y*SIZE, g2d);
		}
		/* check if its ok to draw the bottom line of the segment */
		if ((p == null || p.x != c.x || (p.x == c.x && p.y < c.y)) &&
			(n == null || n.x != c.x || (n.x == c.x && n.y < c.y)) &&
			!lines.contains((c.y + 1)*BOARD.width + c.x)) {
				lines.add((c.y + 1)*BOARD.width + c.x);
				squiggle(c.x*SIZE, c.y*SIZE + SIZE, c.x*SIZE + SIZE, c.y*SIZE + SIZE, g2d);
		}
		/* check if its ok to draw the left line of the segment */
		if ((p == null || p.y != c.y || (p.y == c.y && p.x > c.x)) &&
			(n == null || n.y != c.y || (n.y == c.y && n.x > c.x)) &&
			!lines.contains(c.y*BOARD.width + c.x + BOARD.width*(BOARD.height + 1))) {
				lines.add(c.y*BOARD.width + c.x + BOARD.width*(BOARD.height + 1));
				squiggle(c.x*SIZE, c.y*SIZE, c.x*SIZE, c.y*SIZE + SIZE, g2d);
		}
		/* check if its ok to draw the right line of the segment */
		if ((p == null || p.y != c.y || (p.y == c.y && p.x < c.x)) &&
			(n == null || n.y != c.y || (n.y == c.y && n.x < c.x)) &&
			!lines.contains(c.y*BOARD.width + c.x + BOARD.width*(BOARD.height + 1) + 1)) {
				lines.add(c.y*BOARD.width + c.x + BOARD.width*(BOARD.height + 1) + 1);
				squiggle(c.x*SIZE + SIZE, c.y*SIZE, c.x*SIZE + SIZE, c.y*SIZE + SIZE, g2d);
		}
	}
	
	synchronized void moveSnake() {
		Point head;
		direction = newDirection;
		/* if the snake doesnt grow, remove last segment and add a new one to the head */
		if (!grow) snake.removeLast();
		else grow = false;
		
		head = new Point(snake.peek().x + DX[direction], snake.peek().y + DY[direction]);
		snake.addFirst(head);
		/* check if the move results in food being eaten */
		if (head.x == food.x && head.y == food.y) {
			score++ ;
			grow = true;
			addFood();
		}
	}
	
	/* change the current direction of the snake. make sure the new direction */
	/* isn't the reverse of the current direction. ie. instant death */
	/* an intermediate direction variable is kept in order to preven multiple */
	/* moves being made in a single frame and resulting in a reverse direction */
	synchronized void changeDirection(int d) {
		if (d != (direction + 2)%4) newDirection = d;
	}
	
	/* add a peice of food such that it is not on the snake */
	void addFood() {
		boolean collision;
		do {
			collision = false;
			food = new Point((int)(Math.random()*BOARD.width), (int)(Math.random()*BOARD.height));
			for (Point p : snake)
				if (p.x == food.x && p.y == food.y)
					collision = true;
		} while (collision);
	}
	
	/* check whether the snake is out of bounds or if it's head is on it's tail */
	boolean checkCollision() {
		Point head = snake.peek();
		if(head.x < 0 || head.x >= BOARD.width || head.y < 0 || head.y >= BOARD.height) return true;
		
		for (Point p : snake)
			if (p != head && p.x == head.x && p.y == head.y)
				return true;
		
		return false;
	}

}