A generated map with sparse elements: entries, exits, fountains, chests, keys, pressure plates and locked doors.

So far, we've generated the layout, which is a 2D array of bitmasks, where each tile stores a variety of useful information, e.g. if it's floor or not, if it has liquid, if it's a door, etc. This information is stored densely, as we always need to have such information about every tile.

In the next stage, we need to place things that appear sparsely on the level:

  • Level transitions (map border to exit wilderness, stairs)
  • Interactive objects: treasure chests, fountains, etc.
  • Puzzles and traps: this is a generalized group of a number of locations that have a relationship with each other, such as:
    • Locked door and key (1 tile + 1 tile)
    • Locked door and one or more pressure plates (1 tile + N tiles)
    • Pressure plate and dart trap (1 tile + 1 tile)
    • Pit trap (1 tile)
    • Secret bridge activated by pressure plate (1 tile + N tiles)

We run this sparse generator independently per generator area, so that when placing things, we know that the locations underneath are part of a common theme; for example complex dungeon-specific traps would only be placed in a "dungeon" generator area, rather than a cavernous area or a forest.

In order to place a generic "thing" on a map tile, we pick from a list of candidates, that all fulfill certain criteria. The code does exactly this: Each sparse element specifies a number of criteria, and then we process the map, gather candidates that fulfill those criteria and pick a random one. We repeat the process as many times as needed, re-calculating the criteria each time, as for example we might not want to place 2 fountains next to each other, so after every fountain is placed, we need to regenerate the candidate tiles. This process is repeated for everything below. Some always-on criteria are:

  • Tile must be floor/non-obstacle
  • Must match current generator id
  • No other sparse element on the tile, unless it allows overlapping

Part 1: In and Out

The first and most essential elements to place are the entries and exits to the level, as nothing should block any path. For outdoors maps, which are typically the outermost, encompassing generator (color-coded red here for example), we use all the floor tiles on the border that are not in liquid. Example of this is in the first image of this post, at the borders.

Depending on the map specification, we place zero or more exits (stairs up or down, gateways, anything) at particular generators. For the example that I'm using, I set "generate 3 exits in the innermost generator area" (color-coded blue)

Level entry/exit criteria:

  • On map border (for entries only)
  • Not in a tile with any type of liquid
  • Not on a door tile

After we generate the entries and exits, we calculate all paths from all entries to all exits (using dijkstra maps). We mark tiles on those paths and make the combined "hot path", so we won't accidentally create unsolvable levels (e.g. locking a door that lies in a path and placing the key behind it)

Part 2: Single-tile elements: Locks, keys, chests, fountains, etc

Each of these has their own criteria. Keeping things simple, here's how it stands now:

Fountain criteria:

  • Not next to a wall (looking at 8-neighbourhood)
  • Not in any liquid
  • Not within a distance of 15 (euclidean) to another fountain
  • Not blocking passage (e.g. would not be placed in a single-tile-wide corridor)

Chest criteria:

  • Next to a wall (looking at 4-neighbourhood )
  • Not in any liquid
  • Not blocking passage (e.g. would not be placed in a single-tile-wide corridor)

Lockable door criteria:

  • Door tile that is an edge to the dungeon graph that leads to a leaf node (effectively, provides access to a single room) and is not part of the "hot path" (so we won't lock a room with stairs)

Key criteria:

  • Not in any liquid
  • Not on a door tile
  • Not in the room that is locked
  • Not in the room next to the locked room ("Here's the key, and here's the door, congrats")

Pressure plate criteria:

  • All "key criteria"
  • Within a distance of 15 (euclidean) to the associated mechanism (e.g. locked door)

The results of the above can be seen in the top image. The blue-laced doors are the locked doors with keys, and the green door is the door linked to the pressure plates (the grey-looking things).

We are not generating entities here, but just linking requests "generate some locked doors and keys for me according to these criteria" to results (a list of locations), as it's up to later systems to materialize the entities.

Auto-explore and combining Dijkstra maps

The obvious thing to do after generating a map is to test it. And, what's a better test than auto-explore? So, after adding quickly the recursive shadowcasting algorithm for fov, we create a very basic autoexplore bot:

The bot originally used the logic from here, where we mark all invisible tiles as goals. I did not like that for a few reasons:

  • Goals are invisible, so we can't modify the weights with any intelligent and fair reasoning, as we don't know what the tile is. For example, if I want to prioritize unexplored tiles of a different generator fairly, I can't do that as I don't know the generator id of the unknown goal tile.
  • For a large map, the number of goals starts as ludicrously high, which costs a lot of performance (and can cost memory as well). Gathering all the invisible tiles and setting them as goals in the dijkstra map could require tens of thousands of tiles.
  • We can't necessarily go to the invisible tiles, so intuitively it does not make perfect sense

Alternative algorithm: Goals are visible floor tiles that are next to invisible tiles. This guarantees that the set of goals is never too large (unless the map is very, very weird) and is perfectly intuitive as you want to set as a goal a tile that you can go to and it's next to area that you haven't explored yet. Here's some C# code that conditionally adds a tile into a list of goals for the dijkstra map:

if (visibilityMap[tile] != 0 && !autoExploreFullyVisibleTiles[tile])
{
    if(layout[tile].IsFloor == 1u)
    {
        bool hasNbUnknown = false;
        foreach (var nb2 in math.Shape.Nb8)
        {
            var pnb = nb2 + tile;
            if (visibilityMap.InBounds(pnb) && visibilityMap[pnb] == 0)
            {
                autoExploreActiveBorder.Add(tile);
                hasNbUnknown = true;
                break;
            }
        }
        if (!hasNbUnknown)
            autoExploreFullyVisibleTiles.Set(tile, true);
    }
}

This is run every time we move, and the dijkstra map is re-calculated if any change happens in the list of goals (autoExploreActiveBorder). So far so good, we have a working auto-explore.

Prioritizing areas

Say we want to find the temple of doom, deep within the caves of misery, in the woods of dismay. If we start at the woods and we find the entrance to the caves, and time is ticking, we don't really want to explore the woods anymore. So, how do we do that without a hack? Easy, by modifying goal weights! Our starting generator is say 0, and our goal is "the further the better", so higher generator ids are better. We can set custom goal weights for the dijkstra map, so our goal tiles in the previous area get varying weights: higher generators get a priority boost. This priority boost is applied to all goals of all dijkstra maps, so for example chests in more important areas are more important than chests in less important areas. Now, as you can imagine, the bot prefers to go deeper, where it will find the exit from this level, which is deep into the temple of doom.

Multiple dijkstra maps

Dijkstra maps are like tapas, they are great for sharing. We can make a dijkstra map for the level exits that can be used by any adventurer that comes to the level and tries to find the exit. This is part of the reason that we might needs several dijkstra maps, for example one for the auto-explore, one for the treasures (a sentry entity might want to collect treasure but patrol instead of explore), etc. So question becomes: how to combine the maps? After a lot of experimentation and failures to combine the maps by summing or multiplying them, I ended up with the following solution:

def combined_dijkstra( currentLocation, dijkstra_maps):
    bestCost = infinity
    bestLocation = currentLocation
    for dijkstra_map,desire_strength in dijkstra_maps:
        (new_location, cost_to_new_location) = get_lowest_cost_neighbour(dijkstra_map, currentLocation)
        cost_to_new_location = cost_to_new_location / desire_strength
        if cost_to_new_location < bestCost && new_location != currentLocation:
            bestLocation = new_location;
            bestCost = cost_to_new_location;
    return best_location

So effectively we sample all maps independently for the best candidate, and choose the lowest scoring one, after weighing them based on a "desire" factor (e.g. autoexplore is more important than treasure collecting)

This works like a charm, and causes no oscillations. So now we have a bot that can collect treasure while exploring, with the ultimate goal to find the stairs. For this, we have 3 dijkstra maps and their corresponding desires:

  • Explore. All visible tiles next to invisible ones. Weight: 1.0
  • Treasure. All known tiles containing treasure. Weight: 100.0
  • Stairs. All known exits from the level. Weight: 1000.0

Demo time! Here's a video that shows the bot playing the same level, starting from different entry points:

You might notice the greediness of the bot, as it knows it looks for cavern and temple, but it sees some juicy chests outside, goes and picks them up, and heads back in :)