This blog post is mostly going to be me brainstorming aloud how I plan to procedurally generate the world for Emberwood. For the most part, I’m just reporting what research I’ve done so far on procedural generation techniques and how I plan to implement it into Emberwood. In case you’re new to the blog, Emberwood is going to be a retro-styled ANSII Text Roguelike set in a procedurally generated fantasty world.

If you want to see Emberwood’s progress, feel free to check out the Cider Mill Studio YouTube Channel, where I share major updates, demos, as well as provide an overview of the Java/Gradle code base.

Current Plan Ramble / Brainstorm / Here we go:

What’s very important about the way the world is generated is that it’s generated on the fly, meaning that as you enter a new chunk of terrain (a chunk being the standard unit of terrain generation, 64×64 tiles), the adjacent chunks within the render radius will be generated into existence all at once in that very moment, not before. As you explore in a certain direction, more chunks in that direction will generate around you, and chunks far behind you will automatically unload and cease to exist until you revisit them later.

Furthermore, as the player explores, all chunks will be loaded from a World seed (which is literally just a randomly generated string of numbers/letters which allow for Pseudorandom Number Generation, or PRNG), which essentially serves to provide same-seed-same-world generation (i.e. that if you were to play the game using a given seed, the same exact world would be generated for other players who use that seed on their computers, every time without fail).

So two important aspects so far: on-the-fly world generation (chunk loading and unloading as the player explores), and the same-seed-same-world feature (which I call deterministic procedural generation, because the seed itself determines the generation of the whole world).

Next up will be the ‘engine’ that produces pseudorandom values that we can turn into terrain. This engine will be Perlin noise (specifically, I’m using the open source JNoise library, which allows Java developers to create customized Perlin noise generators. The way Perlin noise works is that a noise generator takes some mathematics function (most commonly a cosine curve) and stacks copies of that function on top of one another as ‘octaves’. Each progressive octave usually has an increased frequency (shorter wavelength) and a diminishing amplitude compared to the previous octave, and the result of multiple octaves added up together is a pseudo-random wiggly line that looks like random noise.

There are a bunch of settings to tweak in Perlin noise generation, including persistence (the size of higher octave amplitudes), lacunarity (idk what this means yet), and scale (the size/wavelength of the resulting noise). So far, I’m excited about some of the results:

This was my first attempt (it’s pretty jagged!), but what you don’t actually see is a ‘color condensor’ which turns many different values of white, black, and gray into an image consisting of only 3-4 tones of gray. Here’s an example of what Perlin noise (with a smaller scale) looks like before condensing the colors:

And now here’s that same image after condensing the colors into just 4-5 shades of gray:

Here, dark gray might represent wall-tiles like the stone wall of an underground cave system, black might represent areas where ore might spawn (and be able to be mined), while lighter shades of gray represent floor tiles, and white may represent spawning points for interesting creatures, enemies, loot, lore, etc…

Here are some other Perlin noise samples so far:

The next question that arises is how to use Perlin noise to generate a simulated game world, with geography, NPCs, quests, and dungeons? Also, what’s special about Emberwood’s procedural generation that is unique compared to other proc-gen games that already exist?

What makes Emberwood’s World Generation Special:

Here’s the question that stumped me for a bit… If Emberwood will be a 2D ANSII Text Based game (consisting of X and Y coords only), then will it even be possible for players to descend down into the world (down as in decreasing along a Z-axis)?

I spent way too much time coming up with a unique solution to this problem, and I’m excited about the possibilities which it offers. But first here’s a quick list of key terms for this article for you to reference back to as needed.

Key Terms:

• World Level: describes one planar level of the world that sits atop and below other types of World Levels. World Levels can be described as being like sandwich contents, all stacked on top of each other (Overworld sits atop the Underground, which sits atop X, etc…).
• World-Bridges: mini-levels that contain one or more floor, and serve to connect different World Levels; might be dungeons, caves, abandoned mines, etc…
• Tile: a tile represents one square of traversable world space. The player can move one tile at a time as they explore an area.
• Chunk: the standard unit of world generation, a world is generated one Chunk at a time, which consists of 64 x 64 tiles, and contains the data for each of those tiles.
• Region: an object that represents a grid of 16×16 Chunks (one Region covers 1024 x 1024 tiles), by containing important metadata that defines the 16×16 Chunk area, including whether or not a structure is present in that region, which structure is present, where the structure is located in that region, and other data that “flavors” the Region, such as the inhabitants of the structure, their personality/alignment, their tone, and their ties to other structures nearby.

Now that we have some key terms identified, let’s get into it. Don’t worry if the terms don’t make sense yet – I’ll do my best to provide context below, which should help.

The player spawns somewhere in The Overworld (World Level 1). The Overworld is generated with very largely-scaled Perlin Noise which defines altitude (lighter colored noise = higher elevation, while darker = lower elevation). Places with high elevation would be mountains, while locations with moderate elevations might be grasslands or forests, while locations with low altitude (dark-gray/black) will be filled with water (lakes, oceans). A separate layer of Perlin noise may be stacked onto the Overworld to determine some variable like ‘Corruptedness’, which determines if a region is peaceful or hostile to the player. Lastly, a final algorithm will be used to determine placement of structures and NPCs to populate the world, which would take into account altitude, corruptedness, and other factors that I have yet to imagine.

As the player explores the Overworld, they’ll eventually find entrances to caves or dungeons that serve two purposes: 1) to be a source of emergent storytelling (the dungeon might serve up some lore, or be the lair of some dangerous creature guarding loot, etc…), and 2) to be a World-Bridge to The Underground (which is World Level 2), which will have different biome types, different (more dangerous) creatures and enemies, and access to new materials which open new possibilities. Most importantly though, The Underground has its own Perlin noise generators to determine elevation, corruptedness, etc… separate from the noise generators of the Overworld.

Here’s how the World-Bridges between World Levels will work in a deterministic way:

Question/Problem: Where would World-bridges spawn in the Overworld?

Solution: As the Player explores the Overworld, new Overworld Chunks are loaded and rendered, but Underground elevation data is also loaded at the same X and Y coordinates that the player is located in the Overworld. If the player is exploring an area of the Overworld, and that same location of the Overworld overlaps an area of the Underground where the Underground altitude is particularly high, those conditions will result in the spawning of a World-Bridge Level and would take the form of either a Cave Entrance, or a Dungeon, or some other lore-significant passage between the Overworld and the Underground. To get from the Overworld to the Underground, the player will need to enter the World-Bridge from the Overworld side, (note that the World-Bridge would be it’s own sort of “in-between level”, but significantly smaller than the world-levels), and the player will need to explore the World-Bridge level until they find the entrance of the Underground level. Important note: The higher the Overworld elevation is where the entrance to the World-Bridge is, the larger the World-Bridge level will be (because logically, if you’re entering the bridge to the Underground from a mountain, you’ll have to dig a lot deeper to reach the same ‘depth’ as you would if you had started descending from a lower altitude, like from an Overworld beach or grasslands biome for example).

Example 1: The player is exploring a Deep Forest Biome in the Overworld, and eventually stumbles upon a large fallen meteor containing wrought iron. The player decides to mine the meteor (which requires significant mining skill, perhaps knowledge of astronomy, a proper pickaxe, and those things alone take some effort to come by, so this probably would not occur until the player has spent quite a few hours exploring the Overworld), and once the meteor crumbles away, an opening to a cavern is left behind. The player is prompted to descend into the cavern. This cavern is one of many “World-Bridges” (a miniature level that may consist of multiple floors), that serve to connect the Overworld to the Underground. You can think of a “World-Bridge” as a Dungeon that connects different layers/phases of the game world together. As the player explores this cavern, they find that this World-Bridge is home to a nest of giant spiders who are holding nearby villages as fresh prey underground. If the player chooses to rescue the villagers, the player may earn some reputation within that village, allowing access to special deals or rewards from the village. Regardless as to whether the player assists the villagers, the player will eventually find the entrance to the Underground (located somewhere deep in the nest), and when this entrance is found the player will be able to enter and explore the Underground World Level. When the player wants to return back to the Overworld, they may come back to this World-Bridge (the spider nest) and climb back up to get to the Overworld. Since this World-Bridge was found rather low in the Overworld’s elevation map (a Forest biome), the cavern will be a small- to moderately-sized map, perhaps 5 or 6 floors in total.

Example 2: The player is exploring a Mountain Biome at high altitude in the Overworld, and comes across an intimidating tower jutting out of the side of the mountain, at such an angle that it appears to disobeying the laws of gravity, with strange ambient sounds emanating from it’s dimly lit windows. The Tower itself gives off a disturbing aura, and is adorned with strange runic glyphs etched into it’s stone bricks. The player recalls rumors from a grasslands village to the South that strange creatures have been reported on the village’s outskirts, and there have been reports of villagers who have gone missing in the night. There are also old tales of a tower-dwelling Wizard who long ago became obsessed with dark magic and went Mad. Could this Tower be related to those reports? The player decides to ignore this tower for now, as their health is quite low from a skirmish with goblins which occurred a few moments ago, and the player isn’t looking for any more trouble. The player pushes forward up the mountain, and eventually, they come across an apparent dead-end consisting of stone-walls, but amidst the stone-walls, they notice one segment of wall is etched with strange runes, similar to those seen on the Tower earlier. When the player tries to interpret the runes, they are given a message: “Cannot understand this language”. The player, now curious if there may be a connection between the mysterious Tower and these Stone Runes, decides to go back to the Tower to explore it. As the player ascends the tower, they find out that the tower is indeed the fortified dwelling of the infamous Mad Wizard (confirming the rumors in the village). The player fights their way up the tower against the wizard’s abominable creations, only to reach the top to find that the Wizard is not at home, but he did leave his scrolls at home, including a Runic Cypher with glyphs that match those etched into the nearby Stone-Wall. The player takes the Cypher back to the runic stone wall, and successfully interacts with the wall in such a way that a door into the mountain opens, and the player is able to enter “The Dungeon of the Mad Wizard” (which, for this example’s purpose, is a large World-Bridge Dungeon connecting the Overworld to the Underground). Since this Dungeon starts in the high altitude of a mountain, the dungeon consists of many floors, perhaps 20, and each floor is progressively harder than the last. Eventually on the deepest floor, you encounter the Mad Wizard, and must defeat him in combat in order to proceed to the Underground. Upon completion of the dungeon, the player is rewarded with very rare and valuable loot, and gains a boost in reputation in the Overworld grasslands village to the South.

Note that the Mad Wizard’s Dungeon in Example 2 is significantly more challenging than the Spider Nest in Example 1, and that’s intentional! The idea is that there should be inter-World-Level difficulty such that Exploring the Overworld offers varying levels of difficulty to keep the player engaged regardless of which World Level they’re exploring. If difficulty could be rated on a scale from 1-10, the Overworld and it’s world-bridges to the Underground might initially offer difficulty levels 1-4, while the Underground initially offers difficulty levels 2-5, thus there’s some overlap in difficulty between the Overworld and the Underground, but there’s also gradual progression to higher difficulties as you descend downwards.

The reason that I said that each World Level initially offers a range of difficulty is because that exploring the Underground will unlock materials and items that will unlock previously inaccessible locations in the Overworld. This means that the player can return to the Overworld from the Underworld with the right materials and equipment, and be able to unlock certain Overworld locations that offer much higher difficulty than the initial difficulty range of 1-4 (in other words, while the initial difficulty of the Overworld is 1-4, you can eventually unlock locations that are difficulty ranges 5-10, all in the Overworld).

But wait… Is there anything deeper than the Underground? Of course, the eventual goal is to expand the world even deeper than the Underground, opening up opportunities for weirder and stranger procedurally generated places. The World Level beneath the Underground might offer difficulty ranges 5-8 for instance. And similarly to how World-Bridges to the Underground exist in the Overworld where the Underground altitude is high, the same system would apply for the World-Bridges that connect the Underground to whatever is beneath it.

However, to prevent me from getting ahead of myself, I think it’s prudent to focus first on the Overworld and Underground before going deeper. Once those two World-Levels are flushed-out and feel playable, then I’ll feel better about adding more content below.

Problem/Question: If the world is infinite along the X and Y coordinates, how will we be able to store all of that data on a hard drive? Wouldn’t it eat up way too much space?

Solution: If we wrote the data for each chunk that the player explores to the disk, then absolutely yes, a modern hard drive of even 1TB would fill up very quickly. The key here is that we’re not saving any chunk data to the hard drive, ever, unless the player changed something about that chunk. So if a player walks through a chunk without changing anything about it, nothing is saved, and the chunk can be unloaded from memory once the player gets far enough away from it. If the player re-visits that chunk, it is regenerated from scratch based on the world seed and will look the exact same to the player. However, if the player does change anything about the chunk (places an object, chops down a tree, etc…), that change is saved to disk so that when the player re-visits that chunk later, those changes can be instantly re-instated to give the illusion of world-persistence.

Many other games with proc-gen use this type of technique. For instance, in Minecraft, when you build your house on a given chunk of land, the disk is saving data only about things that you’ve added or changed. When you go explore a far-away biome in Minecraft, your house unloads from your screen and your changes are saved to your hard drive. But when you go back to your house, the world-seed is used to generate your house’s chunks as they existed before you ever got there, and then instantly loads all the changes that you’ve made to that chunk, and the result is the illusion of your house persisting in the game world.

Question/Problem: How is this deterministic procedural generation? In other words, how does one world seed ensure that you get the same exact World (same Overworld, Underworld, World Bridges, Structures, and NPCs) every single time any player generates a world that uses that specific world seed?

Solution: After doing some reading (mainly on Minecraft, Caves of Qud and Dwarf Fortress), one technique is to allow one world seed to spawn multiple sub-seeds. Let’s say, for the sake of argument, that one world seed will generate 3 sub-seeds per World Level (3 sub-seeds for the Overworld, 3 sub-seeds for the Underground, etc…):

Sub-seed #1 is used to generate the Perlin noise map that will determine elevation of each tile of that World Level.

Sub-seed #2 is used to generate the Perlin noise map that will determine the corruptedness of each tile of that World Level

Sub-seed #3 is used to generate the Perlin noise map that will determine which tiles of that World Level will have special tiles generated (Biome-dependent, also corruptness dependent). Perhaps Forests will have tree tiles and mushroom tiles, whereas grasslands might have rock tiles, crop tiles, manure tiles, and flower tiles. Rarely, in any biome in any World Level, there may be a tile containing something unexpected, like finding in the grasslands the skeletal remains of a long lost traveler (which may be lootable for a few coins, a dagger, and a note he wrote as he was dying, describing some terrible monster that may or may not still be lurking in the region).

Now let’s imagine we just have two World Levels: the Overworld and the Underground. This means that 6 sub-seeds will govern the elevation, corruptedness, and special tiles for the different World Levels. For example, in the Overworld, a given chunk might contain tiles that have a high elevation (thus labeled Mountains), might have high corruptedness (hostile), and may have contain special tiles like various ores.

But what about placing structures?

Intertwined (but Distant) Structure Generation

The challenge here is figuring out how to generate distant structures that are many chunks away from each other but are related to each other in a narrative way. In the example regarding the Stone Wall Runic Door, the Mad Wizard Tower that contains a Cypher, and the terrorized village at the base of the mountains, all three structures need to be aware of each other so they can weave a narrative together: The village is aware of the Wizard’s tower, the Wizard is aware of the village, the Runic Door is aware of the Cypher from the Wizard Tower, and the Tower knows to generate a Runic Cypher that can unlock the Runic Stone Wall Door.

But if the player enters the village first before ever visiting the Wizard Tower or the Runic Door, how does the procedural generation engine know to populate a village with villagers who have knowledge of the nearby Mad Wizard, especially if the Mountain Biome chunks (which will contain the Wizard’s tower and the etched stone wall) have not yet been generated at all? And alternatively, if the player first stumbles upon the Runic Door before visiting the village or the Wizard Tower, how does the game engine know that this door requires a Runic Cypher from a nearby wizard tower, and that the Wizard who once resided in that tower terrorized the grasslands village to the South?

The solution? Regions.

Regions (a ‘chunk’ of chunks?)

Regions define certain behaviors of large patches of the gameworld that are 16 chunks by 16 chunks in size (and since each chunk is 64 x 64 tiles, one Region is 1024 x 1024 tiles in size).

The important thing about Regions is that they won’t contain the high-resolution/memory-expensive data that each Chunk does – they won’t store data about the individual terrain type of each Tile. Region data will be digitally cheap “metadata” that describes certain attributes of the region such as a boolean value (True or False) for whether a given region even has a Point of Interest (let’s call this ‘hasPOI’. A POI might be a structure or series of structures, like a Village, a Castle, or a Shrine). If hasPOI is True, the metadata will have an enum called typeOfPOI, which defines which type of POI is contained in the region. The other parts of the metadata may include an x/y offset (so that POIs don’t always spawn in the dead center of a region, which comes off as artificial), a “dangerLevel” to determine which types of enemies and how many enemies spawn at and around that POI. Other important metadata would include information about the main boss of that POI (if any), that boss’s personality, their allegiance/faction, their loot, etc…

The next natural question that arises is how Region metadata can be made such that it is deterministic. The answer again, is that the world seed will be used to generate the metadata for each region in a pseudorandom way, guaranteeing reproducibility of the World including reproducibility of it’s structures and those structures’ inhabitants, loot, etc… This means that all aspects of the game (geography, biomes, structures, NPCs, enemies, etc…) are all simply a mathematical function of the worldseed and the coordinates of the game map. Since the rules of mathematics are never-changing, feeding the same world seed into different players’ computers will result in identical worlds for both players.

The other reason why Region metadata are so important is, since they have such a small amount of data for such a large region of land, they are easily queryable from any location in the game, even if the Region being queried has never been generated yet! So for example, you could be in the grasslands village without having ever visited the Wizard Tower, and the village will be able to throw a query to the proc-gen engine: “where is the nearest Structure, and how might it relate to this village?” The result of the query is that the village “searches” for adjacent Region metadata and sees that there is a nearby Tower to the North, which is the home of a Mad Wizard who sends scary creatures to terrorize the village, and that the Wizard uses a separate secret door in the mountains that uses a Runic Cypher to open up. Now, the village “knows” everything it needs to know about the Wizard Tower and nearby Runic Door to populate the village with Villagers who can spread rumors about the Wizard, and provide clues to his whereabouts, as well as clues about how to possibly open up the Runic Door. The impressive part about this strategy is that by the time the player interacts with the villagers and hears all the rumors about the Wizard and the Runic Door, the Tower nor the Runic Door, nor the entire Mountain Biome has been generated at all, but the village is STILL aware of these structure because the adjacent regions’ metadata is queryable.

Since this post is getting quite long, I’ll stop for now and quickly summarize:

In Summary:

Procedural Generation is coming to Emberwood, and I genuinely could not be more excited. Learning about different procedural generation techniques has been so exciting and rewarding during the past month or so, and I finally feel like it’s starting to click. What I’m especially excited about is the emergent gameplay that can arise when you combine well-thought out game mechanics with a procedurally generated world map (geography, biomes), and procedurally generated inhabitants, enemies and structures. Hopefully, this will allow players to create their own story through emergent gameplay, with high amounts of replayability.

Go pick some apples, and don’t forget to drink some apple cider this Autumn!

As always, cheers to our dreams,

Wady