Maze.java

package net.gamblore.maze.entities;

import java.util.LinkedList;
import java.util.List;

import com.badlogic.gdx.Gdx;

public class Maze {
    private static final String TAG = "Maze";
	
	public static final int N = 1;
	public static final int S = 2;
	public static final int E = 4;
	public static final int W = 8;
	
	private static final int[] DX = new int[] {0, /*N*/ 0, /*S*/ 0, 0, /*E*/ 1, 0, 0, 0, /*W*/ -1};  
	private static final int[] DY = new int[] {0, /*N*/ -1, /*S*/ 1, 0, /*E*/ 0, 0, 0, 0, /*W*/ 0}; 
	private static final int[] OPPOSITE = new int[] {0, /*N*/ S, /*S*/ N, 0, /*E*/ W, 0, 0, 0, /*W*/ E}; 
	
	private int mWidth, mHeight;
	
	private int[][] mGrid;
	private List<MazeEdge> mEdges;
	
	
	private class MazeBuilderEdge {
		public int x, y, direction;
		public MazeBuilderEdge(int x, int y, int direction) {
			this.x = x;
			this.y = y;
			this.direction = direction;
		}
	}
	
	private class TreeNode {
		public TreeNode parent; 
		
		
		public TreeNode getParent() {
			TreeNode node = this;
			while (!node.isRoot()) {
				node = node.parent;
			}
			return node;
		}
		
		public boolean isRoot() {
			return parent == null;
		}
		
		public void setParent(TreeNode newParent) {
			if (newParent.isRoot()) {
				parent = newParent;
			} else {
				parent = newParent.getParent();
			}
		}
	}
	
	private class Tree {
		private TreeNode mRoot;
		
		public Tree(TreeNode root) {
			mRoot = root;
		}
		
		public TreeNode getRoot() {
			return mRoot.getParent();
		}
		
		public void joinWith(Tree otherTree) {
			otherTree.getRoot().setParent(mRoot);
		}
	}
	
	public static class MazeEdge {
		public int sX, sY, eX, eY;
		
		public MazeEdge(int startX, int startY, int endX, int endY) {
			sX = startX;
			sY = startY;
			eX = endX;
			eY = endY;
		}
		
		public String toString() {
			return "MazeEdge(" + sX + ", " + sY + ", " + eX + ", " + eY + ")";
		}
	}
	
	public Maze(int width, int height) {
		generateMaze(width, height);
	}
	
	private void generateMaze(int width, int height) {
		mWidth = width;
		mHeight = height;
		
		Tree[][] sets = new Tree[mHeight][mWidth];
		for (int y = 0; y < mHeight; y++) {
			for (int x = 0; x < mWidth; x++) {
				sets[y][x] = new Tree(new TreeNode());
			}
		}
		
		mGrid = new int[mHeight][mWidth];
		
		List<MazeBuilderEdge> edges = new LinkedList<MazeBuilderEdge>();
		
		for (int y = 0; y < mHeight; y++) {
			for (int x = 0; x < mWidth; x++) {
				if (y > 0)
					edges.add(new MazeBuilderEdge(x, y, N));
				if (x > 0) 
					edges.add(new MazeBuilderEdge(x, y, W));
			}
		}
		
		while (!edges.isEmpty()) {
			MazeBuilderEdge edge = edges.remove((int)(Math.random()*edges.size()));
			int x = edge.x;
			int y = edge.y;
			int direction = edge.direction;
			
			int nx = x + DX[direction];
			int ny = y + DY[direction];
			
			Tree set1, set2;
			set1 = sets[y][x];
			set2 = sets[ny][nx];
			
			if (set1.getRoot() != set2.getRoot()) {
				set1.joinWith(set2);
				mGrid[y][x] |= direction;
				mGrid[ny][nx] |= OPPOSITE[direction];
			}
		}
	}
	
	public int getCell(int x, int y) {
		return mGrid[y][x];
	}
	
	public int[][] getGrid() {
		return mGrid;
	}
	
    /**
     * WIP
     */
	public List<MazeEdge> getEdges() {
		if (mEdges != null) {
			return mEdges;
		}
		
		mEdges = new LinkedList<Maze.MazeEdge>();
		int mazeCheck[][] = new int[mHeight][mWidth];
		
		// Horizontal
		for (int y = 0; y < mHeight; y++) {
			int sX = -1;
			for (int x = 0; x < mWidth; x++) {
				int cell = mGrid[y][x];
				
				// Already visited
				if ((mazeCheck[y][x] & 1) != 0) {
					continue;
				}
				
				// Not started
				if (sX == -1 && (cell & S) != 0) {
					sX = x;
					continue;
				}
				
				// Finished
				if (sX != -1 && (cell & S) == 0) {
					mEdges.add(new MazeEdge(sX, y, x, y));
					for (int i = sX; i < x; i++) {
						mazeCheck[y][i] |= 1;
					}
						
					sX = -1;
					continue;
				}
			}
		}
		
		// Vertical
		for (int x = 0; x < mWidth; x++) {
			int sY = -1;
			for (int y = 0; y < mHeight; y++) {
				int cell = mGrid[y][x];
				
				if ((mazeCheck[y][x] & 2) != 0) {
					continue;
				}
				
				if (sY == -1 && (cell & E) != 0) {
					sY = x;
					continue;
				}
				if (sY != -1 && (cell & E) == 0) {
					mEdges.add(new MazeEdge(x, sY, x, y));
					for (int i = sY; i < y; i++) {
						mazeCheck[i][x] |= 2;
					}
					
					sY = -1;
					continue;
				}
			}
		}
		
		return mEdges;
	}
	
	public void display() {
		Gdx.app.log(TAG, new String(new char[mWidth]).replace("\0", " _"));
		
		for (int y = 0; y < mHeight; y++) {
			StringBuilder sb = new StringBuilder();
			sb.append('|');
			
			for (int x = 0; x < mWidth; x++) {
				int cell = mGrid[y][x];
				if (cell == 0)
					sb.append(' ');
				if ((cell & S) != 0) { 
					sb.append(' ');
				} else {
					sb.append('_');
				}
				
				if ((cell & E) != 0) {
					if (((cell | mGrid[y][x+1]) & S) != 0) {
						sb.append(' ');
					} else {
						sb.append('_');
					}
				} else {
					sb.append('|');
				}
			}
			Gdx.app.log(TAG, sb.toString());
		}
	}
}