Official development blog

Working with Seeds

No, not plant seeds.

As most fans of the genre are aware, a fair portion of a given roguelike run is determined based on values returned by a pseudorandom number generator, commonly referred to as the RNG. Before it can do its job, an RNG must be “seeded,” or given a value that starts the entire chain of values to be returned beyond that point.

Certainly when a roguelike starts up all it has to do is seed the RNG with the current time (the most common practice) and then not worry about it after that--the RNG helps create maps, chooses what populates that map, determines the outcome of actions, and so much more. But it turns out there are many other seed-related considerations and applications when developing games with procedural content.

Important to all this is the understanding that the seed used to initialize the RNG doesn’t have to be random. If manually set to the same number each time, the resulting chain of numbers it spits out will also be the same!

Cogmind’s Seed Structure

For reasons we’ll get to, Cogmind doesn’t just store one seed. There is of course The One Seed, actually called “worldSeed,” which is the single seed from which all others are derived. So in a normal run the world seed is simply based on the current clock time (meaning yes, players who start their run at exactly the same millisecond will technically be getting the same world layout!). And by reusing a specific world seed value in a future run, the exact same world can be generated again and again. Or by simply starting a new run at a different time, the world generated will be completely different.

But if that’s true, then why do we need more than one seed? The answer in two parts: 1) individual maps are not generated until the player reaches them; 2) different players may visit maps in a different order. Therefore at the very beginning of world generation, right after the world seed is determined, it then creates the world layout and within the data for each potential future map it stores the seed to be used to create that map if and when the player arrives there.

cogmind_source_MapLink_seed

Every map has its own mapSeed, generated by the worldSeed (some extraneous comments and code trimmed for clarity).

When the player arrives at a new map, the map generator loads the seed for that map before starting the process. This ensures that everyone visiting that map via the same world seed will also get the same map, regardless of how they reached it.

Development and Debugging

As you can imagine, the ability to force the world to generate in a predictable, repeatable pattern by manually setting the seed is extremely useful for perfecting a map generator like the ones I’ve talked about before.

My first use of seeds in Cogmind would have to be during early pre-alpha development, where much of the focus was on map generation. Being able to seed the generator to recreate the same map again and again when working out problems with the underlying algorithms saved a ridiculous amount of time compared to just waiting for specific problems to pop up. So I could keep skipping through procedural maps until finding an issue, check whatever seed led to it, force the generator to use that seed, then step through the process to find out what went wrong (or could be improved). It’s really easy to track down isolated issues by simply putting a breakpoint in the debugger for a specific coordinate in question, and examine what’s up with it.

cogmind_map_generation_storage

I spent a lot of my time looking at maps like this, waiting for a “bad seed” to investigate.

After releasing the alpha, bugs either reported by players or that I discover myself are sometimes related to the initial state of a map, and in cases like that it’s ridiculously useful to be able to just load up whatever seed produced that map and take a closer look. Being able to reliably repeat a bug is the first, and biggest, step to actually resolving it! The alternatives are not too pretty--if unable to guess the cause from a simple report, having to wait for it to appear again to get more details is an annoying drawn out process, not to mention much more difficult to do remotely.

cogmind_random_seed_locations

A run’s seed is output to run.log while the game is running, as well as added to the final score sheet.

Preserving Consistency

It turns out there are all sorts of places where a seed can go wrong :P

Ideally a world and its maps and all the little details within those maps originating from a single seed should be the same for each player using it, so there are important game-specific considerations aimed at preventing “divergence.”

A simple example would be scrap piles in the caves, which are kind of like treasure chests that drop loot. If I didn’t care about proper seed support my normal approach would be to simply generate the loot on the fly when the player steps on the pile, but each player will have taken different actions before that point, meaning the RNG will give each of them different items! For consistency, all players using the same seed should have access to the same “random” loot. Of course the brute force method would be to pre-generate and store all the loot when the map is first created, but this is wasteful in terms of both time and memory. Instead each pile just stores its own unique “loot seed,” and when necessary that seed is used to seed an RNG which generates the loot on the fly. That way it comes out the same for everyone on the same map. (It also means that attempting to save scum to get different loot won’t work :P)

cogmind_searching_scrap

Determining loot from scrap at the point of interaction.

An example of a system that required a more involved solution to ensure consistent game worlds is the unique encounter handling. While some encounters in Cogmind are generic and might occur more than once, many are unique and should at most happen only once per run. (It would be weird to meet the same named NPC and specific encounter more than once in the same run :P) But because maps aren’t generated until the player reaches them, there’s no way to know which map might use a certain unique (or otherwise limited-count!) encounter. A given encounter may be allowed to appear on any number of maps, but what if player 1 visits map A first and gets that encounter, while player 2 instead visits map B first and gets that same encounter. Their maps will generate differently! And they’ll have even more divergent experiences if they then visit their respective “other map.”

To address that, all unique or limited encounters are randomly assigned a valid map when the world layout is first generated, and they will be chosen from among the pool of encounters available for their map, which may or may not use them--it can’t be sure because there may be other conditions required for that encounter to actually appear (conditions that cannot be confirmed until the map itself is created), but at least it’s known that said encounters cannot appear on other maps and cause divergent runs from the same seed!

Seed-based map generation also requires explicitly separating out a number of components that factor into the initial state of a map, where those components are derived from player actions. Actions like bringing allies from one map to another, or plot-related content through which the player can affect future events, all need to be taken into consideration to prevent prior actions from affecting the base map, which should remain as consistent as possible aside from purely what the player influences. For this reason I’m careful to exclude anything player-specific from the map generation process until the very end.

cogmind_source_mapgen_player_specific_changes

Cogmind mapgen source transition from the underlying map to player-specific adjustments.

Other changes to the usual behavior are necessary when players manually seed their own run. This is to make sure that the handful of automated player-specific meta features are deactivated. These are features aimed at newer players, such as the tutorial map, which normally replaces the first map for a player’s first three games. Another example is an encounter inserted only the first time a player enters a Waste map, wherein a Derelict says a little dialogue before running ahead and getting brutally crushed so the player immediately realizes that’s not something they want to do :P

cogmind_waste_entrance_warning

Bad things are about to happen.

Seed Formats

Seeds don’t have to be numbers! Well, they are internally, but developers shouldn’t place dev restrictions on players where unnecessary. It’s time for more “ergonomic” seeds :)

Number-based seeds are boring, and not as easy to remember or share, so early on I made sure to allow any alphanumeric strings to count as valid seed input. Players can, for example, try out using their name as a seed, or some other interesting words or phrases. I’ve even had one player go through multiple runs, changing the seed to a new phrase each time, which when read together formed a longer message and appeared in the upload stats :P

Of course, internally these string-based seeds are no different from numbers. Each character is converted to its decimal value, all of which are multiplied against one another to create a final number the RNG can use as a seed.

So manual seeds have always allowed strings, but random seeds (i.e. the majority of seeds players are using by default) have still been represented by numbers. More recently I decided that I wanted to take this a step further and have even random seeds be expressed in words, but how would they be determined?

The solution was inspired by gfycat, which instead of generating a string of random characters for their URLs uses an AdjectiveAdjectiveAnimal format (see the end of their about page). My first thought was to go with lists of Cogmind-relevant words that I’d draw up myself, but that looked like it would be quite a lot of work--there had to be a quicker solution. And there is!

Cogmind already has a bunch of relevant adjectives and nouns in the game data itself, so why not just use those? Specifically, most items are named in a predictable Adjective + Noun format, and those words can be extracted for use in mixing and matching. Cogmind has nearly a thousand items, and the number of permutations if we pick three sub-words in a row gives plenty of variety. AdjectiveAdjectiveNoun it is :D

To create a seed, the entire list of existing item names is parsed according to various rules, creating a separate word pool for adjectives and nouns. Nouns are generally assumed to be the last word in an item name, and all the others are treated as adjectives. Other filters to keep some of the weirder items from creating seeds with odd formatting:

  • Word must contain at least three characters
  • First two characters must be different from one another
  • No words including punctuation or digits
  • Word cannot be entirely upper case

And finally no duplicate words are added to the pool (which would weight them higher). In the end we get random seeds like this:

cogmind_random_seeds_shortlist

Randomized “fake item names” as seeds--much better than something like “1477302648”! (see a longer list of samples here)

These fake item names are a heck of a lot more fun than numbers, and there’s the added bonus of seeing words in there that you may not recognize, as a kind of teaser for other items that are actually out there somewhere. As mentioned before, the random seed used to create a run appears in the score sheet, and each is also listed alongside its run in the composite score history.

cogmind_random_seed_score_history

Scorehistory.txt, with fake item seeds.

Miscellaneous Applications

We’re not done yet! Seeds have a surprising number of applications, so let’s check out some more of them…

Community

Roguelikes are single-player games, but there are plenty of features with community-building potential. One of those is so-called “weekly seeds,” where a single seed is played through by multiple people who can then share their experiences, or compete with one another for the best score, knowing that they are at least playing with the same fundamental circumstances.

Cogmind has had… semi-weekly seeds for the past couple years. Although not as popular as they were in the early days (when lots of the regular players were on the forums instead of chat :P), I’m sure they’ll pick up again when the player base expands again this year. Some roguelikes such as Caves of Qud even have the weekly seeds built into the game itself (with separate leaderboards!), something I haven’t done yet but probably should at some point.

Replays

One thing I’ve always wished I could to do is enable full replays of a run, which is most easily accomplished by combining a seed with the player’s recorded input. But a couple of architecture road blocks have made that all but impossible :/. Cogmind’s animation system is mixed in with the game logic, so features like adjusting the speed of animations (or canceling them altogether) are not possible. For replays to work there’s also a need to use different RNGs for the game logic and any rendering-related functionality, which is something I didn’t do. Essentially, this kind of feature should be built in from the beginning to make sure it works, rather than trying to tack it onto a sprawling 120,000-line code base :P

Obviously replays also add a lot of value with respect to learning and community-building. At least we always have streams and LPs, in any case.

Regarding that replay technique, it can even be used to implement saving. Instead of actually saving the entire state of the game, save all of the player’s input from the beginning. Then when it’s time to load, seed the RNG using the same value, followed by all the same input to get the same final result! I’ve heard that Brogue saves work this way, although “replays” are such a complicated thing that I’ve also heard Brogue’s saves are prone to breaking in some cases, which prevents loading that saved game :/. Still, a very cool system overall!

Saving Large Worlds

Another type of seed-based saving is useful for large open-world games, in which storing the entirety of the game state isn’t feasible (too much space!), nor is keeping every visited location in memory. Instead the world is divided into chunks, each with its own seed (essentially how Cogmind’s map-specific seeds work), and a chunk is only generated when the player nears it. Storing that area on traveling elsewhere, or saving the game, is simply a matter of storing its seed along with whatever changes occurred between its generation and the time it’s stored. So even games with destructible terrain and other player- or NPC-induced changes can take advantage of this kind of “delta map” system to keep system requirements within reason, despite having nearly infinite space to explore. (Literal space exploration games can use this same method. One such example was Infiniverse, but sadly its site and some relevant technical articles are no longer available…)

Seed Catalog

One of the more unique seed applications I’ve seen is the Brogue “seed catalog,” which comes with the game and contains a list of every item found on each of the first five floors for the first thousand seeds.

brogue_seed_catalog_excerpt

Excerpt from Brogue’s seed catalog.

Basically it’s a meta-approach for adjusting the difficulty, or perhaps to look for a seed more suitable for a desired play style (since early-game items in that roguelike can have a significant impact on long-term strategy).

Have you heard of any other uses for seeds? I’m sure there have to be more out there…

This entry was posted in Gamedev and tagged , , , . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

2 Comments

  1. YinYang
    Posted May 3, 2017 at 4:27 am | Permalink

    Did you look at http://www.gamasutra.com/blogs/RuneSkovboJohansen/20150105/233505/A_Primer_on_Repeatable_Random_Numbers.php ?
    It talks about a deterministic random / hash function that can be used to get a random value given a set of coordinates, so you can do things like new Random(seed).get(x,y) and it will return the same value given the same values of seed, x and y.
    Maybe you can use something like that to seed anything location related instead of storing the seeds of everything :-) , I used something like that to seed dungeon generation, where each new level in the dungeon was generated based on the location of the entrance in the previous dungeon level, until you reached the overworld where the location of the dungeon entrance was in the world was used.

    • Kyzrati
      Posted May 3, 2017 at 9:12 am | Permalink

      Good point, thanks for bringing that up! Someone on the Rogue Temple forums also linked another version of that same article on the Unity Blogs :P

      I did neglect to mention the coordinate-based hash seeding approach. I’m aware of it but since I’ve only needed a localized seed for that one case (which only appears at most a few times on a small portion of maps), it was just easier to store a number rather than working in some hash function.

      It’s definitely worth building something more robust for cases like open-world games where you have a lot of location-based content accessible from a single map grid.

Post a Comment

Your email is never published nor shared. Only the anti-spam entry is required. See here for the privacy policy.

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>