LibMozok

LibMozok is a universal quest engine for games. This library implements a system heavily inspired by "Hierarchical generation of dynamic and nondeterministic quests in games".

Mozok, derived from the Ukrainian word "мозок" meaning "brain."

Table of contents

• Introduction
  • Showcase
  • Example #1
  • Example #2
• Further Reading
• Prerequisites
• Installation
• References
• Licenses

Introduction

LibMozok is an experimental quest system for games. It is a universal library, capable of handling quests of various kinds and genres—whether they are linear or non-linear, big or small, connected or independent.

Quests are modeled as a set of preconditions, goals, and actions. Players start in an initial state and, through actions applied to the world, work to achieve (or fail) the quest goals. Depending on the current state of the world, the library determines if a quest goal is achievable, builds a quest plan (a list of actions to achieve the goal), and, if necessary, automatically triggers sub-quests.

To assist with world-building tasks, LibMozok introduces a specially designed .quest format for quest projects and very simple API to handle quest-related problems.

Showcase

LibMozok generates a plan for a quest in real-time and detects when the quest becomes unsolvable:

From: https://github.com/zegalur/libmozok-godot

Example #1

While journeying to visit a distant relative, the princess has been captured by trolls in the forest. You are a brave knight who must find and save the princess. You are in the town now. You need to go to the castle, take your sword, travel to the forest, free the princess, and guide her back to the castle.

The first example is a simple quest with one goal and no sub-quests. Here is how the .quest file for this quest could look like (some parts of the file are omitted; for the full file, see save_princess.quest):

# ...

object knight : Knight
object princess : Princess

# ...

# Quest initial state.
rlist Initial:
    # All characters are alive.
    Alive(knight)
    Alive(princess)
    # ...

    # Roads between the places:
    # [ Forest ] <-=-> [ Town ] <-=-> [ Castle ]
    Road(forest, town)
    Road(town, forest)
    Road(town, castle)
    Road(castle, town)
    # ...

    # Initial locations.
    At(knight, town)
    At(princess, forest)
    # ...


# Travel from place A to place B by the road.
action TravelTo:
    player : Player
    location_A : Location
    location_B : Location
    pre At(player, location_A)
        Road(location_A, location_B)
        Alive(player)
    rem At(player, location_A)
    add At(player, location_B)

# Player takes a sword.
action TakeSword:
    player : Player
    sword : Sword
    location : Location
    pre At(player, location)
        At(sword, location)
        Alive(player)
    rem At(sword, location)
    add Has(player, sword)

#...

# One main quest.
main_quest SaveThePrincess:
    preconditions:
        # none
    goal:
        At(princess, castle)
    actions:
        KillEnemy
        TravelTo
        Guide
        Free_3
        TakeSword
    objects:
        knight
        bigSword
        princess
        troll_1
        troll_2
        troll_3
        castle
        town
        forest
    subquests:
        # none

And this is how a plan for the SaveThePrincess quest at the initial state may look like:

TravelTo ( knight, town, castle )
TakeSword ( knight, bigSword, castle )
TravelTo ( knight, castle, town )
TravelTo ( knight, town, forest )
KillEnemy ( knight, bigSword, troll_1, forest )
KillEnemy ( knight, bigSword, troll_2, forest )
KillEnemy ( knight, bigSword, troll_3, forest )
Free_3 ( knight, princess, troll_1, troll_2, troll_3, forest )
Guide ( knight, princess, forest, town )
Guide ( knight, princess, town, castle )

The player is allowed to perform any possible actions, not just those from the plan. Each action will change the quest world state, triggering the replanning of the quest. For example, if the player travels to the forest first, the planner will add a new action to the front of the plan:

TravelTo ( knight, forest, town )
...

When the player reaches the goal of the quest (either by following the plan or through some other combination of actions), the library will mark the quest as DONE. If the player's actions make it impossible to reach the goal, the library will mark the quest as UNREACHABLE, etc.

Example #2

"A farmer with a wolf, a goat, and a cabbage must cross a river by boat. The boat can carry only the farmer and a single item. If left unattended together, the wolf would eat the goat, or the goat would eat the cabbage. How can they cross the river without anything being eaten?" [Wikipedia Link]

LibMozok can handle more complex "puzzle-like" quests. An example of this is the famous Wolf-Goat-Cabbage Problem. You can find a working wolf_goat_cabbage.quest file in the src\libmozok\tests\puzzles directory, along with some other examples.

The possible winning plan for this quest at the initial state may look like this:

MoveLoad1 ( human, left, right, goat, wolf, cabbage )
MoveFree1 ( human, right, left, goat, wolf, cabbage )
MoveLoad2 ( human, left, right, wolf, cabbage, goat )
MoveLoad2 ( human, right, left, goat, wolf, cabbage )
MoveLoad2 ( human, left, right, cabbage, goat, wolf )
MoveFree2 ( human, right, left, wolf, cabbage, goat )
MoveLoad3 ( human, left, right, goat, wolf, cabbage )

Unfortunately, for now, libmozok is not powerful enough to solve more combinatorically complex puzzles. Libmozok is suitable for planning quests in real-time for games, but it is not intended to be a universal puzzle-solving library. An example of almost too complex puzzle is game_of_fifteen.quest.

Further Reading

• Getting Started:
  • Under Construction
• Demo Projects:
  • https://github.com/zegalur/libmozok-godot
• Manual:
  • .quest Format Reference
  • Doxygen auto-generated reference
• Other:
  • Hierarchical generation of dynamic and nondeterministic quests in games
  • STRIPS

Prerequisites

LibMozok is written in C++, using CMake as a build tool, and VSCode as the default development environment. To set up the development environment, make sure you have the following prerequisites installed:

• Core API Requirements:
  • C++11 compatible compiler
  • CMake (version 3.29 or higher)
  • Doxygen
• Highlight support for .quest files:
  • VSCode (version 1.89 or higher)

Installation

How to build and install libmozok (Release):

1. Navigate to the build directory:
   cd [WorkDir]/libmozok/build

2. Run CMake to configure the project:
   cmake ../src

3. Build the project:
   cmake --build . --config Release

4. Install the project:
   cmake --install . --config Release

5. You should now have the non-empty lib/ and include/libmozok/ directories inside the install directory.

References

• Soares de Lima, Edirlei & Feijó, Bruno & Furtado, Antonio. (2014). Hierarchical Generation of Dynamic and Nondeterministic Quests in Games. ACM International Conference Proceeding Series. 2014. 10.1145/2663806.2663833. Web. https://www.researchgate.net/publication/286454232_Hierarchical_Generation_of_Dynamic_and_Nondeterministic_Quests_in_Games

• Lacan, Olivier. Keep a Changelog. 5 Mar. 2023. Web. https://keepachangelog.com/en/1.1.0/

• Preston-Werner, Tom. Semantic Versioning. Web. https://semver.org/spec/v2.0.0.html

• Kolpackov, Boris. P1204R0: Canonical Project Structure, 8 Oct. 2018. Web. https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1204r0.html

Licenses

All files on this repository are subject to the MIT license. Please read the LICENSE file at the root of the project.