Sign in to follow this  

Splitting a grid field into groups of tiles randomly

Recommended Posts

I have an 2 dimensional array representing the information about tiles of a tile based game.

How would i go about randomly grouping up blocks of tiles in random shapes and sizes in this 2d array? I want to create an effect similar to how biomes are done in Minecraft except on a simpler scale (example: https://media.mojang.com/15e20c7f9936d9ea7d8f4bdee21503fed206cd5e/overviewMap.png where the white areas are snowy places, the yellow areas are desert and the green areas of grassy biomes).

 

Does anyone know any algorithms out there i could use that would be suitable for this sort of thing?

Share this post


Link to post
Share on other sites

Likely there are a zillion algorithms for this thing, but I don't know any names :(

 

At a more concrete level, I'd start with something simple like

1. Assign type of area to some of the tiles randomly. This is sort-of the center tile.

2. For each non-assigned tile, find the nearest assigned tile, and copy the area type.

 

The white areas look much bigger in the image, you may want to do something special there, like assign snow to a range of tiles, or do it as a second sweep where snow takes over a cluster of previously created areas, or so.

Share this post


Link to post
Share on other sites

I got something similar to what i wanted using a modified cellular automata cave generation algorithm from http://www.roguebasin.com/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels which is similar to @Alberth 's idea

 

except i tweaked the settings so that:

-chance of spawning a seed is 20%

-the minimum requirement for filling a tile is that if only 1 tile around it isn't empy space instead of 4+ in the article

-instead of storing the field as booleans, i have them stored as ints, and each distinct int represents a different biome

-on 'growth' cycles, my algorithm finds the most common biome int around the target cell, and if it becomes a non empty space it'll become whatever most common biome around it.

-rather large iteration count of 25 so that i dont have as many empty spaces

 

on a small scale this seems to work fine, which is all i need for the game i'm making. I generated an image with random colour values for biomes:

 

2j5kl7q.png

 

i dont seem to get any empty spaces due to the small size and large iteration count. I guess if i got any i could just flood fill them with some random default biome or surrender to a nearby biome type

 

I think i might want to have an extra 'polish' iteration to remove single block biomes as i sometimes do in the image but that should be easy.

 

I can imagine this might not be the best algorithm though for anything much larger cause i guess the iteration count would need to be bigger to fill up more space with biomes, which would be incredibly slow.

Edited by draika

Share this post


Link to post
Share on other sites

My solution to this problem was to use Voronoi's algorithm and Lloyd's Relaxer, which is a nice, very simple way of defining natural looking terrain generation.

 

The basic idea (without the fancy Official Terms) is to make a handful of random coordinates on your 2d grid and assign each a terrain type (keep a list of these "anchors"). Then go through each member of the 2d grid and ask the anchor list which one of its members is mathematically closest. Assign each of these the terrain of their anchor match.

 

Lloyd's Relaxer adds a few steps. For each anchor point, keep an array of its closest tiles. Then loop through each anchor's tile list, calculate out its average x and y coordinates, and move your anchor to that point.

 

Then run the Voronoi again, this time using the modified anchors. Nice, semi-even, non-bunched groupings. (Also, if I didn't explain this well enough, searching the terms I listed will get you some very good visual steps.)

Share this post


Link to post
Share on other sites
You could use a noise function (e.g. perlin noise https://en.m.wikipedia.org/wiki/Perlin_noise) and then get the tile type from the value output from that function at each position so each tile type covers a set range of values.

So if your noise function returned a value between 0 and 1 then you could say some thing like -

<= 0.5 = TileTypeA
<= 1.0 = TileTypeB

Minecraft will do something like this to calculate it's biomes.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this