Automatic quest generator
Hi, Habr!
I want to talk about the quest generator, which I do for my browser-based ZPG.
')
Despite the fact that the issue of automatic generation of tasks in the RPG is quite ancient, there are almost no generally available working versions of such generators (rather than none at all), except for quite primitive options. There are not many works on this topic either, although if you actively google, you can dig up something. Therefore, I hope that this text (and the generator itself, the link to the repository is at the end of the article) will be useful.
For the hurried: visualization of one of the received tasks .
Further, instead of “quest”, I will use the term “history” as more convenient to explain (each quest is a story limited by a couple of conventions, so it’s wiser to speak about the story generator).
The requirements that I put forward for the stories can be formulated as follows:
In addition to the requirements for the stories themselves, there are several more requirements directly to the generator:
Having defined the requirements, it was necessary to determine the fact that, in fact, such a quest or story. In the end, I came to the following definition:
From the definition of smoothly follows the idea of ​​implementing history in the form of a state machine, which is given under the control of the game.
As a result, our generator should, on the basis of information about the current state of the world, create a graph of history with the properties listed earlier.
In turn, the resulting graph should be interpreted by the logic of the game. Which, based on information about the current state of the story and the expected future state, will initiate the necessary changes in the actions of the hero or the environment, leading to the fulfillment of all the requirements necessary to move the story to the next stage.
The interpreter itself is implemented rather trivially (at the end of the article there will be a link to an example implementation).
So, history is a graph consisting of nodes and edges. Each node has a list of requirements (or checks, if you wish) that must be fulfilled so that history can go to the state corresponding to the node. The requirement may be finding a hero in a particular place or having the necessary amount of money.
In addition to the requirements for the state of the "world" for each node added a list of actions that must be performed when the story will be in this node. Of course, they could be arranged as separate nodes with requirements, but this would significantly increase the graph itself and complicate its analysis by the developers. The action, in this case, may be sending a message to the player, starting a battle with the monster or issuing a reward to the hero. The same lists of actions are assigned to the beginning and end of movement along the edge.
Something like this might look like a simple story.
Movement between nodes can be represented as a loop:
History nodes are conveniently divided into types that define their role:
This is a more complicated story.
The story may consist of several "atomic" tasks. For example, a sick NPC can send a hero for a medicine to a witch who will require a service for him (performing another “nested” task).
Therefore, it is built from a set of "atomic" patterns. The template is the same graph of history, but with all the variants of the development of events (even those that can make the history contradictory).
The important point here is the combination of templates (remember that as a result we should have a connected graph):
After much deliberation, it was decided that all stories, in general, are characterized by a set of key "objects" (places, characters, objects). Therefore, for each template, a set of constructors is created that accept data of a fixed format. Here are some examples of constructors:
When generating a child history, the parent filters all templates by the presence of the necessary constructor, from which it chooses a random one.
Linking the parent history to the start of the child is simple - the parent creates an edge from the desired node to the only starting node of the child history.
There may be several end nodes, and they may have different semantic meaning for the story. For example, in a story about a witch, a hero can not only accomplish her task, but also fail him; accordingly, arcs from different end nodes must be kept strictly in the corresponding nodes of the parent story.
To do this, each end node specifies a list of job results for each of the participant objects. At the moment there are three possible results:
Due to this, for each end node it is possible to determine its general meaning and correctly associate it with the parent history.
After the actions described above, we will have a visually correct history graph in our hands, but without a guarantee of consistency. This column contains all variants of the development of events, even contradicting the current state of the world.
For example, in one of the branches the hero can harm his friend. Or two NPCs marked by enemies can act together.
Therefore, the history must be further processed. This involves the following actions:
The resulting graph will be at least consistent. But it can become impracticable or unrelated (the story will become inappropriate). Therefore, the next step is to check all the necessary properties of the resulting history.
If the check was successful, then we have a new story.
If not, we start creating it from the beginning.
The full rollback approach can lead to very long generation, in case the game world is very small and has a large number of connections. But in practice, there are usually many objects in the world, and there are few links between them, so there are no problems.
In the case of frequent errors, a game using a generator can reduce the number of properties to be set in the world (for example, stop considering friendship). The generator itself does not attempt to make additional assumptions about the state of the world.
The generator is written in Python, laid out on github under the BSD license:
I want to talk about the quest generator, which I do for my browser-based ZPG.
')
Despite the fact that the issue of automatic generation of tasks in the RPG is quite ancient, there are almost no generally available working versions of such generators (rather than none at all), except for quite primitive options. There are not many works on this topic either, although if you actively google, you can dig up something. Therefore, I hope that this text (and the generator itself, the link to the repository is at the end of the article) will be useful.
For the hurried: visualization of one of the received tasks .
Why generator needed
ZPG - Zero Player Game - a game without participation of the player, the closest popular analogue is Godville.
The character of the player (hero) in the game acts completely independently and his main occupation is, of course, the execution of NPC tasks.
The key point is that the tasks are non-linear and the player must make a choice, which NPC his hero will help and which one to harm. The fate of the world directly depends on this (for example, an NPC may leave the game if many people harm him).
In addition, the hero has a “character” that can influence his actions when performing a task (for example, you can indicate that he will seek to help a particular NPC).
The hero gains experience only for completing quests.
Based on this, a mechanism was needed to create interesting and complex tasks that do not contradict common sense and require the player to think before making a choice.
The character of the player (hero) in the game acts completely independently and his main occupation is, of course, the execution of NPC tasks.
The key point is that the tasks are non-linear and the player must make a choice, which NPC his hero will help and which one to harm. The fate of the world directly depends on this (for example, an NPC may leave the game if many people harm him).
In addition, the hero has a “character” that can influence his actions when performing a task (for example, you can indicate that he will seek to help a particular NPC).
The hero gains experience only for completing quests.
Based on this, a mechanism was needed to create interesting and complex tasks that do not contradict common sense and require the player to think before making a choice.
Further, instead of “quest”, I will use the term “history” as more convenient to explain (each quest is a story limited by a couple of conventions, so it’s wiser to speak about the story generator).
Formulation of the problem
The requirements that I put forward for the stories can be formulated as follows:
- nonlinearity (any number of forks and end options);
- nesting (one story can have any number of nested or consecutive sub stories);
- integrity (history must always have an ending, no matter what path the hero goes);
- feasibility (the hero must be guaranteed to go through any story in a finite time);
- consistency (history should not contradict the state of the world or itself);
- scalability (history participants can be any number of player characters or NPCs);
- variability (the stories should differ from each other, even if they are all about the same thing in general).
In addition to the requirements for the stories themselves, there are several more requirements directly to the generator:
- the absence of defective stories (if the story is generated, then it must meet all the requirements);
- the ability to visualize the result (without visualization, the development will turn into hell).
Having defined the requirements, it was necessary to determine the fact that, in fact, such a quest or story. In the end, I came to the following definition:
History is a directed acyclic connected graph. The nodes of which describe the state (state requirements) of the participating objects and the environment at a specific stage in history, and the edges determine possible transitions between these stages.
From the definition of smoothly follows the idea of ​​implementing history in the form of a state machine, which is given under the control of the game.
As a result, our generator should, on the basis of information about the current state of the world, create a graph of history with the properties listed earlier.
In turn, the resulting graph should be interpreted by the logic of the game. Which, based on information about the current state of the story and the expected future state, will initiate the necessary changes in the actions of the hero or the environment, leading to the fulfillment of all the requirements necessary to move the story to the next stage.
The interpreter itself is implemented rather trivially (at the end of the article there will be a link to an example implementation).
History structure
So, history is a graph consisting of nodes and edges. Each node has a list of requirements (or checks, if you wish) that must be fulfilled so that history can go to the state corresponding to the node. The requirement may be finding a hero in a particular place or having the necessary amount of money.
In addition to the requirements for the state of the "world" for each node added a list of actions that must be performed when the story will be in this node. Of course, they could be arranged as separate nodes with requirements, but this would significantly increase the graph itself and complicate its analysis by the developers. The action, in this case, may be sending a message to the player, starting a battle with the monster or issuing a reward to the hero. The same lists of actions are assigned to the beginning and end of movement along the edge.
Something like this might look like a simple story.
Symbols for graphs in the pictures
- gray knots - the beginning and end of the story;
- purple nodes are points of choice;
- green nodes are common plot points;
- red nodes - conditional transitions;
- turquoise contours - subhistory;
- A dark background in the nodes indicates the requirements for the situation that must be met to be able to go to this point of the plot;
- brighter background highlights the actions that should be performed immediately after the transition to the plot point.
Movement between nodes can be represented as a loop:
- selection of the edge of the graph, which will move;
- execution of actions assigned to the beginning of the movement along the edge;
- waiting until all the requirements of the next node are met;
- execution of actions assigned to the end of the motion along the edge;
- transition to the next node;
- performing actions on the node
- return to point 1.
History nodes are conveniently divided into types that define their role:
- the beginning is the only entry point to the story (or sub-story). The requirements of this state must ensure that further everything happens correctly from the point of view of common sense;
- the end is a marker for the completion of a story (or sub-story);
- point of choice - a node in which the hero (or player) must make a choice of the further course of events;
- A conditional transition point is a node in which the further path is determined by some dynamic parameter (for example, the amount of money the hero has);
- a normal node is a node that does not have additional properties (it simply defines the next event in a linear sequence).
This is a more complicated story.
History generation
The story may consist of several "atomic" tasks. For example, a sick NPC can send a hero for a medicine to a witch who will require a service for him (performing another “nested” task).
Therefore, it is built from a set of "atomic" patterns. The template is the same graph of history, but with all the variants of the development of events (even those that can make the history contradictory).
The important point here is the combination of templates (remember that as a result we should have a connected graph):
- at least one node of the parent history must go to the starting node of the child;
- At least one end node of the child history must go to the parent node.
After much deliberation, it was decided that all stories, in general, are characterized by a set of key "objects" (places, characters, objects). Therefore, for each template, a set of constructors is created that accept data of a fixed format. Here are some examples of constructors:
- from a specific place - if it is important for us that the story begins in a certain place, and everything else can be as you please;
- between two NPCs - when it is necessary for one NPC (initiator) to give a task related to the second NPC (recipient)
When generating a child history, the parent filters all templates by the presence of the necessary constructor, from which it chooses a random one.
Linking the parent history to the start of the child is simple - the parent creates an edge from the desired node to the only starting node of the child history.
There may be several end nodes, and they may have different semantic meaning for the story. For example, in a story about a witch, a hero can not only accomplish her task, but also fail him; accordingly, arcs from different end nodes must be kept strictly in the corresponding nodes of the parent story.
To do this, each end node specifies a list of job results for each of the participant objects. At the moment there are three possible results:
- positive - the task has a positive impact on the object;
- neutral - the task had no effect on the object;
- negative - the task caused damage to the object.
Due to this, for each end node it is possible to determine its general meaning and correctly associate it with the parent history.
Postprocessing and validation
After the actions described above, we will have a visually correct history graph in our hands, but without a guarantee of consistency. This column contains all variants of the development of events, even contradicting the current state of the world.
For example, in one of the branches the hero can harm his friend. Or two NPCs marked by enemies can act together.
Therefore, the history must be further processed. This involves the following actions:
- Random events are activated - some nodes are combined into groups of alternative options for the development of history. One node is selected from each group, the rest are deleted.
- All end nodes containing forbidden job results for objects are deleted.
- The resulting graph is cleared of "hanging" nodes. The following types of nodes are considered "hanging":
- a node that is not the end node of the external history itself and from which the edges do not extend.
- a node that is not the starting node of the most external history and which does not have incoming edges.
The resulting graph will be at least consistent. But it can become impracticable or unrelated (the story will become inappropriate). Therefore, the next step is to check all the necessary properties of the resulting history.
If the check was successful, then we have a new story.
If not, we start creating it from the beginning.
The full rollback approach can lead to very long generation, in case the game world is very small and has a large number of connections. But in practice, there are usually many objects in the world, and there are few links between them, so there are no problems.
In the case of frequent errors, a game using a generator can reduce the number of properties to be set in the world (for example, stop considering friendship). The generator itself does not attempt to make additional assumptions about the state of the world.
Links
The generator is written in Python, laid out on github under the BSD license:
- repository: questgen
- example interpreter: example.py
- visualization of the finished task: large_quest.svg
- game for which it was made: http://the-tale.org
Source: https://habr.com/ru/post/201680/
All Articles