Mar 11, 2020 - Natural Path Generation

Comments

Random level generators are great fun to make; there’s nothing quite like coding an algorithm that creates endless variations of maps and dungeons.

A typical random map generator might place rooms randomly around the place and connect them with corridors. Then the map might be filled randomly with inhabitants - monsters, treasure, NPCs and so on. This is simple and effective, giving players unpredictable yet interesting encounters in games. It’s an evergreen approach starting from rogue (1980) all the way up to the latest indie dungeon crawlers.

Rooms and Mazes

This can seem backwards though. One problem is that the layout often seems artificial; there’s not much reason or purpose for the rooms and the connecting corridors. Real locales would be filled with inhabitants, with paths connecting important destinations together. The paths are like arteries; they are inextricably linked to the design of the whole place.

So I thought a fun experiment would be to make a random level generator that builds such a map via simulation: fill it with virtual inhabitants, who need to go from A to B, find out what paths they need via pathfinding, and create the paths based on travel patterns. Let’s see how this goes!

First, I start with a simple “village” generator - just a bunch of buildings scattered randomly around the place.

village

Before we place paths to connect these buildings, we need to think about how these buildings will be used. Some - shops, inns - will be more important than others - private residences. Let’s express that by making some buildings important, giving them a different appearance, and populating them with more NPCs.

village with NPCs

Now to connect the buildings, by taking random pairs of them, then using pathfinding to draw a path between each pair, with two conditions:

  • the more important the building, the more we use it as a path destination;
  • make sure all buildings have at least one path

village with paths

This seems ok but now the village is overrun with paths. Some are obviously more well travelled than others. What if we showed that by using different tile types? From tree (no wear), grass (light wear), dirt road (moderate wear), stone road (heavy wear):

village with varied paths

Now it’s starting to look nice! But there are still a few problems: there’s a lot of grass, representing lightly travelled paths, and odd patches of stone/dirt roads, right next to each other.

It turns out we could make one more improvement: when there’s an existing path, it would make more sense to reuse it, even if it’s slightly out of the way, rather than cutting through untravelled roads. This makes sense and it’s what real travellers do. So let’s modify our pathfinder, so that it favours well-travelled tiles, and see what we get:

village with shared paths

Nice! Now we see some clear heavily-travelled avenues. By observing the paths, we can also make sense of where the important locations are. Cool huh?

You can find this map generator here: https://github.com/cxong/gomapgen under the village option. It’s also where I make lots of different map generators for fun.

Hope you enjoy!

village animation

Oct 26, 2019 - Level Design Patterns in 2D Games

Comments

I’m a sucker for level design and design patterns, so when I came across this article (and paper) called “Level Design Patterns in 2D games”, I had to read it! Unfortunately it’s a bit wordy, so I thought I’d summarise it and throw in a bunch of pictures! Enjoy!

It’s taken a surprising amount of effort to gather these examples. If you know of any please let me know so I can add more!

Guidance

Guide the player through the path they need to take.

  1. Level shape

    Super Mario Bros. Super Meat Boy
    Super Mario Bros. stairs to flagpole Super Meat Boy hills
  2. Collectibles (a.k.a. breadcrumbing)

    Donkey Kong Country 2 Granny Smith
    Donkey Kong Country 2 bananas Granny Smith apples
  3. Enemies

    Super Mario Bros. 3 Sonic 3
    Super Mario Bros. 3 flying shells Sonic 3 monkey and collectible on tree
  4. Environmental cues

    The Legend of Zelda: A Link to the Past Pokemon
    The Legend of Zelda: A Link to the Past bombable walls Pokemon hidden items in conspicuous rocks

Safe Zone

Give the players a place safe from hazards so they can stop and think.

Contra The Legend of Zelda
Contra energy zone flames The Legend of Zelda safe doorways in dungeons

Foreshadowing

Partially introduce something new to the player, only to fully reveal it later. This can serve to teach the player, or encourage exploration.

  1. New hazard that’s out of reach

    Bare Knuckle III Golden Axe
    Bare Knuckle III boss in boat Golden Axe bad brothers
  2. New enemy that foreshadows a boss

    Megaman Contra
    Megaman enemy using Cutman weaponMegaman Cutman boss fight Contra bugger before boss
  3. New objects / obstacles that cannot be used until later, to encourage exploration.

    Chrono Trigger Pokemon
    Chrono Trigger sealed chests Pokemon tree

Layering

Combining multiple objects to create new experiences, like a harder challenge.

  1. Multiples of the same object

    Raiden 2 Streets of Rage 3
    Raiden 2 multiple enemies
  2. Different objects

    Jackal Super Mario World
    Jackal level 5 boss Super Mario World Banzai Bill and Goombas

Branching

Giving the player different choices.

  1. Branching with no restrictions - gives the feeling of exploration

    Binding of Isaac: Rebirth Final Fantasy IV
    Binding of Isaac: Rebirth branching map Final Fantasy IV airship
  2. Conditional branching - stimulates curiosity and may require backtracking

    Super Metroid The Legend of Zelda: A Link to the Past
    Super Metroid coloured doors The Legend of Zelda: A Link to the Past locked doors
  3. Risk-reward branches - encourages players to invest more time in the game by rewarding skill

    Excitebike Sonic 3
    Excitebike branching paths Sonic 3 extra life

Pace Breaking

Dramatically changing the pacing of the game - higher or lower tension.

  1. Introduce difficulty (e.g. bosses) to increase tension

    Lifeforce 1943
    Lifeforce first boss 1943 boss
  2. Decrease tension to let players enjoy other parts of the game, or learn a new mechanic

    Mappy Street Fighter 2
    Mappy bonus round Street Fighter 2 car
  3. Decrease tension to set up for a more dramatic increase later (e.g. just before a boss fight)

    Megaman 2 Chrono Trigger
    Megaman 2 boss corridor Chrono Trigger Magus's Lair
  4. Controlling tension through level design

    Jackal Gradius 2
    Jackal lasers Gradius 2 flares

Sep 2, 2019 - 3 Tips for Super Legible Pixel Fonts

Comments

Recently I restored the font used in C-Dogs SDL to the one used in the original C-Dogs. The reason why they were replaced in the first place was because the original graphics weren’t open source, so I was looking for alternatives. A few years back the author of C-Dogs agreed to open source the original graphics, and I’ve only just gotten around to restoring the font.

But that’s not what this post is about! I want you to take a look at the C-Dogs font:

It’s actually a pretty neat font. Most of the letters are just 3x5 pixels (some wider or taller), but with a few tricks they look super legible for their size. Here I’ll show you some of the tricks used to make pixel fonts really legible.

Tom Thumb

Let’s back up a bit. While I was looking for a free font, I had some tough requirements. The font couldn’t be bigger than 3x5 pixels, otherwise the UI in the game will break. That’s a really small size to work with, and most pixel fonts struggle at that size.

Most pixel fonts are around the 8x8 size

I managed to find a contender in a surprising place; someone made some 3x5 fonts for use on PDAs, where screens could be 160x160 pixels total. The font was jokingly called “Tom Thumb”:

This was the right size, but it’s not nearly as legible as the C-Dogs font. Some letters are so compressed it’s hard to tell what they are without context (take a look at “M” and “N” for example). Tom Thumb, being made for a terminal, strictly needed to be monospace whereas with C-Dogs SDL we could have variable-width fonts. Here’s some tricks we used to enhance Tom Thumb:

Add Outlines

For games, you don’t really know where your text could end up. It could be over a dark or light background, coloured, or with a bunch of busy game objects moving in the background. A plain-white text will get lost over a bright background and so forth.

A really cheap solution is to just add an outline! And if you overlap the outline it doesn’t even need to add to the width of your font.

Use Greys

Before the proliferation of 4k displays, folks have come up with some clever ways to make screen fonts legible. Here’s a simple approach using antialiasing:

We can copy the same idea on pixel fonts and use some greys in the font to hint at curves.

Look at how the “o”s become much rounder, and the “W”’s shape is much improved.

Make it Proportional

We didn’t get to this point with Tom Thumb, but since C-Dogs SDL can handle proportional fonts, why not use the extra horizontal space available? It can really improve wide letters like “W” and “M”.

Here I’ve just replaced the “w” with one from C-Dogs. Doesn’t it look great?

If you’re interested in Tom Thumb, both the original and our enhanced version, you can find it here on OGA. It’s got a great range actually, with lots of Latin1 characters.

And if you’re making pixel fonts yourself, why not use some of these tips?