Quests ~ Design Document - uchicago-cs/chiventure GitHub Wiki
This page specifies the structures and functionality of the quests module.
Quest functionality and structs have drastically changed, so that quests can actually work and be integrated into Chiventure. Quests have been refactored from the previous quests_structs and quests_state files into files that document each part of the feature. The design document follows this refactoring:
Prerequisites
We designed the prerequisite system, so that quests and tasks can requires other quests/tasks to be completed before allowing a player to obtain or complete them. Previous, there was a stat_req of only hp and level that would determine if a player could begin a quest./*
* A single quest/task id node for the linked list
*/
typedef struct id_list_node {
char *id;
struct id_list_node *next;
} id_list_node_t;
/*
* A linked list of quest/task ids
*/
typedef struct id_list {
id_list_node_t *head;
int length;
} id_list_t;
/*
* This struct represents a prerequisite for a quest or task.
*
* Components:
* hp: health points
* level: a number of levels gained
* task_list: a list of task ids that will all be checked for completion
* quest_list: a list of quest ids that will all be checked for completion
*/
typedef struct prereq {
int hp;
int level;
id_list_t *task_list;
id_list_t *quest_list;
} prereq_t;
/* prereq initialization */
/*
* Creates a new prereq object on the heap
*
* Parameters:
* - hp: health points required to begin quest
* - level: level required to begin quest
*
* Returns: a pointer to the newly allocated prereq, or NULL if there was an error
*/
prereq_t *prereq_new(int hp, int level);
/*
* Initializes a prereq object with the given parameters
*
* Parameters:
* - prereq: The prereq getting initialized
* - hp: health points required to begin quest
* - level: level required to begin quest
*
* Returns:
* - SUCCESS for successful init
* - FAILURE for unsuccessful init
*/
int prereq_init(prereq_t *prereq, int hp, int level);
/*
* Frees a prereq struct from memory including the task list and quest list.
*
* Parameter:
* - prereq: the prereq to be freed
*
* Returns:
* - SUCCESS for successful free
* - FAILURE for unsuccessful free
*/
int prereq_free(prereq_t *prereq);
/*
* Creates a new id_list object on the heap
*
* Returns: a pointer to the newly allocated id_list, or NULL if there was an error
*
*/
id_list_t *id_list_new();
/*
* Initializes an id_list as an empty list
*
* Parameters:
* - id_list: The id_list getting initialized
*
* Returns:
* - SUCCESS for successful init
* - FAILURE for unsuccessful init
*/
int id_list_init(id_list_t *id_list);
/*
* Frees an id_list from memory
*
* Parameter:
* - id_list: the id_list to be freed
*
* Returns:
* - SUCCESS for successful free
* - FAILURE for unsuccessful free
*/
int id_list_free(id_list_t *id_list);
/*
* Adds an id to an id_list
*
* Parameters:
* - id_list: The id_list getting added to
* - id: A pointer to a string id getting added
*
* Returns:
* - SUCCESS if successfully added
* - FAILURE if something went wrong
*/
int id_list_add(id_list_t *id_list, char *id);
/*
* Adds a task id to a prereq's task id list
*
* Parameters:
* - prereq: The prereq getting added to
* - task_id: A pointer to a string id getting added
*
* Returns:
* - SUCCESS if successfully added
* - FAILURE if something went wrong
*/
int prereq_add_task(prereq_t *prereq, char *task_id);
/*
* Adds a quest id to a prereq's quest id list
*
* Parameters:
* - prereq: The prereq getting added to
* - quest_id: A pointer to a string id getting added
*
* Returns:
* - SUCCESS if successfully added
* - FAILURE if something went wrong
*/
int prereq_add_quest(prereq_t *prereq, char *quest_id);Task
Task, previously known as achievements was also changed a lot this quarter. Tasks now requires prerequisites, and they can also give rewards when completed. Like before, tasks require the completion of a mission. The previous mission struct utilized a union of passive and active missions, but when one was set NULL, the other would also which defeated the whole purpose of missions. We changed the mission struct to be a mission type which would dictate what the player needed to do to complete it (i.e. interact with a NPC)./* An enum representing the possible mission types currently supported */
typedef enum mission_types {
MEET_NPC,
KILL_NPC,
COLLECT_ITEM,
VISIT_ROOM,
} mission_types_t;
/*
* This struct represents a mission.
*
* Components:
* - target_name: The name of the mission's target (ie the NPC's name, the item's name, etc)
* - type: The type of
*/
typedef struct mission {
char *target_name;
mission_types_t type;
} mission_t;
/*
* This struct represents a reward for completing a quest or task.
*
* Components:
* xp: an xp amount gained
* item: an item gained
*/
typedef struct reward {
int xp;
item_t *item;
} reward_t;
/*
* This struct represents a task.
*
* Components:
* mission: mission to be completed
* id: string identifier for the task
* reward: reward for completing the task.
* prereq: prerequisite for beginning a task
*/
typedef struct task {
mission_t *mission;
char *id;
reward_t *reward;
prereq_t *prereq;
} task_t;
/*
* This is a non-binary tree struct of tasks (to replace linked list)
*
* Components:
* task: task in tree
* parent: parent node of task
* rsibling: the nearest right-hand sibling of the task node
* lmostchild: the leftmost child of the task node
*/
typedef struct task_tree {
task_t *task;
struct task_tree *parent;
struct task_tree *rsibling;
struct task_tree *lmostchild;
} task_tree_t;
/* task functionality */
/* Creates a new mission struct (allocates memory)
*
* Parameters:
* - target_name: The name of the mission's target (the NPC's name, the item's name, etc)
*
*
* Returns: a pointer to the newly allocated mission, that is not completed
*/
mission_t *mission_new(char *target_name, mission_types_t type);
/* Initialize an already allocated mission struct
*
* Parameters:
* - mission: an already allocated mission_t
* - target_name: the name of the mission's target (NPC, item, etc)
* - type: The type of mission
*
* Returns:
* - SUCCESS for successful init
* - FAILURE for unsuccessful init
*
* Note: Also ensures that the mission only includes a single thing to do. If
* there is more than one pointer that is not NULL (excluding mission),
* this function will return FAILURE.
*/
int mission_init(mission_t *mission, char *target_name, mission_types_t type);
/*
* Frees a mission struct from memory
*
* Parameter:
* - mission: the mission to be freed
*
* Returns:
* - SUCCESS for successful free
* - FAILURE for unsuccessful free
*/
int mission_free(mission_t *mission);
/* Creates a new reward struct for completing a quest
*
* Parameters:
* - xp: xp reward
* - item: item reward
*
* Returns: a pointer to the newly allocated reward struct
*/
reward_t *reward_new(int xp, item_t *item);
/* Initializes an already allocated reward struct
*
* Parameters:
* - xp: xp reward
* - item: item reward
*
* Returns:
* - SUCCESS for successful init
* - FAILURE for unsuccessful init
*/
int reward_init(reward_t *rewards, int xp, item_t *item);
/* Creates a new task struct (allocates memory)
*
* Parameters:
* - id: the id of the task
* - mission: the mission to be completed for the quest
* - reward: the reward of the task
* - prereq: the prerequisite of the task
*
* Returns: a pointer to the newly allocated task that is not completed
*/
task_t *task_new(char *id, mission_t *mission, reward_t *reward, prereq_t *prereq);
/*
* Initialize an already allocated task struct
*
* Parameters:
* - task: an already allocated task
* - id: the id of the task
* - mission: the mission to be completed for the task
* - reward: the reward of the task
* - prereq: the prerequisite of the task
*
* Returns:
* - SUCCESS for successful init
* - FAILURE for unsuccessful init
*
* Note: Also returns FAILURE if there is both a mission and prereqs. Missions should all be in their own tasks.
* If you want a task to have a mission and a prereq, make the mission's tasks a prereq for the actual task
* that has the prereqs.
*/
int task_init(task_t *task, char *id, mission_t *mission, reward_t *reward, prereq_t *prereq);
/*
* Frees a task struct from memory but does not free
* its associated pointers
*
* Parameter:
* - task: the task to be freed
*
* Returns:
* - SUCCESS for successful free
* - FAILURE for unsuccessful free
*/
int task_free(task_t *task);
/*
* Frees a task tree struct from memory b
*
* Parameter:
* - task_tree: the task to be freed
*
* Returns:
* - SUCCESS for successful free
* - FAILURE for unsuccessful free
*/
int task_tree_free(task_tree_t *task_tree); Quests
We changed the quest struct marginally. The main point of difference was that the `quest_id` is now a string and we have prereqs instead of stat_reqs./*
* This is the hashtable struct for a quest
* Elements:
* quest_id: the id of the quest
* task_tree: non-binary tree struct holding a tree of
* tasks that make up a quest
* reward: reward of the quest is either experience, an item, or both
* stat_req: stat requirement for the quest
*/
typedef struct quest {
char *quest_id;
task_tree_t *task_tree;
reward_t *reward;
prereq_t *prereq;
UT_hash_handle hh;
} quest_t;
/* Creates a new quest struct (allocates memory)
*
* Parameters:
* - quest_id: string representing the specific quest_id
* - reward: reward of the quest is an item
* - prereq: prerequisites for the quest
*
* Returns: a pointer to the newly allocated quest, with default status of 0
* (not started)
*/
quest_t *quest_new(char *quest_id, reward_t *reward, prereq_t *prereq);
/* Initialize an already allocated quest struct
*
* Parameters:
* - q: an already allocated quest
* - quest_id: string representing the specific quest_id
* - reward: reward of the quest is an item
* - prereq: prerequisites for the quest
*
* Returns:
* - SUCCESS for successful init
* - FAILURE for unsuccessful init
*
*/
int quest_init(quest_t *q, char *quest_id, reward_t *reward, prereq_t *prereq);
/*
* Frees a quest struct from memory including the task list
* and reward, but otherwise does not free associated pointers
*
* Parameter:
* - quest: the quest to be freed
*
* Returns:
* - SUCCESS for successful free
* - FAILURE for unsuccessful free
*/
int quest_free(quest_t *quest);Quest Hash Tables
Integration of quests into Chiventure depends upon holding quests in a hashtable. When a game is started, there is a global hash table of all the quests and tasks in the game. As the player goes through the game, they will pick up quests and tasks, but they will not necessary have all the quests/tasks available in the game. This is why we made a distinction between player quests/tasks and the game ones. We also rewrote many of the hash table functions, so that they were properly working./*
* This typedef distinguishes between quest_t pointers
* which are used to point to quest_t structs in the
* traditional sense and those which are used to hash
* quest_t structs with the UTHASH macros as specified
* in include/common
*/
typedef struct quest quest_hash_t;
/*
* A task hash table. Uses a wrapper instead of adding the hash
* handle to the task struct as with quests since for some reason,
* adding the hash handle to the task struct causes crashes and odd
* behavior.
*/
typedef struct task_hash {
task_t *task;
char *id;
UT_hash_handle hh;
} task_hash_t;
/* Stores important information necessary for the majority of quest functions */
typedef struct quest_ctx {
player_t *player;
quest_hash_t *quest_hash;
} quest_ctx_t;
/* Allocates memory for and initializes a new quest_ctx object
*
* Parameters:
* - player: a player
* - quest_hash: A quest hash table, ideally game->all_quests
*
* Returns:
* - A pointer to an initialized quest_ctx_t object
*/
quest_ctx_t *quest_ctx_new(player_t *player, quest_hash_t *quest_hash);
/* Initializes a new quest_ctx object
*
* Parameters:
* - quest_ctx: An already allocated quest_ctx object
* - player: a player
* - quest_hash: A quest hash table, ideally game->all_quests
*
* Returns:
* - SUCCESS if initialized successfully, FAILURE if any problems occured
*/
int quest_ctx_init(quest_ctx_t *quest_ctx, player_t *player, quest_hash_t *quest_hash);
/* Frees a quest_ctx object, but does not free the player or quest hash in the obejct
*
* Parameter:
* - quest_ctx: The quest_ctx to be freed
*
* Returns:
* - SUCCESS if freed successfully, FAILURE if an error occured
*/
int quest_ctx_free(quest_ctx_t *quest_ctx);
/*
* Helper function to compare two tasks.
*
* Parameters:
* - a1, a2: the two tasks to be compared
*
* Returns:
* - 0 if the tasks are the same
* - 1 otherwise
*/
int compare_tasks(task_t *a1, task_t *a2);
/*
* Traverses the task tree to find the task with the
* given string identifier along a valid quest path.
*
* Parameters:
* - tree: pointer to the task tree to be traversed
* - id: pointer to a string identifier for the desired task
*
* Returns:
* - pointer to the tree immediately containing the task, OR
* - NULL if task cannot be found along a valid path
*
* Note: Traversal no longer relies on task completion, so
* runtime is now O(T) where T is the number of tasks
* in the game
*/
task_tree_t *find_task_tree_of_task_in_tree(task_tree_t *tree, char *id);
/* Gets a quest from the given hash table
*
* Parameters:
* quest_id: the quest's id string
* hash_table: a hashtable of quests, ideally from game_state
*
* Returns:
* quest struct if successful, NULL if quest is not found
*/
quest_t *get_quest_from_hash(char *quest_id, quest_hash_t *hash_table);
/* Gets a task tree who's immediate task has a given id from the given hash table
*
* Parameters:
* id: the task tree's immediate task's id string
* hash_table: a hashtable of quests, ideally from game_state
*
* Returns:
* task_tree struct if successful, NULL if task is not found
*/
task_tree_t *get_task_tree_from_hash(char *id, quest_hash_t *hash_table);
/* Gets a task from the given quest hash table
*
* Parameters:
* id: the task's id string
* hash_table: a hashtable of quests, ideally from game_state
*
* Returns:
* task struct if successful, NULL if task is not found
*/
task_t *get_task_from_quest_hash(char *id, quest_hash_t *hash_table);
/* Finds the element with the given id in the task hash
*
* Parameters:
* id: the id string searching for
* hash_table: a hashtable of tasks
*
* Returns:
* task hash struct if successful, NULL if id is not found
*/
task_hash_t *search_task_hash(char *id, task_hash_t *hash_table);
/* Gets a task from the given task hash table
*
* Parameters:
* id: the task's id string
* hash_table: a hashtable of tasks
*
* Returns:
* task struct if successful, NULL if task is not found
*/
task_t *get_task_from_task_hash(char *id, task_hash_t *hash_table);
/* Adds a quest to the given hash table
*
* Parameters:
* quest: pointer to quest struct
* hash_table: pointer to a hashtable of quests, ideally from game_state
*
* Returns:
* SUCCESS if successful, FAILURE if failed
*/
int add_quest_to_hash(quest_t *quest, quest_hash_t **hash_table);
/* Adds a task to the given task hash table
*
* Parameters:
* task: pointer to task struct
* hash_table: pointer to a hashtable of tasks
*
* Returns:
* SUCCESS if successful, FAILURE if failed
*/
int add_task_to_hash(task_t *task, task_hash_t **hash_table);
/* Gets a player quest from the given hash table
*
* Parameters:
* quest_id: the quest's id string
* hash_table: a hashtable of player_quests from the player
*
* Returns:
* player_quest struct if successful, NULL if the quest is not found
*/
player_quest_t *get_player_quest_from_hash(char *quest_id, player_quest_hash_t *hash_table);
/* Gets a player task from the given hash table
*
* Parameters:
* id: the task's id string
* hash_table: a hashtable of player_tasks from the player
*
* Returns:
* player_task struct if successful, NULL if the task is not found
*/
player_task_t *get_player_task_from_hash(char *id, player_task_hash_t *hash_table);
/* Adds a player quest to the given player's player quest table
*
* Parameters:
* - quest: pointer to quest struct
* - qctx: pointer to quest context struct with info on player and all quests
* - completion: the completion status of the quest
*
* Returns:
* SUCCESS if successful, FAILURE if failed
*/
int add_quest_to_player(quest_t *quest, quest_ctx_t *qctx, int completion);
/* Adds a player task to the given hash table
*
* Parameters:
* task: pointer to task struct
* qctx: pointer to quest context struct with information about player and all quests
*
* Returns:
* SUCCESS if successful, FAILURE if failed
*/
int add_task_to_player_hash(task_t *task, quest_ctx_t *qctx);
/* Removes a quest from a hash table
*
* Parameter:
* - pointer to a quest hash table
* - quest ID,
*
* Returns:
* - FAILURE if the removal was failure, SUCESS if successful
*/
int remove_quest_in_hash(quest_hash_t **hash_table, char *quest_id);
/* Returns the (now NULL) hash table after deleting and freeing
* all quests
*
* Parameter:
* - pointer to a hash table
*
* Returns:
* - FAILURE if the removal was failure, SUCESS if successful
*/
int remove_quest_all(quest_hash_t **hash_table);
/* Removes a task from a task hash table
*
* Parameter:
* - pointer to a task hash table
* - task ID,
*
* Returns:
* - FAILURE if the removal was failure, SUCCESS if successful
*/
int remove_task_in_hash(task_hash_t **hash_table, char *id);
/* Returns the (now NULL) hash after deleteting and freeing
* all tasks
*
* Parameter:
* - pointer to a task hash table
*
* Returns:
* - FAILURE if the removal was failure, SUCCESS if successful
*/
int remove_task_all(task_hash_t **hash_table);
/* Removes a task from a player hash table
*
* Parameter:
* - pointer to a player task hash table
* - quest ID,
*
* Returns:
* - FAILURE if the removal was failure, SUCESS if successful
*/
int remove_task_in_player_hash(player_task_hash_t **ptasks, char *quest_id);Quest Functionality
Found in the `quests_state` module, these are functions that have to do with the way quests work. We added a lot of features this year that would allow the player to actually complete quests/tasks. If the player had the necessary prereqs, they would be able to automatically finish the quest/task. A few of the functions in this list also deal with NPCs.typedef struct item_wrapped_for_llist item_list_t; // Forward declaration
/* Determines whether a player completed a mission (if possible for that mission type)
*
* Parameters:
* - mission: a mission object
* - player: a player
*
* Returns:
* - true if the player completed the mission, false if not
*/
bool completed_mission(mission_t *mission, player_t *player);
/* Checks if a player completed a given task
* - Always returns false if the task has a mission and checks the
* prerequisite if it does not
*
* Parameter:
* - task: pointer to the task
* - player: pointer to player with the task
*
* Returns:
* - false if task is incomplete
* - true if task is complete
*/
bool is_task_completed(task_t *task, player_t *player);
/* Checks a task's status.
*
* Parameter:
* - task: pointer to a task
* - player: pointer to player with the task
*
* Returns:
* - the task's completion for the given player (true = complete, false = incomplete)
*/
bool get_player_task_status(task_t *task, player_t *player);
/* Adds the contents of a reward struct to the player struct
*
* Parameters:
* - reward: the reward getting accepted
* - qctx: pointer to the quest context struct with information on player and all quests
*
* Returns:
* - SUCCESS if added successfully, FAILURE if an error occured
*/
int accept_reward(reward_t *reward, quest_ctx_t *qctx);
/* Checks a task for completion and accepts th reward if it is
*
* Parameters:
* - task_id: The string id of the task getting checked
* - qctx: A quest context containing the player and a list of all quests
*/
void update_task(char *task_id, quest_ctx_t *qctx);
/*
* Determines whether a player meets a set of prerequisites
*
* Parameters:
* - prereq: a prerequisite object
* - player: a player
*
* Returns:
* - true if the player meets the prerequisites, false if the player does not
*/
bool meets_prereqs(player_t *player, prereq_t *prereq);
/* quest functionality */
/* Adds a task to the tree given an parent tree id
*
* Parameters:
* - quest: pointer to a quest
* - task_to_add: pointer to a task to add to the list
* - parent_id: string that is parent task's id
*
* Returns:
* - SUCCESS
* - FAILURE
*/
int add_task_to_quest(quest_t *quest, task_t *task_to_add, char *parent_id);
/* Updates a quest's status to started
*
* Parameter:
* - quest: pointer to quest to be started
* - qctx: pointer to quest_ctx that indicates player starting the quest
* and a hash table of all quests
*
* Returns:
* - SUCCESS
* - FAILURE
*/
int start_quest(quest_t *quest, quest_ctx_t *qctx);
/* Updates a quest's status to failed
*
* Parameter:
* - quest: pointer to quest to be marked failed
* - player: pointer to player failing the quest
*
* Returns:
* - SUCCESS
* - FAILURE
*/
int fail_quest(quest_t *quest, player_t *player);
/* Checks if a player completed a given quest and updates the
* reference to the quest in the player's quest table accordingly
*
* Parameter:
* - quest: pointer to the quest
* - player: pointer to player with the quest
*
* Returns:
* - false if quest is incomplete
* - true if quest is complete
*/
bool is_quest_completed(quest_t *quest, player_t *player);
/* Gets the quest that has the given task as one of its tasks
*
* Parameters:
* task_id: the task tree's immediate task's id string
* hash_table: a hashtable of quests, ideally from game_state
*
* Returns:
* quest struct if successful, NULL if task is not found
*/
quest_t *get_quest_of_task(char *task_id, quest_hash_t *hash_table);
/* Checks a quest's status.
*
* Parameter:
* - quest: pointer to a quest
* - player: pointer to player with the quest
*
* Returns:
* - the quest's completion for the given player
*/
int get_player_quest_status(quest_t *quest, player_t *player);
/* Checks if a task's prereqs are met and if they are, completes the task,
* returning the task's reward on success. After completing the task, checks
* if the task completion also completed the task's quest, adds any new tasks
* from the tree if not and accepts the quest's rewards if so.
*
* Parameter:
* - tree: pointer to a task tree who's immediate task is getting completed
* - qctx: pointer to quest context struct with information on player and all quests
*
* Returns:
* - the task's reward item
* - NULL if the task is incomplete
*/
reward_t *complete_task(char *task_id, quest_ctx_t *qctx);
/* Returns the quest's reward item if the quest has been completed.
*
* Parameter:
* - quest: pointer to a quest
* - player: pointer to player completing the quest
*
* Returns:
* - the quest's reward item
* - NULL if the quest is incomplete
*
* Note:
* The status of the quest should first be checked before this function is called
*/
reward_t *complete_quest(quest_t *quest, player_t *player);
/* Checks if all of the player's tasks are complete and updates them accordingly
*
* Parameter:
* - qctx: a quest context struct which includes the player and a list of all quests
*
* Returns:
* - SUCCESS if tasks are checked successfully, FAILURE if an error occured
*/
int update_player_quests(quest_ctx_t *qctx);
/* Checks to see if the player can start a quest given by the NPC
*
* Parameter:
* - qctx: a quest context struct which includes the player and a list of all quests
* - quest_id: a quest id given by the npc
*
* Returns:
* - true: if the player can start the quest
* - false: if the player cannot start the quest
*/
bool can_player_start_quest(quest_ctx_t *qctx, char *quest_id);
/* Checks to see if the player can start a task given by the NPC
*
* Parameter:
* - qctx: a quest context struct which includes the player and a list of all quests
* - task_id: a quest id given by the npc
*
* Returns:
* - true: if the player can start the quest
* - false: if the player cannot start the quest
*/
bool can_player_complete_task(quest_ctx_t *qctx, char *task_id);This year we were able to integrate quests into many aspects of Chiventure, so that a game could actually be played with quests. The other wiki pages are more detailed in explaining how exactly we incorporated quests, but below are some of the ways quests can be accessed in a game:
- The player holds
player_task_tandplayer_quest_twhich are stored as a list of ids in the player struct. - NPCs will conditionally engage in dialogue that gives players quests/tasks. We designed it so that the NPCs dialogue with the player will be conditional on whether the player can be given the quest/task and if the player can complete it.
- Quests and tasks can be displayed through the command line when the player types "view quests", etc.
As of spring 2021, quest functionality has changed significantly since the original design. Quests utilize a doubly-linked non-binary tree of tasks to allow for multiple pathways of completion.
Missions
Missions are distinguished between passive and active. A passive mission is one that the player doesn't actively pick up from an NPC, or other sources. An active mission is one that the player actively searches for in the chiventure landscape. Previously, a quest was only to visit an NPC or collect an item, but we wanted to branch out more and offer more quest opportunities, like visiting a room or killing an NPC (maybe a dragon!). Both types of missions are included in the union type.typedef struct passive_mission{
int xp;
int levels;
int health;
} passive_mission_t;
typedef struct active_mission {
item_t *item_to_collect;
npc_t *npc_to_meet;
npc_t *npc_to_kill;
room_t *room_to_visit;
} active_mission_t;
typedef union mission {
active_mission_t *a_mission;
passive_mission_t *p_mission;
} mission_t;Tasks
Quests are currently implemented as a doubly-linked non-binary tree of tasks. Previously tasks were structured as a linked list, requiring the player to complete each task in order to complete the quest. With a doubly-linked tree, we now have the ability for the player to follow multiple pathways within a quest. This structure will allow us to progress down the tree to reach further tasks, climb back up the tree to reach other quest paths, and traverse across the tree to take different paths within a subquest. The quest can be finished only if a branch were completed and would not necessarily require every possible task to be finished. Currently, the structure is designed so players must stay on the branch they choose and cannot go back or change their path. Tasks presently must be completed **in order** going from the root to any leaf of the tree to complete a quest.typedef struct task {
mission_t *mission;
char *id;
bool completed; //0 is not completed, 1 is completed
} task_t;
typedef struct task_tree {
task_t *task;
struct task_tree *parent; //parent node of task
struct task_tree *rsibling; //the nearest right-hand sibling of the task node
struct task_tree *lmostchild; //the leftmost child of the task node
} task_tree_t;Quest
|
p1 ----- p2 ------ p3 ---- p4
| | | |
p1 p2 p3 p4
| |
p2a - p2b p4
As shown in the visualization, this data structure allows quests to branch into multiple different paths at any point. This is a huge improvement over the original linked list structure which only allowed a single path. Still, depending on the operations supported by this data structure, it may not be the most efficient solution. Once it is initialized, the size of a quest tree will remain constant, since quests generally don't change once they are given to the player (even if the ability to add more tasks to a quest after assignment to the player is added, there is never a situation where the previously assigned quests will change and where the horizontal linked list in the diagram will change size after initialization). Becuase of this, the extra capability of being able to add tasks to the quest tree due to the linked aspect of this data structure isn't useful, and is not worth the potential performance cost of search functions in linked data structures. Since Chiventure is a text-based adventure game engine and not an engine for a real-time game where framerate would make a massive impact, minor performance issues like this aren't the end of the world, so replacing this structure shouldn't be a priority. Still, it should be kept in mind for future improvements.
Rewards and Stat Requirements
The current reward struct allows a quest to offer XP in addition to an item when completing a quest. Currently, the `stat_req` makes it so that the player cannot access the quest at all from wherever they might be able to get the quest until they reach the stats requirement on the quest.typedef struct reward {
int xp;
item_t *item;
} reward_t;
typedef struct stat_req {
int hp;
int level;
} stat_req_t;Quest and Hash Table
The structure for the quest includes all the previous structures. `quest_hash_t` makes the quest hashable and identifiable by a `quest_id`.typedef struct quest {
UT_hash_handle hh;
long int quest_id;
task_tree_t *task_tree;
reward_t *reward;
stat_req_t *stat_req;
int status;
} quest_t;
typedef struct quest quest_hash_t;In addition to new, init, and free functions for each struct, we also provide the following functionality:
All functions
/*
* Determines whether a player can start a quest with their base stats
*
* Parameter:
* - quest: a quest
* - player: a player
*
* Returns:
* - 1: a player can start the quest
* - 0: a player cannot start the quest
*/
int can_start_quest(quest_t *quest, player_t *player);
/* Adds an task to the tree given an parent tree id
*
* Parameters:
* - quest: pointer to a quest
* - task_to_add: pointer to a task to add to the list
* - parent_id: string that is parent task's id
*
* Returns:
* - SUCCESS
* - FAILURE
*/
int add_task_to_quest(quest_t *quest, task_t *task_to_add, char *parent_id);
/* Updates a quest's status to started
*
* Parameter:
* - quest: pointer to quest to be marked started
*
* Returns:
* - SUCCESS
* - FAILURE
*/
int start_quest(quest_t *quest);
/* Updates a quest's status to failed
*
* Parameter:
* - quest: pointer to quest to be marked failed
*
* Returns:
* - SUCCESS
* - FAILURE
*/
int fail_quest(quest_t *quest);
/* Completes an task in a quest by checking if a given
* task ID matches any incomplete tasks in the
* appropriate level of the task tree.
*
* Parameters:
* - quest: pointer to the quest
* - id: the string identifier of the completed task
*
* Returns:
* - SUCCESS
* - FAILURE
*/
int complete_task(quest_t *quest, char *id);
/* Checks if a quest is completed
*
* Parameter:
* - quest: pointer to the quest
*
* Returns:
* - 0 if quest is incomplete
* - 1 if quest is complete
*/
int is_quest_completed(quest_t *quest);
/* Gets a quest from the given hash table
*
* Parameters:
* quest id string
* pointer to quest hash table
*
* Returns:
* quest struct if successful, NULL if quest is not found
*/
quest_t *get_quest_from_hash(char *quest_id, quest_hash_t *hash_table);
/* Adds a quest to the given hash table
*
* Parameters:
* pointer to quest struct
* pointer to quest hash table
*
* Returns:
* SUCCESS if successful, FAILURE if failed
*/
int add_quest_to_hash(quest_t *quest, quest_hash_t *hash_table);
/* Checks a quest's status.
*
* Parameter:
* - quest: pointer to a quest
*
* Returns:
* - the quest's status code, as described in quests_structs.h
*/
int get_quest_status(quest_t *quest);
/* Returns the quest's reward item if the quest has been completed.
*
* Parameter:
* - quest: pointer to a quest
*
* Returns:
* - the quest's reward item
* - NULL if the quest is incomplete
*
* Note:
* The status of the quest should first be checked before this function is called
*/
item_t *complete_quest(quest_t *quest);Most of the work in 2021 was completed in these branches: quests/implement-trees, implement_new_quest_fcts, quests/add-all-quests-hash, and quests/new_is_quest_completed (this last one was later combined with quests/implement-trees)
In the original design, quests were purely achieved through interacting with NPCs. They were limited to merely interacting and collecting items as opposed to including battle mechanisms as well. The goal was to have the quest struct as part of an NPC struct, so starting a quest would be integrated into the dialogue trees of NPCs. If the player responds accept to a quest, this initiates the start_quest function. This will have a similar means to initiating a battle in the game.
Original Quest Structs
Quests utilized a linked list of tasks that must be unlocked in order. The mission was a union, and each task was converted into a linked list, so it could be passed through the quest struct. The quest struct was made hashable so that each quest can be referenced by a quest_id.Below is the rough design of each of these elements:
typedef union mission {
item_t *item_to_collect;
npc_t *npc_to_meet;
} mission_u;
typedef struct task {
mission_u mission;
bool completed;
} task_t;
typedef struct task_llist {
task_t *task;
struct task_llist *next;
} task_llist_t;
typedef struct quest {
UT_hash_handle hh;
char* quest_id;
task_llist_t *task_list; //linked list struct holding a list of tasks that make up a quest
item_t *reward; //reward of the quest is an item
int progress; //0 if quest is started, 1 if in progress, 2 if completed
} quest_t;
typedef struct quest quest_hash_t;Quest Functions
Besides the basic functionalities of new, init, and free there are also the following basic quest functions:/* Adds a task to a quest
* returns SUCCESS OR FAILURE
*/
int add_task_to_quest(quest_t *quest, task_t *task_to_add);
/* Starts a quest
* returns SUCCESS or FAILURE
*/
int start_quest(quest_t *quest);
/* Checks the status of a quest
* returns status code for various status in the quest:
* 0: quest has been completed
* 1: quest has been started but not completed
* 2: quest has not been started
*/
int quest_status(quest_t *quest);
/* Rewards the prize to the player once the quest has been completed
* returns an item (possible to be added into the inventory of the player
*/
item_t *quest_completed(quest_t *quest);