Quests are a common way for games to add content into their experiences. For this reason, procedural generation of quests has become a popular area of research in recent years. However, in academia there is no consensus on the definition of a quest, despite many researchers attempting to generate them. The purpose of this paper is to do a literature survey of quest definitions in the context of procedural quest generation, and synthesize the different versions into a more general definition that encompasses existing definitions.
The concept of a quest is inherently tied to Role Playing
Games (RPGs) due to the quest-driven story model
Quest generation research shares close ties to story generation research due to the narrative aspect often associated with a quest. However a narrative is not a required element of a quest for it to be functional. For example, the daily quest system common in Massive Multiplayer Online RPGs (MMORPGs) provides quests that do not contain any narrative elements, and instead propose challenges for the player to complete with the various game mechanics. Because a quest is not just the narrative, but also includes this notion of actions for the player to perform within the game, the definitions that are used in story generation may be inadequate for some cases of quest generation research. Individual definitions borrowed from narrative generation research could suit the purposes of a single paper, but would be improper to use for broader research efforts.
Soares de Lima, Feijo, and Furtado (2019) summarize the problem by stating that “[...] differently from the wellestablished theory about quests in literature, there is no general quest theory in computer games [...]”. Though this paper was able to identify this problem, the paper does not attempt to address the issue and instead offers a new version of a quest definition. A full established theory of quests in video games would include a definition of a quest, but the full theory is not necessary to produce effective quest generation systems. Multiple approaches have led to individual success in the field, but without a consensus among researchers interested in this topic, new work is prevented from building on previous work. This can affect the quality of new research being done in the field, because the new research can be difficult to compare to work that has previously been done, and can be difficult to reproduce.
As we will demonstrate, most papers create a definition of a quest that suits the need of the research being done. This creates two main problems. The first problem is that it creates a high barrier of entry to the field. If a new researcher wants to add to the field, they have to either create a new definition or choose a definition from a large pool of options. If the author chooses to create a new definition then it further exacerbates the existing problems, and if the author decides to choose a definition from existing ones then it can be a difficult choice. The author has to evaluate each definition in the context of the planned work, which creates a high level of work that needs to be done before the new quest generation system can even be implemented. The second problem is that it becomes difficult to compare different quest generation approaches. The definition of a quest that one generation system relies on can have completely different requirements or properties to another definition. If one generation system requires that a quest contains a narrative element and another does not, it is challenging to say whether one approach is better than the other because the outputs are fundamentally different. These two problems together compound into another issue, where not every paper that discusses quest research even defines a quest. Instead, some papers opt to talk about the effects or uses of quests within the game, because there is no agreed upon definition of a quest to reference. For these reasons, the purpose of this paper is to perform a survey of the quest definitions currently proposed in procedural quest generation research. As a workshop paper, we hope to further the discussion for a unified quest definition and encourage more communication in this field by combining the existing definitions into a single generic quest definition.
There are many areas of research which have defined quests.
There has been an effort to create a unified quest theory for
video games
Understanding video games using the mechanics,
dynamics, aesthetics (MDA) framework in the context of quests
provides a foundational understanding of how a quest is
represented in a game
The presentation of a video game refers to all of the
components of a video game that the player has within the game
to help them understand the game. Presentation serves as
the interface between the player and the game, and helps the
player gain more information about the video game world
There are two main places where the presentation gets
used in the context of quests: a heads up display (HUD) and
a menu. The HUD is a common way to include UI elements
within a game which will provide player information about
metrics such as health. This is usually where information
about a player’s current goal is found, to serve both as
instructions for the player and a reminder of how to progress
in the game. This is how, for instance, Dragon Age:
Inquisition
3
The methodology for this survey is based off of the review
process commonly used in software engineering literature
reviews
Table 1 shows the definitions of quests proposed by different papers. The definitions were analyzed for their similarities and differences, and a labeling system was designed from the common ideas present in the definitions. Each label in order to a specific property that the definition could have. “T” refers to a definition that contains the concept of a task, action or goal that must be completed. “R” refers to a definition that includes a reward. “P” refers to the requirement that the player must complete the quest. “O” refers to the idea that the tasks must be completed in some order. “C” refers to definitions that include the concept of progression. “N” refers to definitions that include narrative elements, and “E” refers to definitions that are specifically tailored to meet the needs of their quest generation system.
Notably, only one paper cited another work in their
definition of a quest, NC1, while the rest of the papers offered
their own definition of a quest. NC1 cites a paper that
analyzes the personalization effects of the player character in
MMORPGs
The most common idea from all of the definitions is the notion that there individual pieces that must be completed. These are most commonly called tasks, as in TP1, TR2, TNR1, and TPN1. They are also referred to as actions in TRNO1 and TEO3. One definition, TN1, refers to this simply as a single goal, while TR1 and TEO1 refer to a set of goals. Additionally, TP2 calls them “quest points”.
“Task” provides a generic way of dividing a quest into individual pieces, which suggests that each part of the quest needs to be completed. “Action” implies that there has to be some initiative from the player in order to complete the current section of the quest. “Goal” has a slightly different connotation to it, because goals can be short or long term. A short term goal for the player could be to complete the current quest, and a long term goal could be to finish the game. Because goal has a dual nature where it can be used to describe both small sections and large chunks of a game, it would be inappropriate to confine the word “goal” to a single quest. Instead, “goal” should be reserved to describe other game play aspects, and should not be required as part of a quest. This last wording of “quest points” is the most unique way of dividing a quest into different sections, and is functionally the same as the word “task” because they both divide a quest into completable sections.
In order to fully understand the relationship between tasks and actions as defined in these papers, the definitions that the papers provide for a task or action is examined. TPN1 and TNR1 provide examples of what a task should be, and describe them as high level objectives that are not rooted in exact game mechanics or game inputs. Actions, in the context of TRNO1 and TEO3, refer to high level concepts that are executed by the player, and not specific game mechanics. TEO3 bridges the gap by proposing that a task should be the actions that a player can do within the game. There is sometimes a notion of challenge associated with these tasks, with TR2 and TN2, but challenge is also ambiguously defined and can vary highly between players.
Many of these definitions include the idea of a reward: TR1, TR2, TR3, TNR1, TRNO1 and TNCPR1. However, there is no consensus between definitions of what a reward is. Rewards are often thought of as in-game items such as currency, but the precise language of what a reward can be has less impact on the understanding of a quest than the precise definition of a task because the reward doesn’t have to be completable by the player. Progression is also a common theme, and is present in definitions TNCPR1, C1, and NC1. Progress includes things like experience points which allow for a player to increase in level, or skill points which allows them to unlock new skills in a skill tree. Progress could also be the ability to play the next quest in the game or to unlock a new area of the game that the player was previously unable to access. Progress can be labeled as a reward, so these can be viewed as subset of the definitions that include reward.
There are a few papers that include the idea of order associated with the tasks that must be completed TRNO1, EO1 and TEO3. The kind of ordering varies by definition. TRNO1 proposes that an ordering exists, but fail to specify the kind of ordering. EO1 proposes a total ordering as described in the planning problem, and TEO3 proposes a partial ordering in their definition of the hypergraph. The ordering of the tasks usually refers to how the player completes the quest. This varies between games due to the way that the tasks are presented to the player. Sometimes, all of the tasks in a quest are presented to the player at the same time, and other times the tasks are given one at a time as the player completes them. In the first case, the ordering of tasks is decided by the player, and in the second case the ordering is decided by the game. A partial ordering accommodates the first case, because there are one or more tasks that can be completed in any order, and a total order occurs in the second case because each task has to be completed in a specific order. However, both cases can be described as a partial ordering because a total order is a special case of a partial ordering. 4.4
Seven of the quest definitions require that the quest contains
narrative elements: TN1, TNR1, TPN1, TRNO1, TNCPR1,
NC1, N1. Soares de Lima, Feijo, and Furtado (2019) define
quests in traditional literature as a journey toward a specific
goal where multiple adventures can occur, which cites the
body of work analyzing quests only for their narrative
content
The use of the word narrative in the context of video
games can mean both explicit and sifted narrative. Explicit
narrative refers to a story that a designer writes, that is now
being conveyed to the player through the medium of the
video game. Sifted narrative refers to the stories that the
player community applies to game elements that don’t
inherently have explicit narrative
Narrative content could also fall under the category of reward, where if a player completes a quest they are rewarded with the next piece of the story. For that reason, these quests can also be viewed as a subset of the quests that require a reward as part of their definition. Narrative rewards would include game play elements such as a cutscene playing after a quest is completed, or a new dialogue that an NPC says. 4.5
There are a few quest definitions that explicitly describe that the quest must be completed by the player: TP1, TP2, and TNCPR1. This is an important distinction, because quests are meant to be for the player, and only the player. A quest is added to a game by a designer for a specific purpose. These quests allow the designer to highlight specific mechanics, lead the player through a story, or otherwise interact with the game world. The quest then becomes the way for the designer to communicate with the player. NPCs can have the ability to complete a quest, but they can only do so when the player allows the NPC to complete the quest.
There are some games, such as Poke´mon Sword and Poke´mon Shield (Game Freak, The Poke´mon Company, Nintendo 2019), where the NPCs are allowed to go on a quest. In these games, each individual poke´mon (NPC) has a level associated with it, and one of the ways that a player can increase the level of the poke´mon is by leaving the poke´mon at the daycare center. The poke´mon will receive experience points while they are at the daycare center, which allows the poke´mon to gain levels. This gameplay piece can be thought of as a quest, where the poke´mon is assigned the quest of going to the daycare. However, the poke´mon can only go on that quest when the player deems it appropriate, and the poke´mon is not allowed to complete the quest independent of the player. The assignment of quests to NPCs within a game can be thought of as a game mechanic, which means that a player could receive a quest where the task is to provide a quest to an NPC. 4.6
TEO1, E2, and TEO3 are specific definitions specialized to
work within the context of their respective quest generation
system. TEO1 proposes that a quest should be a planning
problem Q = hP; O; S0; Hgi, where P is the set of
predicates that are used to define the game state, O is the set of
planning operators, S0 is the current game state, and Hg is
the totally ordered set of goals. This definition creates two
issues due to its requirement that the quest is a planning
problem. The first is the issue of generality, because only quest
generation systems that can solve a planning problem can
use this definition of a quest. A planning problem can be
solved using a planning algorithm. However, any proposed
quest generation system that is not a planning or
planninglike algorithm cannot use this definition. One quest
generation system uses simulation to generate a quest,
E2 defines their quest as something that is generated from their quest generation system. The quest generation system is made up of constraints on the memory what happened in previous game states, attributes which encompass the player’s ability to complete the quest, actions that the player is allowed to take within the game, layers which define the interaction between the object and the current game state, and proximity, which refers to the closeness of objects to each other. While none of these components are inherently problematic, defining a quest in this way implies that no other information could be part of a quest. Most notably, this definition omits the idea of a reward which is a common requirement of other quest definitions.
Paper TEO3 proposes that a quest is a cyclic action
hypergraph HA(N; E) where N is the set of nodes and each
node is a possible action, and E is the set of directed edges
where each edge is labeled true or false. A hyperedge in this
graph is when a successor node has more than one
predecessor nodes. Practically, this paper defines a valid quest to be
a directed acyclic hypergraph with a single sink node acting
as the final action of the quest. This quest definition has the
same two issues as TEO1. On the first issue of generality,
this definition requires that the quest generation approach
has to generate a specific directed hypergraph. Generation
approaches that cannot output this specific hypergraph
cannot use this definition of a quest. For example, there is a
proposed quest system that uses a genetic algorithm to
generate a quest
These quest definitions can be combined into a single generic quest definition. The new definition attempts to encompass all of the information that is captured in section 3 in the most generic way.
Tasks, actions, goals, rewards, progression, narrative, order and player are all identified as having commonality between different proposed definitions, and are considered to be essential elements of a quest. For that reason, the individual components were generalized into the least amount of requirements to be a part of a quest. Progression and narrative can be viewed as reward, so these ideas were combined into the single component of reward. Tasks, actions and goals have to be more carefully combined. An action implies that there is exactly one thing for a player to do using the game mechanics. Some tasks in a quest require a player to complete multiple actions. For example, a task that a player could receive would be to talk to an NPC in a different location, which would require two actions, one for moving to the location, and one for talking to the NPC. For this reason, the tasks can encompass actions, where a task can be completed by one or more actions. As discussed in section 4.1, goals can refer to long term objectives for the player such as finishing the game, which would require the player to complete all of the main quests. The word “goal” therefore has the potential to include multiple quests within it, and would not be suitable to describe part of a quest. Therefore, the word “task” is chosen over the word goal, in order to reserve that word to refer to other aspects of the game.
The elements in EO1, E2, and TEO3, are considered to be non-essential because they introduced concepts that are too specific to be used in a broader context. EO1 required that the quest be a planning problem, E2 required that the quest be a something generated from the quest system outlined in the same paper, and TEO3 required that the quest be a hypergraph. Because these definitions are so specific, they limit the kinds of approaches that can be used to generate a quest. These components were omitted to allow for any approach to be tried in future quest generation research.
In addition to the ideas expressed in the definitions, gaps in this body of work were identified. These definitions lack a discussion of what a task is and lack a connection to the presentation of the quest to the player. A task needs to be defined so it specifically relates to the game mechanics, and needs to be more precisely defined in how to complete a task. The presentation of quest affects the player’s ability to interact with the quest, and should also be considered an integral part of the quest.
Definition 1 A quest Q = hT; ; Ri is a partially ordered set of tasks T that the player must complete to get one or more rewards from a set R.
defines the partial ordering on the set of tasks, and is created based off of the in-game logic.
Definition 2 A reward r 2 R is an in-game item, narrative elements, or progression elements.
The set R contains any rewards that the developer wants the player to receive in exchange for completing a task within the quest. The rewards for an individual quest R come from the pool of possible rewards R. Rewards can be ingame items can be things like currency, a new weapon or other items that allow the player to interact with the game. Narrative elements can be things like cut-scenes, or new dialogue offered by NPCs which help the player understand the story of the game. Progression elements would include things like experience points which would allow a player to increase in level, or progression points that a player would use to unlock new abilities in a progression tree. All of the possible rewards for the player are aggregated in the set R, but the specifics of when and how the rewards are assigned to the player will be assigned at the task level in the description that follows.
Definition 3 A task t 2 T is a 4-tuple hC; M; I; Rti, where C is the condition that must be made true in order to complete the task, M is the system that monitors the sub-section of the game state that is required to make C true, I is the presentation of the quest, and Rt R is the set of rewards that is given to the player when C is true.
A task t is completed by the player interacting with the game mechanics, which necessitates C as a functional check for whether t is completed or not. This definition proposes a monitoring system M to determine whether C becomes true, which allows for any representation of a game state. As the player completes actions using the game mechanics, the game state will be affected in specific ways. M can check the ways that the game is expected to change in order to measure whether the player has completed the action or not. For example, assume the player is given a task to go to location A. In order to complete this task, the player is allowed to go to any part of the area within location A, not just a specific pixel. M is the monitoring system which determines whether the player is within the area of location A, which includes many different specific coordinates as a possible way to satisfy this requirement. Because there is no requirement for which game mechanics the player interacts with in order to make C true, the player is allowed to choose which mechanics to interact with to satisfy C. When C becomes true, the task is considered completed and the player is presented with the reward Rt, and is optionally presented with the next task in T depending on if the player completed the final task or not.
I is the presentation to the player through various in-game elements that help the player complete the task or situate the quest within the narrative, such as written instructions, markers on a map, or highlighted objects. The presentation clues the player into which mechanics must be used in order to make C true. The presentation is included at the task level because the presentation can vary between tasks that are a part of the same quest. For example, a player might complete a task where the presentation marks a location on a map, and the next task is simply shown to the player as text. I can also optionally include the motivations of why the player should complete the quest according to the game’s internal logic, as suggested by TNR1.
Rewards Rt are also included at the task level in order to specifically define when a player receives rewards. Because progression and narrative are considered a reward, it becomes necessary to define rewards at the task level as well. For example, a player could complete the first task in a quest, which would trigger a cutscene. That cutscene needs to be specifically associated with the task, because that is when the player receives that reward. If all of the rewards are presented to the player at the end of a quest, then the rewards simply need to be associated with the final task of the quest. 6
In this section, the applicability of one of the quest definitions, TR1, is compared to the new definition proposed in this paper. Animal Crossing: New Horizons was chosen because its quest systems offer an alternative perspective where the quest does not have to include narrative elements. Animal Crossing: New Horizons has two quest systems: Nook Miles and Nook Miles+. Nook Miles are quests that include long-term goals such as catching 100 fish, while the Nook Miles+ system includes shorter term goals such as catch 5 fish. Neither of these quest systems offer narrative elements or progression as rewards, and instead reward the player with in-game items.
The Nook Miles system communicates to the player with a stamp card that gets filled as the player completes tasks within that quest. Sometimes the name of the stamp card is shown to the player, which will clue the player into what sort of challenge could be completed to fill the card. Other cards are unavailable for the player to see, and only unlock once the first challenge in the quest has been completed. From there, the player can see the progress they have made towards the next stamp in the card at any time. Each stamp card is themed to a specific game mechanic, and can only be completed once. For example, one of the stamp cards in the game requires to the player to catch fish. The player is challenged to catch 10 fish, catch 100 fish, catch 500 fish, catch 2,000 fish, and catch 5,000 fish. Additionally, the Nook Miles system features a challenge aspect, because the system tracks your ability in each section and progressively assigns more difficult tasks. After the player completes each task, the player is rewarded with different amounts of premium in game currency, where the player gets more of the in game currency for completing the more difficult task. The player is awarded with 300, 500, 1,000, 2,000, and 5,000 in game currency respectively. In addition to the in-game currency, completing a task in this quest will also reward the player with “passport titles” which allow for additional customization. There are 5 titles: “Accomplished Lad/Lass”, “Competent Fishing Fan”, “Moderate Beach Bum”, “Fierce Fisher”, and “Battle-Tested Catch of the Day”.
The Nook Miles+ system generates a set of five possible quests that are presented to the player. If a player completes one quest, then a new one will be automatically chosen and presented to the player so that there are always five quests for the player to complete. A player can choose to complete one or more of these quests in any order. The quests that are chosen from the pool of Nook Miles+ quests tend to take a much shorter amount of time to complete. For example, in the fishing category, the Nook Miles+ system presents the player with the quest to catch five fish. When a player completes one of these quests, the player is presented with different amounts of premium in game currency. For the catch 5 fish quest, the player is rewarded with 150 currency.
Each of these systems draw from different pools of possible quests for the player to complete, which reflect the game play reasons for including two quest systems. The Nook Miles system is intended for players to complete over many play sessions and incentivizes players to play the game multiple days in a row, while the Nook Miles + system provides rewards for short actions that can be completed in short time frames, and incentivizes the players to keep playing the current session. To analyze these quests in the context of different definitions, the fishing category challenges were chosen from both systems because they use the same game mechanics to complete.
Definition TR1 was used as comparison to the proposed quest definition. TR1 states that “A quest is a player task commonly found within role playing games where the player is challenged to complete goals in return for some reward”. TR1 includes goals that need to be completed, and that a single reward needs to be given to the player when the goal is completed. This formalizes TR1 into Q = hfGg; ri, where G is a set of goals and r is the reward. Using this definition, the Nook Miles quest system can be analyzed. The fishing quest is defined as Q = hfg1; g2; g3; g4; g5 2 Gg; ri. g1 is the first task, catch 10 fish, g2 is catch 100 fish, g3 is catch 500 fish, g4 is catch 2,000 fish, and g5 is catch 5,000 fish. The reward for this quest is tricky, because the player receives both in-game currency and passport titles but is only allowed to receive a single reward. This definition fails to fully capture the rewards available to the player in this quest. There is also no notion of the order that the tasks in G should be completed, whereas the game provides a specific order for the player. Additionally, TR1 does not include any information about how the quest is presented to the player. The Nook Miles+ quest system can also be analyzed. The “catch five fish” quest is defined as Q = hfg1 2 Gg; ri. g1 is the task to catch five fish. r is the reward of 150 in-game currency. This time, the definition is able to accurately capture the main components of the quest, but there is still no information about the presentation of the quest.
Using the definition proposed in this paper, the Nook Miles fishing quest can be defined as Q = hft1; t2; t3; t4; t5 2 T g; ; fr11; r12; r21; r22; r31; r32; r41; r42; r51; r52 2 Rgi. t1 is the first task, catch 10 fish, t2 is catch 100 fish, t3 is catch 500 fish, t4 is catch 2,000 fish, and t5 is catch 5,000 fish. r11 is the 300 in-game currency, r12 is the title “Accomplished Lad/Lass”, r21 is the 500 ingame currency, r22 is the title “Competent Fishing Fan”, r31 is the 1,000 in-game currency, r32 is the title “Moderate Beach Bum”, r41 is the 2,000 in-game currency, r42 is the title “Fierce Fisher”, r51 is the 5,000 in-game currency, and r52 is the title “Battle-Tested Catch of the Day”. is the ordering that enforce t1 must be completed before t2, t2 must be completed before t3, t3 must be completed before t4, and t4 must be completed before t5. Each task in T also needs to be explicitly defined. t1 = hC; M; I; Rt1 i, where C becomes true when the player catches 10 fish, and M is the system that monitors how many fish have been caught. I is the presentation of the stamp card, the indicator to let the player know how many more fish they need to catch to complete the task, and the stamp that is presented to the player when task is completed. Rt1 = fr11; r12g, the in-game currency and the title associated with the task. t2 = hC; M; I; Rt2 i, where C is the condition that becomes true when the player catches 100 fish, and M is the system that monitors how many fish have been caught. I is the presentation of the stamp card where the stamp first task, t1, is presented to the player, the indicator to let the player know how many more fish they need to catch to complete the task, and the stamp that is presented to the player when the task is completed. Rt2 = fr21; r22g, the in-game currency and the title associated with the task. t3 = hC; M; I; Rt3 i, where C is the condition that becomes true when the player has caught 500 fish, and M is the system that monitors how many fish have been caught. I is the presentation of the stamp card where the stamps for the first two tasks, t1 and t2, is presented to the player, the current progress indicator to let the player know how many more fish they need to catch to complete the task, and the stamp that is presented to the player when the task is completed. Rt3 = fr31; r32g, the in-game currency and the title associated with the task. t4 = hC; M; I; Rt1 i, where C is the condition that becomes true when the player catches 2,000 fish, and M is the system that monitors how many fish have been caught. I is the presentation of the stamp card where the stamp for the first three tasks, t1, t2 and t3, is presented to the player, the indicator to the let the player how many more fish they need to catch to complete the task, and the stamp that is presented to the player when the task is completed. Rt4 = fr41; r42g, the in-game currency and the title that is associated with the task. t5 = hC; M; I; Rt5 i, where C is the condition that becomes true when the player catches 5,000 fish, and M is the system that monitors how many fish have been caught. I is the presentation of the stamp card where the stamps for the other four tasks, t1, t2, t3 and t4, are presented to the player, the indicator to let the player know how many more fish they need to catch to complete the task, and the stamp that is presented to the player when the task is completed. Rt5 = fr51; r52g, the in-game currency and the title associated with the task. This definition is able to account for the ordering of the tasks, the multiple rewards that are given to the player as the player completes the tasks in the quest, and the presentation of the quest to the player.
Using the definition proposed in this paper, the Nook Miles+ fishing quest can be defined as Q = hft1 2 T g; ; fr1 2 Rg. t1 is the task to catch five fish, is the ordering of a single task, and r1 is the 150 in-game currency. t1 = hC; M; I; Rt1 i, where C is the condition that becomes true when the player catches five fish, and M is the system that monitors how many fish have been caught. I is the presentation showing that the player needs to catch five fish, an indicator of the player’s progress of catching the fish, and a change in the graphic to let the player know that the quest has been completed. Rt1 = fr1g, the in-game currency reward. Though this quest is much simpler, the proposed definition is able to as easily capture the requirements of this quest as the more complicated Nook Miles quest. 7
Since there is no consensus on the definition of a quest in procedural quest generation, this paper offers a survey of quest definitions proposed in that literature. From this survey, a generic definition of a quest was synthesized, and proposed in a form that can accommodate most of the ideas proposed by previous papers. The hope is to further the discussion for a unified quest definition and encourage more communication in this field. Using a more precise definition of a quest can allow for better reasoning about quests and quest systems, as demonstrated in the analysis section. Additionally, if a consensus can be reached, it will be easier to further research in this area.