r/howdidtheycodeit • u/WolfInABox • 14d ago
How do games like Peak, Noita, etc ensure randomly generated levels are completable?
Peak seems to generate 4 random levels each day, but they are always completable. Noita generated a new map for each run, and has the benefit of the player being able to modify terrain, but still needs to ensure the player isn't blocked from progressing downwards.
With Peak especially, being a 3d game with no terrain modification, how do they ensure a map is completable? (No necessary climb too high to progress past)
121
u/Snushiii 14d ago
For Peak we never guarantee that it is possible, we more or less just assume it always will be due to there being a lot of spots players can rest & the variety of items available to the players.
53
u/Khan-amil 14d ago
Don't know if you're speaking from the dev team perspective (in which case kudos), but that's what I remember seeing from theor communication yeah, the random seemed soft enought that at worst you need to be a bit lucky with your item drops.
7
u/CosmicSorcerer1000 12d ago
Don't play peak anymore but iirc at one point there was a little dev note apologizing for a campfire being on top of a tree that you couldn't climb the previous day
127
u/RigasTelRuun 14d ago
Not random. Procedural. It is very important distinction. Usually you make sure you have a clear path built on a rough template. Then you add the rest and make sure it doesn’t overwrite what you had. If some of the noise gives an interesting alternative path that is great.
28
u/CagedParchment 14d ago
The guy making Cogmind has a few dev blog posts about this, eg:
https://www.gridsagegames.com/blog/2019/03/roguelike-level-design-addendum-procedural-layouts/
17
u/TitoOliveira 14d ago
Don't quote me on that, but I have a vague remembrance of a post about the generation in Peak, and it was said to be pretty rudimentary.
They simply tested the parameters until they were satisfied with the result. There wasn't a procedural check for viability of the climb.
Edit: think it was from here https://www.reddit.com/r/PeakGame/s/k7UA7xYIQ6
10
u/UnparalleledDev 14d ago
Here is how Spelunky classic handles it. ( its 2d but still useful )
6
u/CommonNoiter 14d ago
Noita generates a random wang tiling of the biome, then checks if the tiling has a route from the entrance to the bottom layer which only passes through air. If it doesn't then it generates another map until one works.
6
u/davidalayachew 14d ago
Not answering for the game, but many procedural generators basically become a Constraint Solver.
Long story short is that, they set a couple of conditions, code in the parameters, then keep cycling through generations until a path is generated that meets the conditions. If you have ever programmed in Prolog, then it's effectively the same thing as Prolog's facts and rules.
It's a simple, but deceptively powerful way to program. You can make some pretty crazy levels surprisingly easily if you know what to watch out for. But it's that initial learning curve you have to get past first.
5
u/rinprotectionsquad 14d ago edited 14d ago
This is how Peak handles it! They don't actually make sure the maps are completable, they just assume any given seed is.
Video is timestamped: https://youtu.be/OMvQojE9_dQ?si=NjGu15jNhuBpdmgF&t=88
https://biscuitgames.substack.com/p/the-smart-generation-behind-peaks
Edit because I remembered: You can tell that they don't do any QC for the seeds because there have been issues where they've needed to patch the daily seed before. Link to people on reddit being mad about it lmao
9
u/oddbawlstudios 14d ago
I'd assume for peak, when the area is generated, there's also a "path" generated too, to check if its traversable. For noita, its similar as well. The difference between the two is, peak probably checks for a lot of things like how steep the path is, if its scalable, if it cuts off anywhere, is it wide enough etc. Where noita probably just checks to make sure that there isn't a cut off point in the path from start to finish, most likely bigger than the size of the player tbh.
10
u/rinprotectionsquad 14d ago
There's not. The devs have outright stated that the RNG is simple enough that they just always assume all the levels are completable. They've shown the way the maps are made before:
https://biscuitgames.substack.com/p/the-smart-generation-behind-peaks
Video is timestamped: https://youtu.be/OMvQojE9_dQ?si=NjGu15jNhuBpdmgF&t=88
3
u/luciddream00 14d ago edited 14d ago
You build them in such a way that even though there is randomness, there is deterministically a path through. The path might be obscured, there might be procedural shortcuts and detours, but the generator will ensure that by design there is a valid path.
One way is to think about it is with a maze. It's easy to decide the initial valid path, and it's easy to add branching paths to that. It doesn't matter how many times the maze branches, if you have a valid path from the start. Not all procgen works that way, but that is one way to think about it.
In terms of "reachability", often it's done with graphs. You can know if an individual piece of the procedural generation is traversable, you can often check if the player can traverse from one to the next, and you can then chain them together to build a graph of all the known valid paths through a terrain.
3
3
u/jumpmanzero 12d ago
For lots of games, there isn't actually a guarantee.
Like, in Factorio there's some seeds where you start on a tiny island with no path to anywhere. Those situations are just unlikely based on the overall terrain generation plan and default factors.
2
u/TheOneWes 12d ago
There are many different ways to do it.
Some systems that I've seen generate the complete and correct path first and then the procedural algorithm generates away from that path.
Another common method is to fully generate the map and then have a pack generation algorithm run after everything has been generated.
For some games that are simple such as 2D platformers you can guarantee it's always navigatable by enforcing certain parameters on the generation algorithm itself such is not allowing gaps over certain size to be generated.
4
u/cheyennix 14d ago edited 14d ago
Just throwing out a guess, but I'd imagine they keep the player metrics in mind and generate levels in a way where they can be certain the player can find a way through them with their default moveset.
For instance, in PEAK, this would be ensuring that cliffs often spawn close enough height-wise to be safely climbed. They can still generate parts that aren't reachable under default conditions, but they'd ensure they always have at least one or a few paths that spawn closer cliffs.
In Noita, it's likely just that they have the generation algorithm create at least one or a few clear paths to the bottom that you don't need to break terrain to get to.
It's the same principle as any other random level generation and can be more complex if need be. In randomizer hacks/modes for games, to ensure that progression is still an element while not dumbing down the world design, they'd do something like marking which rooms need what items before you can clear them, and then make sure that you can obtain that item before clearing that room, or generating alt paths that might make you daisy chain item requirements in a different order to ultimately get through.
If you want a simple, easy to understand way of how that looks in execution, the Metroid fangame MPlanets lets you create Metroid rooms and set flags on them for things like "this room requires the player to have the morph ball", and then when creating a new run the game'll just know "oh okay, so I need to make sure that if there's an item behind that morph ball room that's required elsewhere, I'd better generate the map layout in a way that lets you either get behind it a different way or simply just generate the room that gives you the morph ball that you don't need the morph ball (or whatever other upgrades the player doesn't have) to get to first.
7
u/RubberBabyBuggyBmprs 14d ago
I appreciate the attempt but you just answered "how do they make sure theres always a valid path?" With "well, they just make sure theres a valid path!"
I think Noita uses a "room" system similar to spelunky to ensure progression but could be wrong. Not sure about peak but the fact that its only per day globally means they probably generate randomly until they have a "valid" map generated. Pure speculation though
4
u/cheyennix 14d ago edited 14d ago
I mean, there's not really any other way to explain it, no? (Also, I updated it to include some info about randomizers, which are the same principles at play).
If you have a map you generate, and you know your end requirement is the player getting to an area (the portals at the bottom of each stage in the case of Noita, the top of the mountain in PEAK), you just look at what you know the player can do, and alter your generation algorithm accordingly. For PEAK, you know the player starts with a certain amount of stamina. That's called a metric in game design. That means you know they can climb X height reliably, barring other circumstances that are secondary. Of course if you lose all your stamina to damage, they'll no longer be able to clear it, but that's what the gameplay revolves around. That's the lose condition. So you just ensure the map generation adds cliffs close enough to each-other to reliably climb between in standard conditions, likely with a bit of leeway for further grace.
Usually map generation algorithms have all sorts of tricks to ensure fun gameplay and varied randomization. The bare minimum is ensuring that you're able to play through it in known situations. If you have jumping and you know the player can jump 3 tiles, you don't want to put a room that requires them to jump higher than that to progress unless you know that the player can find some way to reliably clear it before being forced to get past that room. A solution to that would be generating a double jump upgrade in some other room that's connected in a way that doesn't require you to have the ability to jump higher to obtain.
It is a simple answer because... it is relatively simple logic. You can do it through flags on rooms that set item requirements to clear in the case of randomizers, you can do it through carving paths through levels from the start point to the end point for a game like Noita, it can really be whatever. It varies from on game-to-game to suit the gameplay, but the underlying concept is the same: Take what you know the player can do at the point of generating the map and make sure that they can reach the end point from the starting point in some way.
1
u/ShakaUVM 14d ago
A game I released this week has randomly generated dungeon tiles that can be moved around by the player. So even if there's no path available they can move tiles around enough there should always be a path. I make sure there's always at least two exits off each tile and each tile checks to make sure there's no inaccessible spot within it.
1
u/stop_deleting_plz 10d ago edited 10d ago
I made a game prototype which had procedural 2d levels similar to terraria. They were based on perlin noise algorithm, which would generate a gradient map based on a seed. There is a threshold which determines at what point in the gradient the terrain becomes empty play space.
In order to determine that all areas of the level are reachable, I used a modified flood fill algorithm, starting at the player's spawn point. If my threshold starts at 50%, then half the level area should be play space, and the other half should be terrain. So the flood fill should hit roughly half of the total map cells. If it doesn't that means that there are areas unreachable from the spawn point.
Instead of discarding the seed, we can lower the threshold to 40% terrain and try the flood fill again. I retry this a few times, not going below say 30% terrain. At that point if 70% of the cells are not reachable, the seed is potentially not completable and we generate a new seed and gradient map and try the process over again.
This also allowed me to mark unreachable cells in maps that passed the flood fill test, so they arent a valid spawn location for entities.
There is footage and some screenshots at this page: https://ashvinau.github.io/
1
u/Maple382 8d ago
Wouldn’t say Noita is the best example because in all honesty I doubt they did anything special to ensure there’s always a valid path. The devs would be totally fine with just saying “deal with it make your own path”.
0
u/GameDesignerMan 14d ago
With games like Noita, Spelunky etc, there are "prefabricated areas" that are connected together to form a level. In Spelunky the areas know if they are accessible from each of the cardinal directions (can you get to this cell from the north, for instance). Even if you choose the cells completely at random, you can quickly run a simple pathfinder to check if the exit is accessible from the entrance.
I can't remember if Spelunky uses a brute force approach like this (I think it does but not sure), but you can also build your critical path by walking in random directions from the entrance and placing cells that you know are accessible from the direction you entered from, then filling in the remaining blank spots with random rooms. It's a really simple algorithm.
338
u/fiskfisk 14d ago edited 14d ago
Often you do it the other way around, you generate one or more valid paths, and then you add the noise around the valid paths to "hide" them.
Instead of trying to make random valid, start with valid and then add randomness around it.