You will implement random maze generation. start by downloading the attached source file. study the starting code and make the following changes:
implement makemazerecursive(char[][]level, int startx, int starty, int endx, int endy) using the recursive division method. a general description is on wikipedia:
"mazes can be created with recursive division, an algorithm which works as follows: begin with the maze's space with no walls. call this a chamber. divide the chamber with a randomly positioned wall (or multiple walls) where each wall contains a randomly positioned passage opening within it. then recursively repeat the process on the subchambers until all chambers are minimum sized. this method results in mazes with long straight walls crossing their space, making it easier to see which areas to avoid.
for example, in a rectangular maze, build at random points two walls that are perpendicular to each other. these two walls divide the large chamber into four smaller chambers separated by four walls. choose three of the four walls at random, and open a one cell-wide hole at a random point in each of the three. continue in this manner recursively, until every chamber has a width of one cell in either of the two directions."
you will implement random maze generation. start b
this function is recursive. note: do not call it on a sub-area when that area is less than 3x3 - this will cause walls to double up.
since this algorithm does not use any data structures or back tracking, it can create mazes that are not solveable.
hints:
(the screen shots below use numbers for walls in order to indicate which call to makemazerecursive created them - you should use only a # in your final submission.)
it is not necessary to follow these hints, you may implement this algorithm as you see fit based on the description above.
consider creating a function called randbetween(int l, int u) that creates a random number in an interval - wouldn't this function be useful for deciding where walls should go?
as a first step, implement the basic functionality to draw the two walls that divide the area into four rooms; don't proceed (i. e. add recursion) until it works.
then implement the recursive call for just one of the sub-areas; don't proceed until it works.
then extend the code to the other sub-areas.
after you are done, rename the finalized code to "lastname_pp3.java" (e. g. "acuna_pp3.java"). remember to change the class name as well.
/**
* write a description of class base_pp3 here.
*
* @author (your name), acuna
* @version (a version number or a date)
*/
import java. util. random;
public class base_pp3
{
//standard console size in characters.
private static final int level_height = 25;
private static final int level_width = 80;
private static final char icon_wall = '#';
private static final char icon_blank = ' ';
/**
* returns a 2d array containing a statically created maze with dimentions 80x24.
*
* @return 2d array containing a maze
*/
private static char[][] makemazestatic()
{
//the following maze was generated with the recursive division method and then modified by hand.