How to make non-standard sized zones for a procedurally generated 2d map?

Question

I am making a procedurally generated map with different zones (plains, forest, village, etc) and am currently just designing each one as a square zone. However, I think it'd be neat if the zones were more randomly distributed so that they could be irregular sizes. I'm not sure how to do that in a good way. (Any given tile needs to know what zone it belongs to quickly and deterministically based on its x, y, and random seed for the world)

Are there existing algorithms for this?

Answer 1

I am going to assume extra emphasis on the performance. There are plenty of thorough answers on this topic already, but if you are interested in something brutally simple and fast (as in real-time Python), I can offer you a method of "squeezed squares".

General idea is as follows:

• Each block belongs to some bigger chunk. This is purely virtual construct, the chunk does not need to be a storage unit. Chunk's coordinates can be easily inferred from block's coordinates. The point here is that clusters of blocks may share common seed.
• Chunk's coordinates are feed to deterministic RNG to generate two properties: size_bias and biome_id.
• To determine blocks's biome_id, scan surrounding NxN chunks to select closest one after adjusting for size_bias.
• That is it. Tweak the parameters (size_bias, chunk_size, N) for best results.

Few examples with different settings. (Blue arrows point to selected chunk.)

1	2	3	4

Python pseudocode.

def get_chunk(location):
    half = chunk_size / 2
    location = Vector(location.x % chunk_size + half, location.y % chunk_size + half)
    seed = global_seed + location.x + location.y
    rng = make_rng(seed)
    biome_id = rng.range(num_biome_types)
    size_bias = rng.uniform(1.0, max_size_bias)
    return ChunkInfo(location, biome_id, size_bias)

def get_nearby_chunks(block):
    for x in range(block.location.x - N, block.location.x + N + 1):
        for y in range(block.location.y - N, block.location.y + N + 1):
            yield get_chunk(Vector(x, y))

def get_block_biome_id(block):
    chunks = list(get_nearby_chunks(block))
    biased_distance = lambda chunk: (block.location - chunk.location).size - chunk.size_bias
    chunks.sort(key=biased_distance)
    return chunks[0].biome_id

Cons:

• Not ideal for 3D: surface might look crater-y.
• Sometimes visibly aligns to chunk grid — decrease chunk size, increase sample radius and bias variance.