Introduction
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
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.
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?
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.
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.
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.