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:

  1. Task
    The aim of this project is to write a divide-and-conquer algorithm for the following problem:

    1. Split a given, rectangular room (dimensions i x j, i and j parameters) in random rooms.
    2. Rooms are completely separated from each other by walls.
    3. Rooms are made of a collection of more then d (>5) squares (d given as a parameter, d has to be larger then 5).
    4. A wall takes up 1 square
    5. 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).
  2. Implementation

    1. 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.
    2. 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.
    3. 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.

Edited 3 Years Ago by pyTony: fixed formating

Help to do what?

Do you need help with the divide and conquer algorithm, or designing the room builder, which I assume is done using java's 2d suite? Be more specific and don't just post your entire assignment.

I need help with the divide and conquer algorithm...
I believe there's no need to use java's 2d suite, since a room will simply be turned into a string representation thereof (see the toString() method in Building.java).
I posted my whole assignment so it would be clear what i know and what i have to do, since otherwise, many more questions could have resulted from a lack of information.
Thanks

>I believe there's no need to use java's 2d suite, since a room will simply be turned into a string representation thereof (see the toString() method in Building.java).

Oh ok, I just assumed it had something to do with that since you insisted of posting a few screenshots. My mistake.


>I need help with the divide and conquer algorithm...

Post your ideas here first and someone will help...

This article has been dead for over six months. Start a new discussion instead.