Quests ~ Prerequisite System Redesign

Overview

The current quest prerequisite system is extremely limiting. Right now, quest prerequisites only consist of stat requirements (health and level requirements) that are stored in the stat_req_t struct. We intend to change this system into a fully-fledged prerequisite system that also allows tasks and quests to be pre-requisites of other quests, which is a key feature in RPG games. Additionally, we intend to expand this system's use-cases. Right now, the stat requirement system isn't fully integrated into the Quest module. Even though all of the functions for initializing and checking stat requirements exist, they are never called. This redesign will involve reworking these checks to work with the new quest and task prerequisites and then implementing these checks into the quest completion checks (more info below). Lastly, this redesign will also expand the prerequisite system to work for achievements in addition to quests. By allowing achievements to have other achievements and quests as prerequisites separate from the overall quest tree, complex quest structures, such as quests involving non-linear achievements, become possible.

Structure Changes

Old Structures

Right now, the prerequisite system consists of the following stat_req struct:

typedef struct stat_req {
    int hp;
    int level;
} stat_req_t;

Where stat_req_t objects are then stored in the quest struct and not in the task struct:

typedef struct quest  {
    UT_hash_handle hh;
    char *quest_id;
    achievement_tree_t *achievement_tree;
    reward_t *reward;
    stat_req_t *stat_req;
    int status;  
} quest_t;

typedef struct task {
    mission_t *mission;
    char *id;
    bool completed;
} task_t;

New Structures

First, we want to replace the stat_req struct with the following more general prereq struct that supports our new features

typedef struct prereq {
    int hp;
    int level;
    id_list_t *task_list;
    id_list_t *quest_list;
} prereq_t;

Note the use of a new id_list_t type, which is a reference to a new linked-list struct of string ids, the current format for quest and task ids that are used for searching in other places in the quest module. The id_list struct should be defined as below:

typedef struct id_list {
    id_list_node_t *head;
    int length;
} id_list_t;

typedef struct id_list_node {
    long int id;
    id_list_node_t *next;
} id_list_node_t;

Additionally, references to this new prereq struct should be added to the quest and task structs. The revised structs should look as follows:

typedef struct quest  {
    UT_hash_handle hh;
    char *quest_id;
    task_tree_t *task_tree;
    reward_t *reward;
    prereq_t *prereq;
    int status;  
} quest_t;

typedef struct task {
    mission_t *mission;
    char *id;
    prereq_t *prereq;
    bool completed; 
} task_t;

Other Changes

Obviously, implementation functions need to be added/adjusted to help manage (create, initialize, free, etc) the new data structures. Other than that, there are a couple of other tweaks that are necessary to accommodate this new system.

Currently, stat requirements are checked by the int can_start_quest(quest_t *quest, player_t *player) function. Since the new prerequisite system requires checking these requirements both for quests and for tasks, we propose removing this function and replacing it with int meets_prereqs(prereq_t *prereq, player_t *player). By taking a prereq_t * instead of a quest_t *, the same function can be used for checking prerequisites for both quests and tasks.

Right now, there is a find_task(task_tree_t *tree, char *id) function that searches for a task in a given task_tree and there is no means of searching for a quest. This is not enough functionality, as, since this new prerequisite system involves storing a linked list of only quest/task ids, the ability to search through all of the player's quests and all of the player's tasks without the presence of a specific tree is necessary to find the quests and tasks that need to be checked for completion. The implementation of these searches will be largely dependant on how quests are implemented in the player struct, but the interface should appear as follows:

// The original find_task() function
task_t *find_task_in_quest(task_tree_t *tree, char *id);

// Searches all of the player's tasks for a specific task
task_t *find_task(player_t *player, char *id);

// Searches all of the player's quests for a specific quest
quest_t *find_quest(player_t *player, char *id);

Potential Areas For Improvement

This implementation doesn't allow tasks to be associated with their quest in any way, so searching for tasks will involve searching every task on every quest tree for every quest that the player has, which will be a performance cost. It is worth considering adding a new linked list type for tasks that also includes a separate quest id so the search is limited to only a single quest.