0
\$\begingroup\$

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.

Smth like that

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) Maybe that picture makes it clear

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

\$\endgroup\$
17
  • \$\begingroup\$ Can you freely decide the number, width and height of the rooms or are these fixed? And what exactly are your aesthetic requirements? The trivial solution would to just place the rooms in a line, but something tells me that's not the solution you are looking for. \$\endgroup\$
    – Philipp
    Feb 22 '16 at 13:18
  • \$\begingroup\$ And what do you mean with "one of already placed". Do all rooms need to be adjacent to the first or can they be adjacent to any already placed room? \$\endgroup\$
    – Philipp
    Feb 22 '16 at 13:21
  • \$\begingroup\$ The number, width and height are random values. Every room can be adjacent to any placed rooms. And yes, you are right, I need more aesthetic solution than just a line. The result should look like dungeon, I think, with more than one possible way to go through it \$\endgroup\$ Feb 22 '16 at 13:29
  • \$\begingroup\$ Random values generated by your algorithm or generated by someone else? "not one way to go through" means the room-graph needs to have circles and can not be just a tree. This makes the problem far more complicated. I think you should edit your question and elaborate on your exact requirements. \$\endgroup\$
    – Philipp
    Feb 22 '16 at 14:08
  • \$\begingroup\$ Without knowing more of your requirements, a BSP algorithm is one of many that could get you close. \$\endgroup\$ Feb 22 '16 at 15:26
2
\$\begingroup\$

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. level.png

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.