Sunday, September 28, 2014

Android : Recursive Division algorithm for maze generation in android



I have the java code for Recursive Division algorithm that generate a perfect maze but the problem is i want to implement it and cant find out a way to print the generated maze in android ... since it generates an array of characters for vertical lines "|" and another for horizontal lines "-". i tried to loop on both arrays and draw a vertical line if "|" and a horizontal line if "-" but obviously that didn't work because i cant set the right positions of the lines on the android activity. So how can i set the positions to draw the maze exactly as generated ? OR is their another implementation for the algorithm on android ?


That's the implementation i use:



package com.jforeach.mazegame;


import java.util.*; import android.util.Log;


class RecursiveDivision {



static final char VWALL = '|';
static final char HWALL = '-';

static final char MAZE_PATH = ' ';



int rows;
int cols;
int act_rows;
int act_cols;

char[][] board;

public RecursiveDivision(int row, int col)
{

//initialize instance variables
rows = row*2+1;
cols = col*2+1;
act_rows = row;
act_cols = col;
board = new char[rows][cols];



//set the maze to empty
/* for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
board[i][j] = MAZE_PATH;
}
}*/

//make the outter walls
for(int i=0; i<rows; i++){
board[i][0] = VWALL;
board[i][cols-1] = VWALL;
}

for(int i=0; i<cols; i++){
board[0][i] = HWALL;
board[rows-1][i] = HWALL;
}


}

//storefront method to make the maze
public void makeMaze()
{
makeMaze(0,cols-1,0,rows-1);
makeOpenings();


}

//behind the scences actual mazemaking
private void makeMaze(int left, int right, int top, int bottom)
{
int width = right-left;
int height = bottom-top;

//makes sure there is still room to divide, then picks the best
//direction to divide into
if(width > 2 && height > 2){

if(width > height)
divideVertical(left, right, top, bottom);

else if(height > width)
divideHorizontal(left, right, top, bottom);

else if(height == width){
Random rand = new Random();
boolean pickOne = rand.nextBoolean();

if(pickOne)
divideVertical(left, right, top, bottom);
else
divideHorizontal(left, right, top, bottom);
}
}else if(width > 2 && height <=2){
divideVertical(left, right, top, bottom);
}else if(width <=2 && height > 2){
divideHorizontal(left, right, top, bottom);
}
}


private void divideVertical(int left, int right, int top, int bottom)
{
Random rand = new Random();

//find a random point to divide at
//must be even to draw a wall there
int divide = left + 2 + rand.nextInt((right-left-1)/2)*2;

//draw a line at the halfway point
for(int i=top; i<bottom; i++){
board[i][divide] = VWALL;
}

//get a random odd integer between top and bottom and clear it
int clearSpace = top + rand.nextInt((bottom-top)/2) * 2 + 1;

board[clearSpace][divide] = MAZE_PATH;

makeMaze(left, divide, top, bottom);
makeMaze(divide, right, top, bottom);
}

private void divideHorizontal(int left, int right, int top, int bottom)
{
Random rand = new Random();

//find a random point to divide at
//must be even to draw a wall there
int divide = top + 2 + rand.nextInt((bottom-top-1)/2)*2;
if(divide%2 == 1)
divide++;

//draw a line at the halfway point
for(int i=left; i<right; i++){
board[divide][i] = HWALL;
}

//get a random odd integer between left and right and clear it
int clearSpace = left + rand.nextInt((right-left)/2) * 2 + 1;

board[divide][clearSpace] = MAZE_PATH;

//recur for both parts of the newly split section
makeMaze(left, right, top, divide);
makeMaze(left, right, divide, bottom);
}

public void makeOpenings(){

Random rand = new Random(); //two different random number generators
Random rand2 = new Random();//just in case

//a random location for the entrance and exit
int entrance_row = rand.nextInt(act_rows-1) * 2 +1;
int exit_row = rand2.nextInt(act_rows-1) * 2 +1;

//clear the location
board[entrance_row][0] = MAZE_PATH;
board[exit_row][cols-1] = MAZE_PATH;

}

public void printMaze()
{
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){

Log.d("MAZE", i +" "+ j+" "+ String.valueOf(board[i][j]));

}
}
}


public Maze getMaze()
{
Maze maze = convert();
return maze;
}


}


Thanks in advance.


No comments:

Post a Comment