As part of a more general research, this paper presents a work in progress experiment for generating videogame mechanics and rules in a fully procedural way. A practical application of the detailed theoretical approach is also detailed as an experiment based on a genetic programming algorithm that allows to generate new video game speci cations ful lling the most important aspects highlighted by the game designers. To meet those requirements, we take advantage of the potential of the new features included in the last version of Xml-Based Video Game Description Language (XVGDL), termed XVGDL , and the corresponding advances in the XVGDL Game Engine (XGE ). Taking advantage of both tools, the execution and the evaluation methods are about to be included in the experiment making the process to be performed without any human intervention. We expect to have new videogame speci cations as the output of the process, created according initial requirements and designers' needs, with a minor e ort of programming.
This work in progress is framed into a more general research in the eld of video game de nition languages (VGDL) and could be considered as a particular case of procedural content generation (PCG) (although it will be focused on non-visualization components). Applying di erent computational techniques for generating game content directly related to the graphics or visualization{such as maps, levels or game components{is one of the most common approaches.
In this research, we are focused as well in other non-visual aspects of the game like game mechanics, game rules or game end conditions. After developing a new VGDL called Xml Video Game Description Language (XVGDL ) and the corresponding Game Engine supporting XVGDL game speci cations (XGE), at the moment, just intended to be a basic game engine to allow to play XVGDL game speci cations, the research is currently in a experimental phase in which some experiments are being performed to demonstrate and take advantage of the XVGDL and XGE features.
The interested reader is referred to [
Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
At this point of the global research, we can highlight the following aspects: { XVGDL is a complete VGDL with powerful features to take advantage of and contributing some improvements compared to other existing VGDLs implementations. { XGE is a complete functional game engine with research purposes that allows to execute XVGDL speci cations and provides great feedback to evaluate games' speci cations. { XVGDL and XGE are already implemented and presented. Used together, they are a powerful tool to develop real experiments that can de nitely contribute during the game design phase, providing the game designers useful information and feedback during the game play and after game executions.
The new step in our research path is, using both XGE and XGE features, to provide a software that will be able to generate game mechanics. As a general concept, that can be understood as generating new games as they will be potentially di erent games one from each other. This is actually a previous stage to generate full games automatically, including some other concepts like graphics, maps/levels de nitions, game objects, etc . . .
This work in progress presentation is structured as follows. In section 2, the state of the art is exposed including some of the most relevant related works and also explains more in deep the XVGDL and XGE features that allow to evaluate and optimize video game speci cations. Following, section 3 and its di erent subsections explain in detail the approach that we are following to generate game mechanics and how the genetic programming algorithm is developed to help on the main goal of the experiment. In particular, in subsection 3.3, the practical experiment approach is described including the requirements, the algorithm implementation and the expected outputs in the latest subsections. In subsection 3.6 we analyze then the expected outputs and how this experiment can contribute to the community. Last section 4, nally presents the conclusions and future work, mentioning the following steps to complete the global research project and the aspects to continue improving XVGDL and XGE . 2
Bio-inspired algorithms and, in particular, genetic programming (GP) has been widely used in many di erent research and engineering areas, including lots of many real examples and applications of this technique. Studies and researches in the computer games (videogames) eld are not an exception in this sense, and we can nd also existing works that take advantage of the GP features.
Focusing on computer games eld, GP has been applied to agents [
Getting deeper into game mechanics sub-area inside games research, many
recent publications about this topic can be found, but at the moment, it is
di cult to nd works directly related to game mechanics generation. Some of
the most interesting works in this particular area are related to game mechanics
modelling and how they a ect somehow to the players [
As stated, there are many di erent approaches that contribute so much to
the community, although it seems less common to nd game mechanics (game
design) generation approach using Genetic Programming (GP). As an example,
[
As stated in the previous chapter, Game mechanics in general represent a very
interesting and active game component to study. The research on game
mechanics can be done from many di erent approaches, ranging from theory to practical
applications. As aforementioned, we can not easily nd works that are fully
focused on game mechanics generation automatically and, as a consequence, there
are just a few approaches to generate complete games, as an example [
The main reasons and barriers that we nd in order to develop a game mechanics generator include the following points: { There is no standard VGDL that allows to extend the research in this and other related elds. This makes the advances to be so slow and so coupled to a concrete solution. { There is no current approach that allows to test and experiment for games of di erent nature. The point here also is that the existing works in this eld are heavily tied to a concrete example or implementation of a game, making it di cult to be extended. { Evaluating the computational creations is not a easy task to be performed in a procedural way, and that is a key part of the whole process. A reliable way to evaluate games is needed to automate the game generation process and, in particular, the game mechanics generation.
The lack of having an standard way of describing game speci cations or in particular, game mechanics, is in our opinion, the most important barrier to cross. In this sense, the publication of XVGDL has been great contribution as the majority of those problems, making possible to extend the research in elds like game mechanics, without focusing on other points, like describing or specifying a game, an example to use, a game engine to execute, etc...
With previous experiments and researches, it has been demonstrated that XVGDL and XGE are a really useful tools to explore and can contribute so much with their potential and, with this new work, we want to give a new step forward in this eld, making possible to create mechanics and/or games, taking advantages of the mentioned researches. In the next sub-section, the process of generating game mechanics using an XVGDL approach is fully detailed. 3.1
Given the ability we have to specify very di erent parts of a game at the content, visualization or mechanics level, this work in progress presents a procedure that allows to generate parts, or even complete, videogames speci cations using XVGDL . Chasing the idea of applying a genetic programming (GP) technique and taking advantage of the XVGDL nature, an speci cation can be easily interpreted as a tree, by the inherited representation of an XML itself. At rst, it seems a feasible solution to apply GP to nd new solutions (speci cations) that represent new games.
For our case of study in particular, the XVGDL has by de nition an structure which is really likely to be applied to a GP approach. XVGDL (based on XML language) can be easily transformed into a tree representation. Also, di erent nodes or even complete branches can be de ned so they can be t perfectly with the GP de nition, being used in the di erent GP algorithm phase.
Being XVGDL a concrete implementation of the eXtensible Markup Language (XML), it can therefore easily be interpreted as a tree structure. The Document Object Model (DOM) is the foundation of XML documents have a hierarchy of units called nodes. DOM, is a way of describing the nodes and the relationships between them. A DOM document is a collection of nodes or pieces of information organized in a hierarchy.
If we interpret an existing speci cation of a game in XVGDL language taking into account these mentioned characteristics, we could easily represent the speci cation in the form of a tree and, in addition, separating the XVGDL nodes theoretically and by concepts as indicated in the Figure 1.
As it can be appreciated in the Figure 1, all the information of a speci cation of a game in XVGDL would be lower in the hierarchy of each of the main nodes represented in the image. In addition to the main parent node, at the rst level of the hierarchy, the detail of each of the levels represented is speci ed below: { Structural Information: At this level, all XVGDL nodes related to the structure of the game, its maps, levels, screens or its controls, as well as the general properties that are established, are represented. { Graphic Information: From this level, all XVGDL nodes related to graphic aspects would hang. We talk, for example, about details at the renderer level, the bitmaps associated with each of the game objects or the screen layout. { Mechanics Information: All XVGDL nodes related to game mechanics. This node would be much more extensive in depth including game rules, end conditions, game states, the objects present in the game and events. { Arti cial Intelligence (AI): Considering it has importance enough to have its own node. AI sub-tree includes all the information and speci cations related to agents and AI applied to any object in the game. It also includes all di erent AI implementations not directly related to an object, but a ecting somehow during game play. As an example, an algorithm implementation to set the weather conditions during the game play or the game di culty according to the player conditions and behaviour. 3.2
We have seen, in general terms, how we could conceptually group XVGDL elements in four di erent dimensions. From these nodes, let's call them main, in general the intermediate nodes will represent concepts (existing elements/tags in XVGDL ) as well as their properties. To complete the tree, the leaf nodes will represent speci c values for each of the properties of the parent node. Each leaf node will have a value in relation to the parent node it represents.
As an example, in Figure 2, the representation of a bitmap element de ned in XVGDL is detailed from the following code: 1 <bitmap id='PlayerRunning' file='/bitmaps/player-running.png' />
In Figure 2, the blue Bitmap node represents an element of the XVGDL . The red nodes named id and file represent properties of the parent node. The leaf nodes, in green, represent speci c values of these properties.
Following the same color code represented in Figure 2 (blue for components, red for attributes and green for values), another bit more complex case is represented in Figure 3, which shows graphically the tree representation of the following XVGDL code: : 1 <rule name="eatSmallDot" type="collision"> 2 <ruleAction objectName="pacman" result="score-up" value="100" /> 3 <ruleAction objectName="smallDot" result="disappear" /> 4 </rule>
Following this type of representation and given the four main nodes from which the information hangs (structural, mechanical, IA and graphic), we can represent an entire speci cation in the form of a tree and work with it in a future genetic programming experiment. 3.3
Supporting the underlying research, a practical experiment was conducted to
demonstrate the potential of this approach and also to be able to extract valuable
information about the game design in a particular case, using an speci cation
of the Pacman [
As aforementioned, the main idea of this global research is to generate full games from scratch (or at least, with a minimum e ort of development), but at this point, we are focusing on the game mechanics and game rules. That means that the whole game generation is not covered.
This approach will allow us to create new game speci cations including new mechanics. Practically, this means we can create new games. Not only that, but also if we apply the same solution to all the elements in the XVGDL tree representation, is easy to extrapolate it to di erent nodes in the tree, that is, covering not only mechanics but also other game components.
As discussed above, an algorithm can be perfectly applied to any part of the speci cation. As a future opportunity to explore, it would be a matter of deciding what elements we are going to consider in a future experiment to allow applying the same idea (GP approach) to generate other di erent videogame speci cation components. With the theoretical approach, the representation and division that we have detailed in the previous sections, we can easily proceed to other game components, being important in this particular work to limit the generation for the experiment. We have identi ed the components or sections where the algorithms can be applied, in such a way that we can complete the game generation, dealing with the following points globally or individually: { Generation of game mechanics (Main mechanics node), covered by this work making possible to generate di erent games with a base set of components. { Generation of game's components at a visual level (Main graphics node), covering all generation of graphics and visual components of a game. { Generation of game's levels and/or maps (Main structure node), automating the creation of new game maps or levels. 3.4
To carry out the generation of game mechanics we should have the following elements: { A seed, that is to say, a base version of a game, from which we could generate the part that interests us. It could be as basic as we want, thus being the more complex generation process, or we could have a seed in which the structural and graphic information is de ned and is immutable, and we apply the generation only at the level of nodes related to mechanics. { A repository containing an initial set of rules, termination conditions and events.
At this point we need what we call a Primary Data store. This is important in order to make sure the generated games (experiment outputs) will be correct and valid in terms of game speci cations. That means that the games will have sensible rules and mechanics, end conditions to make sure the game will nish and some basic de nitions, assuring the game can be executed properly.
So, the main requirement now before starting the generation experiment will be to make sure we have a data store, keeping an initial set of rules (mechanics) and end conditions, as well as basic game de nitions. Taking advantage of the current development, of XVGDL and XGE , we have created a simple process that ful lls the data store as needed. Di erent combinations of all possible values for rules and end conditions are performed in order to have the rst base set of rules. As aforementioned, basic game speci cation (for Pacman in this case) has also been used to store a base game de nition which will be evolved to a variant of the original video game using the GP approach. To make sure the data store is accessible from di erent sources, at the moment, data is stored using three di erent sources of information, a relational data-base, a local data set (in les) and a secured access to a S3 bucket from AWS. Figure 4 expose graphically this procedure and the communication between di erent stacks involved in the videogame mechanics generation process. As already explained, the implementation approach is to use GP, implementing an algorithm that, starting from a seed, will nd for di erent interesting videogames' speci cations, according to previously de ned requirements. The initial seed can be already described (con gured) or even can be generated from the aforementioned repositories, at last, it will be the base game to evolve. The base seed will be slightly modi ed to make sure we have an interesting population to start the algorithm. This is performed using a simple software in charge of generating new values for the base speci cation de ned nodes. Once the initial population of speci cations are obtained, those must be transformed into the tree form, as detailed in sub-section 3.2 making possible then to apply the main steps de ned by a genetic programming algorithm. In a general way, we have de ned the following operations: { Selection: We would apply an evaluation function to each of the solutions found. Is part of this experiment to de ne a tness function to evaluate each possible solution, focusing in parameters that can be de ned by the game designers before starting the experiment. Aspects like wining/loosing the game, time to complete, number of lives remaining, etc... will be considered to create the tness function.
Crossing: From the population of speci cations that we have at a given moment, the crossing of individuals could be done by exchanging leaf nodes (values) for certain aspects of the game, or directly exchanging sub-trees that represent a speci c structure, including elements and their values. Mutation: We could drastically change a complete branch of a tree from the elements that we have in the repositories or change leaf nodes (values) for distant values (within the allowed ranges).
From the crossover and mutation operations, we would have solutions that we could evaluate thanks to the tness function that we de ne and applying the characteristics of XVGDL .
Somehow, even not starting from speci c game requirements, we could have very di erent games visually, structurally and mechanically, always starting from some generic objectives to be evaluated, such as the total playing time, assessment of victory player, di culty level, etc. 3.6
The main output of this experiment will be di erent videogames' speci cations that, starting from a base game and given initial designers' requirement, are valid and complete, in such a way that they are playable games, using XGE , the game engine interpreter of XVGDL game speci cations. It is important to highlight here the following aspects.
{ During the experiment, we will apply a tness function to every single solution guided by the designers' criteria in such a way that we will nally have videogame speci cations that will maximize the designers' initial requirements. { The output, which will be a population of videogames, will nally represent game speci cations that can end up in completely di erent games one from each other, as eventually, the rules and mechanics will be di erent for each solution.
It is important to point as well that this work is not oriented to nd the best solution (best game speci cation in this case) as there is no such solution. The main idea is to nd a set of solutions, ful lling some initial requirements, making sure the games are playable (correct). A solution is not better than other, but the output will help designers to de ne and describe new game speci cations, according the ones obtained for the nal population. Even those nal speci cations could be then gathered into a single game speci cation, just taking into account the most promising game mechanics and rules from each of them.
We have covered game mechanics and rules but as the XVGDL is easily transformed into a tree, the whole game generation is a feasible future opportunity to explore.
In this work, we are taking advantage of the already implemented and presented XVGDL and XGE . With this experiment, we demonstrate the important contribution and a bunch of possibilities open using those tools. This research path is a really promising branch, opening many di erent new opportunities for future researches.
Although GP is widely used in videogames research elds, generating game mechanics automatically will be a great contribution as there is not so much work in the library in regards to this particular sub-area.
During the paper we have also mention how this proposal can be applied to other game spec cations' components, not only considering game mechanics. The process detailed here can be extended to maps/levels, AIs and other graphical components. In this sense, we consider this work as a core point to nally be able to generate complete games in an procedural way, which is also in our research path. This, or a similar proposal, can be used for future implementations to keep the same approach in generating graphics or structural components of a videogame, completing the full automatic generation.
The evaluation of these computational creations is a key factor to consider here, as we need to ensure that the solutions accomplish the designers' speci cations and requirements. Previous works optimizing game speci cations with XVGDL and XGE , cleared the way to perform these evaluations and allow us now to perform this work with key tools, ideas and providing a good level of reliability.
Algorithm performance and data will be analyzed once the executions will be nished. Hopefully, GP will be a good approach to get the expected output, although applying some other search techniques or approaches will be evaluated for future experiments.
We consider this work as a core point to nally be able to generate complete games in an procedural way. While this idea needs to be investigated yet, this work will contribute so much to the automatic complete videogame generation, together with the other approaches mentioned in the paper.
This work has been supported by Spanish Ministry of Economy and Competitiveness (MINECO) projects: EphemeCH (TIN2014-56494-C4-1-P), and DeepBio (TIN2017-85727-C4-1-P) { Check: http://blog.epheme.ch and http:// blog.deepb.io {, and Universidad de Malaga, Campus de Excelencia Internacional Andaluc a Tech.