Distributing mobs in a dungeon based on player’s level (or some dungeon level difficulty factor) was somewhat straightforward, but I would still like to document the progress. I needed to place a mob that’s somewhat within the difficulty level I want, plus minus a few difficulty levels to spice it up.

Above you can see three rats, three cats, a dog (r, c, d, all level 1), a farmer (f, level 2), and a lonely bandit (b, level 3) in a level 1 dungeon.

Without going straight into measure theory, I generated intervals for each mob based on the diff of desired level and their level, and then randomly selected a point within the boundaries. Here’s the abstract code:

import bisect
import random


def get_random_element(data, target, chance):
    """Get random element from data set skewing towards target.

    Args:
        data   -- A dictionary with keys as elements and values as weights.
                  Duplicates are allowed.
        target -- Target weight, results will be skewed towards target
                  weight.
        chance -- A float 0..1, a factor by which chance of picking adjacent
                  elements decreases (i.e, with chance 0 we will always
                  select target element, with chance 0.5 probability of
                  selecting elements adjacent to target are halved with each
                  step).

    Returns:
        A random key from data with distribution respective of the target
        weight.
    """
    intervals = []  # We insert in order, no overlaps.
    next_i = 0
    for element, v in data.iteritems():
        d = max(target, v) - min(target, v)
        size = 100
        while d > 0:  # Decrease chunk size for each step of `d`.
            size *= chance
            d -= 1
        if size == 0:
            continue
        size = int(size)
        intervals.append((next_i, next_i + size, element))
        next_i += size + 1
    fst, _, _ = zip(*intervals)
    rnd = random.randint(0, next_i - 1)
    idx = bisect.bisect(fst, rnd)  # This part is O(log n).
    return intervals[idx - 1][2]

Now, if I test the above for, say, a 1000000 iterations, with a chance of 0.5 (halving probability of selecting adjacent elements with each step), and 2 as a target, here’s the distribution I end up with:

target, chance, iterations = 2, 0.5, 1000000

data = collections.OrderedDict([  # Ordered to make histogram prettier.
    ('A', 0), ('B-0', 1), ('B-1', 1), ('C', 2), ('D', 3), ('E', 4),
    ('F', 5), ('G', 6), ('H', 7), ('I', 8), ('J', 9),
])

res = collections.OrderedDict([(k, 0) for k, _ in data.iteritems()])

# This is just a test, so there's no need to optimize this for now.
for _ in xrange(iterations):
    res[get_random_element(data, target, chance)] += 1

pyplot.bar(
    range(len(res)), res.values(), width=0.7, align='center', color='green')
pyplot.xticks(range(len(res)), res.keys())
pyplot.title(
    'iterations={}, target={}, chance={}'.format(
        iterations, target, chance))
pyplot.show()

You can see elements B-0 and B-1 having roughly the same distribution, since they have the same weight.

Now, if I decrease the chance, likelihood of target being selected increases, while likelihood of surrounding elements being selected decreases:

I works the opposite way as well, increasing the chance decreases likelihood of the target being selected and increases the probability for surrounding elements.

For the sake of completeness, it works with 0 chance of surrounding elements being picked:

And an equal chance of picking surrounding elements:

After playing around with the configuration in Jupyter Notebook, I cleaned up the algorithm above and included it into mob placement routine.

After generating a few good looking random dungeons, I was puzzled with randomly placing mobs on resulting maps. To make it fair (and fun) for the player mobs should be evenly distributed.

The obvious idea was to pick coordinates randomly within the rectangular map boundaries, and then place mobs if they have floor underneath them. But this way I lose control of the number of mobs and risk having a chance of not placing any mobs at all. Plus, dungeons with bigger surface area would get more mobs - which sounds somewhat realistic, but not entirely what I was aiming for.

I could improve on the above by rerunning enemy placement multiple times and select the most favorable outcome - but the solution would be rather naive.

To have control over the number of mobs I decided to place them as I generate the rooms of the dungeon. There’s a trick one can use to get a random element with equal probability distribution from a sequence of an unknown size:

import random


def get_random_element(sequence):
    """Select a random element from a sequence of an unknown size."""
    selected = None
    for k, element in enumerate(sequence):
        if random.randint(0, k) == 0:
            selected = element
    return selected

With each iteration the chance of the current element to become a selected item is 1 divided by number of elements seen so far. Indeed, a probability of an element being selected out of a 4-item sequence:

1 * (1 - 1/2) * (1 - 1/3) * (1 - 1/4) = 1/2 * 2/3 * 3/4 = 6/30 = 1/4 

Now all I had to do is to modify this to account for multiple mob placement. Here’s a generalized function above which accounts for selecting n elements from the sequence with even distribution.

import random


def get_random_element(sequence, n):
    """Select n random elements from a sequence of an unknown size."""
    selected = [None for _ in range(n)]
    for k, element in enumerate(sequence):
        for i in range(n):
            if random.randint(0, k) == 0:
                selected[i] = element
    return selected

I incorporated logic above into the room generation code, accounted for duplicates, and ended up with decent distribution results.

After playing with random dungeon generation for a bit, I seem to be satisfied with the results:

The above is displayed using ADOM notation - # represents a wall, . is a floor tile, and + is meant to be a closed door. After fiddling about with a few random dungeon generation ideas, I settled with the following.

The algorithm

1. Start with a random point on a canvas.
2. Create a room with random width and height. Don’t worry about walls yet.
3. Select a few points on the sides of the room, put those in a stack. Save the direction in which the potential doors would point.
4. Go through the stack, and try to add a room or a corridor (corridor is just a room with a width or a height of 1). Higher chance of corridors seems to look better and results in those wiggly passageways.
   1. Try to add a room a few dozen times with different random configurations. If no luck - give up and grab a new item from the stack. If couldn’t generate a continuation to the corridor - mark it as a loose end, we’ll clean those up later.
   2. If a room was added successfully - add a door where it connects to the previous room/corridor. Add a floor section if it’s a corridor connecting to another corridor.
   3. At this point one ends up with quite a few interconnected corridors, merged rooms, and all kinds of fun surroundings (my desired goal).
5. Do the above until the stack is empty or a desired number of rooms has been generated.
6. Clean up the loose ends from step 4.1. Remove loose corridor segments one by one until intersection with another room/corridor is detected.
7. Add walls around the rooms and corridors, while also cleaning up any extra doors we may have left behind when creating merged corridors or rooms.
   1. I simply used slightly modified depth first search starting inside any room and drawing walls wherever I could find floor/door not connected to anything.
   2. When encountering a door - check if it’s surrounded by walls or doors from the opposite sides. If not - remove the door and replace it with a floor tile. If any doors were adjucent to the removed door - requeue the door check on them.
8. Perform steps 1-7 a few hundred times, saving the resulting dungeons each time. Pick the best candidate with the most desired features - like a number of rooms, breadth, square footage, longest corridors, etc.

A more detailed explanation of the steps is below. For now, here are a few more dungeons generated using this method:

I think dungeon generation is far more art than science, and I had a lot of fun tweaking all the different input parameters:

• Room size boundaries.
• Corridor lengths.
• Frequency of corridor occurrences.
• Number of exits from the room.
• Number of room generation attempts.
• Number of dungeon generation attempts.
• Final dungeon picking heuristics.

Last item on the list is the most interesting one - with few hundred dungeons as an input, picking the right one is rather important. I ended up settling on using max priority queue with a rough surface area of the dungeon as a key (it’s more of a breadth, really - how wide and tall it is). Then I’d sift through some top results and pick the one with the most rooms available. This results in the most fun-looking map which feels up most of the screen, while still usually not being too cluttered.

Here’s a breakdown of a simple scenario:

Steps 1 and 2

Pick a random spot on a canvas and generate a room of random size (4 x 3):

....
....
....

Step 3

Select potential spots for doors, let’s label them 1, 2, 3.

....2
....
....1
  3

I went for a uniform distribution by unfolding the rectangle and folding it back in to get a proper coordinate on the perimeter. Now, stack contains coordinates of [1, 2, 3] (along with the directions in which they are pointing).

Steps 4 and 5

Add a room or a corridor to a connector number 3. We’ll be adding the room to the right of number 3. Let’s assume random sends a corridor of length 5 our way. We’re happy with the corridor pointing either up, down, or right - so we let the random decide again: up.

     4
     .
     .
....2.
.... .
....3.
  1

We add the end of the corridor to the stack as number 4 (now [1, 2, 4]). We also mark 4 as a loose end, in case we end up not adding a room to it. Dangling corridors are never pretty.

Now, to replace number 3 with a door:

     4
     .
     .
....2.
.... .
....+.
  1

Adding another random corridor of length 2 to the point 4, pointing right. Replace number 4 with a floor segment, since point 4 was the end of another corridor. Remove point 4 from loose ends, add point 5.

     ...5
     .
     .
....2.
.... .
....+.
  1

Take point 5, generate a room of size 3 x 6. 5 becomes a door. Loose ends list is empty.

     ...+...
     .   ...
     .   ...
....2.   ...
.... .   ...
....+.   ...
  1

For simplicity’s sake, let’s assume we don’t want any more exits from this room. Back to the stack of [1, 2]. Point 2 seem to not have much room for growth. After a few unsuccessful attempts to place a room or a corridor there, we give up:

     ...+...
     .   ...
     .   ...
.... .   ...
.... .   ...
....+.   ...
  1

Now for point 1: we get another corridor of length 3. Point 6 is now added to the loose ends list.

     ...+...
     .   ...
     .   ...
.... .   ...
.... .   ...
....+.   ...
  +
  .
  .
  .
  6

Let’s assume we run out of space and can’t add anything to the end of 6. We’re done generating the dungeon. Our stack is empty, and our loose ends contains coordinates of 6.

Step 6

Start with the loose end, and remove items one by one until a tile with multiple neighbors is encountered:

     ...+...
     .   ...
     .   ...
.... .   ...
.... .   ...
....+.   ...
  X
  X
  X
  X
  X

Viola:

     ...+...
     .   ...
     .   ...
.... .   ...
.... .   ...
....+.   ...

Steps 7 and 8

There are no rogue doors in this scenario, so all we need to do is add the walls:

     #########
     #...+...#
     #.###...#
######.# #...#
#....#.# #...#
#....#.# #...#
#....+.# #...#
######## #####

All of the steps above should be repeated a few hundred times with different dungeons, and then the best dungeon should be picked as a final one.

Did I miss anything? Was cleaning up “loose ends” too much of a hack? What should have I done differently?

Notes to make sure I don’t forget how to do this in the future. First, install mssql and vcli tools:

npm install -g sql-cli
pip install vcli

Encrypt desired database account passwords:

mkdir -p ~/.passwd
echo '$PASSWORD' | gpg --use-agent -e > ~/.passwd/$DB_ACCOUNT.gpg

Set up a set of aliases with the desired level of flexibility in ~/.bashrc to avoid typing too much:

function _sql-helper-command {
  host=$1
  user=$2
  password=$3
  db=$4
  opt_query_file=$5

  if [ -z $opt_query_file ]; then
    mssql -s $host -u $user -p $password -d $db
  else
    mssql -s $host -u $user -p $password -d $db -q "`cat $opt_query_file`"
  fi
}

function _vsql-helper-command {
  host=$1
  user=$2
  password=$3

  vcli -h $host -U $user -w $password
}

# Usage: `sql` for interactive mode, `sql filename.sql` to execute a file.
function sql {
  opt_query_file=$1

  host='$SOME_HOST'
  user='$SOME_USER'
  password=`gpg --use-agent --quiet --batch -d ~/.passwd/$SOME_FILENAME.gpg`
  db='$SOME_DB'

  _sql-helper-command $host $user $password $db $opt_query_file
}

# Usage: `vsql $VERTICA_HOST`
function vsql {
  host=$1
  user=`whoami`
  password=`gpg --use-agent --quiet --batch -d ~/.passwd/$SOME_FILENAME.gpg`

  _vsql-helper-command $host $user $password
}

Replace $SOME_USER, $SOME_HOST, $SOME_DB, $SOME_FILENAME above with specific user, host, DB, and filenames respectively. I usually make a bunch of aliases for different environments/machines I use: sql-prod, sql-dev, sql-local or vsql-host1, vsql-host2.

I like traveling. I’ve been living on the road on and off for the past half a year, traveling across the US. This whole time I live in my car, and quite frankly, I enjoy it.

Passing beautiful vistas and not having a place to call home are two sides of the same coin. It’s something that gives me time to think.

From a very young age we surround ourselves with objects of comfort. It all starts with toys we have as children. First things we own. Our room. Friends. House. Job. Town. Country. We take comfort in certain parts of the environment. Be it objects, people, or places.

After getting rid of most of my belongings and starting my journey - I felt like a lot of things which made me feel comfortable and safe were gone. It made me feel very exposed to the world.

When objects of comfort are gone, one has to face a lot of their own demons. Issues hidden by a security blanket are let out to roam freely. Living on the road amplifies the experiences I have: the ups are high, and the downs are low. A wider specter of emotions is thrown onto me.

I guess there’s a reason why majority of people all live in a similar manner. It’s comforting. It’s a void inside you that needs filling. It’s things we don’t want to think about, deal with.

But there’s also strength in letting go. Items, places, people. Thoughts. Ideas. It’s a way of growth. To become a better version of yourself, you need to be destroyed a little. Deal with the darkness within.

Some days it’s exhausting, some days it’s revitalizing. But that’s why I do what I do.