Type: Evaluation Essays
Sample donated: Gina Williams
Last updated: April 19, 2019
Abstract—In this paper we represent a pattern generator NMF-GVG-LG using Non-Negative Matrix Factorization (NMF General Video Game Level Generation).
We use ?ve levels of zelda game to train NMF models that learn patterns about the components of the game. The developed model is then automatically generating content that resemble the training data. The methodology we followed and the results show that the proposed generator has powerful capability to generate game content.I.
INTRODUCTION Researchers are increasing their interest in receiving automaticcontentgenerationofgameinthegamedevelopmentand game industry. There are some successful applications in the literature which motivates towards further investigation and demonstrates the application of this research direction. The ?rst major implementation of procedural content generation is in the game rogue where PCG is used to overcome the limitation of storage by allowing the creation of all levels in runtime. Different PCG techniques are recently employed in several commercial games for providing variations, support human designers, and cut development budget. (Shaker, Togelius, and Nelson 2014). Some remarkable use-cases include the creature creation interface in spore which allows procedural animations of custom design, and the random map generation in Civilization IV (Firaxis Games 2005).
However the focus is mostly on automatic generation of individual aspects of game content such as weapons in space shooter games ( hasting, guha and Stanley 2009) , car racing game tracks (cardamone, Lanzi 2011), level design for physics based games and levels in platform games. Some attempts have made the problem of evolving the complete game but in board games or arcade games the successful implementations are still limited. Several studies have witnessed attention which has been conducted towards realizing the automatic generation of 2D games levels.
Many of the studies examined the popular games Super Mario Bros (SMB). Each of the generators proposed for SMB was developed independently and has its distinctive characteristics. While each excels in creating speci?c level they are limited by the design choice imposed by designer or by choice of methods. The grammatical evolution generation (Shakir et al. 2012), use a design grammar and score to formalize its generative space. It is certain that the use of grammar helps understandability permits straightforward modi?cations, once evolution process starts, the content explode is con?ned by the ?nal grammarspeci?ed and exploring a new space is only possible through a new run after tweaking the grammar. In a recent study (horn et al. 2014) many dissimilar generators for this game have been analyzed and analysis experiment is conducted in an attempt for a frame work where content generators can be thoroughly investigated and compared.
The study showed that although the generators are quiet different; they all exhibit a limited generative space the matrices de?ned. During game play and after playing some level the player becomes aware what will come next so the surprise factor will decrease over time resulting in an increase in the state of boredom and ultimately quitting the game. The presence of a certain degree of unpredictability is important factors for the experience of fun.
The PCG is one way to compensate for the surprise factor is to imitate human designer style. According to Arthur Samuel Machine learning is de?ned as the ?eld of study that gives computers the ability to learn without being explicitly programmed. A more formal de?nitionwasgivenbyTomMitchellasacomputerprogramis said to learn from experience (e) with respect to some task (t) and some performance measure (p), if its performance on t, as measured by p, improves with experience e then the program is called a machine learning program. Newly there has been improved interest in the use of machine learning-based approaches to create video game content ( Riedl, 2016) (Dahlskog ,2014) also called PCG through machine learning or PCGML (Summerville ,2017). on the other hand, most of these approaches are based on modeling level geometry, without considering how the player moves through levels, which is an important part of level design. Supervised learning is used especially if the state space is large. In supervised learning one must determine how training dataisgenerated.Itisclear-cutforsimpleenvironments.
Every instance in any dataset used by machine learning algorithms is represented using the same set of features. The features may be continuous, categorical or binary. If instances are given with known labels (the corresponding correct outputs) then the learning is called supervised. Boosting variations and supporting unpredictability by combining patterns from different generators are the aims of this paper. We propose an approach NMF-GVG-LG based on combinations for content creation using non-negative matrix factorization (NMF) method. To apply NMF the large space of representative content is extractedfromdissimilargeneratorsofZelda.EachNMFmodels learns meaningful patterns also approximate the trainingdata and generate novel content for speci?c game.
II. LITERATURE REVIEW Role of computer games is increasing in our lives day by day. In the whole world, Hundred of Millions of players love to entertain themselves by games such as FarmVille, World of Warcraft, Call of Duty, The Sims, and StarCraft. Procedural technique is a way to make any complex game much easier in limited amount of time by reducing burden on game content designer.
The main though behind this technique is that game content is generated automatically by executing a well de?ned procedure rather than manually by human designers.(Hendrikx , 2011 ). Now a days Procedural content generation (PCG) is commonly practicing area of research in game design. Researchers in arti?cial intelligence are creating more expressive methods for having a computer create levels, weapons, terrain, and even game rules . Procedural content generation (PCG) is used in a variety of ways in games, with the common justi?cations of replay ability and tailoring content for an individual player.
(Smith, 2014 ).There is relation between procedural content generation (PCG) and design patterns in games. In digital games PCG refers to automated or semi-automated creation of game content by using algorithms. Design patterns are a way of structuring design and the design process into recurring elements. Design patterns can provide answers to those problems which faced by the game designer. Patterns can also be used in the procedural content generation as objectives like evaluation/?tness functions or constraints in search-based PCG. (Dahlskog,2012 ) According to Daniel non negativity is a most useful constraint for matrix factorization which can learn a parts representation of the data (Daniel D.Lee ) .
To generate levels for any puzzle game seems interesting but it also cause lots of problems like Puzzle Games ideas have no restriction. For instance some games have continuous space where game actions depend on perfect timing and players skills like angry birds. While other games have discrete space space where game actions depend on the best sequence of actions regardless of the time taken like sokoban. Collectively their work consists of three following steps: Generate ,Check, Evaluate. Levels are generated from amalgamation a group of vertical slices called Micro Patterns. Non-Negative Matrix Factorization (NMF) technique is use to capture the patterns of level design of SMB by Shaker and Abou-Zleikha.
According to them NMF can be implemented on any game if it has a large amount of levels to learn the patterns from them. NMF method factorizes these levels into two new matrices: Pattern Matrix: captures the patterns found in each vertical slice of SMB. Weight Matrix: captures the percentage of each pattern to appear in the current level.(Khalifa,2015) A fundamental technique in dimensionality reduction is Principal Component Analysis (PCA).
One main problem with PCA is that the basis vectors have both positive and negative components, and the data are represented as linear combinations of these vectors with positive and negative coecients. The thought of non-negative matrix factorization can be tracedback to a 1994 paper of Paatero and Tapper . Their aim was to perform factor analysis on environmental data, which problem involves nding a small number of root causes that explain a large set of measurements.
Each factor is a positive combination of some elementary variables. ( Joel A. Tropp)III. PROPOSED TECHNIQUEA. VGDL B.
GVG-AI C. GVG-LG D. NMF GVG-LG NMF-GVG-LG is a Non-Negative Matrix Factorization General Video Game Level Generation technique that is implemented by using GVGAIG framework and python language.
We used this technique for level generation. In Non-Negative Matrix Factorization(NMF), the matrix V is represented by the two smaller matrices W and H which when multiplied approximately reconstruct V. Matrix W represents patterns extracted for each component and H represents coef?cient matrices corresponding to the weights applied to each pattern. The game we are using for our experiment is Zelda. In this paper, we focus on utilizing NMF models as a generator.
The NMF GVG-LG generator is developed to automatically generate content for the game. The main goal of this study is to generate new levels based on NMF training. The dataset of ?ve levels Matrix(W) is used as an input for the level generation. Utilizing NMF for level generation corresponds to the extraction of parts (patterns) Matrix W from a set of training levels V.
Fig. 1. The ?gure shows that the framework implemented to estimate the model and to use it to generate new content.A matrix is used as an input to construct eight NMFs.
Levels are ?rst converted in to binary and arranged the matrices that are used as input to estimate W and H for each level component. And then create a new level coef?cient matrix generated from level0(means previous level)that represents weights applied on matrix Wand thetransformationinwhichconversionofthebinarymatrixtocharactermatrix and reverse in to the game structure to generate a new levelE. Parameters in Matrix Representation Wall(Vw): A vector w represents that wall is generated in the matrix.Floor monster moment quick(V1): A vector 1″ represents that monster is generated, and it has a quick moment. Floor monster moment normal(V2): A vector 2 represents that monster is generated and it has a normal moment. Floor monster moment slow(V3): A vector 3 represents that monster creates and it has a slow moment.
Floor(V.): A vector . represents that ?oor generates. Floor no key(player)(VA): A vector A represents that key is not generated but player creates.
Floor goal(Vg): A vector g represents that it is the starting point of player and it is players goal. Floor key(V+): A vector + represents that After key collection, the player achieves a goal and level changes. F. Training A set of ?ve levels is used to train the model. As NMF is a mathematical model, it doesn’t accept characters directly. Our game description is in characters form. So, we make game in a form so that mathematical operations are performed, and it accepts our character input. For this purpose character to binary conversion is performed.
We ?rst convert character matrix W into binary matrix. We have 8 parameters w, 1, 2, 3,., A, g, +. In Matrix where w is present, it means that wall is generated. In Matrix where 1 is present, it means that monster is generated, and it has a quick moment. In Matrix where 2 is present, it means that monster is generated, and it has a normal moment. In matrix where 3 is present, it means that monster is generated, and it has a slow moment.
In matrix where . is present it means that ?oor generates. In matrix where A is present, it means that key is not generated but player creates. In matrix where g is present, it means that it is the starting point of player and it is player/s goal. In Matrix where + is present it means that After key collection, the player achieves a goal and level changes.
When we tune our parameters, it gives us different results. Earlier when we tune it gives us a zeros matrix, so we tune these parameters to get a binary output. If the element is present in the matrix then it is added as “1” otherwise “0”. First parameter is w. w parameter is of 9×13.In w parameter we have 9 rows and 13 columns. In matrix where w is present, it is represented as 1 otherwise 0.
And we have 5 levels. It means that we have 45×13 matrix of w. This is training set of NMF w matrix.
For 1 parameter we have 9×13 matrix. It means that we have 9 rows and 13 columns, so for 1 parameter as levels are 5, so we have 45×13 matrix. In matrix where 1 is present, it is represented as 1 otherwise 0. This is training set of NMF 1matrix. For 2 parameter we have 9×13 matrix.
It means that we have 9 rows and 13 columns, so for 2 parameter as levels are 5, so we have 45×13 matrix. In a matrix where 2 is present, it is represented as 1 otherwise 0. This is training set of NMF 2matrix. For parameter 3 we have 9×13 matrix. It means that we have 9 rows and 13 columns, so for 3 parameter as levels are5 so we have 45×13 matrix. In matrix where 3 is present, it is represented as 1 otherwise 0. This is training set of NMF 3 matrix.
For parameter . we have 9×13 matrix. It means that we have 9 rows and 13 columns, so for. parameter as levels are 5 so we have 45×13 matrix.
In matrix where. is present it is represented as 1 otherwise 0. This is training set of NMF . matrix.
For parameter A we have 9×13 matrix. It means that we have 9 rows and 13 columns, so for A parameter as levels are 5, so we have 45×13 matrix. In matrix where A is present, it is represented as 1 otherwise 0. This is training set of NMF A matrix.
For parameter g we have 9×13 matrix. It means that we have 9 rows and 13 columns, so for g parameter as levels are 5 so we have 45×13 matrix. In matrix where g is present, it is represented as 1 otherwise 0. This is training set of NMF w matrix. For parameter + we have 9×13 matrix. It means that we have 9 rows and 13 columns so for the + parameter as levels are 5 so we have 45×13 matrix. In matrix where + is present, it is represented as 1 otherwise 0.
This is training set of NMF + matrix. Now the binary matrix generation.For w parameter,the training set matrix of 45×13 and a input prediction matrix of 9×13 and get the new matrix of w. For 1 parameter,the training set matrix of 45×13 and a input prediction matrix of 9×13 and get the new matrix of w.
For 2 parameter,the training set matrix of 45×13 and a input prediction matrix of 9×13 and get the new matrix of w. For 3 parameter,the training set matrix of 45×13 and a input prediction matrix of 9×13 and get the new matrix of w. For . parameter,the training set matrix of 45×13 and a input prediction matrix of 9×13 and get the new matrix of w. For A parameter,the training set matrix of 45×13 and a input prediction matrix of 9×13 and get the new matrix of w. For g parameter,the training set matrix of 45×13 and a input prediction matrix of 9×13 and get the new matrix of w. For + parameter,the training set matrix of 45×13 and a input prediction matrix of 9×13 and get the new matrix of w. To estimate an NMF Model, the multiplicative update algorithm is used which is shown below: NMF = F(W,H) = 1/2||V HW||2 (1)Fig.
2. Multiplicative Update AlgorithmThe ?nal NMF model consists of eight independent models (NMF w, NMF 1, NMF 2, NMF 3, NMF ., NMF A, NMF g, NMF +). Each level matrix appends next to other like NMF w appends to NMF 1, NMF 1 appends to NMF 2, NMF 2 appends to NMF 3, NMF 3 appends to NMF .,NMF . appends to NMF A, NMF A appends to NMF w and ?nal NMF w appends to NMF +.
Training the NMF model results in an approximation of eightpartbinarymatrices.EightpartWmatricesthatrepresents patterns extracted for each component and Eight part H matrices that represents weights applied to each pattern. This is shown in ?gure given below:Fig. 3. Base MatrixFig. 4. W MatrixFig.
5. 1 MatrixFig. 6. 2 MatrixFig.
7. 3 MatrixFig. 8. Dot MatrixG. Testing By coef?cient or dot product levels are generating based upon the success of the previous level.The levels become more dif?cult if player is continuously completing the levelsFig. 9.
A MatrixFig. 10. g MatrixFig. 11. + Matrixsuccessfully.
If player wins the game a new matrix is generated and when player loses the game the matrix is not generated. The output display of different stages of zelda game levels are shown below:Fig. 12. Game startsFig. 13.
Player wins new level generatesH. Style Transfer Style Transfer is basically transformation which means that the multiplication of Ws and Hs matrices which covert binary matrix to character matrix and reverse into game structure. TheFig. 14. Player lost level is not generatedNMF model results in an approximation of eight part character matrices. Our NMF GVG-LG model is constructed to estimate Ws and Hs matrices.
We give input of 1st level,and on the basis of 1st level it generates new levels.Because training is completed now.We trained our NMF GVG-LG on all levels of zelda game. We constructed NMF GVG-LG till level n, so it automatically generates new level every time.Levels are generated till a player wins the game. After transformation, a matrix of 9×13 is generated. And as a result, our NMF-GVG-LG is constructed.
We implement this technique in python language by using NMF machine learning library.Python language is one of the most ?exible language and can be used for various purposes.The multiplicative update algorithm is implemented in python.
We test that new levels are generated according to our requirement, so we choose python for implementation as python is a powerful machine learning language. We embed python function into java through command line. In java, it is implemented by using GVGAI framework and it will give us results. Character conversion of a matrix which is our output is stored in a text ?le. And every time it generates a new Matrix W. These steps should be followed to run python from cmd. 1.Open cmd and write cd.
./ 2.Then again write cd and copy the ?le path of Zelda game and paste it on cmd. 3.
Then press enter and again paste the path and writes python and python ?le name then the output of a character matrix is displayed. The output display of matrices is shown below.Fig.
15. Character Matrix 1Fig. 16. Character Matrix 2Fig. 17. Character Matrix 3Fig. 18. Character Matrix 4Fig.
19. Character Matrix 5Fig. 20.
Character Matrix 6IV. EXPERIMENTATIONA. Linearity B. Lineancy C. DensityV. CONCLUSION This paper proposes a use of NMF GVG-LG Non-Negative Matrix Factorization(NMF General Video Game Level GenFig. 21. Character Matrix 7Fig.
22. Character Matrix 8eration) for modeling and generating game content. To train the model,?ve levels of Zelda game are used as input. The levels in the training dataset are converted into sequences in which NMF models are built and learn patterns about the game components. The experiment is conducted to test that new matrices are generated. The results show that the suggested NMF GVG-LG based generator can mimic the input levels used for training. And as a result, a matrix of W is generated which is a character matrix and our ?nal output.