Category: Gamedev

📅 May 24, 2021 🏷️ Gamedev
Abandoned project showcase: Hikaya

Roguelikes are once niche, but an increasing mainstream video game genre. The genre is named after 1980 “Rogue” - a procedurally generated dungeon crawler. Rogue and games inspired by it often include simple ASCII graphics, feature procedural generation of the world, and include “permadeath”: the game is over once you die.

Many games were heavily inspired by it - like Ancient Domains of Mystery and Nethack, or more recent Cataclysm: DDA and Caves of Qud. Modern games bring a lot of fantastic fusion into the genre too with like The Binding of Isaac or Hades. But I digress.

A few months ago I was struck by a bout of inspiration. I’ve tried countless times before, but never produced a complete video game – this was meant to be the time! I’ve significantly reduced the scope, came up with a plan of action, and started coding!

I codenamed the game “Hikaya”, which means “a fairy tale” in Tatar - my native language (although I think the word itself has been borrowed from Arabic). I planned to make a fairly straightforward roguelike, without too many bells and whistles.

I’ve found a wonderful tutorial on rogueliketutorials.com, which introduces libtcod – a library to simplify the mundane: drawing on screen, handling input, field of view and lighting, pathfinding. I’ve struggled through all of the above before, and knew that getting deep into the mechanical details would slow me down.

Alas, I didn’t finish the game. I’ve gotten maybe half way there, before my focus slipped away from the project. But not before getting some screenshots and documenting some interesting ideas I had!

The only contains a dozen dungeon levels, with a short story being told through item descriptions. The player is an adventurer who’s sent by their village to a nearby cave to retrieve the last flame - a placeholder MacGuffin.

Every item and monster posses a fantasy-sounding name, contrasted with a short, but colorful description hinting at a science fiction nature of the objects. Think magic scrolls with touch screens, or injectable health potions.

Each monster type has a unique behavior - with goblins running away and regrouping, ogres snacking on goblins to restore health, and so on.

As the player descends down the dungeon, they encounter multiple bosses guarding the staircases. The bosses drop unique armor pieces, which tell a story of a group of adventurers descending into the dungeon, but succumbing to traps, greed, and treachery.

Finally, a dragon guards the last light on the final floor. The game ends with the player becoming a dragon, and a cycle becomes anew.

I know, I know: edgy, uninspired – but I enjoyed the premise.

The combat is focused on tactical movement and avoiding damage, and the player unlocks new moves – like kicks, jumps, or faints – as they progress through the dungeon.

I wanted to experiment with the health system. Inspired by FATE tabletop roleplaying system, I attempted to use health pools. The system was meant to keep combat dangerous and entertaining throughout the game by making even the goblins dangerous throughout the game.

My biggest experiment came from a health system. Inspired by FATE tabletop roleplaying ruleset, the health consists of multiple pools (as opposed to a single bar). The goal of the system is to make combat deadly, and create a sense of danger even for trivial encounters, while still leaving room for error.

Let me try to explain. For example, a player might have three health pools - for 1, 2, and 3 hit points each. Each time a player takes damage, the smallest pool is used to absorb that damage. For instance, a 2 damage hit voids the 2 hit point pool. A second 2 damage hit clears out the 3 hit point pool. A third 2 damage hit is fatal.

You can see the voided health pools marked as red on the screenshot below, and the full health pools in green:

To complicate thing further, I give players some leeway by slowly draining partially damaged pools over time. For instance, if the player uses their 5 hit point pool to absorb 2 points of damage, I’ll slowly drain that pool over the next three turns. This would let the player take another 2 damage hit (or a few 1 damage hits) “for free” immediately after being hit. You can see those hearts marked as yellow on the screenshot above.

Needless to say, the system turned out to be very convoluted to explain in game (and on paper too – I don’t think the above is clear enough). I still think it’s a great idea, but it desperately needs better user experience design to make it accessible. In fact, FATE itself got rid of confusing health pools in it’s latest “FATE Condensed” release, simplifying health down to binary hit markers.

Despite not finishing it, putting together Hikaya was a fun experience. I’ve had a great time working on the prototype: I’ve learned a lot, and maybe I’ll lead my next video game project to completion given everything I’ve learned!

📅 Oct 2, 2016 🏷️ Gamedev · Programming

Mob level distribution

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.

Random mob distribution in roguelike dungeon.

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()

Distribution histogram: 1000000 iterations, 0.5 chance, and 2 as a target.

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:

Distribution histogram: 1000000 iterations, 0.33 chance, and 2 as a target.

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

Distribution histogram: 1000000 iterations, 0.9 chance, and 2 as a target.

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

Distribution histogram: 1000000 iterations, 0 chance, and 2 as a target.

And an equal chance of picking surrounding elements:

Distribution histogram: 1000000 iterations, 1 chance, and 2 as a target.

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

📅 Sep 30, 2016 🏷️ Gamedev · Programming
Spawning evenly distributed mobs
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.
📅 Sep 29, 2016 🏷️ Gamedev · Programming
Randomly generated dungeons
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?

Category: Gamedev

Abandoned project showcase: Hikaya

Mob level distribution

Spawning evenly distributed mobs

Randomly generated dungeons

The algorithm

Steps 1 and 2

Step 3

Steps 4 and 5

Step 6

Steps 7 and 8