I've talked about dungeon generation in the past, specifically an algorithm that I've used in a few places. That same algorithm is at work in my roguelike which I've been calling "Explore". Since I've already covered exactly how that algorithm works, I'm going to cover a slightly different aspect of dungeon generation in this post.

One part of procedural generation that tends to be overlooked, or at least is less well documented, is actually placing items and enemies inside a level after you've already generated the layout. This placement might seem relatively simple compared to level layout generation, but I think it's important enough to talk about.

The reason I see it as being important is that coming up with a simple way to define what should be in a dungeon isn't easy. In a game like NetHack, which has numerous different levels (using a number of different kinds of level layouts and even predefined levels in some cases) there has to be a better way to define each level than hardcoding it. NetHack does, indeed, have some tools to build predefined map layouts and mazes.

For Explore, I want to have a way to both define what generation algorithm is going to be used for each level, and also what entities will spawn (and where).

A scripting system

I've built a fairly simple scripting system to solve this problem. I say scripting system, but I didn't develop a custom scripting language or anything (as much fun as I've had doing that in the past) - I turned to XML. As much as I'll probably be burned at the stake for saying so, I actually (sometimes) appreciate the structured format of XML as verbose as it is. C# and .Net also have great support for it, so it seems like a reasonable choice.

The system that I've come up with involves two major parts - a world definition and a set of level definitions. The world definition contains a list of level definitions and when to use each of them - it tells the game "use this set of generation parameters when the player is this far into the dungeon."

The world definition file is incredibly simple, so I'm actually going to skip over it for now. It does contain one extra feature (classname aliases) but we'll come back to that later.

Level Definitions

Level definitions contain a list of steps to execute when generating levels. These steps are generally one of two types - a generator or a spawner.

Generators create the actual layout of the level. This is what my previous dungeon generation post was about. A generator step contains the name of the class that will do the generating and any configuration options to go with it. Here's what a generator step looks like:

<generate class="@G.ConnectedDungeon" />

This defines a generator step to run with no parameters and the @G.ConnectedDungeon class. What does the @ mean? It's an alias - in the world definition there's a list of aliases and this one will be replaced with the full class path to the ConnectedDungeon class. ConnectedDungeon happens to be the class which implements the algorithm I've talked about previously.

In general, there will only ever be a single generator step. This isn't a restriction (it's certainly possible to have multiple generators in a single level) - i just haven't found a use for it yet. Maybe in the future I'll have a reason to use multiple generators.

The result of that single generator step is the following level (well, a level like this since it's random):

The level has floors and walls! Except, there's nothing in any of the rooms. That's why we have spawner steps. Here's the spawner step to setup the player's spawning location:

<spawn class="@T.PlayerSpawn" name="PlayerSpawn">
    <filter class="@F.Region" mode="center" tags="spawn" />
</spawn>

A bit more to take in this time. Spawners are setup to spawn entities based on a template class. This spawner is setup to spawn entities based on the template @T.PlayerSpawn, which again is an alias to the actual class name. The spawner will also name all entities it spawns PlayerSpawn (entity names do not have to be unique).

The hard part of placing entities in a dungeon is knowing where to place them. Set positions won't work since levels are random every time. My answer to this problem is the idea of filters. Each spawner can have any number of filters where each filter is meant to narrow down the possible positions for entities to spawn. Once the last filter has run, then all remaining positions will have an entity spawned. Additionally, the first filter in a spawner will generally sample the entire level (though this depends on the filter itself).

Now, before I describe what the @F.Region filter does, I need to quickly explain one aspect of level generators. In addition to creating the level itself (which is made up of "tiles" on a grid), generators can also define "regions" in the level and tag those regions for specific purposes. In the case of the @G.ConnectedDungeon generator, it outputs a region for each major room and tags rooms for where the player is supposed to spawn and also for the exit of the level.

Back to filters. The @F.Region filter, depending on the mode, will either allow positions that are inside regions to pass through the filter, or only allow the center position of regions to pass through. In this case, we are matching only the center of regions tagged with "spawn" (of which there is only one). Since this is also the last filter, we know that @T.PlayerSpawn will spawn in one place - the center of the "spawn" region.

Spawning Zombies

Here's a more complex spawner.

<spawn class="@T.Zombie">
    <filter class="@F.Region" chance="0.5" tags="main" />
    <filter class="@F.Walkable" />
    <filter class="@F.SelectInRegion" min="1" max="8" tags="main" />
</spawn>

This spawns zombie enemies - entities of the template @T.Zombie. Here's a breakdown of what each filter does:

• @F.Region - Selects all positions in regions. In this case, we select all "main" regions with a chance of 50%. As such, about 50% of all major rooms should have some amount of zombies in them.
• @F.Walkable - Gets rid of all positions that have something blocking the space. This could be another entity or just a wall.
• @F.SelectInRegion - For each region in the level tagged with "main", we select between 1 and 8 positions that we have filtered already. Effectively, this selects up to 8 random positions per room to spawn a zombie.

Giving the player a bed

For testing purposes, I have a bed appear next to the player's spawn. This is the spawner used to do that:

<spawn class="@T.Object">
    <arg type="tile" tileset="@TS.Overworld" id="Object_Bed" />
    
    <filter class="@F.Entity" name="PlayerSpawn" />
    <filter class="@F.Shift" y="-1" />
</spawn>

This spawner creates entities based on the template @T.Object. This is a fairly generic entity template, which includes nothing but a transform (position), sprite, and a collider.

This spawner shows off passing arguments to an entity template. Here, we're passing an argument that says what sprite the object should use (the Object_Bed sprite from the @TS.Overworld tileset).

Here's what the filters do:

• @F.Entity - Selects the positions of the specified entities. In this case, we get the position of the entity named "PlayerSpawn".
• @F.Shift - Shifts all positions in a specified direction. Here, we shift up one so that the bed appears one tile above the player's spawn.

Conclusion

Here's the full level definition file that I currently use for testing. It's pretty simple, and will have much more added to in the future.

<level>
  <steps>
    <generate class="@G.ConnectedDungeon" />
    
    <spawn class="@T.PlayerSpawn" name="PlayerSpawn">
      <filter class="@F.Region" mode="center" tags="spawn" />
    </spawn>

    <spawn class="@T.Object">
      <arg type="tile" tileset="@TS.Overworld" id="Object_Bed" />

      <filter class="@F.Entity" name="PlayerSpawn" />
      <filter class="@F.Shift" y="-1" />
    </spawn>
    
    <spawn class="@T.StairsDown">
      <filter class="@F.Region" mode="center" tags="exit" />
    </spawn>
    
    <spawn class="@T.Door">
      <filter class="@F.Door" />
    </spawn>
    
    <spawn class="@T.Zombie">
      <filter class="@F.Region" chance="0.5" tags="main" />
      <filter class="@F.Walkable" />
      <filter class="@F.SelectInRegion" min="1" max="8" />
    </spawn>
  </steps>
</level>

The only filter type here that I haven't mentioned is the @F.Door filter, which is somewhat special in that it's not meant to be reusable. It just finds all positions where there should be a door.

That's about it for level definitions. Not sure what I'll be writing about next time, but for now I'll leave with an image of the spawn room (don't mind the chair - that's hardcoded for testing purposes):