Procedural content generation (PCG) has been used in digital games since the early 1980s. Here we focus on a new problem of generating personalized combat encounters in role playing video games (RPG). A game should provide a player with combat encounters of adequate difficulties, which ideally should be matching the player's performance in order for a game to provide adequate challenge to the player. In this paper, we describe our own reinforcement learning algorithm that estimates difficulties of combat encounters during game runtime, which can be them used to find next suitable combat encounter of desired difficulty in a stochastic hill-climbing manner. After a player finishes the encounter, its result is propagated through the matrix to update the estimations of not only the presented combat encounter, but also similar ones. To test our solution, we conducted a preliminary study with human players on a simplified RPG game we have developed. The data collected suggests our algorithm can adapt the matrix to the player performance fast from little amounts of data, even though not precisely.
Many games today implement some form of procedural
content generation (PCG) [
One of the current widely accepted psychological
models of engagement in games is flow [
Focusing on RPG combat encounters, the challenge of their design is how to compose a group of monsters players should face in order for them to stay in the flow channel (Fig. 1). This is problematic as the player’s ability is not known when the game starts. Whereas we can fathom how difficult a given combat encounter is, e.g., by statistics over monsters combat values (total health, damage per second, etc.), we do not know how proficient a player is at first or how fast they can improve in playing the game. We propose to solve this problem using reinforcement learning, i.e., to create a system that given the observation of player’s performance in the game can generate next combat encounters of appropriate difficulty.
The rest of the paper is structured as follows. In Section 2, we examine work related to ours. In Section 3, we formulate the combat encounter generation problem (CEGP) and requirements on its solutions, namely the ability to adapt to concrete game instances and the fact the solution must be able to adapt to the player fast. In Section 4, we detail our approach tackling CEGP. In Section 5, we present an implementation of our approach for an example RPG game we have created to test it. In Section 6, we describe and discuss the results of an experiment with human subjects that was conducted to test our approach. Finally in Section 7, we conclude the paper with notes on future work. 2
While procedural content generation in games is a
wellstudied field, it seems that existing research does not focus
on generating combat encounters. The works we found
about content generation in RPGs focus either on
generating levels [
We tried looking at other genres for inspiration, yet we
were unable to find any relevant research. It seems that
even in genres such as platformers[
The encounters we generate must be appropriately difficult for the player. Therefore, techniques for runtime adjustment of difficulty might be relevant to us.
Xue et al.[
Missura and Gärtner[
As the goal of the algorithm will be generating encounters
suitably difficult for the players, its evaluation must
involve real people playing the encounters generated by the
algorithm. We have chosen to also measure the player’s
feeling of flow [
In psychology, flow is a state where the person is fully concentrating on some task. It is also known as being “in the zone”. A person in a flow state loses track of time and she focuses completely on the activity she is doing. To enter the flow state, the person must feel competent at the task and the task must be appropriately difficult for her.
To measure the player’s feeling of flow, we use the Flow
Short Scale [
Here we define several terms commonly used in RPG games, which we will use throughout the paper; defined terms are in italics. Some terms are formulated in an openended manner as different games will differ in details.
For the purpose of this paper, we will understand a game as a double (W; S) of a game world W and a game state S.
A game world as a double (L; P) of game locations L and actor prototypes P. A game state consists of spawned actors only.
Game locations L is a set of all possible positions in the game world, which actors may occupy. In some games locations could be a grid of discrete tiles, whereas in others it could be a more complex 3D structure. The number of these atomic locations can be in thousands per game level for grid-based games, or infinite in case of 3D worlds where location is represented by floating point numbers.
An actor prototype, p 2 P, is a prototype of a character that can be spawned as an actor into the game. An actor prototype is a tuple of all the attribute values that describe the class of an actor, e.g., its health, damage per second, size, skills, etc. These attributes are game specific, but we assume health and damage per second to be present at least to allow for combat between actors.
Actor, a = (pa; sa; la; ca), is a spawned actor prototype that can be present within the game and a part of the game state. It consists of actor prototype pa definition, its current state sa of pa attributes (initial values set according to pa), location la 2 L an actor occupies in the world and a controller ca, which is either a human or an AI. We label the set of all possible actors as A.
A hero(r) ::= fr 2 A j cr = humang is an actor a player currently controls. A party(R) ::= P(fr 2 R j hero(r)g) is a set of heroes the player may control. All such parties are denoted as r.
An enemy(e) ::= fe 2 A j ce = AIg is an actor a player does not control and the party has to fight. enemies(E) ::= P(fe j enemy(e)g) is then a group of enemies a player may face in the game, all such enemy groups are denoted as e.
A combat area, O = fl 2 L j 8l1; l2 2 O : path(l1; l2) Og, represents some continuous area in the game world where some combat encounter may take place.
A combat encounter is a triple, c = (Ec; Rc; Oc), that represents a situation where a party must defeat some enemies. It consists of enemies Ec the party Rc has to fight inside some combat area Oc. The set of all possible combat encounters is labelled as C. In particular, actor prototypes are not the only part of c as also their runtime states are included. As such, C can be thought of as game states in the space of combat; as actors are exchanging damage, this space is traversed until either side is eliminated (their total health reaches zero).
We model the player y = (sy), as a single number sy 2 [0; 1] denoting the skill of the player. 0 means no skill, which can be thought of as not issuing any actions to heroes during any combat encounter. 1 refers to an optimal play, i.e., player can achieve the best outcome possible regardless the encounter given. We denote set of all kinds of player abilities as Y .
We define the difficulty of an encounter c 2 C as a function D : C Y !< 0; 1 >, where its value states how many percent of party health will be lost during encounter as played through by the player of given skill. 0 means the party Rc will defeat enemies Ec at Oc without any health losses and 1 means the party Rc will certainly be eliminated by the enemies Ec regardless player actions. Importantly, there can be encounters that cannot be won even by optimal players (enemies are too strong for the party to defeat).
The combat encounter generation problem (CEGP) is than an optimization problem: given a set of all possible combat encounters C for a given party R, a player y, and a desired difficulty d, find cmin 2 C such as 8c 2 C : jd D(cmin; y)j jd D(c; y)j. 3.1
The CEGP consists of two sub-problems: 1) how to evaluate the difficulty D; 2) even if D is known, how to search for appropriate c 2 C fast. The challenge of solving them stems from the problem formulation itself (e.g., the size of C) and from the video game context, which poses additional requirements on the CEGP solution.
Difficulty evaluation. The skill of a player is not known beforehand. As the result, we cannot compute precise values of D even via simulation. Moreover, player’s skill can change throughout the game as the player improves in playing the game. Therefore, once observed difficulty of a concrete c may become irrelevant in future as the player skill changes. Finally, if the game is played in real-time, the skill may fluctuate as player’s reflexes improve. Problem size. Considering solving the CEGP for the game Dragon Age: Origins (Bioware, 2009) featuring 140 enemy actor prototypes (according to https://dragonage.fandom.com) trying to generate an optimal encounter that consists of about 7 enemies in the game, we would need to go through 1407 possible groups of enemies. Moreover, every enemy group can be spawned into the game to a different locations, which could affect difficulty of the encounter greatly. E.g., if a group of archers is spawned behind a strong knight that is blocking the path towards them, it would pose an extra challenge to the player than if the group of archers could be easily reached. The size of C is thus enormous.
Training data. The only direct way to model skill of a player playing an instance of the game is through observation of his combat encounters. Such observations can be seen as training data, provided during the gameplay. However, it is not realistic to expect a player to play even ten tutorial encounters just to calibrate the model of the player, which is still very few still given the size of C.
Video game context. RPG games are (typically) played in real-time and there are usually several to tens of combat encountered prepared by game designers in each game level. Therefore, the algorithm solving the CEGP must compute fast in order not to interrupt the gameplay and it should not consume an unnecessary amount of memory. 4
Our current approach to solving the CEGP is to use reinforcement learning for estimating the difficulty function D, while heuristically reducing the size of the combat encounters set C. If we can contract the set, it would make both the estimation of D and the search for suitable c 2 C much easier. For looking up an encounter of some required difficulty d, we are softening the requirement of optimality and use stochastic hill-climbing to look for a combat encounter c of difficulty that differs up-to d from d, i.e., jd D(c; y)j < d . 4.1
Looking at a combat encounter definition c = (Ec; Rc; Oc), we disregard Oc (simplification) and maintain a sparse difficulty matrix M indexed by enemies and a party. The matrix then holds estimated difficulties of a combat encounters Mer given enemies Ee and the party Rr for the player y that is currently playing the game.
The size of the matrix is huge. Adapting only single matrix element after each encounter would not result in fast adaptation to the player. Therefore, we propose to adapt multiple values from the matrix given a single observation using some difficulty adjustment function.
A difficulty adjustment function, which we denote by D(dm; Em; Rm; do; Eo; Ro; a) should return a new difficulty value for an encounter between enemies Em and the party Rm, which was thought to be of dm difficulty, given the observed difficulty do from just finished encounter between enemies Eo and the party Ro; a is a learning factor.
Given the observation of do for some encounter c(Eo; Ro; Oo), we update each matrix element with Mer = D(Mer; Ee; Rr; do; Eo; Ro; a).
To be able to construct D, we define two heuristic functions, which computes similarities of enemies and parties. Enemies similarity function is defined as SE : e e ! [0; 1] and party similarity function is defined as SR : r r ! [0; 1]. 0 value means total difference, while 1 means equality of elements.
We then compute D(dm; Em; Rm; do; Eo; Ro; a) = dm + (do dm) maxf0; 1 SE (Em; Eo) SR(Rm; Ro)g a. The 1: procedure UPDATEMATRIX(M; do; Eo; Ro; a ) 2: for each (Em; Rm) 2 M do 3: dm = M[Em; Em] 4: M[Em; Em] = D(dm; Em; Rm; do; Eo; Ro; a ) 5: end for
function updates the estimation of its error scaled according to the similarity of enemies and the party of the matrix element to real enemies and party participating in combat that was just observed (and multiplied by the learning rate a ).
Updating matrix is then done by updating all of its elements (Fig. 2) using D function. This is the place where similarity functions are used the most as they allow us to update multiple elements of the matrix. 4.2
Ideally, initialization of M should be based on real-data by letting players play the game to obtain observations. However, the amount of required observations is usually so high that it is probably unreasonable to require it even from big video game making companies. Instead, we propose to implement a simple reactive player that can play through combat encounters and use it to obtain first difficulty estimations for the matrix. We do this only for a selected subset of enemies and parties. 4.3
Having matrix M estimating D for player y, enemies and party similarity functions SE , and SR we can implement stochastic hill-climbing algorithm for finding a combat encounter to present as a challenge to the player.
The algorithm (Fig. 3) is getting the party R, the combat
area O and required encounter difficulty d as an input. It is
supposed to find a suitable set of enemies E in order to
return an encounter c(E; R; O), whose difficulty differs from
a required d by an amount, which is smaller or equal to
d . It works in a stochastic hill-climbing manner. It keeps
adding/removing random enemies to/from the E trying to
match required d. For estimation of D, it queries passed
difficulty matrix M. If particular element M[E; R] is not
present within M, it uses similarity functions SE ; SR to pick
the most similar element of M. For practical real-time
constraints, the algorithm does not perform more then itermax
iterations before terminating.
1: procedure GENENCOUNTER(R; O; d; M; d ; itermax)
2: i = 0
3: Ebest = Ecurr = fpick random enemy for Og
4: dbest = dcurr = jM[Ecurr; R] dj
5: while d dbest & i < itermax do
6: if M[Ecurr; R] d 0 then
7: remove random enemy from Ecurr
8: else
9: add random enemy for O into Ecurr
10: end if
11: dcurr = jM[Ecurr; R] dj
12: if dcurr dbest then
13: Ebest = Ecurr
14: dbest = dcurr
15: end if
16: i + +
17: end while
18: return c(Ebest ; R; O)
19: end procedure
In order to test our approach, we implemented a simple
PC game of the RPG genre, which is mouse-controlled.
Its design is inspired by gameplay mechanics of
wellknown, if a bit dated, RPG games such as Baldur’s gate
(BioWare, 1998) and Planescape Torment (Black Isle
Studios, 1999). A player is leading a party of three preset
heroes through a dungeon, which is a procedurally
generated maze consisting of rooms, which constitute
combat areas where encounters with enemies take place. We
tried to design the game to be fun and to have a certain
gameplay depth. Heroes represent three RPG archetypes:
knight (high health, melee attack only), ranger (low health,
strong ranged attack) and cleric (healer and area
controller). Each hero, apart form the attack action, has three
different skills they can use to affect the fight. A player
can level heroes between encounters, i.e., improve their
health and dealt damage per second. For enemies, there
are 4 archetypes. Some of them having multiple instances
for variety. Each archetype is designed to behave
differently in the combat in order to prolong the learning curve
for the player. Additional information can be found in a
previous master’s thesis [
The combat. Every time the party enters a new room, i.e., opens the door, an encounter is generated inside given the difficulty assigned by the designer (us) to the room. Then, the party enters, the door closes behind it, and the party has to fight spawned enemies until one of the sides is eliminated. The combat happens in real-time, though the player is able to pause it anytime to analyze the situation and reconsider their heroes’ actions. Enemies are driven by a simple reactive AI, that chooses their attack according to a script associated with the enemy archetype. Heroes also attack automatically if player does not intervene, i.e., orders them to use some skill, changes their target or moves them around the room.
The difficulty range. As the party consist of 3 heroes, we modified the range of difficulty to be [0;3]; a difficulty was then the summed portions of health points lost during the encounter.
Difficulty matrix. To generate the initial sparse matrix, we generated 83572 scenarios, in each of which a random party was fighting a random group of monsters. In these scenarios the party was controlled by a very simple script doing random actions. This proved to be a better approximation of player behavior than a script making tactical decisions, which was too strong and produced estimations suitable for a skillful player rather then a beginner. The results of these scenarios were recorded and used as the initial matrix to be modified at runtime. We set the learning rate a = 0:75 for UpdateMatrix method (Fig. 2).
Visualization of the initial difficulty matrix is provided in Fig. 5. 6
To test our combat encounter generator we conducted a pilot experiment with human subjects playing the game. 6.1
As there is no prior work to compare our results to, we designed the experiment to be exploratory only. We were interested to see if the algorithm can adapt initial estimation of combat difficulties to the player and improve the initial estimation of encounter difficulties. Our only hypothesis therefore was that the algorithm would be able to adapt initial difficulty matrix to the ability of players, i.e., it would provide better difficulty estimates. Each participant was given the build of the game to play. The data about encounters was collected by the game itself and stored within online database. The game consist of three levels.
1. Tutorial level. A short and easy level with 4 combat encounters, which were fixed and created by us. The level existed for two reasons. First, it was designed to teach the player the basic mechanics of the game. Second, while the algorithm was not generating enemies in this level, it was still estimating the difficulty of these static encounters and was updating the matrix. Therefore, after the tutorial level the matrix could have matched the player skill more closely.
2. Static levels. Two levels with encounters fixed and created by us. Unlike the tutorial level, the difficulty matrix was not being modified during this phase.
3. Generated levels. Two levels with encounters being generated according to the matrix. The matrix got updated after every combat encounter.
Participants were split into two even groups A and B
randomly. Group A was called static-first as their
members played the game in the sequence 1-2-3. Group B was
called generated-first as their members played the game
in the sequence 1-3-2. The difference wrt. to difficulty
estimation was that for static-first group, there was a gap
in the matrix adaptation between levels 1 and 3. Here we
were interested to see if there is going to be difference
between groups as participants of the static-group should be
more experienced when they enter the third level.
We collected both subjective categorical data from
participants (both quantitative and qualitative) and objective
numerical data concerning combat encounters, collected
automatically by the game. Originally, we were also
interested how would the players rate the game and collected
data on flow via the Flow Short Scale [
Regarding the encounters, for each encounter in levels 1 and 3, the game recorded the enemies spawned, estimated difficulty by the initial version of the matrix and the current version of matrix and the result of the encounter, which is the final observed difficulty. We also generated a visualization of the difficulty matrix state after every matrix update for every participant. 6.4
The experiment was carried out during COVID-19 outbreak in May, 2020. Therefore, all experiments happened online in an uncontrolled environment, typically participants’ homes. We had 22 participants out of which a total of 11 participants were not able to finish the level 3 (either because of a bug in a game, lack of time or not being able to understand all game mechanics) and thus we decided to discard their data from the analysis. In total, we analysed data from 11 participants (Table 1); all but two participants reported they play games more than 2 hours per week (majority more then 10), but these two reported that they played games regularly in the past. We consider both groups to consist of experienced game players only. Participants were split into groups randomly, they were of similar age (20-25). 6.5
Even though all the participants finished level 3, they played a different amount of combat encounters. This was the result of the difficulty we preset for some rooms, where some participants have their parties eliminated and were thus forced to replay the level.
Together, we assembled 260 combat encounter observations. The first 11 observations are irrelevant as they come from the first combat in level 1 where the matrix has been in the initial setting. In total, we analyse 249 combat encounters for which we can observe the differences between the adapted matrix (referred to as ADAPTED in graphs) and its initial version (referred to as INIT in graphs). We mainly analysed with estimation errors, i.e., difference between difficulty prediction of a matrix and the real difficulty observed within the game .
To visualize the data, we are using R version 4.0.5 together with the package ggstatsplot v0.8.0 and its ggstatsplot for group comparisons.
First, we were interested to see whether the algorithm was able to provide better difficulty estimations. For that, we measured errors of difficulty prediction as the difference between predicted difficulty and observed difficulty (negative value means the encounter was more difficulty then it should have been). Data for groups A and B respectively are summarized by Fig. 6 and Fig. 7.
For both groups, mean values between ADAPTED and INIT differ. Interestingly, mean of INIT matrix errors for group A is higher then in group B. This is probably the effect of "static-first" ordering in group A. Majority of data collected for group A happens only after participants played level 2. As the result, they are more skilled and INIT matrix is more off then for group B.
Then we looked how errors of ADAPTED matrices between groups looked like (Fig. 8).
Interestingly they are not much different, which is a bit surprising. Given the previous observation, that INIT matrix has a larger error for group A, we expected the same would be true for ADAPTED matrices between groups A and B. However, that’s not the case. It seems that missing observation from level 2 in group A did not influence the ability of the algorithm to adapt to boosted players’ abilities. The only difference, visually speaking, is the data distribution, which is more packed for group B.
Finally, we checked the error differences between ADAPTED and INIT matrices for both groups respectively (Fig. 9).
Interestingly, the analysis shows that the adapted matrix provided correct predictions more frequently (173/249 times in total 69.5%, 86 / 120 times for group A 71.7%, 85 / 129 times for group B 65.9%). Also means are different for both groups. We think this is the influence of statics-first vs. generated-first level again as INIT matrix had larger error for group A due to longer gameplay. Results per participants are summarized in Table 2.
We do not comment on statistical significance of findings as reported by graphs (e.g. Welch test and others) as not all samples are independent because multiple samples (estimation errors) are grouped according to players. 7
In this paper, we discussed a new procedural content generation problem: the Combat Encounter Generation Problem. We proposed an open-ended formalization of RPG games, in which CEGP arises. Moreover, if the game is not solving the CEGP during runtime, it must be solved by designers by hand during design time. We proposed an approach for solving CEGP consisting of two parts: a) an estimator of combat encounters difficulties, which needs to be able to adapt to players’ ability online, and b) a generator that can propose next encounters given the estimation of their difficulties, which need to generate encounters fast. Our first implementation is making use of a) a custom reinforcement learning algorithm, which attempts to estimate difficulties of combat encounters despite the limited number of observations, and b) utilize stochastic hill-climbing for finding a combat encounter of required difficulty. We presented and discussed preliminary results of the pilot study with human subjects. Even though the number of players is small, which is limiting the results, the number of combat encounters observed is moderate (249). The data shown that the algorithm was indeed able to adapt the difficulty estimation of encounters to players though the prediction was not always better wrt. initial setting of the matrix as computed from synthetic simulations using simple AI as human player surrogates. Given the fact that the number of encounters is huge and our approach is rather simplistic, we deem our results as promising. Encouraged by the results of our pilot experiment, we see many directions for future work.
First, it would be interesting to employ the algorithm in the context of a different game, ideally existing one, though this is usually very challenging technically. Second, if a (large enough) data set on how human players are playing a given game is available, it might be possible to model human-like play in order to experiment with the algorithm without the need of experiments with human subjects. Finally, proposed algorithm is a skeleton that can be configured at many places (e.g., creating different similarity functions or providing different abstractions for combat encounters), thus it would be interesting to observe how it behaves under different configurations.
Acknowledgement This work was supported by the Charles University grant SVV-260588.