Random layout rooms with intersecting walls

Question

I am trying to layout few rectangle rooms on un unlimited map. The main condition is that every next room has to intersect with one of already placed with at least one point of the wall.

The number, width and height are random values generated by something like D&D dice rolling. Every next room can be adjacent to any placed rooms. Result should look like a kind of dungeon (hope the picture makes it more clear)

I am afraid that different packing algorithms too heavy for that problem. I would greatly appreciate any advice!

Answer 1

A very rough algorithm:

1. Create a temporary room
2. Check if the position of the room is allowed
3. Move the room if necessary

The first two are relatively simple, the last one you have to make you own algorithm that suits the layout you prefer.

The following java code produce a level where

1. The room is a Rectangle object
2. If the Rectangle intersects any existing rectangle, it is forbidden, otherwise allowed.
3. The room is moved counter clockwise in a circle, where the circle's diameter is increase with 1 pixel each revolution - this makes the room placement adjacent to existing rooms. (I think there might be some refinement needed, but the general idea seems to work).

(I've just started to learn java, so if you're experience with that you can likely find some better way to achieve the same results)

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.Rectangle;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;

import javax.imageio.ImageIO;


public class GenerateLevel {
    private ArrayList<Rectangle> Rooms = new ArrayList<Rectangle>();
    private Random r = new Random();
    private BufferedImage levelImage;

    public static void main(String[] args){
        new GenerateLevel();
    }

    public GenerateLevel(){
        Rooms.add(new Rectangle(500,500,10 + r.nextInt(50), 10 + r.nextInt(50)));
        int numberOfRooms = 30;
        for (int i = 0; i < numberOfRooms; i++){
            addRectangle(50 + r.nextInt(30), 50 + r.nextInt(30));
        }

        levelImage = new BufferedImage(1000, 1000, BufferedImage.TYPE_INT_ARGB);

        drawImage(levelImage);
        //Writes the BufferedImage levelImage to the level.png file.
        try {
            ImageIO.write(levelImage, "png", new File("src/res/level.png"));
        } catch (IOException e) {
            System.out.println("ImageIO.write exception");
            e.printStackTrace();
        }
    }

    //Draws the final level into the BufferedImage levelImage.
    private void drawImage(BufferedImage levelImage) {
        Graphics2D drawGraphics = levelImage.createGraphics();

        for(Rectangle room:Rooms){
            drawGraphics.setColor(new Color(r.nextInt(255), r.nextInt(255), r.nextInt(255)));
            drawGraphics.fill(room);
            drawGraphics.setColor(Color.BLACK);
            drawGraphics.draw(room);

        }

    }

    //Adds a rectangle to the ArrayList Rooms.
    private void addRectangle(int width, int height){
        int[] position = findAllowedPosition(width, height);
        Rooms.add(new Rectangle(position[0], position[1], width, height));
    }

    //Finds an allowed position by scanning clockwise and increasing the scan diameter.
    private int[] findAllowedPosition(int width, int height){
        boolean positionFound = false;
        boolean intersectionFound = false;
        int radiusCounter = 1;
        int scanCounter = 0;

        Rectangle tempRect = new Rectangle(500, 500, width, height);

        int[] origin = {500, 500};
        int[] lastPosition = {500, 500};
        while(!positionFound){

            //Check if tempRect intersects with any already placed rectangles.
            intersectionFound = false;
            for(Rectangle r : Rooms){
                if (r.intersects(tempRect))
                {
                    intersectionFound = true;
                    break;
                }
            }

            //If tempRect intersects any rectangle, move tempRect.
            if (intersectionFound){

                if(scanCounter == 0){
                    lastPosition[1]--;
                }

                lastPosition = scanClockwise(radiusCounter, origin, lastPosition);
                scanCounter++;
                tempRect.setLocation(lastPosition[0], lastPosition[1]);
            } 
            //If tempRect doesn't intersect any rectangle, set PositionFound = true;
            else {
                positionFound = true;
                break;
            }

            //Check if one revolution of the scan radius has been performed, if so, increase scanRadius.
            if(((radiusCounter * 2-1)*4 + 4) < scanCounter){
                radiusCounter++;
                scanCounter = 0;
            }
        }
        int[] foundPosition = {(int)tempRect.getX(), (int)tempRect.getY()};
        return foundPosition;
    }

    private int[] scanClockwise(int scanRadius, int[] origin, int[] lastPosition){
        int[] returnArray = lastPosition;

        // Upper line of the scan rectangle
        if (lastPosition[0] >= origin[0] - scanRadius && lastPosition[0] < origin[0] + scanRadius && lastPosition[1] == origin[1] - scanRadius){
            returnArray[0]++;
        } 
        // Right line of the scan rectangle
        else if (lastPosition[1] >= origin[1] - scanRadius && lastPosition[1] < origin[1] + scanRadius && lastPosition[0] == origin[0] + scanRadius){
            returnArray[1]++;
        }
        // Bottom  line of the scan rectangle
        else if (lastPosition[0] <= origin[0] + scanRadius && lastPosition[0] > origin[0] - scanRadius && lastPosition[1] == origin[1] + scanRadius){
            returnArray[0]--;
        }
        // Left line of the scan rectangle
        else {
            returnArray[1]--;
        }
        return returnArray;
    }
}

Below is a picture made by this code, but point 3 above is where you'll have to write an algorithm that suits whatever level-layout you have in mind.