Maze.java

/*
 * Copyright © 2012 Nokia Corporation. All rights reserved.
 * Nokia and Nokia Connecting People are registered trademarks of Nokia Corporation.
 * Oracle and Java are trademarks or registered trademarks of Oracle and/or its
 * affiliates. Other product and company names mentioned herein may be trademarks
 * or trade names of their respective owners.
 * See LICENSE.TXT for license information.
 */

package com.nokia.example.amaze.model;

import java.util.Random;

/**
 * The model of the maze.
 */
public class Maze {
	// Constants
	private final static int UP = 0;
	private final static int DOWN = 1;
	private final static int LEFT = 2;
	private final static int RIGHT = 3;
	private final static int MAX_SIZE = 31;
	
	// Members
	private long[] _maze = null; // Maze rows are encoded as bits in a long field
	private final float _sideLength;
	private final float _height;

	// Utility variables
	private final float _origin;
	private float _spaceBetweenPlanes = 0f;
	
	// Store the location on X of the start and end
	private int _startX = -1;
	private int _endX = -1;

	/**
	 * Constructor.
	 * @param corridorCount
	 * @param mazeSideLength
	 * @param mazeHeight
	 */
	public Maze(final int corridorCount,
				final float mazeSideLength,
				final float mazeHeight)
	{
		if (corridorCount > MAX_SIZE) {
			throw new IllegalArgumentException("Maze is too big!");
		}
    
		_sideLength = mazeSideLength;
		_height = mazeHeight;
		_origin = -_sideLength / 2;
	}
	
	/** 
	 * @return The maze height.
	 */
	public final float height() {
		return _height;
	}

	/** 
	 * @return The maze origin.
	 */
	public final float origin() {
		return _origin;
	}
	
	/** 
	 * @return The space between planes.
	 */
	public final float spaceBetweenPlanes() {
		return _spaceBetweenPlanes;
	}
	
	/** 
	 * @return The maze content as an array.
	 */
	public final long[] array() {
		return _maze;
	}
	
	/**
	 * @return The X coordinate of the start position in the maze.
	 */
	public final int startX() {
		return _startX;
	}
	
	/**
	 * @return The X coordinate of the goal in the maze.
	 */
	public final int goalX() {
		return _endX;
	}
	
	/**
	 * Resolves and returns the start position. 
	 * @return The start position.
	 */ 
	public float[] startPosition() {
		float[] position = new float[3];
		position[0] = _origin + _startX * _spaceBetweenPlanes;
		position[1] = _height / 2; // Not used, hopefully
		position[2] = _origin + _spaceBetweenPlanes;
		return position;
	}

	/**
	 * Checks if the given position (x, z) is near enough of the end (goal)
	 * position of the maze. The "near enough" is determined by the given
	 * tolerance.
	 * @param x
	 * @param z
	 * @param tolerance
	 * @return
	 */
	public final boolean isAtTheEnd(final float x,
									final float z,
									final float tolerance)
	{
		// Use linear distances
		return Math.abs(x - (_origin + _endX * _spaceBetweenPlanes))
				< tolerance
				&& Math.abs(z + _origin) < tolerance;
	}

	/**
	 * Creates a new random maze.
	 * @param mazeSize The size of the maze array to create.
	 */ 
	public void createNew(int mazeSize) {
		_startX = -1;
		_endX = -1;
		Random random = new Random();
		int totalSize = mazeSize * 2 + 1;
		_maze = new long[totalSize];
		
		for (int i = 0; i < _maze.length; i++) {
			_maze[i] = -1;
		}
		
		int backtrack[] = new int[mazeSize * mazeSize];
		int backtrackIndex = 0;		
		int x = 1;
		int y = 1;

		// Traverse the maze finding unconnected spots
		while (true) {
			_maze[x] &= ~(0x1 << y);
			int directions[] = new int[4];
			int availableSpaces = 0;
			
			if (y - 2 > 0 && (_maze[x] & (0x1 << (y - 2))) != 0) {
				directions[availableSpaces++] = UP;
			}
			
			if (y + 2 < totalSize && (_maze[x] & (0x1 << (y + 2))) != 0) {
				directions[availableSpaces++] = DOWN;
			}
      
			if (x + 2 < totalSize && (_maze[x + 2] & (0x1 << y)) != 0) {
				directions[availableSpaces++] = LEFT;
			}
      
			if (x - 2 > 0 && (_maze[x - 2] & (0x1 << y)) != 0) {
				directions[availableSpaces++] = RIGHT;
			}

			if (availableSpaces > 0) {
				int chosenDirection =
						directions[(random.nextInt() >>> 1) % availableSpaces];
				backtrack[backtrackIndex++] = chosenDirection;
        
				if (chosenDirection == UP) {
					_maze[x] &= ~(0x1 << (y - 1));
					y -= 2;
				}
				else if (chosenDirection == DOWN) {
					_maze[x] &= ~(0x1 << (y + 1));
					y += 2;
				}
				else if (chosenDirection == LEFT) {
					_maze[x + 1] &= ~(0x1 << y);
					x += 2;
				}
				else if (chosenDirection == RIGHT) {
					_maze[x - 1] &= ~(0x1 << y);
					x -= 2;
				}
			}
			else { // If nothing is not visited in the neigborhood backtrack
				if (backtrackIndex == 0) {
					// end of algorithm
					break;
				}
				
				backtrackIndex--;
        
				if (backtrack[backtrackIndex] == UP) {
					y += 2;
				}
				else if (backtrack[backtrackIndex] == DOWN) {
					y -= 2;
				}
				else if (backtrack[backtrackIndex] == LEFT) {
					x -= 2;
				}
				else if (backtrack[backtrackIndex] == RIGHT) {
					x += 2;
				}
			}
		}

		// Find start and end points
		while (true) {
			int pos = (random.nextInt() >>> 1) % totalSize;
			
			if (_startX < 0 && (_maze[1] & (0x1 << pos)) == 0) {
				_startX = pos;
				//_maze[0] &= ~(0x1 << pos); // Make a hole to the wall
			}
			
			if (_endX < 0 && (_maze[_maze.length - 2] & (0x1 << pos)) == 0) {
				_endX = pos;
				_maze[_maze.length - 1] &= ~(0x1 << pos); // Make a hole to the wall
			}
      
			if (_endX >= 0 && _startX >= 0) {
				break;
			}
		}
		
		_spaceBetweenPlanes = _sideLength / (_maze.length - 1);
	}
	
	/**
	 * Releases the resources but keeps the meta information such as the start
	 * and the end of the maze last created.
	 */
	public void clear() {
		_maze = null;
	}
}