4
\$\begingroup\$

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:

Don’t Starve World

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:

Biomes

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

\$\endgroup\$
  • \$\begingroup\$ +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. \$\endgroup\$ – DMGregory Oct 22 '17 at 14:31
  • \$\begingroup\$ Possibly unrelated, but this map looks like a partially-rendered inkblot with jagged edges. See: mathematica.stackexchange.com/questions/3345/… \$\endgroup\$ – user83935 Oct 23 '17 at 2:27
4
\$\begingroup\$

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.

enter image description here

\$\endgroup\$
8
\$\begingroup\$

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

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – DMGregory Oct 22 '17 at 18:37

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.