Bequestor:
A Versatile Quest System

Custom parameters

Only being able to create prerequisites or objectives of 4 preset types can be very limiting. Any specific game would have unique kinds of prerequisites and objectives that need to be specified. The Quest Creator tool allows for this through custom types and parameters. Let's open the tool, import our batman_quests.json, and update it to use custom prerequisites and objectives. I'll remove the second "Kill Creatures" objective, and replace it with a custom objective. We name the custom type "Do Nothing" (to become Batman, one must be patient). Now we can add any number of custom parameters. For each of these parameters we can specify a type, name, and value. Let's add a float named "seconds" and give it a value of 5.0. We must do nothing for 5 seconds. Let's also add a custom prerequisite. To start the quest, we can't have walked more than 10 steps. Let's export it again, and overwrite the batman_quests.json file.

In order to use these custom prerequisites and objectives in our own game implementation, we'll need to create our own PrerequisiteChecker and ObjectiveChecker. Let's start with the PrerequisiteChecker. Implementing the PrerequisiteChecker interface requires us to implement the IsSatisfied() function. We'll make our own MaxDistanceWalkedChecker as follows:

class MaxDistanceWalkedChecker : public Bequestor::PrerequisiteChecker
{
public:
  inline MaxDistanceWalkedChecker(int const& distanceWalked) : distanceWalked(distanceWalked) {}

  bool IsSatisfied(Bequestor::Prerequisite const& prereq) const override;

private:
  int const& distanceWalked;
};

When implementing the IsSatisfied() function, we can get the values of our custom variables through the templated Prerequisite::Get() function. In this case, we get an integer for the specified "steps" parameter.

bool MaxDistanceWalkedChecker::IsSatisfied(Bequestor::Prerequisite const& prereq) const
{
return distanceWalked < prereq.Get<int>("steps");
}

Prerequisites don't keep track of their own state, so instead we provide a reference to a variable in game and save it in a member variable.

Now we just need to register this checker to our QuestManager. For this we can use the WithCustomPrerequisiteChecker() function, which takes a string for the name of the checker (this needs to be equal to the custom type name specified in the quest creator), and a shared pointer to your PrerequisiteChecker. We can register the checker as follows (where the distanceWalked variable is a context variable known by my game):

questManager = make_shared<QuestManager>(
  QuestManager()
    /*(with preset checkers)*/
    .WithCustomPrerequisiteChecker("Walked At Most", make_shared<MaxDistanceWalkedChecker>(distanceWalked))
);

In the demo game, you can see from the two images below that now the quest only shows up in the quest log if the player hasn't walked more than 10 steps.

Now we do still have the problem that as soon as the quest starts, we are spammed with the following console messages:

It appears we need to create a custom ObjectiveChecker, too. When implementing the ObjectiveChecker interface, we need to implement both the OnEvent() and IsSatisfied() functions. To accurately measure time, I'm also keeping track of some variables using std::chrono.

class DoNothingObjectiveChecker : public Bequestor::ObjectiveChecker
{
public:
  DoNothingObjectiveChecker();

  void OnEvent(Bequestor::Objective const& objective, Bequestor::ObjectiveEvent const& event) override;
  bool IsSatisfied(Bequestor::Objective const& objective) const override;

private:
  bool started = false;
  std::chrono::high_resolution_clock::time_point lastTime;
  float secondsPassed = 0.0f;
};

Before implementing these functions, let's see what kind of events we will be sending. We want the time to continuously update when the player does nothing, but to reset if the player does something. Let's distinguish between doing something or nothing with an event parameter. When we do nothing on a frame, we send an event as follows:

void Game::Update(float dt)
{
  Bequestor::ObjectiveEvent didNothingEvent = Bequestor::ObjectiveEvent("Do Nothing");
  didNothingEvent.AddParameter("Did Something", false);
  Notify(didNothingEvent);
}

"Do Nothing" is simply the objective type name. We specify this so the quest manager can find the attached ObjectiveChecker. We also attach a boolean parameter that we give the name "Did Something". We send an event with a different value for this boolean whenever the player moves or interact.

void Game::handleKeyboardInput()
{ // (if the player moves or interacts:)
  Bequestor::ObjectiveEvent didNothingEvent = Bequestor::ObjectiveEvent("Do Nothing");
  didNothingEvent.AddParameter("Did Something", true);
  Notify(didNothingEvent);
}

Now we can handle this event in our DoNothingObjectiveChecker::OnEvent() function. We use the started boolean just so the timer starts running when the first event is caught. We also set an objective state variable, named "seconds". We will have to make sure to register this variable later. Finally, I'm using the std::chrono namespace.

void DoNothingObjectiveChecker::OnEvent(Objective const& objective, ObjectiveEvent const& event)
{
  if (!started || event.Get<bool>("Did Something"))
  {
    objective.state->Set("seconds", 0.0f);
    lastTime = high_resolution_clock::now();
    if (!started) started = true;
  }
  else
  {
    float secondsPassedSinceLastEvent = duration<float>(high_resolution_clock::now() - lastTime).count();
    objective.state->Set("seconds", secondsPassedSinceLastEvent);
  }
}

We also have to implement the IsSatisfied() function, where we simply compare our state variable to the "seconds" specified in the quest creator (5, in our case):

bool DoNothingObjectiveChecker::IsSatisfied(Objective const& objective) const
{
  return objective.state->Get<float>("seconds") >= objective.Get<float>("seconds");
}

Finally, we register our custom ObjectiveChecker to our QuestManager analogous to how we did it for the custom PrerequisiteChecker, by using the QuestManager::WithCustomObjectiveChecker function, which again takes a string referring to the custom type name, and a shared pointer to this time an ObjectiveChecker, but there is one more optional parameter for state parameters and their staring values. We can name these parameters anything we want, and the type is automatically inferred. We simply name it the same as our objective parameter, "seconds", with a starting value of 0.0f (indicating it's a float). This is the state variable we were updating in our DoNothingObjectiveChecker::OnEvent() function. Below is the code used to register our custom ObjectiveChecker.

questManager = make_shared<QuestManager>(
  QuestManager()
  /*(with preset checkers and custom prerequisite checker)*/
  .WithCustomObjectiveChecker("Do Nothing", make_shared<DoNothingObjectiveChecker>(), {{"seconds", 0.0f}})
);

Below is a screenshot of my demo game showing the custom objective in progress.

Objective dependencies

What if we want objectives that depend on one another, or that can branch, have multiple ways of completion? For this we can use objective dependencies. Let's say to complete the quest, the player either has to wait 5 seconds, or they have to talk to Alfred and kill a bat. Either way they have to travel outside of the cave to the grassy area to complete the quest.

We open back up the quest in the quest creator. We add objectives for killing a bat, and reaching the grass area. Different dependencies represent branches; the current objective can only be started if either of these dependencies is complete. Within a dependency, we can specify multiple objectives that all need be complete for the entire dependency to be complete. So, for the "Travel Place" quest, we press the little "+/-" icon to add or remove objectives to our first dependency, and we add the "Do Nothing" objective. Then we add a new dependency, press the "+/-" icon for that dependency, and add both the "Talk to Alfred" and "Kill a bat" objectives. The numbers behind the objective correspond to its ID; make sure you pick the right ones. Finally, we need to mark all objectives but the "Travel Place" objective as "optional", otherwise the quest will not be marked as complete until all objectives are complete, regardless of their individual dependencies. We export once again as batman_quests.json

With these new objectives, we need to make sure we actually send events when we travel to a place, but other than that, we won't have to change anything in the demo game.

void Game::handleAreaUpdates()
{
  // (...)
  Notify(Bequestor::ObjectiveEvent::MakeLocationEvent(area.name));
  // (...)
}

In the demo game, you can see as long as the player hasn't done nothing for 5 seconds and also hasn't both talked to Alfred and killed a bat, the "Travel Place" objective displays a "DEPENDENCIES NOT MET" message. Otherwise, the "Travel Place" objective is active, and the quest will complete upon entering the grass.

Import

Under the hood, importing a quest is done using the nlohmann/json library [1]. My JSON reader is mostly hardcoded based on the quest JSON structure. The conversion from string to enum can easily be done using the NLOHMANN_JSON_SERIALIZE_ENUM macro.

NLOHMANN_JSON_SERIALIZE_ENUM(QuestStatus,
  {{QuestStatus::UNAVAILABLE, "Unavailable"},
   {QuestStatus::CAN_START, "Can Start"},
   {QuestStatus::STARTED, "Started"},
   {QuestStatus::CAN_FINISH, "Can Finish"},
   {QuestStatus::FINISHED, "Finished"},
   {QuestStatus::CANCELLED, "Cancelled"}});

Reading in the JSON itself, in turn, is quite easy with the nlohmann library. Below is my ReadQuests() function implementation:

vector<Quest> JsonReader::ReadQuests(string const& filepath /*...*/)
{
  vector<Quest> quests = {};
  ifstream f(filepath);

  if (!f.is_open())
  {
    cerr << "error opening file." << endl;
    return quests; 
  }

  json questsJson = json::parse(f);
  for (json const& questJson : questsJson["quests"])
  { 
    Quest quest; quest.id = questJson["id"].get<int>();
    quest.name = questJson["name"];
    quest.description = questJson["description"];
    //(...)
    quests.push_back(quest);
    shared_ptr<Quest> questPtr = make_shared<Quest>(quest);
  }

return quests;
};

PrerequisiteChecker Implementation

Under the hood, to keep track of different prerequisite checkers, I use a Command Pattern [2]. The base class PrerequisiteChecker is an interface with a single virtual IsSatisfied() function that returns a boolean. This interface is implemented for specific checkers, such as the IdAmountPrereqChecker class. This takes a std::function<unsigned int(std::string const&)> idAmountQuery and is used for the item PrerequisiteChecker. The other preset PrerequisiteCheckerss work similarly. Below is the IsSatisfied() implementation. The templated Get() function will be explained in the section on custom parameters.

bool IdAmountPrereqChecker::IsSatisfied(Prerequisite const& prereq) const
{
  unsigned int currentAmount = idAmountQuery(prereq.Get<string>(string(PROP_PREREQ_ID)));
  unsigned int targetAmount = static_cast<unsigned int>(prereq.Get<int>(string(PROP_PREREQ_AMOUNT)));

  return currentAmount >= targetAmount;
}

The QuestManager keeps track of a hashmap of each of its PrerequisiteCheckers: std::unordered_map<std::string, std::shared_ptr<PrerequisiteChecker>> prereqCheckers;. When the QuestManager::WithItemChecker() function is called, a new IdAmountPrereqChecker is created with the function provided, and an entry is added to the hashmap for the string "Has Items". Then on Update(), for each of the inactive quests' prerequisites, based on the type (converted to a string), the the PrerequisiteChecker is found in the hashmap, and its IsSatisfied() function is executed (see the code under the Custom Checkers section).

Event System Implementation

Under the hood, Bequestor uses an Observer pattern [3]. An EventDispatcher keeps track of a set of Observers and when its Notify() function is called, it calls OnNotify() on all of its Observers.

From that point on, it works similarly to prerequisites. QuestManager saves a hashmap of ObjectiveCheckers: std::unordered_map<std::string, std::shared_ptr<ObjectiveChecker>> objectiveCheckers;. For the preset objectives, since these don't require a specific query, these are already automatically created in the QuestManager's constructor.

QuestManager::QuestManager()
{
  //(...)
  objectiveCheckers.insert({OBJECTIVE_TYPE_TO_STRING.find(ObjectiveType::ITEM)->second, make_shared<IdAmountObjectiveChecker>()});
  objectiveCheckers.insert({OBJECTIVE_TYPE_TO_STRING.find(ObjectiveType::CREATURE_KILL)->second, make_shared<IdAmountObjectiveChecker>()});
  objectiveCheckers.insert({OBJECTIVE_TYPE_TO_STRING.find(ObjectiveType::LOCATION)->second, make_shared<IdObjectiveChecker>()});
  objectiveCheckers.insert({OBJECTIVE_TYPE_TO_STRING.find(ObjectiveType::NPC)->second, make_shared<IdObjectiveChecker>()});
}

In QuestManager::OnNotify(), for each of the active quests' objectives, the ObjectiveChecker is found in the hashmap and its OnEvent() function is executed, passing along the event parameter. Furthermore, in the QuestManager::Update() function, for each of the active quests' objectives, the IsSatisfied() function is executed.

Custom Parameters

Under the hood, for objects with custom parameters, I use a Parameterized class. In here, I simply keep track of a hashmap which maps from the paramater name to its value. Its value is stored as an std::variant, and a templated Get() function is used to retrieve the value of the correct type. Prerequisites as well as Objectives extend this Parameterized class. Below is the Parameterized implementation:

class Parameterized
{
public:
  void AddParameter(std::string name, std::variant<std::string, int, unsigned int, float, bool> value)
  {
    parameters.insert({name, value});
  };

  template <typename Type>
  Type Get(std::string name) const
  {
    return std::get<Type>(parameters.at(name));
  };

  // (...)

private:
  std::unordered_map<std::string, std::variant<std::string, int, unsigned int, float, bool>> parameters;
};

Custom Checkers

In order to find the right PrerequisiteChecker or ObjectiveChecker in the appropriate hashmap, each custom checker is saved under its prerequisite/objective's custom type name (where preset checkers simply map from their enum to their index string). As an example of how this is used, see the QuestManager::checkPrerequisitesForQuest() implemenation:

bool QuestManager::checkPrerequisitesForQuest(Quest const& quest) const
{
  for (auto const& prereq : quest.prerequisites)
  {
    string const& prereqStr = prereq->type == PrerequisiteType::CUSTOM ? prereq->customType : PREREQ_TYPE_TO_STRING.find(prereq->type)->second;
    auto const& result = prereqCheckers.find(prereqStr);
    if (result == prereqCheckers.end())
    {
      cerr << "No prerequisite checker for " << prereqStr << " exists." << endl; 
      return false; 
    }
    else if (!(result->second->IsSatisfied(*prereq))) return false;
  }
  return true;
}

State Parameters

Custom objectives can also come with custom state parameters. These are registered along with the ObjectiveChecker. They are saved in a multimap in QuestManager that maps from the custom type to the parameters. These custom parameters are then passed along to the JsonReader::ReadQuests function. Only in here are they actually added to the objective state as the objectives are read in.

vector<shared_ptr<Objective>> readObjectives(json objectivesJson,
                unordered_multimap<string, pair<string, variant<string, int, unsigned int, float, bool>>> const& extraParameters)
{
  vector<shared_ptr<Objective>> objectives;
  for (json const& objectiveJson : objectivesJson)
  {
    shared_ptr<Objective> objective = make_shared<Objective>();
    objective->type = objectiveJson["type"].get<ObjectiveType>();
    // (...)
    readParameters(objectiveJson["parameters"], objective);

    if (objective->type == ObjectiveType::CUSTOM)
    {
      objective->customType = objectiveJson["custom_type"];

      auto its = extraParameters.equal_range(objective->customType);
      for (auto& it = its.first; it != its.second; it++)
      objective->state->AddParameter(it->second.first, it->second.second);
    }

    objectives.push_back(objective);
  }
  // (...)
  return objectives;
}

Dependencies

Under the hood, dependencies are stored as sets of sets of pointers to objectives: std::set<std::set<std::shared_ptr<Objective>>> dependencies; For each of the objectives, we set a status to UNAVAILABLE at the start. Then for each of the unavailable objectives, we execute QuestManager::objectiveDependenciesAreMet(), and if this returns true, we set the objective status to ACTIVE. I can make use of the std::all_of() and std::any_of() algorithms to easily specify that the dependencies are met if for any of them, all of the associated objectives are complete.

bool QuestManager::objectiveDependenciesAreMet(Objective const& objective, Quest const& quest) const
{
  return any_of(objective.dependencies.cbegin(),
                objective.dependencies.cend(),
                [&completedObjectives](set<shared_ptr<Objective>> const& dependency)
                {
                  return all_of(dependency.cbegin(),
                                dependency.cend(),
                                [](shared_ptr<Objective> const& objective)
                                { return objective->state->status == ObjectiveStatus::SATISFIED; });
                });
}