[2020] Dan_GGG explains the mystery behind square Cemetary Maps and insights into procedural level generation

Originally posted by Sargon16

Hmm, yes, I understood a few of those big words. Explain like I'm stupid please?

Originally posted by Tyler_Zoro

/u/Dan_GGG's shorter explanation is certainly clearer to the non-programmer, but let me try to translate the original in whole, as it might be interesting.

Procedural level generation sometimes yields some rather strange bugs, and recently there's been none stranger than one that causes the majority of a Cemetery map to be completely unwalkable. We've applied a fix for this internally and found the issue relatively interesting so wanted to share this insight with you.

"Unwalkable," here, means that it's an area where the player can't go or move, like the water along the shore in Twilight Strand: you can only go so far and then the game won't let you wade any deeper into the ocean. That's because the ocean is marked as "unwalkable" on the map.

We have two ways to generate levels, which we refer to as "indoor" and "outdoor" generation. In an indoor area such as The Prison, or The Crypt, we build the level room-by-room. Cemetery uses outdoor generation, which is a lot more flexible because it constructs the level tile-by-tile. The issue was almost certainly outdoor generation related, because it's a lot less predictable.

We usually say, "map" or "zone" but the generic term in the industry is "level". A level is any area of game world that you can move around.

"Generating levels" in PoE is a process of what's called "procedural generation". This means that there are some basic rules (like "water needs to go along one edge and rocks along another, with a start point at one end and a boss and exit at the other"). But from there, mostly everything else is randomly put together from building blocks like a lego set when you ask to go into a zone (e.g. be creating a character and logging in for the first time).

He also used the word "tile" here. A tile is pretty much exactly like a tile in a bathroom or kitchen. It is square and has a certain pattern (like a tile of beach or a tile of water). These are the smallest unit of the map that the game manages, laying them out to form a zone map.

Outdoor areas are defined by tile edges. We place a series of nodes, then draw connections between them that are marked as belonging to a certain edge type. The generator then places a sequence of tiles between them that connect via that edge. That's what the outer wall of the Cemetery map is. The edge between the walkable interior and the unwalkable exterior.

Okay, lots of jargon, here. First, let's take, "We place a series of nodes". Really this just means marking points of interest on the blank level map (like "you start here" and "Hillock and the exit go here.") You're not laying out tiles yet, so there's nothing the user is going to see, but these nodes give you an outline to start from.

So in Cemetery, the nodes were things like a start point and an exit to the boss arena, but there are multiple places that each can show up. It lays down the potential start and exit points on the map, then draws a line between them all (all potential start and exit points) making a big loop that outlines the basic shape that the map will eventually take. Inside the loop will be the tiles you can move around on and outside are those "unwalkable" tiles we talked about before.

This exterior wall edge is defined as having walkable ground on one side and unwalkable ground on the other, but in Cemetery, that's not actually necessary. Any ground type that goes off the edge of an area is automatically flagged as unwalkable.

Which he then re-stated more clearly, there.

This time we were ready - I enlisted the Quality Assurance team to identify the instance in which this had happened, and they were able to get me a seed that finally showed the issue:

The word "seed" here might be confusing. What this means is clear with an example. Let's say that the way I generate "random" numbers is to use the digits of pi. But the reason that they look random to an observer is that you can give me a big number to start, and I'll give you the digits of pi from there on. So you give me 2 and I give you back 415... but if you give me zero, I give you 314.... Makes sense, right? Now let's say that each time my level generation needed a new random number it asked me for one and I gave it the next digit of pi. As long as the starting point was different, the map would end up looking very different.

This is kind of what happens. That initial number is called a "seed" and instead of digits of pi, the system uses a "pseudo-random number generator," but you can just think of it as the digits of pie for simplicity.

If you give the system the same seed again, it will give you back the same map. So the QA team didn't need to give him a big, bulky data file with the content of the finished map. They just had to give him one number and he could re-create the map himself!

The level had generated inside-out. This shouldn't be able to happen, but an examination of the generation graph yielded some insight:

By "inside out" he means that the starting point and the entrance to the boss arena were both in the "unwalkable" part of the map, not in the walkable part where they should have been.

The "graph generation" is that process of putting down potential points of interest and connecting them with lines.

The grey line of the exterior wall connects to three nodes marked entrance, and three marked exit - these are all potential locations that those rooms can spawn in. Somehow, this big open loop had decided it would prefer to snake its way around behind the entrance room instead.

He's saying "room," here, but you don't think of those as "rooms" they're just outdoor areas like the rest of the zone. What he really means by room is a pre-generated block (notice that the entrance area always looks the same?) that gets put into the map on one of those points we talked about.

So the rest makes sense, the walls around the walkable area were, for some reason, snaking around outside of where those start and exit points were being laid down.

We theorized that because the only proper nodes were semi-optional features, they were being dropped when the features didn't generate there, causing our big wide loop to snap inwards like a rubber band.

It's a bit confusing the way he says this, but what I get out of it is that the programmers were thinking of the map layout in terms of ALL of the potential places where the entrance/exit could have gone, but once the system chose a start and entrance to the arena, it threw away all the other points of interest and then the map had nothing to work with. It's still not clear to me why it didn't enclose the points that it DID choose, but you see the basic problem: when the map involved very few points of interest, there was no good way to draw it.

So:

We were then able to fix the problem by changing the two blue x-shaped pseudo-nodes that you see in the above graph into full nodes that were guaranteed to be present regardless of which entrance and exit location was picked. This ensures that the wall is always drawn downwards instead of upwards, as well as keeping the map's size more consistent.

The blue is REALLY hard to see in the picture, but basically, they made sure there were points that would always show up and always make the walkable map area a big, open place.