Procedural Level Generation Bug

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.



While I attempted to gather information and replicate this issue, I tried to understand what might have happened.

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.

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.

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.

I knew that the wall hadn't become flipped, because it still connected properly to the manually placed walls in the entrance room. However the interior of the Cemetery map had somehow become exposed to the edge of the area and been turned unwalkable. But how?

This is what the Cemetery map usually looks like:



And indeed my initial attempts to replicate it all looked like that. During the investigation of this issue, another instance of this bug occurring was shared in the community.

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 level had generated inside-out. This shouldn't be able to happen, but an examination of the generation graph yielded some insight:



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.

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.

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.

Thanks to the rest of the team who helped to solve this issue, and to the players who reported it in the first place!

"

Pyromancer4 wrote:

Is the boss room always generated at the exact same spot on the map?
Also now i'm wondering how the minimap works, since you would normally be able to see the boss room (or at least the void around it). Brb, launchin PoE in triple screen :D

Learning about this is amazing, thank you so much for sharing!

There are several Cemetery graphs that the area generates from, this was just the one that we managed to reproduce the bug on. On this graph yes, it's always there.

As to whether or not the boss room is visible...