Hello,
I've been set to complete this project within a week and a half, and have had quite a few problems attempting to implement it. I have problems with the recursive part of it, which really, is the whole project. Any help would be ENORMOUSLY appreciated, and i would like to thank anyone willing to help me in advance.
Here is the project:
Task
The aim of this project is to write a divide-and-conquer algorithm for the following problem:- Split a given, rectangular room (dimensions i x j, i and j parameters) in random rooms.
- Rooms are completely separated from each other by walls.
- Rooms are made of a collection of more then d (>5) squares (d given as a parameter, d has to be larger then 5).
- A wall takes up 1 square
- Squares are part of a room if they can be reached through horizontal or vertical displacement, without going through a wall (that implies, diagonal displacements are not permitted).
Implementation
- Write a divide-and-conquer algorithm for the above problem. The problem can be initially divided into 2 similarly-sized parts or problems. Split the large room into two random rooms. Split each of these rooms again, and continue this recursively. A room which consists of less then d+1 squares does not have to be split any further.
- Implement your divide-and-conquer algorithm by adding to the Java code of RoomBuilder.java. It is forbidden to change the headers of the public methods.
- DO NOT modify Building.java, use it as is.
Building.java:
/* DO NOT modify this document!
*
* Divide-and-conquer algorithm
*/
/**
* Class that represents a 'walled', rectangular room as an i x j matrix. The borders
* of the building are walls. A wall takes up 1 square, and is represented by a 1 in the matrix.
*/
public class Building {
/** Representation of the building */
private final int[][] building;
/** Representation of a wall */
private static final int WALL = 1;
/**
* Creates a new building
*
* @param i Height of the room (number of rows)
* @param j Breadth of room (number of columns)
*/
public Building(int i, int j) {
building = new int[i][j];
for (int loop = 0; loop < j; loop++) {
building[0][loop] = WALL;
building[i-1][loop] = WALL;
}
for (int loop = 1; loop < i-1; loop++) {
building[loop][0] = WALL;
building[loop][j-1] = WALL;
}
}
/**
* Checks if a wall is present on a given coordinate
* @return TRUE if a wall is present on the given coordinate;
* else FALSE
*/
public final boolean isWall(int i, int j) {
return building[i][j] == WALL;
}
/**
* Places a wall on the given coordinates
*/
public final void setWall(int i, int j) {
building[i][j] = WALL;
}
/**
* Returns a String representation of the building, where a wall is represented by an 'x' and an open space by a space (' ')
**/
public final String toString() {
StringBuffer buf = new StringBuffer();
for (int i = 0; i < building.length; i++) {
for (int j = 0; j < building[i].length; j++) {
if( isWall(i,j) )
buf.append("X");
else
buf.append(" ");
}
buf.append('n');
}
return buf.toString();
}
}
RoomBuilder.java
/*
* Divide-and-conquer algorithm
*/
/**
* TODO: Complete the Java code. All empty methods must be implemented, but DO NOT modify their headers.
* You are equally allowed to add other methods to this class, or write additional classes.
*/
public class RoomBuilder {
/**
* Creates a new instance of RoomBuilder
*
* @param i Height of the building
* @param j Breadth of the building
* @param d Maximum size of rooms
*/
public RoomBuilder(int i, int j, int d) {
/**
* TODO: Implement this method
*/
}
/**
* Splits the building into rooms
* @return An object of the class Building
* @see Building.java
*/
public final Building buildRooms() {
/**
* TODO: Implement this method
*/
return null;
}
/**
* Splits the building in rooms
* @param seed Seed to be used with the random generator
* @return An object of the class Building
* @see Building.java
*/
public final Building buildRooms(long seed) {
/**
* TODO: Implement this method
*/
return null;
}
/**
* @param args
* The command line arguments
* args[0]: height of the building
* args[1]: breadth of the building
* args[2]: maximum size of building
*/
public static void main(String[] args) {
try {
int i = Integer.parseInt(args[0]);
int j = Integer.parseInt(args[1]);
int d = Integer.parseInt(args[2]);
RoomBuilder builder = new RoomBuilder(i, j, d < 6 ? 6 : d);
System.out.println(builder.buildRooms());
} catch (Exception ex) {
ex.printStackTrace();
}
}
}
Ps. how can i post screenshots? That way i could post a shot of what it's supposed to look like, and what i've achieved so far.