Massive Maze

MassiveMaze.java

import java.util.ArrayList;
//Saving Maze as Monochrome Bitmap
import java.io.*;
import java.awt.Color;
import java.awt.image.BufferedImage;
import javax.imageio.ImageIO;
import java.io.IOException;

//     __   _    ___  _____ _____ ______ _   __ _____
//    /  | / |  /   |/ ___// ___/__  __/| | / // ___/ 
//   /   |/  | / /| |\__  \\__  \  | |  | |/ // __/
//  / /|  /| |/ __  |___| |___| |__| |__|   // /___
// /_/ |_/ |_|_/  |_/_____/_____/______/|__/ \____/
//            __   _    ___  _____   _____
//           /  | / |  /   |/__  /  / ___/
//          /   |/  | / /| |  / /  / __/
//         / /|  /| |/ __  | / /__/ /___
//        /_/ |_/ |_|_/  |_|/____/\____/
//

/** 
 * A Maze that is split up into areas to reduce memory usage.
 * Between each area is a barrier that delegates the pathways from
 * area to area. Each area is created using Prim's algorithm with
 * the difference of having several initial frontier cells instead
 * of one. Every individual area is then saved as a Monochrome 
 * bitmap (JUST Black and White) to minimize the size of each image
 * file. The actual size of each area in memory is calculated by: <br>
 * <br>
 * bits = (areaWidth * 2 + 1) * (areaHeight * 2 + 1)<br>
 * <br>
 * The amount of pathways in a barrier is calculated by:<br>
 * <br>
 * (barrierLength * percentOfBarrierFilled)<br>
 * <br>
 * @author Philip Diffenderfer
 */
@SuppressWarnings("unused")
public class MassiveMaze {

	/** The maximum size in cells an Area can be. */
	public static int MAX_WIDTH = 1000;
	public static int MAX_HEIGHT = 1000;
	/** The value a cell has if its a wall, by default all cells are FILLED. */
	public static final boolean FILLED = false;
	/** The value a cell has if its an opening or path. */
	public static final boolean EMPTY = true;
	
	/** The maze cells of the current Area. */
	private boolean[][] cells = null;
	/** The cells that are on the horizontal barrier. */
	private boolean[] horBarrier = null;
	/** The cells that are on the vertical barrier. */
	private boolean[] verBarrier = null;
	
	/** The width of the Massive Maze to create in cells wide. */
	private int actualWidth = 0;
	/** The height of the Massive Maze to create in cells high. */
	private int actualHeight = 0;
	/** The extra width calculated of the Massive Maze. (actualWidth % MAX_SIZE) */
	private int extraWidth = 0;
	/** The extra height calculated of the Massive Maze. (actualHeight % MAX_SIZE) */
	private int extraHeight = 0;
	
	/** The number of areas across that are the full MAX_SIZE. */
	private int fullAreasAcross = 0;
	/** The number of areas down that are the full MAX_SIZE. */
	private int fullAreasDown = 0;
	/** The total number of areas across. */
	private int totalAreasAcross = 0;
	/** The total number of areas down. */
	private int totalAreasDown = 0;
	
	/** How many pathways from area-to-area relative to the width or height of the area. */
	private double percentOfBarrierFilled = 0.40;
	
	/** The size of the walls on the monochrome bitmaps created. */
	private int wallWidth = 1;
	/** The size of a cell on the monochrome bitmaps created. */
	private int cellSize = 1;
	
	/** A cell that is on the "Frontier" line of creating a maze. */
	private class FrontierCell 
	{
		/** X-coordinate of previous cell. */
		public short prevX = 0; 
		/** Y-coordinate of previous cell. */
		public short prevY = 0;
		/** X-coordinate of current cell. */
		public short currX = 0;
		/** Y-coordinate of current cell. */
		public short currY = 0;
		/** Constructor */
		public FrontierCell(int currentX, int currentY, int previousX, int previousY)
		{ prevX = (short)previousX; prevY = (short)previousY; currX = (short)currentX; currY = (short)currentY; }
		/** X-coordinate of the mid point. */
		public short midX() 		
		{ return (short)((prevX + currX) / 2); }
		/** Y-coordinate of the mid point. */
		public short midY()		
		{ return (short)((prevY + currY) / 2); }
		/** Returns true if this cell is an initial frontier. */
		public boolean isStarter() 
		{ return Math.abs(prevX - currX) + Math.abs(prevY - currY) < 2; }
	}
	
	/** The list of frontier cells on the current area. */
	private ArrayList<FrontierCell> frontiers = null;
	
	private String name = "";
	
	/**
	 * Creates a Massive Maze with this width and height.
	 * 
	 * @param width How many cells across.
	 * @param height How many cells down.
	 */
	public void create(int width, int height, String mazeName) {
		//Create Maze Folder
		name = mazeName;
		File folder = new File(name);
		folder.mkdir();
		folder = null;
		//
		actualWidth = width;
		actualHeight = height;
		//Gets the remaining (extra) bounds
		extraWidth = width % MAX_WIDTH;
		extraHeight = height % MAX_HEIGHT;
		//How many Areas are MAX_SIZE big
		fullAreasAcross = (int)((width - extraWidth) / MAX_WIDTH);
		fullAreasDown = (int)((height - extraHeight) / MAX_HEIGHT);
		//How many total Areas to be created
		totalAreasAcross = fullAreasAcross + (extraWidth == 0 ? 0 : 1);
		totalAreasDown = fullAreasDown + (extraHeight == 0 ? 0 : 1);
		
		//Steps to Area creation
		//#1 Fill Barriers so the area knows where to put frontier cells
		//#2 Create area using setup frontier cells
		//#3 Save area (maze) as monochrome bitmap
		//
		
		//Move down each row of areas
		for (int row = 0; row < fullAreasDown; row++) {
			//Move across each full area and generate maze and save it
			for (int col = 0; col < fullAreasAcross; col++) {
				createArea(MAX_WIDTH, MAX_HEIGHT, col, row);
				saveArea(col, row, MAX_WIDTH, MAX_HEIGHT);
				fillVerticalBarrier(MAX_HEIGHT);
				fillHorizontalBarrier(MAX_WIDTH);
			}
		}
		//If the maze has remaining width create the 'extra' mazes
		if (extraWidth != 0) {
			//For each row of extra mazes create one
			for (int row = 0; row < fullAreasDown; row++) {
				fillVerticalBarrier(MAX_HEIGHT);
				createArea(extraWidth, MAX_HEIGHT, fullAreasAcross, row);
				saveArea(fullAreasAcross, row, extraWidth, MAX_HEIGHT);
				fillHorizontalBarrier(MAX_WIDTH);
			}
		}
		//If the maze has remaining height create the 'extra' mazes
		if (extraHeight != 0) {
			//For each column of extra mazes create one
			for (int col = 0; col < fullAreasAcross; col++) {
				fillHorizontalBarrier(MAX_WIDTH);
				createArea(MAX_WIDTH, extraHeight, col, fullAreasDown);
				saveArea(col, fullAreasDown, MAX_WIDTH, extraHeight);
				fillVerticalBarrier(extraHeight);
			}
		}
		//If the maze has both remaining height and width then create the small area in the bottom-right
		if (extraWidth != 0 && extraHeight != 0) {
			fillHorizontalBarrier(extraWidth);
			fillVerticalBarrier(extraHeight);
			createArea(extraWidth, extraHeight, fullAreasAcross, fullAreasDown);
			saveArea(fullAreasAcross, fullAreasDown, extraWidth, extraHeight);
		}
		
		System.out.println("Done.");
	}
	
	/**
	 * Sets up the horizontal barrier which reaches the whole way across the maze.
	 * 	 There will be <code>(percentOfBarrierFilled * actualWidth)</code> of open
	 *   paths along the barrier set at random.
	 *   
	 * @param areaWidth The relative width of the barrier.
	 */
	private void fillHorizontalBarrier(int areaWidth) {
		//
		horBarrier = new boolean[areaWidth];
		//Random number from 0 to actualWidth - 1
		int random = 0;
		int filled = 0;
		//How many cells with be set as pathways
		int toFill = (int)(percentOfBarrierFilled * areaWidth);
		//Fill in the exact amount of open paths
		while (filled < toFill) {
			random = (int)(Math.random() * areaWidth);
			//Check if the cell is not a pathway...
			if (horBarrier[random] == FILLED) {
				filled++;
				horBarrier[random] = EMPTY;
			}
		}
	}
	
	/**
	 * Sets up the vertical barrier which is located on the right side of the
	 *   current area, the current area is <code>areaHeight</code> cells high.
	 *   There will be <code>(percentOfBarrierFilled * actualWidth)</code> of open
	 *   paths along the barrier set at random.
	 *   
	 * @param areaHeight The relative height of the barrier.
	 */
	private void fillVerticalBarrier(int areaHeight) {
		//
		verBarrier = new boolean[areaHeight];
		//Random number from 0 to areaHeight - 1
		int random = 0;
		int filled = 0;
		//How many cells with be set as pathways
		int toFill = (int)(percentOfBarrierFilled * areaHeight);
		//Fill in the exact amount of open paths
		while (filled < toFill) {
			random = (int)(Math.random() * areaHeight);
			//Check if the cell is not a pathway...
			if (verBarrier[random] == FILLED) {
				filled++;
				verBarrier[random] = EMPTY;
			}
		}
	}
	
	/**
	 * Creates an area with a certain size and location index using frontier cells
	 *    based on the barriers around this maze.
	 * 
	 * @param areaWidth The relative width in cells of the Area to create.
	 * @param areaHeight The relative height in cells of the Area to create
	 * @param x The index of the current Area on the X-Axis.
	 * @param y The index of the current Area on the Y-Axis.
	 */
	private void createArea(int areaWidth, int areaHeight, int x, int y) {
		//
		System.out.println("Creating Area (" + x + "," + y + "," + areaWidth + "," + areaHeight + ")...");
		//Fills initial frontier list based on barriers and area position
		fillFrontierList(x, y, areaWidth, areaHeight);
		//The actual size of the area in memory
		int width = areaWidth * 2 + 1;
		int height = areaHeight * 2 + 1;
		//Allocate that many cells
		cells = new boolean[width][height];
		
		//Pick the first frontier cell at random
		int random = (int)(Math.random() * frontiers.size());
		FrontierCell n = null;
		FrontierCell f = null;
		FrontierCell c = frontiers.get(random);
		
		if (frontiers.size() != 1)
			clearCells(c);
		
		while (true) {
			//If the cell to the west of this is empty and in bounds...
			if (isEmpty(c.currX - 2, c.currY, width, height))
				frontiers.add(new FrontierCell(c.currX - 2, c.currY, c.currX, c.currY));
			//If the cell to the north of this is empty and in bounds...
			if (isEmpty(c.currX, c.currY - 2, width, height))
				frontiers.add(new FrontierCell(c.currX, c.currY - 2, c.currX, c.currY));
			//If the cell to the east of this is empty and in bounds...
			if (isEmpty(c.currX + 2, c.currY, width, height))
				frontiers.add(new FrontierCell(c.currX + 2, c.currY, c.currX, c.currY));
			//If the cell to the south of this is empty and in bounds...
			if (isEmpty(c.currX, c.currY + 2, width, height))
				frontiers.add(new FrontierCell(c.currX, c.currY + 2, c.currX, c.currY));
			
			for (int i = frontiers.size() - 1; i >= 0; i--) {
				f = frontiers.get(i);
				if (cells[f.currX][f.currY] == EMPTY && cells[f.prevX][f.prevY] == EMPTY) {
					frontiers.remove(i);
				}
			}
			
			//If there are no more frontier cells then we're done
			if (frontiers.size() == 0)
				break;
			//Index of a random frontier cell
			random = (int)(Math.random() * frontiers.size());
			//Search for a next frontier 
			n = frontiers.remove(random);
			//Clear the next frontiers cell, the previous cell, and the pathway between
			clearCells(n);
			//Set the current frontier to the next one
			c = n;
		}
	}
	
	/**
	 * Fills the frontier list based on the Barriers set up.
	 */
	private void fillFrontierList(int x, int y, int width, int height) {
		
		frontiers = new ArrayList<FrontierCell>();
		
		//If the Area is not on the left of the Maze
		if (x != 0) {
			//Add Vertical Barrier Frontiers
			for (int row = 0; row < height; row++) {
				if (verBarrier[row] == EMPTY) {
					frontiers.add(new FrontierCell(1 ,row * 2 + 1, 0, row * 2 + 1));
				}
			}
		}
		//If the Area is not on the top of the Maze
		if (y != 0) {
			//Add Horizontal Barrier Frontiers
			for (int col = 0; col < width; col++) {
				if (horBarrier[col] == EMPTY) {
					frontiers.add(new FrontierCell(col * 2 + 1 , 1, col * 2 + 1, 0));
				}
			}
		}
		//If the Area is on the upper left corner
		if (frontiers.size() == 0) {
			//Frontier at Random Location
			int col = (int)(Math.random() * width) * 2 + 1;
			int row = (int)(Math.random() * height) * 2 + 1;
			frontiers.add(new FrontierCell(col, row, col, row));
		}
		
	}
	
	/**
	 * Returns false if <code>x</code> or <code>y</code> are out of the bounds of
	 *   the area OR if <code>cell[x][y]</code> is <code>EMPTY</code>
	 *   
	 * @param x The actual X-coordinate in <code>cells</code>.
	 * @param y The actual Y-coordinate in <code>cells</code>.
	 * @param width The actual width in <code>cells</code>.
	 * @param height The actual height in <code>cells</code>.
	 * @return True if a FrontierCell can advance here.
	 */
	private boolean isEmpty(int x, int y, int width, int height) {
		if (x < 0 || x >= width || y < 0 || y >= height) return false;
		return (cells[x][y] == FILLED);
	}
	
	/**
	 * Opens up <code>cell</code>'s previous cell and the current cell as well 
	 *   as the pathway in between, calculated by <code>midX() & midY()</code>
	 *   
	 * @param cell The frontier cell to clear
	 */
	private void clearCells(FrontierCell cell) {
		cells[cell.midX()][cell.midY()] = EMPTY;
		cells[cell.prevX][cell.prevY] = EMPTY;
		cells[cell.currX][cell.currY] = EMPTY;
	}
	
	/**
	 * Saves an Area as a Monochrome Bitmap with a certain wallWidth and cellSize.
	 * 
	 * @param column Used in the filename to name the Area
	 * @param row Used in the filename to name the Area
	 */
	private void saveArea(int column, int row, int areaWidth, int areaHeight) {
		if (wallWidth == 1 && cellSize == 1) {
			saveAreaUnitSize(column, row, areaWidth, areaHeight);
		}
		
		//new MazeDisplayer().display(cells);
		//If (x == fullAreasAcross) Then a Left wall is drawn
		//If (y == fullAreasDown) Then a Bottom wall is drawn
/*		int halfWall = wallWidth >> 1;
		int actualWidth = (cellSize + halfWall) * areaWidth + wallWidth;
		int actualHeight = (cellSize + halfWall) * areaHeight + wallWidth;
		//int increment = cellSize + halfWall;
	    BufferedImage b = new BufferedImage(actualWidth, actualHeight, BufferedImage.TYPE_BYTE_BINARY);
		//int white = Color.white.getRGB();
		int black = Color.black.getRGB();
		
		drawLine(0, 0, actualWidth, actualHeight, 1, black, b);*/
	}
	
	/**
	 * Saves an Area as a Monochrome Bitmap with each actual cell an actual pixel.
	 * 
	 * @param column Used in the filename to name the Area
	 * @param row Used in the filename to name the Area.
	 * @param areaWidth The relative width of the area in cells.
	 * @param areaHeight The relative width of the area in cells.
	 */
	private void saveAreaUnitSize(int column, int row, int areaWidth, int areaHeight) {
		int pixelsWide = areaWidth * 2 + 1;
		if (column != fullAreasAcross) pixelsWide -= 1;
		int pixelsDown = areaHeight * 2 + 1;
		if (row != fullAreasDown) pixelsDown -=1;
		
		int white = Color.white.getRGB();
		int black = Color.black.getRGB();
		
		BufferedImage b = new BufferedImage(pixelsWide, pixelsDown, BufferedImage.TYPE_BYTE_BINARY);
		
		for (int y = 0; y < pixelsDown; y++) {
			for (int x = 0; x < pixelsWide; x++) {
				b.setRGB(x, y, (cells[x][y] == EMPTY ? white : black));
			}
		}
		
		File file = new File(name + "\\" + column + "x" + row + ".bmp");
		try {
			  ImageIO.write(b, "bmp", file);
		} catch (IOException e) {
			  e.printStackTrace();
		}
		file = null;
		b = null;
	}
		
	/**
	 * Returns a string representation of this class with its information
	 */
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("Maze " + actualWidth + " x " + actualHeight + "\n");
		sb.append("ExtraWidth:      " + extraWidth + "\n");
		sb.append("ExtraHeight:     " + extraHeight + "\n");
		sb.append("FullAreasAcross: " + fullAreasAcross + "\n");
		sb.append("FullAreasDown:   " + fullAreasDown + "\n");
		sb.append("TotalAreasAcross:" + totalAreasAcross + "\n");
		sb.append("TotalAreasDown:  " + totalAreasDown + "\n");
		return sb.toString();
	}
	
	/**
	 * Sets the maximum size of an area. Can be no larger then 1000 and no smaller then 10.
	 * @param maxSize The maximum cells
	 */
	public static void setMaximumSize(int maxWidth, int maxHeight) {
		MAX_WIDTH = maxWidth;
		if (maxWidth < 10) MAX_WIDTH = 10;
		if (maxWidth > 1000) MAX_WIDTH = 1000;
		MAX_HEIGHT = maxHeight;
		if (maxHeight < 10) MAX_HEIGHT = 10;
		if (maxHeight > 1000) MAX_HEIGHT = 1000;
	}
	
}

MazeGenerator.java

import java.util.Scanner;

public class MazeGenerator {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String name;
		int width, height;
		
		System.out.println("Massive Maze Generation:");
		
		System.out.print("Maze Name: ");
		name = sc.next();
		
		System.out.print("Maximum Width: ");
		width = sc.nextInt();
		System.out.print("Maximum Height: ");
		height = sc.nextInt();
		
		MassiveMaze.setMaximumSize(width, height);
		
		System.out.print("Maze Width: ");
		width = sc.nextInt();
		System.out.print("Maze Height: ");
		height = sc.nextInt();
		
		MassiveMaze mm = new MassiveMaze();
		mm.create(width, height, name);

	}
	
}