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

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.

• +1, you're on the right track. But "like Don't Starve" only communicates if the person you're talking to is deeply knowledgeable about that one specific game, and thinks the same bits of its world are important as you do. By including more details about what specific outcomes Don't Starve does well that you want to achieve too, we can target answers toward achieving those specific results, rather than something that has a vaguely similar appearance in some sense. Oct 22, 2017 at 14:31
• Possibly unrelated, but this map looks like a partially-rendered inkblot with jagged edges. See: mathematica.stackexchange.com/questions/3345/…
– user83935
Oct 23, 2017 at 2:27
• dontstarve.fandom.com/wiki/World_Generation Here you can find info about how they generate worlds :) Mar 8, 2020 at 21:34

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.

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.

• The Don't Starve screenshots look to me like they might be generated from a tree of connected nodes, laid flat through some type of graph drawing algorithm. I think that's what gives rise to the discrete peninsulas fanning out from a central spine. This could then provide the input points for a Voronoi diagram. Oct 22, 2017 at 18:37