Shuffling

A while back I went through my iTunes library and took the songs/albums/artists not already living in their own playlist and put them into a mega-playlist I called all of it.1 This way I could just hit “shuffle my library” when in my car and emulate what I used to do with my iPod. I don’t want to fuss with any UI, or play some algorithmically-generated playlist full of suggested music I might like. I just want to listen to my library, on shuffle.

But I’ve been feeling lately like shuffling just… isn’t good. Maybe the same artist plays twice in a row, or within just a couple minutes of my past listen. Or each shuffle still front-loads the same small selection of songs, so I don’t really get to explore the depths of my library. It’s not a large library (10,000 songs), but not small either, so why am I hearing the same old stuff? This is the 21st Century, is it really so hard to shuffle music?

The short answer is: no, it’s not. We can pretty much shuffle any list of things in an almost truly random fashion. But there are plenty of reasons shuffling doesn’t seem random. Humans are inherently pattern-seeking animals2, and in a truly random sequence of songs, a given artist is no more or less likely to play next based on the previous artist. So you could have two artists play in a row—or if it’s truly random, the same song!

Another problem is that once software gets Good Enough™ it doesn’t usually get touched again until there are actual problems with it—or there is a strong monetary incentive to do so. So a developer with the task to write a shuffle feature might do what’s Good Enough™ to close the ticket according to the requirements and test plan3, then move onto the next ticket.

So what does it really take to do a good job shuffling a playlist? I wanted to do a little experimenting so I thought I would start from the ground up and walk through a few different methods. First, I need…

The Music

I took my playlist and ran it through TuneMyMusic to get a CSV. Then I wrote a little bit of code to parse that CSV into a list of Song objects, which would be my test subject for all the shuffling to come.

True Random

First I wanted to see how poorly, or how well, a “true” random shuffle worked.4 This is easy enough.

We’ll just do a simple loop. For the length of the song list, grab a random song from the list and return it:

for (var i = 0; i < songList.Count - 1; i++) 
{
    var index = RandomNumber.Next(0, songList.Count - 1); 
    yield return songList[index]; 
}

And right away I can see that the results are not good enough. Lots of song clustering, even repeats: one song right after the other!

[72]: Goldfinger - Superman 
[73]: Metallica - Of Wolf And Man (Live with the SFSO) 
[74]: Orville Peck - Bronco 
[75]: Def Leppard - Hysteria 
[76]: Kacey Musgraves - Follow Your Arrow 
[77]: Kacey Musgraves - Follow Your Arrow 
[78]: The Thermals - My Heart Went Cold 
[79]: Miriam Vaga - Letting Go

A Better Random

After looking at the results from the first random shuffle, two requirements have become clear:

  1. The input list must have its items rearranged in a random sequence.
  2. Each item from the input list can only appear once in the output list.

Kind of like shuffling a deck of cards. I’d be surprised to see a Deuce of Spades twice after shuffling a deck. I’d also be surprised to see the same Kacey Musgraves song in my queue twice after hitting the shuffle button.

Luckily this is a problem that has been quite handily solved for quite a long time. In fact, it’s probably used as the “default” shuffling algorithm for most of the big streaming players. It’s called the Fisher-Yates shuffle and can be accomplished in just a couple lines of code.

for (var i = shuffledItemList.Length - 1; i >= 0; i--) 
{ 
    var j = RandomNumber.Next(0, i); 
    (shuffledItemList[i], shuffledItemList[j]) = (shuffledItemList[j], shuffledItemList[i]);
}

Starting from the end of the list, you swap an element with a random other element in that list. Here I’m using a tuple to do that “in place” without the use of a temporary variable.

The results are much better, and at first glance almost perfect! But scanning down the list of the first 100 items, I do see one problem:

[87]: CeeLo Green - It's OK 
[88]: Metallica - Hero Of The Day (Live with the SFSO) 
[89]: Metallica - Enter Sandman (Remastered) 
[90]: Guns N' Roses - Yesterdays

It’s not the same song, but it is the same artist, and in a large playlist with lots of variety, I don’t really like this.

Radio Rules

Now I know I don’t want the same song to repeat, or the same artist, either. While we’re at it, let’s say no repeating albums, too. So that’s two new requirements:

  1. No more than x different songs from the same album in a row.5
  2. No more than y different songs from the same artist in a row.

This is pretty similar to the DMCA restrictions set forth for livestreaming / internet radio. It will also help guarantee a better spread of music in the shuffled output.

Here’s some code to do just that:

var shuffledItemList = ItemList.ToArray();
var lastPickedItems = new Queue<T>();
for (var i = shuffledItemList.Length - 1; i >= 0; i--)
{
    var j = RandomNumber.Next(0, i);

    var retryCount = 0;
    while (!IsValidPick(shuffledItemList[j], lastPickedItems) &&
           retryCount < MaxRetryCount)
    {
        retryCount++;
        j = RandomNumber.Next(0, i);
    }

    if (retryCount >= MaxRetryCount)
    {
        // short-circuiting; we maxed out our attempts
        // so increment the counter and move on with life
        invalidCount++;

        if (invalidCount >= MaxInvalidCount)
        {
            checkValidPick = false;
        }
    }
    
    // a winner has been chosen!
    // trim the stack so it doesn't get too long
    while (lastPickedItems.Count >= Math.Max(ConsecutiveAlbumMatchCount, ConsecutiveArtistMatchCount))
    {
        _ = lastPickedItems.TryDequeue(out _);
    }
    
    // then push our choice onto the stack
    lastPickedItems.Enqueue(shuffledItemList[j]);
    
    (shuffledItemList[i], shuffledItemList[j]) = (shuffledItemList[j], shuffledItemList[i]);
}
return shuffledItemList;

This, at its core, is the same shuffling algorithm, with a few extra steps.

First, we introduce a Queue, which is a First-In-First-Out collection, to hold the x most recently chosen songs.

Then when it’s time to choose a song, we look in our queue to determine if any of the recent songs match our criteria. If they do, then we skip this song and choose another random song. We attempt this only so many times. While the chance is low, there’s still a small chance that we could get stuck in a loop. So there’s a short-circuit built in that will tell the loop it’s done enough work and it’s time to move on.

In addition to that, there’s a flag with a wider scope: if we’ve short-circuited too frequently, then the function that checks for duplicates will stop checking.

This is an extra “just in case”, because if I hand over a playlist that’s just a single album or artist, I don’t want to do this check every single time I pick a new song. At one point it will become clear that it isn’t that kind of playlist.

Once a song has been chosen, the lastPickedItems Queue gets its oldest item dequeued and thrown to the wind6, and the newest item is enqueued.

How does this do? Pretty well, I think.

[89]: Metallica - One (Remastered) 
[90]: Stone Temple Pilots - Plush 
[91]: Megadeth - Shadow of Deth 
[92]: System of a Down - Sad Statue 
[93]: Jewel - Don't 
[94]: Def Leppard - Love Bites 
[95]: Elton John - 16th Century Man (From "The Road To El Dorado" Soundtrack) 
[96]: Daft Punk - Aerodynamic 
[97]: Kacey Musgraves - High Horse 
[98]: Above & Beyond - You Got To Go 
[99]: Gnarls Barkley - Just a Thought

But not all playlists are a wide distribution of artists and genres. Sometimes you have a playlist that is, for example, a collection of 80s rock that’s just a bunch of Best Of compilations thrown together. How does this algorithm fare against a collection like that?

Answer: not well.

[0]: CAKE - Meanwhile, Rick James... 
[1]: CAKE - Tougher Than It Is (Album Version) 
[2]: Breaking Benjamin - I Will Not Bow 
[3]: Enigma - Gravity Of Love 
[4]: CAKE - Thrills
[5]: Clutch - Our Lady of Electric Light

It immediately short-circuits, and we see lots of clustering. Maybe not a deal-breaker for a smaller, more focused playlist, but I can’t help but feel there’s a better way to handle this.

Merge Shuffle

Going back to the deck of cards analogy: there are only 4 “albums” in a deck, but shuffling still produces good enough results for countless gamblers and gamers. So why not try the same approach here?

We want to split our list into n elements, then merge them back together, with a bit of randomness. Like cutting and riffling a deck of cards.

First, we’ll do the easy part: split up the list into a list of lists – like a bunch of hands of cards.

private List<List<T>> SplitList(IEnumerable<T> itemList, int splitCount)
{
    var items = itemList.ToArray();
    return items.Chunk(items.Length / splitCount).Select(songs => songs.ToList()).ToList();
}

Then, we pass this list to a function that will do the real work of shuffling and merging.

private IEnumerable<T> MergeLists(List<List<T>> lists)
{
    var enumerable = lists.ToList();
    var totalCount = enumerable.First().Count;
    var minCount = enumerable.Last().Count;

    var difference = totalCount - minCount;
    var lastList = enumerable.Last();

    lastList.AddRange(Enumerable.Repeat((T)dummySong, difference));
    
    // set result
    var resultList = new List<T>();
    var slice = new Song[enumerable.Count];

    for (var i = 0; i < totalCount - 1; i++)
    {
        for (var l = 0; l <= enumerable.Count - 1; l++)
        {
            slice[l] = enumerable[l][i];
        }

        for (var j = slice.Length - 1; j >= 0; j--)
        {
            var x = RandomNumber.Next(0, j);

            (slice[x], slice[j]) = (slice[j], slice[x]);
        }

        for (var j = 1; j <= slice.Length - 1; j++)
        {
            if (slice[j - 1] == dummySong)
            {
                continue;
            }
            
            if (slice[j].ArtistName == slice[j - 1].ArtistName)
            {
                (slice[j - 1], slice[slice.Length - 1]) = (slice[slice.Length - 1], slice[j - 1]);
            }
        }

        if (i > 0)
        {
            var retryCount = 0;
            while (!IsValidPick(slice[0], resultList.TakeLast(1)) &&
                   retryCount < MaxRetryCount)
            {
                (slice[0], slice[enumerable.Count - 1]) = (slice[enumerable.Count - 1], slice[0]);
                retryCount++;
            }
        }
        
        resultList.AddRange((IEnumerable<T>)slice.Where(s => s != dummySong).ToList());
    }
    
    return resultList;
}

This is kind of a big boy. Let’s go through it step by step.

First, we cast our input list to a local variable. I am allergic to side-effects, so I want any changes (destructive or otherwise) confined to a local scope inside this function to keep it as pure as possible.

We’ll take the local list, and then find the length of the biggest chunk, and the length of the smallest chunk. There will only be one chunk smaller than the rest. We’ll fill it up with dummy songs so it’s the same length as the other chunks, and then disregard the dummy songs later.7

Once our lists are in order, we slice through them one section at a time. The slice gets shuffled8, then checked for our earlier-defined rules, but a little more relaxed: no artist or album twice in a row. If a song breaks a rule, we just move it to the end of the array and try again, always with a short-circuit so we don’t get caught in an endless loop.

And of course, we will always allow / ignore the dummy songs, so they don’t interfere with any real choice.

But, there’s a problem! Like a deck of cards, shuffling once just isn’t enough. Like you do with a real deck of cards, let’s go through this process at least seven times.

for (var i = 0; i <= ShuffleCount - 1; i++)
{
    var splitLists = SplitList(list.ToList(), SplitCount);
    list = MergeLists(splitLists);
}

And… the output looks really good, in my opinion!

[0]: Daft Punk - Digital Love 
[1]: America - Sister Golden Hair 
[2]: CAKE - Walk On By 
[3]: Guns N' Roses - Yesterdays 
[4]: Hey Ocean! - Be My Baby (Bonus Track) 
[5]: CAKE - Meanwhile, Rick James...
[6]: Fitz and The Tantrums - Breakin' the Chains of Love 
[7]: Digitalism - Battlecry 
[8]: Harvey Danger - Flagpole Sitta 
[9]: Guttermouth - I'm Destroying The World

However, this only really works well in the areas where the plain-old Fisher-Yates shuffle doesn’t. When used on smaller or more homogeneous sets, the results still leave something to be desired. These two shuffle methods complement each other, but cannot replace each other.

Shuffle Factory

So what happens now?

I thought about checking the entire playlist beforehand to see which algorithm should be used. But there’s no one-size-fits-all solution for this. Because, like my iTunes library, there could be a playlist with a huge number of albums, and also a huge number of completely unrelated singles.

So let’s get crazy and use both.

First we need to determine the boundary between the Fisher-Yates shuffle and the “Merge” Shuffle (for lack of a better term). I’m going to just use my instincts here instead of any hard analysis and say: if it’s a really small playlist, or if more than x percent of the playlist is one artist, then we’ll use the Merge Shuffle.

private ISortableList<T> GetSortType(IEnumerable<T> itemList)
{
    var items = itemList.ToList();
    if (HasLargeGroupings(items))
    {
        return new MergedShuffleList<T>(items);
    }
    return new FisherYatesList<T>(items);
}

public bool HasLargeGroupings(IEnumerable<T> itemList)
{
    var items = itemList.ToList();
    if (items.Count <= 10)
    {
        // item is essentially a single group (or album)
        // no point in calculating.
        return true;
    }

    var groups = items.GroupBy(s => s.ArtistName)
        .Select(s => s.ToList())
        .ToList();

    var biggestGroupItemCount = groups.Max(s => s.Count);

    var percentage = (double)biggestGroupItemCount / items.Count * 100;

    return percentage >= 15;
}

Pretty straightforward! There is also the function that performs the check, and returns a new shuffler accordingly.

Now let’s shuffle.

public void ShuffleLongList(IEnumerable<T> itemList,
    int itemChunkSize = 100)
{
    var items = itemList.ToList();
    if (items.Count <= itemChunkSize)
    {
        chunkedShuffledLists.Add(GetSortType(items).Sort().ToList());
        return;
    }

    items = new FisherYatesList<T>(items).Sort().ToList();
    
    // split into chunks
    var chunks = items.Chunk(itemChunkSize).ToArray();

    // shuffle the chunks
    var shuffledChunks = new FisherYatesList<T[]>(chunks).Sort();

    foreach (var chunk in shuffledChunks)
    {
        chunkedShuffledLists.Add(GetSortType(chunk).Sort().ToList());
    }
}

Again, pretty simple.

Split our input into x lists of y chunk size (here, defalt to 100). Again we’ll do a little short-circuiting and say if the input is smaller than the chunk size, we’ll just figure out the shuffle type right away and exit immediately.

Otherwise, we do a simple shuffle of the input list and then split it into chunks of the desired size. I chose to do this preliminary shuffle as an extra degree of randomness. I hate hitting shuffle on a playlist, playing it, then coming back and shuffling again and getting the same songs at the start.9 So this will be an extra measure to guarantee the start sequence is different every time.

Next we shuffle the chunk ordering. Again, using Fisher-Yates, and again, for improved starting randomness.

After that we just iterate through the chunks and shuffle them according to whichever algorithm performs better for that particular chunk.

The output here is, again, really nice in my testing. I ran through and checked multiple chunks and felt overall very pleased with myself, if I’m being honest.

[0]: Rina Sawayama - Chosen Family 
[1]: Clutch - Our Lady of Electric Light 
[2]: Matchbox Twenty - Cold 
[3]: Rocco DeLuca and The Burden - Bus Ride 
[4]: Rob Thomas - Ever the Same 
[5]: MIKA - Love Today 
[6]: CeeLo Green - Satisfied 
[7]: Metallica - For Whom The Bell Tolls (Remastered) 
[8]: Elton John - I'm Still Standing 
[9]: Rush - Closer To The Heart 
... 
[0]: Wax Fang - Avant Guardian Angel Dust 
[1]: Journey - I'll Be Alright Without You
[2]: Linkin Park - High Voltage 
[3]: TOOL - Schism 
[4]: Daft Punk - Giorgio by Moroder 
[5]: Fitz and The Tantrums - L.O.V. 
[6]: Stone Temple Pilots - Vasoline (2019 Remaster) 
[7]: Jewel - You Were Meant For Me 
[8]: Butthole Surfers - Pepper 
[9]: Collective Soul - No More No Less

Outtro

I don’t think there’s any farther I can take this. I know if I looked closer and the end results, I could find something else to change. There’s a whole world of shuffling algorithms out there, and plenty to learn from. If I felt so inclined I could write something to shuffle my playlists for me, but this exercise was really to learn first why shuffling never seemed good enough, and second if I could do better.

(The answers, as usual, were “it’s complicated” and “maybe”.)

Further Reading

  • The source code for my work is over at my github.
  • Spotify, once upon a time, did some work on their shuffling and wrote about it here
  • Live365 has a brief blog post on shuffling and DMCA requirements here

The Zelda Formula: Part Two

Previously.

We left off talking about how it’s fun, more than any other aspect of a game, that makes you feel like a hero. If you’re handed an über-powerful weapon at the start of the game and just start mowing down mobs, sure, that could be fun for a few minutes, but it very quickly loses its charm. Similarly, the game’s narrative can call you “Hero” all it wants, but if the gameplay doesn’t make you feel it, again, you’re left wanting. The Zelda franchise has mastered the art of achieving this feeling, balancing the narrative with tight, well-balanced gameplay that continuously challenges and delights.

This is done by adhering to a small handful of rules. Each of these leads into and supports each other, less like pillars supporting the structure of the game, and more like a web holding it aloft.

Today I want to focus on the first, and in my opinion, the most important aspect: exploration.

Exploration is the main goal, above all else, and should be rewarded.

If you can create mysterious locales with satisfying discoveries, then the player will continue to dive deeper to sate their curiosity. Image: Digital Dreams via Youtube

If we’re talking about concrete examples of what makes a Zelda game, we must begin ab ovo. Exploration is in the Legend of Zelda’s DNA. Miyamoto’s childhood exploration through caves and waterfalls and woods served as the primary conception point for the entire series.10 You need an exciting world filled with light and darkness, monsters and wonder, new mysteries around each corner. It’s the call to adventure that keeps you pushing forward.

At its peak, this series creates that sense of wonder, that mystery and darkness, almost primal in its allure. The fields are vast and bright. The caves are deep and crawling with danger. Faeries, treasure, and knowledge all wait behind waterfalls, around the bend. Intrepid curiosity is self-rewarding; power and wisdom await those with the strength and courage to plumb the depths and brave the trials that guard these secrets.

The first Zelda game was almost only a series of labyrinthine caves and dungeons to explore. This idea grew to include a large field to connect the dungeons, a place for the player to find respite and choose where they needed to go next.11 But this overworld was not a safe place either. Even outside the dungeons creatures roamed, and before traveling in any direction the player needed to rationalize their choice and ration their resources.

It should be no surprise that even in the first Zelda, everything was already there. The dungeons, the puzzles, the secrets, the steady progression of power until you truly feel like a hero. This was, after all, grown from childhood fantasies. Subsequent games all use these same pillars of progression.

Even so, the team knew that navigating an endless series of labyrinthine dungeons would not be enough.

There needed to be more; more than simply another series of rooms to clear. To continue that drive, to really empower the player, the player needed to be challenged and rewarded at turns. They needed to make choices, sometimes difficult ones, involving real risk. And, most importantly, the world needed to continue to enchant the player, to tantalize with the possibility of something new around every corner.

Some of the strategies they used to achieve this certainly weren’t there in the beginning — but they were very quickly developed, and by the time A Link to the Past was released, were already solidified into the formula.

Combat and exploration are simultaneous

Hyrule is a land teeming with danger. In A Link to the Past, you’re a wanted man: the king’s guards jump at the sight of you and chase you down until you escape or destroy them. In Ocarina of Time, the otherwise peaceful expanse of Hyrule Field becomes claustrophobic with menace once the sun sets, as undead claw their way through the dirt to chase you down as you pass by. And in Breath of the Wild, the world has already ended and the monsters moved in.

Each game, after the introductory level or two, practically opens the entire world to you right away. But this exploration is not without cost: behind every new screen (in the older games) or around every bend in the river, curve of the mountain, there’s a camp of monsters. Always you’re balancing the reward of exploring somewhere new with the cost of encountering some unknown danger. Maybe there’s a new type of monster over there, or a more powerful version of one you know that you’re not yet ready to face. Even when you backtrack through the places you’ve been, it’s possible to get overwhelmed simply by being a bit too cocky.

You know there’s treasure behind that waterfall. Or, if you put a bomb by that crack in the wall, it will reveal a cave with something special inside. You also know that there’s monsters inside — or, instead, some puzzle to solve.

Recently while playing the 3DS’s Link Between Worlds, I found a giant boulder against a wall. I knew that if I blew up this boulder, there would be a cave behind it. But regular bombs did nothing. Several screens over was a giant bomb that would follow you around, but immediately explode when struck. So I have to go back, collect this bomb, and then navigate over the multiple screens around and through monsters trying to kill me. If they struck and missed me, they might hit the bomb. It was an actually challenging bit of fun, entirely optional with no bearing on progression or plot, and when I finally made it (using multiple different tools at my disposal), I felt great. And for my struggles, I received a Piece of Heart.

This, I think, is a great example of the challenges and rewards of exploration. None of this was part of the core game. Every single screen was filled with monsters, and each monster required a different tactic to defeat: Shield Moblins, whose shields protect them from direct attacks; flying Zirros who initially avoid and run from you, only to swoop in and drop a bomb; Snap Dragons who leap at you from afar. And I didn’t need to complete this challenge I set for myself. I could beat the game easily without it. But because I wandered over here and over there, cut my way through and snuck around mob after mob, I could connect the dots and give myself a little challenge to occupy myself between dungeons.

Which is another “pillar” of these games.

Everything is a break from everything else — and it all wears you down

Combat is a break from exploration. Puzzles are a break from combat. The overworld is a break from the dungeons, and the caves and towns are breaks from the overworld. In each area, within each “break,” there’s a new set of goals, something new to accomplish or solve or defeat. Sometimes this is a player-driven goal, sometimes it’s a secret you know is hiding around somewhere, and sometimes it’s a quest or something that pushes forward the story.

What matters is this: when you get tired of one thing, there’s something else. And in the later games they made this even easier. Quick travel, portals to leave the dungeon once you hit around the halfway mark, collectables.

Put another way: there are distractions everywhere. It’s up to the player to choose what they pursue first, and this choice gives agency. Even if it’s mostly an illusion, this agency is what makes it feel like you, the player, are the one choosing to undertake this grand quest to save Hyrule. Because you could, instead, just spend your time gathering trinkets and wandering around.

This does get pushed to an extreme in the more recent Zelda games, and I believe detrimentally so. The Korok seeds in Breath of the Wild or the Maiamais in Link Between Worlds do little but artificially pad the bulk of the game. They pull in the worst aspect of JRPGs — grinding — to give you tiny bits of mechanical progression, to beef up your character without actually giving you something meaningfully new.

Sure, it can be nice to take a break and hunt for an upgrade for your bow. But wandering Hyrule and seeing or hearing that little chirp saying there’s a thing nearby you have to collect right now! feels like the game grabbing onto your belt to slow you down.

But that’s not the way the player should be worn down. Instead, they should feel that simultaneous exhaustion / exhilaration that comes from defeating a particularly difficult foe. Or they’ve used up their arrows or potions, or maybe teased their brain figuring out some puzzle. By the time a particular encounter is over, the player should be ready and happy to move onto a new, different encounter, that will use some other resource while they recharge what was just spent. Think of a dungeon, where one room is a pure combat encounter, and then next is a puzzle, and the next is half-combat, half-puzzle, or sometimes just an empty room with a chest. A quiet spot, for a breath and a break.

Walls are mechanic- and not plot-based

When you can’t progress (spatially) in a Zelda game, it’s typically not because you need to go finish a quest first. It’s because you don’t have an ability that will let you surpass an obstacle. And usually, the ability doesn’t just unlock one new area. For example, when you get the Power Glove in A Link to the Past, you don’t just get the ability to move on to the next dungeon. Entire swaths of the overworld are now yours to explore, and you can go back to any of a dozen areas and suddenly they’re new again: new secrets, new caves to explore, new puzzles to solve.

This really makes you feel like you’re a part of the story, an agent pushing the game forward, instead of just sitting along for the ride. After all, you’re the one who braved the dungeon to find the tool that now unlocks huge chunks of the world. And now you’re the one who can choose to go back and see what new frontiers are available for you to explore.

Sometimes, it isn’t new areas unlocked, but new methods to traverse areas you’ve been to previously. Like the glider in Breath of the Wild (which, yes, is unlocked early, but still feels amazing to get), or the hookshot in A Link to the Past.

This was an interesting choice that Link Between Worlds made: from near the beginning of the game, you can “rent” every special item there is. This means you can traverse all of the overworld from the start. But, you may not be ready: tread too far up the slopes of Death Mountain, for example, and you might run into a deadly Lynel, which will definitely kill you in a single hit in the first portion of the game. And when you die, everything you’ve rented goes back to the shop for you to pony up more rupees to recover.12

Even with so many abilities at your fingertips from the start, there are places you simply can’t get to yet. And then, when you unlock the ability that gave the game its name, you suddenly have another huge section of the world you can explore — not to mention a whole other world!

The world teases you with possibility

This boths follows from, and leads to, the previous “rule.” From the beginning of the game you see areas that you can’t get to — yet. You know, though, that it’s only a matter of time before you’ll be able to go there and see what’s hiding in that cave, under those rocks, beyond that curve.

In Breath of the Wild and Tears of the Kingdom the teasing is less mechanic-based. Past the introductory area, you can literally go to any corner of Hyrule you want, as long as you can evade or fight the enemies there. Instead, you’re tantalized by the possibility of finding new secrets, new collectibles13, something cool, even if it’s nothing more tangible than a breathtaking vista. In these later games especially, the exploration and journey are their own reward, with all of the mechanical and audio design geared toward making it inherently rewarding.

Regardless of the reward, Zelda games have perfected the art of luring the player. The call to adventure becomes irrestistible when you enter Hyrule, the promise of rewards not just material impossible to ignore. When you explore this new world, overcome its trials and tribulations, you’re not just seeing numbers on a screen go up to indicate growing strength. You are truly growing more powerful, both with knowledge, skill, and ability, and the promise of even more on the horizon keeps you coming back for more.

Wrapping Up

That’s about all I have to say about exploration, for now. It’s difficult turn these “rules” into a list, because as I mentioned before, they’re so tightly interwoven. Zelda games are well-oiled machines and these rules are the parts. And the machine doesn’t work unless the parts do, as you can see by playing any number of fan-games, Zelda-wannabes, or even the lesser Zelda titles. It’s a fine, fine tightrope to walk, and it’s a miracle the franchise has been so consistent.

Next up is dungeon design and breaking convention. My notes for that are even rougher, and it’s taking longer than I’d like to organize. So I will be taking a short break from this series to work on that and to work on some other little side projects. There will also be a few gamedev-specific posts about that little game demo I made, the full game following it that is a sort of love letter to A Link to the Past, and some of the more difficult mechanics to implement.

The Zelda Formula: Part One

Before I started writing that little game demo way back in 2021, I knew exactly what kind of game I wanted to make. I learned a lot, threw out just about everything I’d made, and started fresh with the plan crystallized: to make a game evocative of the best Legend of Zelda titles. But I knew I had to step back and think about this. What really makes a Zelda game?

At first I thought I grasped this on an intuitive level. I mean, I’ve played through A Link to the Past at least ten times.14 For a proper throwback I knew I needed more than something that looked like Zelda or played like Zelda. In order for my game to not just be some reskin, I needed to identify and follow the same first principles that guided the Zelda designers themselves.

The thing about first principles is, intuition isn’t enough. It’s not enough to have played a ton of these games, and it’s not enough to love them. The games, their themes, and their central mechanics all need to be grokked. To start, I needed to codify my beliefs about what a Zelda-like game should be. Once written, these rules can be referenced when in doubt, rewritten when they no longer serve, or set aside for future consideration.

So, I started writing.

What are the Rules?

A picture of a sketch outlining dungeon progression in an early Zelda game.

An early design sketch from Zelda. Dungeons and combat, though a central part of the series, are only that: a part.

To put it lightly, I’m not exactly the first person to tackle this subject. In my quest to define the criteria that makes a Zelda game, I read quite a few excellent articles on specific aspects of game design used. But, it felt like everything I read only examined something specific and easily repeatable: how to replicate the level design, how you might imitate progression through dungeons, and so on. They focused on individual mechanics, which I argue are the expression of the principles that drive a game’s design.

Nothing I read, outside of interviews with Miyamoto, really tried to talk about why we are drawn to Zelda games over and over again. You can imitate the aesthetic and the mechanics, but without knowing exactly how to synthesize them, the end product becomes something like Stranger Things.15 It might look like Zelda and walk like Zelda, but don’t let that fool you.

So what’s the connective tissue here? How do you marry the aesthetic, mechanical, and narrative all together into something that is tangibly Zelda-esque?

I spent a long time reading, thinking, and writing about this, and came up with just four of what I consider to be guiding principles. The first is very broad and may seem obvious, but is the single most important goal for which to aim.16 The other three follow from the first — but this doesn’t make them secondary; in fact, all four of these become pillars upon which the foundation of the game rests.

Fun makes you the hero, not the plot.

(Image: Master Sword by Orioto.)

The Master Sword rules because of what you can do with it, not because it’s a storied blade of virtue.

This might sound a little reductive, or at least obvious. But, it’s important to stress this point and I think a lot of games miss this mark. A big part of the appeal of Zelda is that it makes you feel like a hero. The story gives you a nudge in that direction, but it’s not the story alone that engenders the feeling. It’s fun that does it.

A sprawling overworld, dark dungeons, a princess/world/timeline that needs saving; these alone aren’t enough. No matter how well-written your dialog is, or how moving your cutscenese are, if you aren’t having fun while you traverse and overcome the obstacles set before you by the game, then you might as well be watching a movie. Movies are great, and can be empowering in their own way, but that’s not what these games are after. It’s player agency we want. Zelda offers you power through your choices.

The goal is to empower the player through the actions they choose while playing the game. Let their choices lead to heroic challenges with heroic conclusions. You give them these seemingly insurmountable challenges and an arsenal of tools with which to tackle them, and then leave them to their own devices. When the player comes out the other side of an encounter (dungeon, fight, puzzle, etc.)17 for the first time, they should feel like they synthesized and used all the knowledge they had gained unto that point and that the experience enriched them.

It’s easy, in a Zelda-like game, to make this literal. Dungeon encounters often use tricks that require some special item that you only obtained at the end of the last dungeon, or somewhere in between, making it feel novel. And at the end, you get a new item and more health, literally leaving stronger than when you came. (More on this later.)

That said, your adventure grows kind of stale without some kind of narrative to push you along. The point to remember is that the two don’t live in vacuums. They are inextricably linked; propped up by each other. The story informs the game mechanics and the game mechanics express the story in a literal sense. And in the best Zelda games, “narrative” in a certain sense is superseded by the gameplay.

The “Fun Formula”

Because it’s not enough to say, “just make it fun!” I want to share a formula. This expresses the delicate balance between choice and narrative in a game, and provides a concrete way to think about each. It also makes a nice segue into our next topic.

First, to reiterate: the player’s choice makes them a hero. They must choose this adventure. The corollary to that is that you need to design an adventure that is compelling and challenging. The adventure needs to draw in the player, at the same time empowering the player through their actions. Once combined, the effect propels the player through the game world.

We can look at it this way:

(Exploration + Combat) = Player's Story
--------------------------------------------------
(Puzzles * Narrative * Quests) = Developer's Story

This is the balancing act every Zelda game pulls off, and the same one that makes imitators struggle. If these factors could actually be expressed numerically, we’d want the result to be greater than 1.

Leaning too hard on the Player’s Story can be detrimental, but won’t kill you, if your world is compelling enough (see Breath of the Wild for a Zelda example, or just about any roguelike for examples from other RPGs). Conversely, if you pull hard in the direction of the Developer’s Story, you risk losing the plot altogether. (How many times have you heard a gamer complain about fetch quests?)

So, how do we thread this needle? How do we ensure that everything remains fun and challenging and grounded in player choice without veering into Survival Game territory? How do we really capture that Zelda magic?

If “fun makes the hero” is the keystone, then what follows are the cornerstones, all of which are essential to make the final thing stand on its own.

Wrapping Up

In writing this post I’m trying to condense a notebook’s worth of notes into just a few thousand words. It’s taken much longer than I originally thought, so in the interest of actually publishing something and not holding off forever, I’ll be breaking this into parts. The next part will cover the Player’s Story, and the third part the Developer’s Story.

There’s also a tangentially-related “dungeon design tips” post in the works.

Stay tuned!

A Game in Thirty Days: Part Two

I made a game in thirty days! And now I’m writing about it. In part one of this mini-series I talked about the process of getting started: setting my goal, picking my tools, etc. Now, in part two, I’d like to talk about a few things I learned along the way.

As a quick refresher, this is the end product:

It’s a short Zelda-like action game built with GameMaker Studio 2. The game consists of a village, a dungeon, a quest, and “remembered” progression — that is, if you unlock a door or complete a puzzle, the dungeon will remember.

Lesson: Don’t just dive in

More than once, I decided what to do next and started working on it right away. The time this bit me hardest was when I originally implemented elevation changes and pits you could fall into.

Originally the game had just two elevations. Collisions worked with tile layers, one for each elevation, and had multiple tile maps for each elevation. This worked fine, but ended up being a lot more work than it needed to be: code to set depth/z-ordering based on an entity’s current elevation; code and triggers to change elevation; code to reset elevation when certain conditions were met; extra work mapping “portions” of the map; so on.

Then came time to implement pitfalls. In Zelda you can walk over a pit or hole, or knock an enemy into one, and you fall. I tried to do this using objects, collision, and triggers, and eventually got something that worked most of the time, except for if you walked funky or collided without realizing it. This ended up being frustrating if you didn’t take the happy path. I spent a lot of time tuning and tweaking these triggers. It felt like I was banging my head against GameMaker for a while.

I spent an entire day on these pits before scrapping the feature altogether.

Five days later the solution came to me, along with a way to unify both features and simplify the collision system. I spent another day doing this, as well as adding ledge jumping, while also removing large swaths of code and combining everything into a sort of “collision state machine.”

Doing this made it easier to implement all of these features, and more, with less code. The end result was more robust, required less work to build out when creating new maps, and made it easier to extend to add new features. A similar approach was used by the Pokemon games, which is where I got the idea.

Plus, it looks kind of neat.

collision tile map

The collision tile map. Each tile represents a different state or elevation.

The main lesson here? A little bit of planning can save days of work. If I had sat back and thought about this a little while before jumping in, I’d have had at least an extra day to work on other things.

Lesson: Get friendly with graph paper

Pen and paper will always be cheaper and easier to use than writing code or building tilemaps or whatever else. This is, luckily, something I did not have to learn the hard way.

Before placing a single tile in GameMaker, I drew every room of the dungeon on a graph pad. I placed doors, monsters, traps, chests, in little squares on paper, and ran through the dungeon in my imagination. Once I found a tileset to use, it was just a matter of putting the pieces together in GameMaker and running through to make sure it was all right.

Iterating on paper instead of in-game reduced the overall time spent on the project by a considerable amount.

That said, there were still a few changes made in-game once I was able to playtest the dungeon. A puzzle got scrapped, a room was rearranged, and a new room was added.

Still, pen and paper proved invaluable, and for the next steps in the project I’ve been doing almost all the up-front work on my trusty graph pad. If anything can be mapped visually or sketched up, then it’s probably worth doing that before you even think of writing code or building maps or anything of that nature.

Lesson: Waste your time wisely

I’m not an artist. In the beginning of this project I spent a little too much time trying to draw my own sprites and animations. The fourth time I scrapped everything and closed GraphicsGale in frustration, I decided it was time to find some art to use.

There’s almost too much good, free, and open art to use on the internet. You could spend hours looking through everything, which I did. The point is, as usual, just to pick something and stick with it. It’s not worth spending too much time on the visual appearance of your game at the early stages. As long as it’s tolerable, or at least the intent is clear in your presentation, it doesn’t matter how it looks until much, much later.

In the end I paid for some assets and drew some others. It’s probably clear which ones were “mine”: the slimes and the bosses don’t necessarily jive with the rest of the game’s aesthetic. But that’s fine.

Lesson: Play it!

You can’t know if your game is fun unless you play it. Not just the one room you’re working on, or the new feature you’re building and testing in your debug room.

Before releasing the demo, I went through the game beginning to end more than a dozen times. In the process I tweaked hitboxes, changed some behaviors, found some bugs (and left some bugs! for the attentive player to exploit if they want), and adjusted the difficulty.

Me, almost getting wrecked by a simple encounter.

This might have also worked against me. I was worried the game would be too easy, but the first feedback I got was exactly the opposite. One of my first players spent nearly an hour, collecting 12 heart containers and throwing 23 bombs, and still struggled with the final boss.

(This was partially due to the fight difficulty and partially due to the control scheme being a struggle, but the point stands! I added a new control scheme and it became easier for him. )

Details aside, the bottom line is this: if you’re not having fun playing in, then others won’t, either.

Wrapping Up

If nothing else, the thing to take away from all this is, “plan ahead, and plan the right way for what you’re doing.”

Or don’t. Five hours of work can save you twenty whole minutes of planning. 😉

The Game

If you want to view, download, or leave feedback for the game, click here:

A Game in Thirty Days: Part One

Recently, I was struck by that familiar urge: to make a video game. After a few hours of reading and thinking I decided I was going to jump in and do it, but this time it would be different. I would just pick a platform, start working, and make a game in thirty days.

This is the result.

As you can see it’s got a few rough edges, and it’s obviously incomplete (no title screen, no saving, etc.), but for now it’s “done” and it’s time to reflect, take away some key lessons, and move on to the next project. For the curious, I’ll put a link to the download page on Itch.io at the bottom of this post.

I want to talk about this project: how it was formed, what I learned, and what’s next. This post is part one in a series.

The Plan

Obviously, the Zelda games were a huge inspiration for this project. A Link to the Past is my favorite game in the series and in my opinion one of the greatest games of all time. I always thought that, given the rise of nostalgia titles and revivals of older genres, no one had really given ALTTP the same treatment.

(This isn’t entirely true. There have been some. But none that have really captured the essence of the games, like the two I linked above. But that’s probably a topic for another blog post.)

So I thought I should be the change I wanted to see. It was time to dig in.

Picking My Tools

In every past attempt to make a game, I always focused too hard on vague future possibilities. Not picking Tool X because I might want to do XYZ thing in the future. Or picking Tool Y because I wanted better control over ABC thing. This focus on tools, platforms, or languages limited me and doomed my projects from the beginning: by focusing too much on some nebulous definition of quality or maintainability or extensibility, the projects became about the code and not the game.

This is not to say that these things are unimportant! Just that when you’re making a game, the game comes first. If you’re not producing something that can be played, you’re not making a game. And that’s fine if the goal is to learn about specific aspects of game development, because there are a lot. But this time, my goal was to make a game.

So my mantra became make it work; make it right; make it fast.

I closed my eyes, picked an engine, and downloaded the 30 day trial of GameMaker Studio. No further thought or planning went into this, for better or worse. The important thing was to just stick with something and make a game with it.

The first week of my thirty day trial I spent learning about GameMaker Studio and GML, its scripting language. The official resources and Shaun Spalding are excellent, and I could not have done this so quickly without help from his ARPG tutorials.

Picking My Battles

After all that, the next most important thing to focus on was scope. I didn’t want this to balloon out of control and become another thing I wouldn’t finish because I decided I wanted to do more than was possible. So I decided, one dungeon. That was it. If time allowed, maybe a little more, like a village.

If I was going to stick with the Zelda format, one dungeon meant kind of a lot. Secret rooms, special items, chests, a variety of monsters, traps, a boss battle, item drops. The idea was to write out a list of these high-level ideas. Each day I would pick an item from the list and implement it.

This was a huge help even if I wasn’t completely successful at it. There are a few features I implemented that aren’t even really visible in the end product. On top of that, there are a few features I started to implement then scrapped when I realized they were too much work, or not very fun. I probably spent a week total on these things.

A few other features I started to implement, took a break, then came back and restarted with fresh eyes. Sometimes this meant throwing away everything I’d done before, and others it was just a wall I’d hit and I needed a break. Sometimes a feature I thought would take me an hour took me a day.

I wouldn’t consider any of this lost or wasted time. That’s part of making a game: if it isn’t fun, scrap it. So it was important to frequently playtest and make sure even this narrow slice of gameplay was fun and satisfying.

The Process

During the development process I kept a devlog, just kind of raw notes at the end of each day going over everything I did and what I wanted to do the next day. This was helpful for me because I could come back without that “what now?” feeling: I already knew what was next, and Past Me told Present Me exactly what it was.

I also started sharing screenshots and gifs with some friends and family over Discord and Twitter. Feedback, even if it was just “that’s cool, keep it up,” really helped keep my motivation up.

The devlog details my setbacks and triumphs. Originally I kind of wanted to post daily or weekly updates with the devlog but decided it would take too much time to clean up and post and would detract from the energy I needed to make the game. Later, I’ll clean it up and post it. I always enjoy reading other developers talk about their process and it’s always heartening to read about others facing and overcoming their own setbacks. I want to share my own experiences with that.

Next

This post is already longer than I thought it would be, so I’ll cut things short for next time, where I’ll go over some specific lessons I learned, a few techniques I used, and more.

The Game

View the game, download it, etc., below.

How to Teach Yourself to Code

Several times over the past few years I’ve been asked how I learned to code. I didn’t go to school for it, and it wasn’t originally something I aspired to do. So I never really had a good, straightforward answer, and just ended up rambling on for a while. The more I thought about it, the more I realized that my path to becoming a software developer was almost as meandering as my answers, and just as packed with fitful starts and dead ends. So, I figured I would sit down and write it down, though unlike my Teach Yourself SQL post, this post’s scope is much wider, on just how to teach yourself to code in general.

Or, more specifically, how I taught myself. Everyone learns differently, so just because something worked for me this doesn’t mean it will work for someone else. I’ll try to also include “further reading” and other types of resources that I didn’t use, but I know to be useful.

So… how do you teach yourself to code?

0. Get Very Comfortable with Google

Or your search engine of choice.

The point is that part of being a software developer, or working in any capacity with technology, is being able to find and parse information online. You need to be able to form your question in a way someone else can understand, then find the appropriate resource, then understand what you’re reading.

This might be official documentation from a company about its products. It might be a StackOverflow post, or a thread on a forum. You might need to be the one to ask the question, because it hasn’t been asked before. Which leads into the more important point, way more important than just knowing how to google something:

A fundamental part of being any good at any of this is the ability to clearly define your problem.

This will not only make it easier to find answers to your questions, but it will make it easier for you to solve your own problems. The vast majority of the work is taking a nebulously-defined problem, breaking it down into solvable chunks, and then solving those chunks. Remember word problems in your math classes in high school? It’s like that, forever.

1. Pick a Language

I know this seems like a weird first step. How do you pick a programming language if you don’t know anything about programming? In reality it doesn’t matter very much which language you pick; what matters is that you pick a language and stick with it.

This advice I drop with personal experience. The list of languages I picked up and forgot is longer than the list of languages I use today. First was Ruby, when I was 11 or 12 and building games with RPG Maker XP. Then it was C, then C++, then JavaScript… the problem was, every time I started with a new language it was like starting over. This was because I didn’t stick around long enough to master the fundamentals. Once you get the fundamentals down, then moving languages is easy. But you’ve gotta stick around long enough to do that. That’s the hard part.

That said, if I were to start again today, I’d pick one of these and stick with them.

  • C#: Developed by Microsoft. The tools are free, the documentation is extensive and detailed, and you can pretty much choose exactly how deep you want to dive here. The language and the tools have everything built-in to let you get started easily, and learn its inner workings at your own leisure. This is my favorite language, and my default when starting a new project.
  • JavaScript: If you can use a web browser, you can write and run JavaScript. Nothing extra is needed to run this code, making it the easiest to just get up and running. As a bonus, you’ll never be out of a job if you can master this language.
  • Python: Similar to JavaScript in a lot of ways, this still requires some setup before you can use it. Once set up, though, Python is another great language to start with, and perfect for building everything from small tasks to games to big web server applications.

Obviously, you should do your own research, but don’t get too deep in the weeds. Just pick a language, any language, and decide that it’s the language you’ll use to learn how to program. Some do come with a learning curve just because extra tooling might be needed to run them (C#, Python), so decide if you want to fiddle with installers or just get going (JavaScript).

2. Learn Your Fundamentals

Now it’s time to hunker down and start the real learning. I linked to some documentation for each language above, which is a great place to start.

From a bird’s-eye view, your learning path would cover:

  • Data Types: These are the building blocks of programming, and are how your code is represented to you, the coder, and how it’s interpreted by the machine. It’s the difference between an integer (1), a decimal (1.0), and regular text ("1")and how these can and can’t interact with each other.
  • Operators: These are how you set and update your data. Like mathematical operations, they let you add things together, check for equality, and more.
  • Conditions and Loops: “If-this-then-that” logic, or “for every item in this list” logic.
  • Functions / Methods: Like formulas, or small mini-programs. If data types, operators, and conditions are water, rocks, and paste, then functions and methods are the bricks that make the foundation for a program. You put everything together into a method, then call that method from other code to do a predefined set of work. Like “2+2=4”.

Remember that Google is your friend, and there are countless resources on all of the above out there. The official documentation for the languages I posted above includes info on these terms, or the resources I will link to below will guide you through them in a more structured manner.

3. Dive a Little Deeper

This is where the Computer Science comes in: algorithms and data structures.

This is a big topic. Entire textbooks are written on just this alone. The important thing to remember is that every piece of code you write comes with its own complexity. Some code will perform better than other code, and many problems can be generalized, or abstracted, and solved with algorithms that some other smart people have already figured out. Like, what’s the best way to sort a list of items of a certain type?

Anyway, here are two specific places to start:

  • Look up “Big O Notation” and how it relates to the speed or complexity of an algorithm. You don’t need to know specific algorithms to understand this. It’s a good primer on efficiency, and an important part of describing the complexity of a particular piece of software.
  • You like video games? Look up “binary space partitions” and how they’re used to generate dungeons in roguelikes. Here’s a link to check out, without any code in it. This is a great example of taking a more generalized data structure / algorithm, and applying it to the specific problem of “how do I automatically generate dungeons for my video game?”

4. Make Something

As I stressed in my SQL post, if you don’t use it, you lose it. All this reading is worthless if you don’t do anything with it. It will just fall out of your head in six months and you’ll have to start over again.

Pick a project, any project. Find a small task you do that’s repetitive and might be automated and try to automate it. Go through this list of project ideas and work down it. Build a Pong clone, or a Breakout clone. Find a textbook and do the questions at the end of each chapter.

Start small, and work your way up to bigger things. Don’t overwhelm yourself. But keep going, keep building. It’s okay to just follow tutorials and copy code as long as you’re also thinking critically about what you’re copying and why it worksand better, how you might do things differently on your own. Go past the end of the tutorial. Keep going. It’s okay to get stuck, it’s okay to break things. That’s how you learn.

But keep going. Keep building and learning and growing.

5. Read

Maybe this should have been first. Or maybe it should replace everything above. Textbooks remain the single best method of distributing and acquiring knowledge. The good ones structure themselves in a logical and approachable way so that you can start out as ignorant as the day you were born, and finish as an adept.

The only downside is that technology moves at a fast pace, and textbooks for things like specific languages might be a little outdated by the time you find them. That’s okay, really. Most languages don’t change enough for it to matter, or you could use the book’s structure to set your pace and help you find more modern materials that are available elsewhere.

Or you could focus on books that aren’t about a particular language. Some of the best books on programming are more about how to approach the work, ways to think about code, and the “soft skills” many of us lack in the industry; that is, how to navigate people, culture, and politics. Here’s a good list of these books.

6. Further Resources

Okay, you’ve made it this far, but maybe everything above is still too vague to really get started. Here’s a list of free resources designed to get you going. Most of these are structure learning, like online classes, for you to do at your own pace.

  • Harvard University’s CS50 Course: My advice above kind of contradicts this course in the sense that the course covers multiple programming languages. When in doubt, trust the professionals, because they know better than me. This course covers everything from the very basic on through to some fairly complex projects. Really, you can’t beat this. There are other universities out there like MIT that also post courses online for free.
  • /r/learnprogramming: A friendly little community with good resources and helpful community members. I just linked to the wiki, but the sub itself is great for if you have questions and for finding even more great programming links. Click around in here and you’ll definitely be able to find where to get started on just about anything.
  • The Odin Project: Everything you need to know to become a successful and well-versed web developer. A full curriculum, from start to finish.
  • Project Euler: Not necessarily a tutorial resource, but a great way to flex your math and problem solving skills. This website is a series of math problems that start fairly simple and very quickly escalate. These are a great way to get your bearing on a new language.
  • The RogueBasin Roguelike Tutorial: This is a tutorial for making a roguelike game using Python and a Python library called libtcod. It’s a great tutorial, has pointers on using Python in general, and by the end you have a fully functioning game base which you could extend, or at the very least you’ll learn a great deal about handling user input, graphics, dungeon generation algorithms, and more. It’s fun and the roguelike genre is a great playground for any developer.

That’s all, folks!

This was by no means an exhaustive how-to. Nor did it cover the actual path I took. But I started over this is how I might do it today. Learning new things is a skill all on its own. Sometimes the best thing is to just get a few pointers and go off to explore on your own. That’s how my brain works.

Custom Authorization Schemes in .Net Core 3

Recently while working on a .Net Core API project I had to add some authorization features to further protect endpoints based on user-level security. This security scheme was conceptually pretty simple, but a little complicated to implement. In the end I had to implement some custom authorization middleware myself, so I would have just the right level of granularity and control.

The Problem

The project I was working on has some fairly granular and customizable security controls originally implemented in the legacy codebase. This API needed to reimplement the same security controls for parity with the legacy codebase, so that from a user’s standpoint nothing changes at all.

To do this, I wanted to put a top-level auth check on a resource, or endpoint, so the API could reject unauthorized requests right off the bat without even thinking of going any further. A simple want, but the details were a little hairier.

In this system, each user is assigned a security group. These security groups determine the accessibility of roughly 800 controls, actions, data points, and more. This translates to roughly 800 VMAD-style permission combinations. Further, security groups were customizable per-installation. So an ADMIN at one site might be a SYSADMIN at anotheror, even if the names are the same, the permissions for the ADMIN groups at each site might be just slightly different.

This immediately ruled out any baked-in authorization feature. I couldn’t use role-based and policy-based authorization, because these rely on roles or policies to be named in a standard fashion, and for that I had zero guarantee.

Claims-based authorization was likely out. Stuffing the required data into claims data itself didn’t appeal to me. Neither did having to write out the requirements for every possible VMAD permission needed.

Fortunately, there was one constant across all this: because of the way the permission data was stored, the index of the permission would never change. So the ability to “view(44)” meant the same no matter what configurations you made.

So I decided my end goal would be simple: slap a custom authorize attribute on the endpoints that need one, and then move on. It would look like this18:

[CanView(44)]

The Solution

In the end I needed to implement my own IAuthorizationProvider, along with custom attributes and an in-memory cache storing configured security information.

I’ll show some examples for a theoretical “CanView” requirement, assuming we’re implementing a classic VMAD permission scheme with the structure I outlined above.19

Defining an Authorize Attribute

We’ll need to start with the authorization attribute first. This includes the IAuthorizationRequirement as well as a new attribute implementation.

public class CanViewRequirement : IAuthorizationRequirement
{
  public int Index { get; }

  public CanViewRequirement(int index)
  {
    Index = index;
  }
}

[AttributeUsage(AttributeTargets.Class | AttributeTargets.Method, AllowMultiple = true)]
internal class CanViewAttribute : AuthorizeAttribute
{
  const string POLICY_PREFIX = "CanView";
  
  public int Index
  {
    get
    {
      if (int.TryParse(Policy.Substring(POLICY_PREFIX.Length), out var index))
      {
        return index;
      }
      return default;
    }
    set
    {
      Policy = $"{POLICY_PREFIX}{value}";
    }
  }

  public CanViewAttribute(int index)
  {
    Index = index;
  }
}

internal class CanViewAuthorizationHandler : AuthorizationHandler<CanViewRequirement>
{
  private readonly IServiceProvider Services;

  public CanViewAuthorizationHandler(IServiceProvider services)
  {
    Services = services;
  }

  protected override async Task HandleRequirementAsync(AuthorizationHandlerContext context, CanViewRequirement requirement)
  {
    if (!context.User.Identity.IsAuthenticated)
    {
      return;
    }

    SecurityGroup security;
    using (var scope = Services.CreateScope())
    {
      var securityService = scope.ServiceProvider.GetRequiredService<MySecurityGroupService>();
      security = await securityService.GetSecurityGroupInfoAsync(context.User).ConfigureAwait(false);
    }

    if (security.CanView(requirement.Index))
    {
      context.Succeed(requirement);
    }
    else
    {
      // reject and log the request accordingly
    }

    return;
  }
}

Okay, there’s a bit going on here. First, we create a class that implements the IAuthorizationRequirement interface. The CanViewRequirement simply holds the index of the permission in our data, and implements that interface so we can use it for our AuthorizationHandler down below in HandleRequirementsAsync.

In HandleRequirementsAsync, we check an in-memory cache holding the security groups to see if the calling user’s security group does indeed have the requested permission. If so, context.Succeed(requirement) allows the request throughotherwise, we log the failed request and it’s rejected by default.

The CanViewAttribute class simply lets me set all this up as defined above, by using an attribute on a method or endpoint like this: [CanView({index})]

A note about attributes

In C# attributes can be used for metadata and code extensions. They go above your method declaration and provide helpful documentation, often extending behavior in a standardized way. It’s helpful to think of attributes as wrappers around methods, especially in this case. If you look at a method like this:

[CanView(44)]
public async Task<IActionResult> GetFooAsync()
{
  // do things
  return Ok();
}

And then unbox it, it might look something like this (pseudocode):

public async Task<IActionResult> CanGetFooAsync(int index, GetFooAsync getMethod)
{
  if (authService.IsAllowed(CanView, index))
  {
    return await getMethod;
  }
  return Unauthorized();
}

public async Task<IActionResult> GetFooAsync() 
{ 
  // do things 
  return Ok(); 
}

The Authorization Provider

All the above is well and good, but none of it does anything on its own. We have to set up a policy provider for the right code to get called when the attribute is reached. For this, we need to implement IAuthorizationPolicyProvider:

internal class VmadPolicyProvider : IAuthorizationPolicyProvider
{
  const string POLICY_PREFIX_VIEW = "CanView";
  public DefaultAuthorizationPolicyProvider FallbackPolicyProvider { get; }

  public VmadPolicyProvider(IOptions<AuthorizationOptions> options)
  {
    FallbackPolicyProvider = new DefaultAuthorizationPolicyProvider(options);
  }

  public Task<AuthorizationPolicy> GetDefaultPolicyAsync() =>
    FallbackPolicyProvider.GetDefaultPolicyAsync();

  public Task<AuthorizationPolicy> GetFallbackPolicyAsync() => 
    FallbackPolicyProvider.GetFallbackPolicyAsync();

  public Task<AuthorizationPolicy> GetPolicyAsync(string policyName)
  {
    if (policyName.StartsWith(POLICY_PREFIX_VIEW, StringComparison.OrdinalIgnoreCase) &&
        int.TryParse(policyName.Substring(POLICY_PREFIX_VIEW.Length), out var index))
    {
      var policy = new AuthorizationPolicyBuilder(JwtBearerDefaults.AuthenticationScheme);
      policy.AddRequirements(new CanViewRequirement(index));
      return Task.FromResult(policy.Build());
    }

    return FallbackPolicyProvider.GetPolicyAsync(policyName);
  }
}

All this is a semi-fancy way to generate the policies we need on an as-needed basis. Instead of hardcoding every CanViewRequirement possibility from 1 to 800, these are built for us by the attributes and requirements as we go. The interface also specifies that we add a default and fallback policy provider, from which I simply grabbed the defaults from the default, created in the class’s constructor.20

This is the ultimate goal of the code: do the work once, and use it everywhere. If we wanted to extend or refine details behind our CanView security, that is only done in one place.

Plugging it All In

Since this is .Net Core 3, we’re relying on dependency injection to keep things afloat. So we need to add services for everything we’re using here:

services.AddSingleton<IAuthorizationHandler, CanViewAuthorizationHandler>();
services.AddSingleton<IAuthorizationPolicyProvider, VmadPolicyProvider>();
services.AddAuthorization();

This tells the software that we’re using some custom authorization handlers and policy providers and points it to their definitions.

After this, using custom authorization attributes for our endpoints is a breeze. With just one line, we can narrow access to a single flag in the database out of thousands. Extending this would likewise be a breeze. Definitely easier than defining every single one manually, or crossing our fingers and hoping a security group name doesn’t change!

Wrapping Up

This may or may not be the best way to solve this particular problem. But we analyzed the trade-offs and made a calculated decision. If you were to go through and comment the code above with the intentions behind it all, I personally believe it would be easier for a new developer to hop on and get going than the alternatives. While complexity has to go somewhere, it’s better for these types of abstractions to have a gentle curve. Let someone care about the details only if they need to.

From WordPress to Pelican and Back to WordPress

This blog started out built on WordPress. For some reasons that made sense to me at the time, last year I moved everything over to a platform called Pelican.

Pelican is a static site generator that takes plain text input and converts it to web pages.  This is great for a variety of reasons, especially if you like writing in Markdown or want to keep your blog in some kind of source control.

Both of those sounded pretty neat to me and I got tired of WordPress, so I made the jump. I downloaded my WordPress installation, ran a script to convert its posts to Markdown, then tinkered with a few themes and plugins until I had something that looked fairly close to the original.

For a time, things were good. I enjoyed writing in Markdown. It took me back to the “old days” of plain text, scratching out the words without care for how they might appear. There was a kind of magic to the process. Writing, then waiting, then finally seeing the article published. All it took was Notepad++ and a command line and baby, I had a blog going.

Then I took a break. Life got in the way. I finally returned to add new posts, but when it came time to publish I actually forgot for a moment what the damn tool was even called. Then I forgot the command line options. Then I forgot where the output went. Most recently, I tried linking one article to another and this caused the generator to throw new errors. I googled around for about ten minutes before thinking, “I don’t have time for this.”

So instead of fixing that problem I spent an evening restoring WordPress. If you’re curious, here’s how to do it like I did:

  • Create a brand new WordPress installation
  • Google “export pelican to wordpress”, then wonder if you have your old backup still
  • Find the backup *.tar.gz file and poke around its contents
  • Upload everything over FTP
  • Play Master of Orion while you wait for 3,500+ files to upload
  • Update wp-config to point to the new database
  • Drop all the tables and recreate them with the old WordPress DB table contents
  • Find the functions.php file for your theme and add a few lines of code to programmatically update all mentions of the old URL to the new URL
  • Refresh the login page about 5 times
  • Log in and update WordPress
  • Update hyperlinks in posts
  • Copy-paste the Pelican posts into WordPress posts

And voila! It’s like I never left WordPress! Except for all the times I linked to the old old blog, then destroyed them by moving to Pelican, and then destroyed those links by moving again over here. One day I’ll write a redirect so folks following those old links will come here, instead. Another day.

Mang 1.0 is Released

As part of my ongoing work with SCOREDIT, I’ve been working on porting some old code to a new utility for use in my newer project as well as a few other things I’ve got going on. To that end, I released Mang (Markov Name Generator), a tool for generating names and words.

Sigh… A procrastinator’s work is never done…

Mang uses Markov chains to generate output that is similar to, but not the same as, a given set of inputs. This means if you feed it a dictionary of English words, it will output words that look like English but are just a little bit off. This is great for building up conlangs, creating NPC names for your tabletop games, etc.

The library comes “batteries included,” meaning it already has a small collection of names you can use for name generation. The readme has more details on this. You can also browse the source to see what all is available.

I’ve had the old Mang lying around for a long time gathering dust. Built with WPF, it was serviceable and the output was okay. But I wanted to extract the Markov and name generation code and make it into something more portable. I was also frequently unhappy with the output, hitting the refresh button forever until I found something inspiring.

The new Mang has a few improvements to word generation to ensure no gibberish is put out. The library itself is tiny – just a few files. And its interface is small and foolproof.

To prove all these things to myself I plugged it into SCOREDIT today and got to generating:

Mang used with SCOREDIT to generate words

As you can see, it’s not all perfect, but there’s a few good ones in there to serve as starting points. In the future I plan to extend the generation capabilities to come up with more “realistic” output, but that’s another blog post.

Head on over to the repo to check it out!

SCRL: Week 06

After motivation petered off, it was easy to rationalize not doing anything on this project. The excuses rolled in: what’s the point, it will never make money; no one will play it; making games fun is hard. Etc.

Times like these, I remind myself when motivation wanes, it’s usually because of a good reason. I’d hit a wall, and it had nothing to do with the excuses I was making. After some thought and false starts, I finally found out what was happening: working on SCRL was no longer fun.

Above all else this project is supposed to be fun for me. It’s a side project for a game that likely no one will ever play but me. So why not make it fun just for me? And why not work on the things that are fun and interesting to me? With that in mind, I thought about what I dreaded doing the most for the project, then thought of a way to make it fun for myself to do it.

Enter… SCOREDIT! (I am not good at naming things.)

SCOREDIT is a GUI application to add and edit game data, from NPCs to game regions (dungeons and towns) to treasure drops. A few semi-difficult decisions were made in the process of setting this up:

  • The GUI will be written in WPF.
  • The CSV files are getting replaced with a SQLite database.

I went with WPF because I know it and can move relatively quickly with it. SQLite (along with Dapper) will make it so I worry less about how I’m serializing/deserializing data and more about the data itself. Plus, most of the data does require some kind of relational integrity, such as monsters referencing aspects, treasure classes, and other monsters. Using a proper mini-database will make it harder for me to shoot myself in the foot.

a screenshot of SCOREDIT

Nothing pretty, but that’s not the goal here. So far it’s purely UI. I’m using this as a kind of mockup phase, where as I think of attributes or pieces of data to add, I add the boxes for them. Then, once I’m done, I’ll write up the database to back it. After that, I’ll rewire SCORLIB to talk to the database instead of the CSV files.

So far, for the screen above what I like the most is the auto-generation of stats. Of course, this could be done at runtime, but I like to tweak things beforehand and I don’t want to rely too much on in-game random generation for things like this. The plan is to choose a monster type — is it a tank? magic user? a speed demon? — and adjust its stat distribution accordingly. When I was still staring at the CSV files, manually choosing and writing out stats was one of the things I dreaded most.

This UI is bound to change quite a bit before it’s finished.