Skip to content

Instantly share code, notes, and snippets.

@gamblore
Created July 7, 2013 23:13
Show Gist options
  • Save gamblore/5945328 to your computer and use it in GitHub Desktop.
Save gamblore/5945328 to your computer and use it in GitHub Desktop.
Maze generation in Java. (For libGDX)
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());
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment