/**
* Copyright (c) 2012-2013 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;
}
}