Noise generation: 'Room Noise'

Question

Last weeks I was developing a world generator (for a Minecraft mod). However, I wasn't looking for just Perlin noise, but rather something based on cell noise. I want to generate a sort of underground lab, existing of several rooms of different sizes.

To explain the problem I use 2D examples.

The noise generator takes a grid cell position (int x, int y), and returns an object with this stucture:

boolean top;
boolean right;
boolean down;
boolean left;

int roomType;

The 4 booleans represent the walls which are enabled or disabled:

The roomType represents the type of the room respectively.

The final result should be something like this:
Here, the background checkerboard pattern represents the base grid, and the black lines represent the walls. This is just a simple example that could generate, but in the real case, the grid is infinite in both x and y directions.

The problem I'm getting now is that the noise generator only takes in an x and y coordinate, which is the coordinate of the grid cell it should generate. There is a seed of which I can generate more random seeds for hash functions:

long seed = 0x75fd239de48;

Random r = new Random(seed);
int seed1 = r.nextInt();
int seed2 = r.nextInt();
// etc.

I could use a hash function: Hash.hash2D(int seed, int x, int y), which returns a random double for a coordinate, according to a seed.

That will give the ability to generate information for the surrounding cells.

To easily generate larger rooms, you could set a max size for a room, and check an area for rooms that try to be larger than 1x1. If they are there, and will span to the current room, the room will be an extension of another room. However, checking if a room will extend requires a check if it isn't already extending (otherwise, unwanted room extensions appear to room bases that extend another), which runs into an infinite loop.

In my case, there is a given table of room types, their sizes and their weights. Example:

name:   size [weight]
room-1: 1x1  [128]
room-2: 1x1  [128]
room-3: 2x1  [16]
room-4: 1x2  [16]
room-5: 2x2  [8]
room-6: 3x1  [4]
room-7: 1x3  [4]

There are many others, coming with sizes up to 5x5, but I use this example list for my question. The max size in this example is 3x3 (just max-width by max-height).

Here I have an example class of some basic setup in Java:

public class RoomNoise {
    private final long seed;
    private final Random rand;
    public RoomNoise( long seed ) {
        this.seed = seed;
        this.rand = new Random( seed );
    }

    public enum RoomTypes {
        ROOM1( 1, 1, 128 ),
        ROOM2( 1, 1, 128 ),
        ROOM3( 2, 1, 16 ),
        ROOM4( 1, 2, 16 ),
        ROOM5( 2, 2, 8 ),
        ROOM6( 1, 3, 4 ),
        ROOM7( 3, 1, 4 );

        public final int width;
        public final int height;
        public final int weight;
        private RoomTypes( int w, int h, int weight ) {
            width = w;
            height = h;
            this.weight = weight;
        }
    }

    public static class Output {
        public final RoomTypes roomType;
        public final boolean upWall;
        public final boolean rightWall;
        public final boolean downWall;
        public final boolean leftWall;
        public Output( RoomTypes type, boolean u, boolean r, boolean d, boolean l ) {
            roomType = type;
            upWall = u;
            rightWall = r;
            downWall = d;
            leftWall = l;
        }
    }

    public Output generate( int x, int y ) {
        // What should be here
    }
}

I'm looking for the content of the generate method, for which I've tried many things, but every time I turned into an infinite loop or it didn't work.

Is there any way to generate this noise in O(N) with N less than infinity? And if there is a way, which way is that and how could I implement it? I've searched the internet and tried many things (for 3 weeks now) and still haven't found a solution.

I use Java 1.8, but I prefer any C-style language.

Again, I have this hash function:

Hash.hash2D( int seed, int x, int y );

---

Edit:

Expected result:

Blue lines are corridors, which are generated later on. Just forget them.

---

Note:

I'm not able to load and delete chunks (grid cells) manually, the base API (Minecraft) is doing that for me. It only gives me the coordinate (which depends on the player interaction) and I should give back a (part of a) room that fits the chunk at that coordinate. I also know that once a chunk is generated, it isn't generated again.

Whew

In addition: It could be useful for city generation too, where walls are roads and rooms are buildings. – Insulate

Answer 1

I'm not sure I perfectly understand the problem you're trying to solve, so please feel free to comment if this is short of the mark:

If you want to be able to generate an infinite grid, you're only going to be able to approximate infinite. I think you have two options:

1. Generate a "big enough" grid. This might be time / space intensive, but if there's an upper bound on how much you could need, and it's feasible to do it all at once, it's the simplest option. E.g. if the user couldn't possibly make it more than 1000 squares away from the center, generate 2000x2000.

OR:

2. Use lazy evaluation. This means, don't generate anything until you need it. If the user gets close to an area that has not yet been generated, generate it then. The flip side to this is you can also throw away old parts that the user isn't likely to return to, if you need to free up resources. For example: cut your area into squares (e.g. 20x20 or 1000x1000), and generate additional, adjacent squares, as the player gets close to them, or the map pans over in that direction, etc., as needed.

Akela

That isn't going to work for me. As I said, i'm making a Minecraft mod and Minecraft handles infinite worlds. I already have tried such things with pregenerated regions but that would take too much memory after some time... Btw, I'm not able to set which chunks will generate, as I just get a coordinate on the grid, which is infinite. And I don't believe that there is no solution for my problem... – Insulate

I'm not familiar with Minecraft modding - when you get a coordinate out of this infinite grid, how much area do you need to generate around it? The answer can't be "infinite" (no computer has infinite memory), so my question is, how much do you generate when you get a coordinate, and do you generate more at a later time, or only when you next get a coordinate? – Akela

You don't have to be familiar with that, I just need the basic principle I described. When I got the grid cell location, I get one input coordinate, and I can only generate that cell. However, using the hash function, I can get some basic information about near cells. – Insulate

Answer 2

Ok, I think I've solved it myself.

This is the grid, not infinite here but it could be.

In this grid you have some cells that want to extend. This is directly defined by the hash function:

However, some extensions do overlap others. This is something we don't know actually.

Take for each cell a priority. You could do that in several ways:

• Just use the hash function to give them a random priority

• Give each possible room type / size a priority (e.g. larger rooms have higher priority).

The priority is only important on cells that want to extend. In my example, the bigger cells have higher priority.

Then we have the input coordinate, which is the blue cell:

Ok, knowing this, you have to do some steps. We know the maximum size is 3x3.

If the input cell doesn't want to extend

1. Check in the area of the maximum size if there is any cell that tries to extend to this cell:
   
   In this case it exists.

2. Knowing this, we need to check if one of the found cells could extend to this cell. To check that, check if this wants this cell to be an extension, then do the steps below and take the check cell as input coordinate. In the example, the extending cell is able to extend. We also know the extending cell will extend the input cell so the input cell is an extension.

3. Now we could easily check which walls exist and which not. In this case, every wall is gone because it is the center of this extending room:
   
   

Some other examples:

Input coordinates. None of them wants extension:

Check regions:

As you can see, one cell found an extension room, but that extension room doesn't extend that input cell. That makes all those rooms a 1x1 room:

If the input cell wants to extend

And how to check if a cell can extend

1. Do a hard check. The hard check checks the area of the extension (3x3 in this case) size right below the input cell for other cells trying to extend. If there is one, check if that one could extend. If it could, the input cell couldn't extend and go on with the steps for non-extending cells on your input cell. To save memory and time, you could skip checking if the found cells could extend (maybe this will run into an infinite loop), and just take an 1x1 cell directly (non-extending cell steps are not necessary then).
   This is the extension area / hard check area in this case. There is no extending cell here so the cell could extend.
   

2. Now do a soft check. The soft check checks for extending cells in the maximum size area left below, and right above the cell:
   
   Also here, you could check if they do extend, but that takes much memory and time.
   For each found cell, check in their extension area right below them if they will extend to any of the extension cells the input cell will extend. This check if the two extension areas overlap. If they don't, your cell is able to extend and you could skip step 3 and go to step 4. If they do, go to step 3. In this case an overlap is found:
   
   Here, the yellow cell with red outline is a found overlap.

3. You've found an overlap. Here the priority is going to play a role. Take the priority of the extension cell which area does overlap the input cell area. Also take the priority of the input cell itself. Compare them. If the priority of the input cell is larger that the other priority, the input cell can extend and you could go to step 4. If the input cell has lower priority, it couldn't extend and you could make it a 1x1 room (or you could do the non-extending cell steps, which is necessary if you validate found cells in the hard check). If the priorities are equal, take the cell with the highest X or Y coordinate, or something.
   In my example, the input cell has the highest priority, because it is bigger.

4. The final step. The cell is guaranteed to extend. You could calculate which walls exist. Notice that the left and the top wall always exist, as the extension cells are always in the top left corner.
   Our cell could extend and we get this result:
   
   

Another example

The input cell:

Do the hard check:

Oh, it found one, so it couldn't extend and turns into a 1x1 room:

---

That's it, actually. I hope I've been clear enough. Rather than using squares, you could use rectangles too, or more complex shapes like L-shaped rooms.

And this is the final result of my example:

Whew

Haha, this also seems not to work after many months developing. – Insulate