How can I implement world generation like in Don't Starve?

Question

I am working on a game similar to Don’t Starve. Mechanics of the game are all also pretty similar. You craft things, you can explore a random open world and you need to survive. Because I really like the way Don’t Starve generates worlds with biomes, and this branch like structure:

I want my world generator to generate worlds similar to this on a large tilemap, with custom biomes, but I don’t think they use perlin noise for it. Here you can see different biome sections of the game:

Also I want to explore other possibilities than noise to generate worlds, so I don’t want to use it for this project.

Answer 1

I'm gonna give another shout out to RRTs (rapidly exploring randomized trees). It looks to me that you could generate this terrain using an RRT in the following way:

1. Randomly sample a point in the play area and add it to a tree T. Assign it a random biome B.
2. Randomly sample another point in the play area called P2 and label it biome B2.
3. Find the closest point in the tree T to point P2, and call it Pt.
4. Grow a branch from Pt toward P2 a random length up to the distance between Pt and P2. At the end of this branch, add another node to the tree T called P3. Label P3 using the following rule: if it closer to P2, label it B2. Otherwise, label it whatever the biome was of Pt.
5. Repeat step 2 until some number of nodes is in the tree T.
6. Post process the tree to create the world. Create a grid of tiles that covers the same area that the tree covers plus or minus some margin.
7. For each grid cell, determine the closest node in T called Pt, with biome label Bt. The biome of the this grid cell is Bt. If you are above a certain distance from Pt, instead your biome will be ocean.

EDIT: Here is the output of this algorithm that I've sketched up in Python. I had to modify step 4 so that it only labels with Bt if Pt is ten times closer to the new node than the random sample. You can play with that parameter to get biomes of different sizes. Here is a gist of that algorithm.

Answer 2

You can achieve a very similar result by using voronoi diagrams:

You'll need to generate a set of points (one for each biome) with a seeded pseudo random generator (if you want the maps to be repeatable), then when you generate the tiles, get the distance between that tile and the points and set the biome of the tile to the one represented by the closest point.