0
\$\begingroup\$

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?

\$\endgroup\$
2
  • 5
    \$\begingroup\$ We commonly call these distinct zones "biomes", and searching with that keyword can help you find past Q&A on this topic. Many of these answers recommend using a Voronoi diagram to generate irregular polygonal zones — have you tried something in that vein? \$\endgroup\$ – DMGregory Mar 14 at 17:16
  • \$\begingroup\$ Welcome to GDSE. A web search for procedural map generation & procedural biome generation brings up a number of options; so much so that this is probably an overly broad question. You're welcome to ask for informal recommendations in chat. Or if you have specific questions about using a particular technique with your game, you could edit your question to include those details. Also, the (x,y) + seed constraint you mentioned is often referred to as chunks, chunking, chunk-based, etc which might help you narrow your search. \$\endgroup\$ – Pikalek Mar 14 at 18:56
2
\$\begingroup\$

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
enter image description here enter image description here enter image description here enter image description here

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.
\$\endgroup\$

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.