Writing a Fuzzy Pattern Matcher in C#

A Blog Post and Video Spark an Idea

By sheer coincidence, I came across a blog post written for Starsector. Called “You Merely Adopted Rules.csv, I Was Born Into It”. The basic idea is that we have a dialog that queries the world state and based on the world state certain dialog is shown or not shown. While being in the dialog and talking the system also can write to the world state and add data that can be relevant later or only limited to the current dialog.

The same post mentions a video by Left for Dead developer that implemented a dynamic voice over system where characters can react to what is happening. This includes how gets attacked by what, where someone gets attacked, what other NPCs stand nearby, how much health is left, which NPCs already died, etc. Again it’s all about the current game state that gets used to dispatch certain actions based on the conditions that are met.

I found the idea that we can dispatch actions based on current state interesting. Creating complex branching trees of dialog/events is not easy. Especially when we write video games where the tree gets reworked every so often and adding new branching becomes cumbersome.

A Code Example

Imagine we want to trigger an event based on current world state from a list of events and use the one that triggers the most conditions.

// Traditional approach with deeply nested conditions
if (player.Level >= 10 &&
    player.HasItem("MagicSword") && 
    !questLog.IsCompleted("DragonSlayer") &&
    world.TimeOfDay == "Night" &&
    player.Location == "MysticalForest" &&
    player.Health > 50 &&
    player.MagicPoints >= 30 &&
    !player.HasStatusEffect("Cursed") &&
    player.Reputation > 100)
{
    // Trigger special encounter with ancient dragon
    SpawnAncientDragon();
}

Using my created fuzzy-pattern matcher. We abstract a condition as a Criteria and bundle them in a Rule that if the most conditions in the Rule list (not every condition) are met, executes its payload SpawnAncientDragon()

We decouple where the data comes from, the criteria only care for the key, we could use a dictionary. Your own object or what ever.

var gameEvents = new List<Rule>
{
    // It's the most specific rule, requiring 9 conditions to be met.
    new Rule(
        new List<ICriteria>
        {
            new Criteria<int>("PlayerLevel", level => level >= 10),
            new Criteria<List<string>>("PlayerItems", items => items.Contains("MagicSword")),
            new Criteria<List<string>>("CompletedQuests", quests => !quests.Contains("DragonSlayer")),
            new Criteria<string>("TimeOfDay", time => time == "Night"),
            new Criteria<string>("Location", loc => loc == "MysticalForest"),
            new Criteria<int>("Health", health => health > 50),
            new Criteria<int>("MagicPoints", mp => mp >= 30),
            new Criteria<List<string>>("StatusEffects", effects => !effects.Contains("Cursed")),
            new Criteria<int>("Reputation", rep => rep > 100)
        },
        // This is the action to execute when the rule is the best match.
        () => SpawnAncientDragon()
    ) { Priority = 10 }, 
    // High priority because it's a special event.
    // We use priority to select the rule with the highest priority when two rules with the same number of 
    // critera met

    // A second, less specific rule. Only requires the player to be in the forest at night.
    // This demonstrates how the matcher can fall back to a less perfect match.
    new Rule(
        new List<ICriteria>
        {
            new Criteria<string>("Location", loc => loc == "MysticalForest"),
            new Criteria<string>("TimeOfDay", time => time == "Night")
        },
        () => SpawnGoblinAmbush()
    ) { Priority = 1 } // Lower priority.
};

Here is a conceptual example building a dummy query.

var playerStateForGoblins = new Query()
    .Add("PlayerLevel", 3) // Too low for dragon
    .Add("PlayerItems", new List<string> { "Wooden Shield" }) // No MagicSword
    .Add("CompletedQuests", new List<string>())
    .Add("TimeOfDay", "Night") // Matches both
    .Add("Location", "MysticalForest") // Matches both
    .Add("Health", 80)
    .Add("MagicPoints", 10) // Too low for dragon
    .Add("StatusEffects", new List<string>())
    .Add("Reputation", 10); // Too low for dragon

//  The matcher will find the dragon rule matches only 2/9 criteria.
//  The goblin rule matches 2/2 criteria.
//  Even though the match count is the same, the goblin rule is a "perfect" match
//  for its own criteria, while the dragon one is not. The system will favor
//  the rule that is most completely fulfilled. If both were equally fulfilled,
//  it would fall back to priority.
playerStateForGoblins.Match(gameRules);

Try it Yourself

I uploaded a C# library to NuGet here and a JavaScript implementation can be found here.