import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class MazeGenerator
{
	static Random RANDOM = new Random();

	public static int[][] generate(int width, int height)
	{
		int[][] maze = new int[width][height];
		initMaze(maze);

		ArrayDeque<int[]> moves = new ArrayDeque<int[]>();
		moves.push(new int[]
		{ width / 2, height / 2 });

		while(moves.size() > 0)
		{
			int[] xy = moves.peek();

			maze[xy[0]][xy[1]] = moves.size() - 1;

			Integer[] dirs =
			{ 0, 1, 2, 3 };

			Collections.shuffle(Arrays.asList(dirs));

			boolean dirFound = false;

			for(int i = 0; i < dirs.length; i++)
			{
				int[] dxy = dir2xy(dirs[i]);

				if(isInRange(maze, xy[0] + dxy[0], xy[1] + dxy[1]) && maze[xy[0] + dxy[0]][xy[1] + dxy[1]] == -1)
				{
					moves.push(new int[]
					{ xy[0] + dxy[0], xy[1] + dxy[1] });
					dirFound = true;

					break;
				}
			}

			if(!dirFound)
			{
				moves.pop();
			}
		}

		return maze;
	}

	public static int[][] generate2(int width, int height)
	{
		int[][] maze = new int[width][height];
		initMaze(maze);

		ArrayDeque<int[]> moves = new ArrayDeque<int[]>();
		moves.push(new int[]
		{ RANDOM.nextInt(width), RANDOM.nextInt(height) });

		while(moves.size() > 0)
		{
			int[] xy = moves.peek();

			maze[xy[0]][xy[1]] = moves.size() - 1;

			Integer[] dirs =
			{ 0, 1, 2, 3 };

			Collections.shuffle(Arrays.asList(dirs));

			boolean dirFound = false;

			for(int i = 0; i < dirs.length; i++)
			{
				int[] dxy = dir2xy(dirs[i]);

				if(isInRange(maze, xy[0] + dxy[0], xy[1] + dxy[1]) && maze[xy[0] + dxy[0]][xy[1] + dxy[1]] == -1)
				{
					moves.push(new int[]
					{ xy[0] + dxy[0], xy[1] + dxy[1] });
					dirFound = true;

					break;
				}
			}

			if(!dirFound)
			{
				moves.pop();
			}
		}

		return maze;
	}

	public static void initMaze(int[][] maze)
	{
		for(int i = 0; i < maze.length; i++)
		{
			for(int j = 0; j < maze[i].length; j++)
			{
				maze[i][j] = -1;
			}
		}
	}

	public static int[] dir2xy(int dir)
	{
		dir %= 4;

		switch(dir)
		{
			case 0:
				return new int[]
				{ 1, 0 };
			case 1:
				return new int[]
				{ 0, 1 };
			case 2:
				return new int[]
				{ -1, 0 };
			case 3:
				return new int[]
				{ 0, -1 };
		}

		//should never happen
		return new int[]
		{ 0, 0 };
	}

	public static boolean isInRange(int[][] maze, int x, int y)
	{
		return x >= 0 && x < maze.length && y >= 0 && y < maze[x].length;
	}

}