Author Topic: Considering when to generate random map details, all at once or as needed?  (Read 3010 times)

evildrspock

  • Acolyte
  • *
  • Posts: 1
    • View Profile
    • Email
I was considering when creating a roguelike game with random map generation, and you have more than one map, room, or level that the player only occupies one of at a time (I'll focus on levels).  Using a pseudo random number generator, I see two unique, broad approaches:

  • Generate all levels and map details immediately upon starting a new game.
  • Generate new levels on-demand, only when needed.


From a gameplay perspective, the two approaches have an identical effect: each visited level is randomly generated each time the game is played.

The first option feels more "pure" for myself as a developer since the world exists based on the random seed and my game's map generation logic, and the player's decisions don't in any way effect the layout of dungeons.  However, depending on the complexity of the world I want to create, this may take a considerable amount of time to generate, and I can't create a truly unending sequence of levels, there is physical limit of storage space.

The second option at first jumps out to the software engineering side of me in that I can only create the necessary levels on demand, spreading the time cost of level generation out across the game, and the processing time for generating the next level can even be done concurrently while playing the current level.  However, if I use only one RNG for the game and in-game effects may be randomized, RNG manipulation can occur and the player's choices can change the next generated map.  Furthermore, if there are multiple exits from one level, the order in which the layer chooses where to explore further complicates the decision and dependency on the order of events.

I know I could track multiple RNGs depending on the needs of my game, so that one RNG handles the maps, and another handles NPC decisions, etc, but I am curious as to what others have done when faced with this decision.

Please note, I am new to the forum so if this question has been discussed before and I missed it, please point me in the right direction.  Thanks!
I like mazes.  If I ever share a roguelike with the community, it will be one of my projects that involve exploring mazes.

elwin

  • Priest
  • **
  • Posts: 92
    • View Profile
    • Roguelike Gallery
Re: Considering when to generate random map details, all at once or as needed?
« Reply #1 on: December 02, 2015, 01:12:46 AM »
Almost all games generate each level when the player first enters it.  Some may make a few high-level decisions at the beginning, but most generation happens only when it's needed.

Most developers consider the player's actions affecting the RNG state a feature.  It makes level generation less predictable.  To get the exact same game twice, you need to both seed the RNG and make exactly the same moves.

You might want to check out HyperRogue.  It's set on an infinite (hyperbolic) plane, and it generates new cells each turn as the player discovers them.
Roguelike Gallery: play Rogue online.  SSH or in browser.

mekaerwin

  • Acolyte
  • *
  • Posts: 11
    • View Profile
    • Email
Re: Considering when to generate random map details, all at once or as needed?
« Reply #2 on: December 02, 2015, 03:20:47 AM »
I think that there are ways you could obfuscate the player's ability to influence the next level generated if that is important to you. You could generate a couple of levels ahead as one way. Depending on how hard it is to implement, I think your idea of a separate RNG would be more logical though.

I do think that generating the whole world at once would need some good justification if it could conceivable be done on the fly (Not saying that there aren't valid justifications, there are).

tuturto

  • High Priest
  • ****
  • Posts: 259
    • View Profile
    • pyherc
Re: Considering when to generate random map details, all at once or as needed?
« Reply #3 on: December 02, 2015, 04:40:17 AM »
Do you want to use the same seed everytime game is played and have the world to be the same? Or do you want to select a random seed, based on something keyboard/mouse noise, time, etc. and use that? Because if latter, then it usually doesn't matter if the player actions change rng state. From their point of view, the game would still have unique world, that was generated just for them to play and they wouldn't be able to affect the creation in a feasible way.

If you want to use the same seed for every game and avoid player actions altering the world state, you could still generate levels one by one and have them come out the same. Just store a random seed for each stairs and reset rng with that seed when generating next level. Because random seed comes from rng originally, which had that specific seed you chose to use, it should always be the same. No matter what player does on the level will affect that seed and change the next level, even if there are multiple stairs that can be taken in a single level. Basically the same thing the original Elite does, but in a simpler scale.
Everyone you will ever meet knows something you don't.
 - Bill Nye

Krice

  • Protector of the @
  • *****
  • Posts: 2049
    • View Profile
    • Email
Re: Considering when to generate random map details, all at once or as needed?
« Reply #4 on: December 02, 2015, 06:34:39 PM »
I do think that generating the whole world at once would need some good justification if it could conceivable be done on the fly (Not saying that there aren't valid justifications, there are).

Good thing about generating the world at once is that you can then (double) check everything and possibly avoid bugs that way. It'll probably take a while, but can be easily displayed with some kind of progress bar or whatever so it doesn't have to be instant. On the contrary I think these days you should justify why the game world is created one level at a time, or even in smaller pieces.

AgingMinotaur

  • Protector of the @
  • *****
  • Posts: 746
  • Original Discriminating Buffalo Man
    • View Profile
    • Land of Strangers
Re: Considering when to generate random map details, all at once or as needed?
« Reply #5 on: December 02, 2015, 09:07:54 PM »
My own game Land of Strangers currently has (nothing but) a continuous overworld, which is generated on the fly, one "sector" at a time. The player can set the world generation seed if they want, and it's a bit tricky to maintain two seeds and all that, but straightforward enough to get around. My reasons for doing it this way is a bit just to see how that goes, and I'm hoping it will make world generation more flexible for things like random questlines. For instance, if the player chooses a mission to neutralize a robber camped "under an abandoned railway bridge to the north", the game could randomly pick a sector which hasn't been built and mark it to generate the quest location once the player enters (matters more complicated if there are no more unbuilt sectors, of course ;) ). A general outline of the world probably needs to be done at game start. I'm currently generating a rough climate map before the game begins, and am planning to also predetermine where some "important places" will lie (so you'll always have 2-3 friendly settlements and a few central danger locations), as well as a map of roads, rivers and plateaus.

As always,
Minotauros
This matir, as laborintus, Dedalus hous, hath many halkes and hurnes ... wyndynges and wrynkelynges.

Ancient

  • High Priest
  • ****
  • Posts: 453
    • View Profile
Re: Considering when to generate random map details, all at once or as needed?
« Reply #6 on: December 03, 2015, 08:14:26 AM »
Easy. Keep two RNG states: one for gameplay plus another for creating levels. SporkHack went as far as introduce RNG state for each monster to ensure it will not behave differently depending on whether you zigged or zagged when entering the room.

PRIME creates all levels up front. It has few of them. so this is quick. Furthermore, in generation I place constraints and features depending on vertical relation of levels near them. This is important for digging down.
Michał Bieliński, reviewer for Temple of the Roguelike

Trystan

  • Bishop
  • ***
  • Posts: 164
    • View Profile
    • my blog
Re: Considering when to generate random map details, all at once or as needed?
« Reply #7 on: December 04, 2015, 02:43:11 AM »
One big advantage of doing it all at once is that it can be easier to guarantee things about the entire world, like connectivity or distribution of loot, at once. I also prefer to have the worldgen stuff in seperate code that only happens once.

The only major advantage to doing it one level at a time that I can think of is that you can create the next level or item based on the current situation. That is, you can do something like have a 10% chance of the next level being The Ice King's lair if the player has the Ice Crown, spawn a bunch of cursed loot if the player is unlucky, spawn a thief for each 100 gold the player has, etc.

I've tried both ways with 7DRLs and personal test projects and I find the all-at-once way easier to code and reason about. Maybe a mix where the levels are created first but the loot in treasure chests or boss drops are determined when needed based on the what the player is doing?

forumaccount

  • Acolyte
  • *
  • Posts: 6
  • is there an ignore list feature?
    • View Profile
Brogue generates a floor ahead of the player so that it can know what happens to items and creatures that fall.

Technically the whole dungeon is set in stone because the seed is randomly generated or player inputted at the start, and each further floor uses that number + 1. But the engine still doesn't actually know layout / items / creatures until the player is near.

The time savings can be seen like this: click new game. Bam you're in! Now run a seed scummer and force it to search the whole dungeon... takes several seconds per dungeon which would actually be noticable, though minor, at game start.

sokol815

  • Priest
  • **
  • Posts: 84
  • Web Developer by Day, still Web Developer by night
    • View Profile
    • My Projects
    • Email
Slight necro up there, but this is one of my favorite topics, so I thought I would comment, too. I personally prefer the method of keeping 2 main rngs. The first would be for level generation, the second for everything else.

With Strife(which I am planning to get back into), I have a basic world structure that gets generated upon starting a new game... an overworld is generated by randomly choosing n spots across the map, where n is a random number inside a certain set of bounds, and is chosen as the first thing after the map seed is set. These represent seeds of random terrain features called regions(mountain, lake, plain, forest, desert, swamp, volcano) which are chosen using weights to create an acceptable distribution. (E.g. less volcanoes, more plains) All the map cells are assigned to a region using a voronoi diagram approach.

At this point, I generate the dungeon seeds for all mountain ranges and volcanoes, which are placed in the geometric center of the region. This includes how deep they go and difficulty of the dungeon (chosen based on the starting location of the player), any special rewards, and the seeds for each level. I also generate city seeds for all the regions that were determined to be "bountiful" enough to support a city/town population.

Because I have the ability to generate the level from a seed number, I can easily store level deltas... changed doors, smashed walls... etc. while maintaining a smaller memory footprint. Items, traps and monsters are spawned outside of the seed rng (and consequently have to be saved as additional info about the level), but could easily be worked into the process if you wanted the monsters and items to be the exact same each time you chose a specific level seed. (which I chose not to do)

This allows the ability to play in a familiar world when using the same seed, but make sure that a player can't gain a substantial bonus through brute-forcing the locations of desirable items or artifacts. Anyways, that is the balance that I decided was fair for my game. It will be different for everyone.

I would also like to mention how useful this feature is while developing. I can just manually set the world seed, which allows me to test in the same environment every time... If I encounter an error with map generation, I know exactly how to reproduce it, and i don't have to generate any previous maps before I can get the RNG back into the state that generated the troubled map.
My projects - http://exilania.com/landing/   |  Minotaur vs orcs -  http://exilania.com/minotaur/ |  Strife  -  http://exilania.com/strife/

abraksil

  • Priest
  • **
  • Posts: 83
    • View Profile
    • Email
Because I have the ability to generate the level from a seed number, I can easily store level deltas...

I like it! It's smart and elegant :)

jere

  • Bishop
  • ***
  • Posts: 224
    • View Profile
    • Email
I ran into the same problem on my 7drl, The Only Shadow That the Desert Knows.

The world map has 1200 sectors (40x30) and each sector has 1200 floor tiles. I wanted the results to be deterministic, but still generate floors on the fly. So the solution I came up with was to, at game start, store a random number for each tile (1.4million in total), which doesn't take too long. Then later I can use the that random number as a seed to get the RNG ready for tile generation, which is the expensive part.

Also, because my game features time travel I save the RNG state on every turn. And because I don't want combat rolls to have a butterfly effect on generation I maintain separate RNGs for generation and everything else. Sounds like a convergent solution to what other people have mentioned.
Golden Krone Hotel -- available on Steam Early Access now

Lord_Mork

  • Acolyte
  • *
  • Posts: 42
    • View Profile
Generating all at once is probably easier to program, check, and debug. But it has disadvantages, in that it will be harder to change the level "on the fly".

If a player sets off some kind of unknown trap in one area of a level, you can add in a slight chance for the player to then walk into a room with a collapsed ceiling, lava floor, etc, later on as a consequence. This is easier to do if you generate piece by piece as the player explores, using percent chances to determine what sort of "piece" comes next.

So I believe it is better and possibly more fun not to generate an entire level at once, but I might be coming at it in a rather narrow-minded fashion.

Untrustedlife

  • Bishop
  • ***
  • Posts: 119
    • View Profile
    • My Blog
    • Email
Re: Considering when to generate random map details, all at once or as needed?
« Reply #13 on: September 17, 2016, 09:24:54 PM »
My game currently generates creatures items and such for the next 3 floors  so that it can hint at them in the floor (skeletons of creatures, etc) through 'books' and such.

It doesnt generate the actual floor until you get there, but it generates the detail 3 floors in advance.I find it works pretty well.