Development of random level generator for PoP1 using genetic algorithm

Discussions about all other tools (CusPop, SAV/HOF editors) and hex editing.
Post Reply
User avatar
starwindz
Sultan
Sultan
Posts: 133
Joined: March 8th, 2009, 4:48 pm

Development of random level generator for PoP1 using genetic algorithm

Post by starwindz »

1. Background
Several years ago I have developed the random level generator for PoP1. But it is a pre-defined chunk based level generator so it is not true random. Always I would like to make the true random level generator for PoP1 but I could not know how to start to make the algorithm for true random level generation.

2. Motivation
Recently I have found some interesting technical documents about the true random level generation theory and Norbert let me know some web site, youtube movie and documents as follows. That algorithm is mainly based on the genetic algorithm and the technical game programming theory. So I has tried to make some program based on PDF documents.
1) Technical document as PDF format (Refer to attached screenshots #1, #2, #3)
http://hdl.handle.net/10362/18497
* Short version of PDF document is attached in this article.
2) You tube movie
https://www.youtube.com/watch?v=cNqbtqbuh-0
3) Level editors
http://platformer.gearmind.com/
4) Simple genetic algorithm written in C++
(It is a C++ program but I think it is a C program since it does not use any C++ syntax.)
https://people.sc.fsu.edu/~jburkardt/cp ... le_ga.html

3. Issue
However I have come to know that it is very difficult for me to develop the level generator by only reading that document since the specific technique looks very difficult, especially graphical analysis and genetic algorithm implementation such as crossover, mutation, fitness function and post-processing. The PDF document does not contain the source-code-level information and data. Also the software and source code of that web site looks commercial, direct use of the source code is not proper since it is not 'open-source and freeware'. (Currently the source code is not public, so I have already asked to author for sharing the source code but it would not be possible.)

4. Solution
In order to cope with this issue and this limitation, I think that some people such as David or other people can make the random level generator based on PDF document without using the original source code of software in platformer.gearmind.com. How about my idea? And is there any other idea to make the TRUE RANDOM LEVEL GENERATOR!.
Attachments
Using Graph Based Analysis to Enhance Automatic Level Generation for Platform Videogames.pdf
(1.42 MiB) Downloaded 107 times
Enhancing level difficulty and additional content in platform videogames through graph analysis (Mourato).pdf
(535.17 KiB) Downloaded 87 times
Automatic level generation for platform videogames using Genetic Algorithms (Mourato).pdf
(649.96 KiB) Downloaded 82 times
00.png
01.png
02.png
Last edited by starwindz on April 1st, 2017, 7:53 am, edited 5 times in total.
User avatar
Norbert
The Prince of Persia
The Prince of Persia
Posts: 5743
Joined: April 9th, 2009, 10:58 pm

Re: Development of random level generator for PoP1 using genetic algorithm

Post by Norbert »

starwindz wrote:How about my idea? And is there any other idea [...]
It's interesting subject matter.
When I think of a way to do it, I usually think of this.
But I'm not an academic like the people who wrote that thesis. :)
salvadorc17
Calif
Calif
Posts: 553
Joined: August 27th, 2011, 2:04 am

Re: Development of random level generator for PoP1 using genetic algorithm

Post by salvadorc17 »

This does also include generate random tiles inside each room, like apoplexy does( or not?) or just like rearrange the rooms in random positions?
User avatar
starwindz
Sultan
Sultan
Posts: 133
Joined: March 8th, 2009, 4:48 pm

Re: Development of random level generator for PoP1 using genetic algorithm

Post by starwindz »

'Main principles and motivation of the random level generation' and 'Genetic Algorithms overview' are shown as follows.
3.1 Main principles and motivation
As previously referred, the generation process was created focusing, in particular, the videogame Prince of Persia. However, we believe that, with proper changes, a similar approach can be used for a generic platform game. The most significant aspect that guided that inspiration is that this game, like many others, has areas represented in a grid. Essentially, each level is composed by cells, grouped in screens of 10 by 3 cells, as it is possible to see in the screenshot provided in Figure 2, where cells have been delimited.

This structure based on cells allows us to think about two main aspects. First, it is theoretically possible to generate all conceivable levels for this game by generating all possible combination of cells. Secondly, it is plausible to construct a system that can test a generated level regarding movement (and possibly some more aspects) and reasonably perceive its quality. Consequently, the main issue is that, in practice, it is not possible to test all conceivable levels. A simple screen where, to make it simple, cells have only three possibilities (empty, wall block and simple floor, as show in the images of Figure 3) consists of 3^(10*3) combinations and, as a matter of fact, one single screen is not much of a level.

With this in mind, a stochastic solution appears to be plausible as a way to tackle the problem. In one hand, it would provide different results in different runs and, in the other hand, it provides an adequate sampling on all possible solutions without testing them all. Inside stochastic algorithms and techniques, the usage of Genetic Algorithms appeared as an interesting solution because this is a case where it is not trivial to define an operator to explore alternative solutions. There is no direct perceptible relationship among levels to be represented in a tree as it is complex to define a set of successors for a particular level. Also, the previously referred cell based representation for levels can be mapped with some ease in a structure that can be used with genetic operators, as we will see next.


from attached PDF document(Short version) page 3
3.2 Genetic Algorithms overview
As stated before, Genetic Algorithms mimic real life evolution, in particular based on Darwin’s theory of Natural Selection. In short terms, this theory states that living beings that fit best their environment are more willing to survive and reproduce. Consequently, their features are reinforced in future generations. Features change over time due to natural mutations and mutual heritance.
In a Genetic Algorithm, one represents Individuals, coded with certain data (genotype) that will manifest some effective features (phenotype), in the same way it happens in nature. To represent evolution, the system has to be able to perceive the inherent quality of each individual. Genetic Algorithms simulate the process of evolution by sorting a set of individuals (a generation) and making the most scored more whiling to continue to the next generation. For this purpose, a Fitness Function is defined to evaluate an individual with a certain score. In addition, after a new generation is defined, according to some probability parameters, mutations are applied and some individuals are combined among themselves.
In the next sub-sections we present a possible level representation, a corresponding fitness function and crossover and mutation operators.


from attached PDF document(Short version) page 3
Attachments
Automatic level generation for platform videogames using Genetic Algorithms (Mourato).pdf
(649.96 KiB) Downloaded 86 times
summary_fig2 and fig3.png
Falcury
Calif
Calif
Posts: 565
Joined: June 25th, 2009, 10:01 pm

Re: Development of random level generator for PoP1 using genetic algorithm

Post by Falcury »

This is very interesting. It's nice that they we able to use Prince of Persia for that research.

This reminds me of Spelunky, which has randomly generated dungeons. Every time you play the game, the layout is different. It's brutally hard as well...

This lecture also springs to my mind:
https://www.youtube.com/watch?v=rskI8qg-7qQ
In that talk, Jonathan Blow explains why it is such a hard problem to create interesting puzzle level designs through algorithms alone. (I may have posted this before...)
Post Reply