How far can you make it? Battle through randomly generated lands and 1000 randomly generated dungeons. Slay monsters, gather resources, and craft new an powerful weapons. All to see just how far you can go. Die in dungeon 999? Start over from one. This is a war of perseverance.

Report article RSS Feed World Generation in Depth

An in depth look into how the worlds in 1000 Dungeons are randomly generated.

Posted by trihex on Apr 13th, 2013

Introduction

I wanted to take a little time and give an in depth explanation of how the random world generation for 1000 Dungeons works.  I think it's an interesting way of approaching random world generation that gives some very interesting (and non-obvious it is random) results.

When a player starts a new game of 1000 Dungeons, they are asked to name the world.  The name given is used as the seed for the random generation of all terrains and dungeons for that game.  This allows players to "share" worlds in that if they find an interesting layout, they can tell their friends the world name they used and they can generate the same world and dungeons.  The experiences the players have will not be exactly the same though, as there are still random elements that are not seeded via the world name, ensuring that there is variety to every new world built.

In each world, there are 10 locations the player must travel through, clearing out every dungeon in a location before moving to the next.  Each location has 100 dungeons in it.  100 dungeons in each of 10 worlds, gives you the 1000 dungeons the title of the game eludes to.  The player has the ability to choose the relative size (small, medium, large) of the dungeons, so they can control how long it will take to progress through the game.  In this post, I will be detailing how the game generates the 10 locations of each world.

World Generation

Each of the locations is made up of a 100x100 tile map, each tile representing a specific terrain type.  That gives each of the 10 worlds 10,000 tiles of terrain to randomly generate.  1000 Dungeons uses a seed and grow method to fill all of the 10,000 tiles per location.  What we mean by a seed and grow method, is that out of the 10000 tiles for a given map, 100 of those tiles will be filled with a random terrain type (grass, mountain, water, forest, desert, etc.).  Then, in successive loops through the map, each of those tiles spreads its type to any blank adjacent tiles.

So as an example, here is what an 8X8 tile map might look like after the inital seeding:


As you can see, we have a randomly placed grass tile, forest tile, mountain tile, and water tile.  The location of each of those starting seed tiles is kept in a list for quick access during the next step.

After the initial seeding, we then begin to grow each seed tile by setting the eight surrounding tiles to the same type as the seed: 


One of the first things you may notice is the blank squares by the water and forest areas, highlighed here:


One of the next steps in the evolution of the generation system is the ability to place transition tiles when certain types come up against certain other types.  As an example, if water moves to the edge of a forest, then we end up with swamp:


This growth phase is repeated until all of the tiles of the map have been filled:


The final step in the generation process is to do a final clean up pass.  This final cleanup pass looks for any stray single terrain tiles, like a loan grass tile in the middle of a mountain range, and replaces that tile with the terrain type of one of the randomly selected tiles surrounding the lone tile.

As always, you can find out more about 1000 Dungeons at our website, or follow us on Twitter

Post comment Comments
Komposten
Komposten Apr 13 2013, 6:09am says:

A very interesting read!
I am, myself, interested in World Generation, and it is always fun to see how other people solve this "problem".
Can't wait to see an overview of a zoomed-out world!

A couple of question, though. Considering the other posted images the tiles aren't placed in squares around the seed all the time, since this would create a very square-shaped terrain, am I right?
How do you address this?

+3 votes     reply to comment
trihex
trihex Apr 13 2013, 6:17pm says:

Has each tile is taken, it's index is put into a separate used tile list. Each loop through the growth function actually goes throw this used tile list to find tiles to grow. So, as an example, lets say we seed indices 9, 20, and 32. The first growth loop will grow the plots around 9, 20, then 32 and add each index to the used list. So on the second loop through, the list may contain something like this:

9, 20, 32, 0, 1, 2, 8, 10, 15, 16, 17... and so on.

So, second loop through, we are growing different tiles in different areas, based off what we grew last time, which will have some (and in may cases all) the growth tiles already filled. This isn't the most efficient means of filling the map, but you jump around enough that you don't get just constantly growing square plots of terrain types. And so far, on the various machines I've run this on the generation of a world is nearly instantaneous, so inefficiency isn't a problem.

Hopefully that explanation makes sense. If not, feel free to ask additional questions.

+2 votes     reply to comment
Pabo
Pabo Apr 17 2013, 7:20am says:

Very interesting. I'm also experimenting these days with tile-based map generation, although my approach is rather probability-based (ie I calculate for each tile the probability for a certain terrain). It gives pretty interesting maps, and I like how I can change some parameters to go from vast riverland to mountainy islands, but I also guess it's less efficient than yours.
Out of curiosity, how long would it take you to generate a 1000x1000 map? Mine takes around 6-7 seconds, even if my algorithm doesn't support the nice "terrain border" feature that you have.

+2 votes     reply to comment
trihex
trihex Apr 17 2013, 11:44am replied:

Not sure on a 1000x1000 tile map. For a 100x100, which is our standard size, it's less than a second to generate the terrain. I would guess it would take a couple of seconds to do a 1000x1000. The "frequency" of each terrain type is set before generation. The way it is currently handled, is 100 random tiles are seeded, then grown. So, if a grass tile has a 0.40 seed value, then we are going to place 40 random grass tiles. The probabilities are distributed between the 5 base types and always add up to 1. This way we can build worlds that are more of certain terrain types and less of another. This plays a roll in the game, as the terrain type a dungeon is on determines what kinds of resources the player can find within it, and the resources the player gathers dictate what they craft. So, with dungeon placement randomized, we need to make sure that there is a good chance, but not guaranteed, that the player will have access to all resource types in any given game.

+3 votes     reply to comment
Post a Comment
click to sign in

You are not logged in, your comment will be anonymous unless you join the community today (totally free - or sign in with your social account on the right) which we encourage all contributors to do.

2000 characters limit; HTML formatting and smileys are not supported - text only

Icon
1000 Dungeons
Platforms
Windows, Mac, Linux
Engine
Torque 2D
Contact
Send Message
Official Page
Bloodytongue.com
Release Date
TBD
Game Watch
Track this game
News
Browse
News
Report Abuse
Report article
Related Games
1000 Dungeons
1000 Dungeons Indie Single Player Roguelike
Related Engines
Torque 2D
Torque 2D Commercial Released Dec 31, 2004
Related Groups
Bloody Tongue Games
Bloody Tongue Games Developer with 2 members