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.

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.