Introduction

Mímir is a contextual query engine for video games with dynamic events (e.g. dialog, animations) driven by their current world's state.

    use subtale_mimir::prelude::*;

    // create a rule requiring that five enemies have been killed
    let mut rule = Rule::new("You killed 5 enemies!");
    // Rule<&str, f64, FloatEvaluator, &str>
    rule.insert("enemies_killed", FloatEvaluator::EqualTo(5.));

    // create a more specific rule that also requires at least 2 doors to have been opened
    let mut more_specific_rule = Rule::new("You killed 5 enemies and opened 2 doors!");
    more_specific_rule.insert("enemies_killed", FloatEvaluator::EqualTo(5.));
    more_specific_rule.insert("doors_opened", FloatEvaluator::gte(2.));

    // bundle the rules into a ruleset
    let ruleset = Ruleset::new(vec![rule, more_specific_rule]);

    // run a query against the ruleset
    let mut query = Query::new();
    // Query<&str, f64>
    query.insert("enemies_killed", 2.5 + 1.5 + 1.);

    assert_eq!(
        ruleset.evaluate(&query).unwrap().outcome,
        "You killed 5 enemies!"
    );

    // run a more specific query against the ruleset
    let mut more_specific_query = Query::new();
    more_specific_query.insert("enemies_killed", 2.5 + 1.5 + 1.);
    more_specific_query.insert("doors_opened", 10.);

    assert_eq!(
        ruleset.evaluate(&more_specific_query).unwrap().outcome,
        "You killed 5 enemies and opened 2 doors!"
    );
    ```

High-level overview

Queries

Your game's world is defined as a collection of facts: the player killed x amount of enemies, an NPC has opened y amount of doors, the player is currently near z NPC, etc.

In Mímir, facts are collected together into a map (Query), where the key is the unique identifier of the fact, and the value is the fact's value.

Rules and evaluators

Also, your game will (most likey!) have predefined rules that define behaviour that should occur when one or more facts are true. We represent rules as a map (Rule), where the key is the unique identifier of the fact, and the value is a predicate (Evaluator) that is evaluated against the fact's value.

Rulesets

Finally, rules can be stored together in collections known as rulesets (Ruleset). Rulesets allow a query to be evaluated against many rules at once: Mímir will always look to match a query against the rule in the ruleset with the most requirements (i.e. more specific).

ℹ️ If multiple rules with the same specificity are matched within a ruleset, one is chosen at random.

Inspiration

Mímir is heavily inspired (both in concept and general architecture) by Elan Ruskin's amazing session from GDC 2012 on AI-driven Dynamic Dialog:

Fundamentally speaking, Mímir is simply a Rust implementation of Elan's proposed system for dynamic dialog. However, Mímir does offer some differences and/or extensions that cater specifically to games developed internally at Subtale.

Tutorial (WIP)

This guide serves as a tutorial for newcomers to Mímir; a hypothetical scenario is established for a game and then an exemplar, step-by-step implementation is provided.

Scenario

You're working on a game that is an "open world": more specifically, there is a non-linear quest tree (i.e. the player is free to explore and start/complete quests as they please).

As a game designer, you've decided that you'd like your game's dialogue to be more "aware" of what has happened. You'd like NPCs to make different remarks depending on what the player has/hasn't already done.

This scenario can be easily achieved with Mímir; let's get started!

Steps

Installation

Start off by adding Mímir to your project's Cargo.toml, including the optional float feature (whose relevance will be explained later):

[dependencies]
subtale-mimir = { version = "0.5.1", features = ["float"] }

Changelog

Visit the releases page on GitHub for a list of all historical releases.

v0.5.1 (2023-08-19)

• Upgraded indexmap to 2.0 and criterion to 0.5
• Migrated from Nextra to mdBook for docs site

v0.5.0 (2023-04-15)

• Added Query::with_capacity
• Added prelude module (use subtale_mimir::prelude::*)
• Implemented benchmark for ruleset evaluation performance
• Created devcontainer configuration for GitHub codespaces development
• BREAKING: Moved float-related features to separate module (subtale_mimir::float)
• Upgraded indexmap to 1.9.3 and pnpm (for docs site) to 8.1.0
• Implemented benchmark for ruleset instantiation (and sorting) performance
• Added missing Rust documentation
• Refactored codebase into separate modules (rule => query, rule, ruleset)
• Changed Ruleset::sort to use .sort_unstable_by_key (~10% performance improvement)

v0.4.0 (2023-02-27)

• Migrated library to Cargo workspace for future modularity
• Replaced usage of BTreeMap with IndexMap
• BREAKING: Renamed Criterion to Requirement
• Created initial version of this website
• Added example use case to website (loading screen tips)
• Reworked structs to support generic fact value type
• Implemented trait-based system for evaluating requirements
• BREAKING: Renamed Ruleset::from to Ruleset::new
• BREAKING: Renamed many functions names to be more "idiomatic" (mirroring Rust's standard library)
• Renamed Cargo.toml crate name from mimir to subtale-mimir (due to crates.io clash)
• Added justfile for dev/build tasks
• Added Subtale's opinionated rustfmt configuration
• Migrated documentation site from JavaScript to TypeScript
• Added check against query length during rule evaluation (for performance)

v0.3.0 (2022-12-16)

Refactored to use generics for fact identifiers/names (Query => Query<FactKey>, Rule<T> => Rule<FactKey, Outcome>, Ruleset<T> => Ruleset<FactKey, Outcome>).

v0.2.0 (2022-12-12)

Introduced Criterion::NotEqualTo(f64) for defining criteria for facts that don't equal a supplied floating-point number.

v0.1.0 (2022-12-12)

Initial pre-release of Mímir.

Evaluator

An evaluator is a trait that represents a predicate function evaluating against a value.

trait Evaluator<T> {
    fn evaluate(self, value: T) -> bool;
}

Specifically, in the context of Mímir, an evaluator checks if the value of a fact about the game's current state matches a certain condition.

You can choose to create your own implementation of the trait, or use the provided FloatEvaluator implementation (see below) that allows you to evaluate floating-point numbers (Rust's f64 type).

Real world

In the real world, an evaluator represents a condition that must be true for a contextual event to take place. However, events will typically have many evaluators that need to evaluate to true, not just one!

ℹ️ An NPC might query Mímir to ensure that they're only commenting on another NPC's behaviour if they've not exhibited the same behaviour previously (to avoid being hypocritical).

FloatEvaluator

⚠️ To use the pre-made FloatEvaluator implementation, you must enable the float feature in your project's Cargo.toml:

[dependencies]
subtale-mimir = { version = "0.5.0", features = ["float"] }

The FloatEvaluator is a built-in implementation of the Evaluator<T> trait, allowing you to define evaluators that match against floating-point numbers.

enum FloatEvaluator {
    EqualTo(f64),
    NotEqualTo(f64),
    LessThan(FloatRangeBound),
    GreaterThan(FloatRangeBound),
    InRange(FloatRangeBound, FloatRangeBound),
}

If you're interested in how we've implemented the Evaluator<f64> trait for FloatEvaluator, check out the source code on GitHub!

ℹ️ FloatRangeBound is an enum that holds a boundary value that can be inclusive (FloatRangeBound::Inclusive(f64)) or exclusive (FloatRangeBound::Exclusive(f64)).

Helper functions

Several helper functions are exposed to easily instantiate FloatEvaluator with common equality expressions:

ℹ️ FloatEvaluator::range is designed to mimic the functionality of Python's built-in range function.

Floating-point equality

Internally, Mímir's FloatEvaluator uses the float-cmp crate to perform approximate comparisons when FloatEvaluator::EqualTo or FloatEvaluator::NotEqualTo are evaluated.

Query

A query is a collection of facts about the current game world's state.

Mímir represents these facts in Rust as an IndexMap<FactKey, FactType>, where the FactKey generic type indicates the unique name of the fact, and the FactType generic type indicates the type of the fact's value.

struct Query<FactKey, FactType>
where
    FactKey: std::hash::Hash + std::cmp::Eq,
{
    facts: IndexMap<FactKey, FactType>,
}

Rule

A Rule is a collection of facts and their evaluators (requirements) stored in a map, along with a specific outcome (Outcome). All evaluators in the rule must evaluate to true for the rule itself to be considered true.

struct Rule<FactKey, FactType, FactEvaluator: Evaluator<FactType>, Outcome>
where
    FactKey: std::hash::Hash + std::cmp::Eq,
{
    marker: PhantomData<FactType>,
    evaluators: IndexMap<FactKey, FactEvaluator>,
    pub outcome: Outcome,
}

Evaluation

Rules can be evaluated against queries to determine if they are true given the current game world's state:

let mut rule = Rule::new(true);
rule.insert("enemies_killed", FloatEvaluator::eq(5.));

let mut query = Query::new();
query.insert("enemies_killed", 2.5 + 1.5 + 1.);

assert!(rule.evaluate(&query));

In the above example, the rule evaluates to true for the supplied query because it's expecting 5 enemies to be killed (enemies_killed), and the query confirms the fact that 5 (2.5 + 1.5 + 1) have been killed.

ℹ️ Our generic outcome type (Outcome) for the example is just a standard boolean value (true). In the real-world, you'd probably use a more complex enum to denote different types of outcome (e.g. dialog, animation).

Insertion order

Mímir stored rule facts and evaluators inside an IndexMap which preserves the insertion order of evaluators.

This distinction is important because it allows you to extract more performance when evaluating rules by ensuring that your "namespace" facts are inserted into the rule first.

For example, imagine a scenario where you're using Mímir to handle character dialog. By establishing a fact that identifies who's speaking (e.g. "speaker"), and having the evaluator for the speaker at the beginning of each rule, you can improve performance substantially (because the rule will stop iterating over its remaining evaluators if it finds one that evaluates to false).

Ruleset

Rulesets are collections of rules, represented in Rust as Vec<Rule<...>>.

struct Ruleset<FactKey, FactType, FactEvaluator: Evaluator<FactType>, Outcome>
where
    FactKey: std::hash::Hash + std::cmp::Eq,
{
    rules: Vec<Rule<FactKey, FactType, FactEvaluator, Outcome>>,
}

ℹ️ Check out the ruleset storage section on the performance page for further details on how Mímir represents rulesets in Rust to improve performance when evaluating queries against them.

Evaluation

Just like rules, rulesets can be evaluated against queries to determine if they are true given the current game world's state:

let mut rule = Rule::new("You killed 5 enemies!");
rule.insert("enemies_killed", FloatEvaluator::EqualTo(5.));

let mut more_specific_rule = Rule::new(
    "You killed 5 enemies and opened 2 doors!"
);
more_specific_rule.insert("enemies_killed", FloatEvaluator::EqualTo(5.));
more_specific_rule.insert("doors_opened", FloatEvaluator::gt(2.));

let ruleset = Ruleset::new(vec![rule, more_specific_rule]);

let mut query = Query::new();
query.insert("enemies_killed", 2.5 + 1.5 + 1.);

assert_eq!(
    ruleset.evaluate(&query).unwrap().outcome,
    "You killed 5 enemies!"
);

let mut more_specific_query = Query::new();
more_specific_query.insert("enemies_killed", 2.5 + 1.5 + 1.);
more_specific_query.insert("doors_opened", 10.);

assert_eq!(
    ruleset.evaluate(&more_specific_query).unwrap().outcome,
    "You killed 5 enemies and opened 2 doors!"
);

In the above example, we define a ruleset with two rules. Both rules require that 5 enemies have been killed, but one rule is more specific (also requiring that more than 2 doors have been opened).

The first query evaluates to the simpler rule, because the query does not satisfy the doors opened requirement. However, the second query evaluates to the more complex rule because the query does satistfy the doors opened requirement.

ℹ️ In the second query, although the simpler rule is satisfied, Mímir does not evaluate it as true because it's less specific (i.e. contains fewer evaluators).

Loading screen tips

For as long as most gamers can remember, video games have offered tips and hints on loading screens (and various other game states inbetween gameplay, e.g. lobbies).

This page describes an example implementation of Mímir providing hints that dynamically change based on game events that have recently happened (or are about to happen).

Outcome type

In this use case, our outcome type will be an enum (Outcome) with one variant (Tip) that contains the tip's message (String) and the ID (usize, for simplicity) of the model that we want to render alongside the tip (à la Bethesda titles):

enum Outcome {
    Tip { message: String, model_id: usize },
}

Defining some tips

Now let's define some tips (represented as rules in Mímir):

use subtale_mimir::prelude::*;

let mut just_died = Rule::new(Outcome::Tip {
    message: "Have you tried, like, not dying?".into(),
    model_id: 123,
});

let mut finished_level_three = Rule::new(Outcome::Tip {
    message: "Thought that was hard? You ain't seen nothing yet...".into(),
    model_id: 456,
});

ℹ️ In a production environment (i.e. distributing your game), it makes more sense to serialize your tips during development and include them in your distributed assets, ready to be deserialized at runtime!

Adding requirements

Without evaluators (requirements), these tips are pretty useless. Let's add some!

⚠️ The FloatEvaluator implementation used in this example requires enabling the float feature in your project's Cargo.toml!

just_died.insert(
    "player_just_died",
    FloatEvaluator::EqualTo(1.),
);

finished_level_three.insert(
    "last_level_completed",
    FloatEvaluator::EqualTo(3.),
);

// Your game needs to maintain the values of `player_just_died` and
// `last_level_completed`: this logic is outside of Mímir's scope!

ℹ️ In the above example, we mimick a bool by checking if the float's value is equal to 1.0 (FloatEvaluator::EqualTo(1.)).

Alternatively, you could write your own implementation of Evaluator that can evaluate boolean values.

Bundling the tips

Now let's bundle the tips into a ruleset so we can evaluate them all against our game's current state in a performant manner:

let tips = Ruleset::new(vec![just_died, finished_level_three]);

⚠️ As outlined on the performance page, invoking Ruleset::new is expensive!

Instead of creating the ruleset each time your game enters a loading screen state, you should setup your ruleset once during your game's initial load.

Retrieving a valid tip

Now that are tips are stored in a rulset, we can evaluate the ruleset (supplying our game's current state as a query) and see if any of our tips are applicable!

let mut current_state = Query::new();
query.insert("player_just_died", 1.);
query.insert("last_level_completed", 4.);

let tip = tips.evaluate(&current_state);
// Some(Rule { outcome: { message: "Have you tried, like, not dying?" }})

No valid tips

You may find that there are no valid tips based on what you've defined and your game's current state; this is completely normal behaviour!

Ruleset::evaluate returns an Option<Rule<...>: this means that you can use a match expression and perform some alternative logic if no matching tip is found (i.e. pick from a selection of predefined, generic tips).

Multiple valid tips

It's also a reasonable expectation that there will be times when your game's current state matches multiple tips that you've defined.

Out-of-the-box, Mímir will evaluate to a randomly chosen rule in a ruleset if multiple are evaluated as true.

Alternatively, you can use Ruleset::evaluate_all(&current_state) to return a Vec<Rule<...>>: this means that you can iterate over all of the rules that Mímir evaluated as true (none, one, or many).

Repeated evaluations

As you start to delve into Mímir, you'll probably come across a scenario where you only want a rule to be evaluated once (or n amount of times).

There a few different solutions to achieve this functionality, which we'll explore on this page.

Removing from the ruleset

The naive approach would be to mutate the ruleset after evaluation to remove the rule that shouldn't be repeated. However, this approach has multiple drawbacks (and we don't recommend that you go down this route in your implementation).

Firstly, as explained on the performance page, creating (and modifying) a ruleset is expensive, because it needs to be (re)sorted in such a way that evaluations are more performant.

Also, as described on the serialization page, we recommend that your implementation uses serialized rulesets that are bundled as assets alongside your game's executable and then deserialized at runtime. By introducing the logic of removing rules after evaluation, you will also need to re-serialize your ruleset and overwrite your persistent assets.

Storing evaluation history

We recommend that you track which rules are evaluated by Mímir (and potentially how many times they are evaluated) and store this data alongisde the rest of your game's persistent state (e.g. a save file).

With this tracking system established, you can add evaluators to your rules that check if the rule hasn't been evaluated before.

You'll need to implement the logic that populates every query made during evaluations with the history of what rules have been evaluated.

Performance (WIP)

Ruleset storage

Because Mímir evaluates rulesets by returning the most specific rule for a given query, the rules are stored in descending order of requirement count. This avoids scanning the entire ruleset for matching rules, as the first rules in the underlying collection are the most specific.

However, this does mean that care should be taken when invoking ruleset.append(...) to introduce more rules into a ruleset, as this function also triggers the underlying collection to be sorted again after the new rules are appended.

ℹ️ In production, we recommend that rulesets are only manipulated during your game's loading state, and then only evaluated during your game's main loop.

Multiple rulesets

Where possible, you should look to divide your game's entire database of rules into smaller rulesets that can be loaded in and out of memory depending on the game's current state.

For example, you might want to partition your rules into individual rulesets for each level/map/region of your game. Otherwise, you'll be subjecting yourself to an unnecessary performance cost by having Mímir evaluate rules that have no relevance to the game's current state.

ℹ️ The specific implementation of a system as described above is outside the scope of Mímir.

Serialization

Evaluators (including the FloatEvaluator implementation), rules, and rulesets are all (de)serializable using serde if you enable the respective feature in your project's Cargo.toml:

[dependencies]
subtale-mimir = { version = "0.5.1", features = ["serde"] }

This makes it easy for you to serialize rulesets into a persistent medium (i.e. files) during your game's development process, bundle them with your game, and deserialize them at runtime.

ℹ️ This also means that Mímir can effortlessly support modding by allowing you to deserialize and load user-defined rulesets at runtime.