Automatically generating multiple levels and creating infinite game-play for video games is a complicated task. In this paper, we introduce a pattern-based level generator for general video games. Our generator uses a genetic algorithm to automatically generate levels. The fitness function promotes contiguous patterns and penalizes levels with single or isolated elements. The generator generates levels using two different types of fitness functions; α and β. α levels are generated using the original fitness function and β levels through the inverse of the fitness function. In our experiments, Relative performance profiles indicate that controllers using more advanced techniques achieve better overall performance on α generated levels. The generator finished at the third spot in the 2018 general video game level generation competition.
Alexander, C., Ishikawa, S., Silverstein, M., Jacobson, M., Fiksdahl-King, I. & Angel, S. (1977). A Pattern Language: Towns, Buildings, Construction (Center for Environmental Structure). Oxford University Press.
2.
Ashlock, D., Lee, C. & McGuinness, C. (2011). Search-based procedural generation of maze-like levels. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 260–273. doi:10.1109/TCIAIG.2011.2138707.
3.
Dahlskog, S. & Togelius, J. (2012). Patterns and procedural content generation: Revisiting Mario in world 1 level 1. In Proceedings of the First Workshop on Design Patterns in Games (pp. 1–8). ACM.
4.
Dahlskog, S. & Togelius, J. (2013). Patterns as objectives for level generation. In Proceedings of the Second Workshop on Design Patterns in Games. ACM.
5.
Dahlskog, S. & Togelius, J. (2014). A multi-level level generator. In 2014 IEEE Conference on Computational Intelligence and Games (pp. 1–8). IEEE.
6.
Ebert, D.S. & Musgrave, F.K. (2003). Texturing & Modeling: A Procedural Approach. Morgan Kaufmann.
7.
Gamma, E. (1995). Design Patterns: Elements of Reusable Object-Oriented Software. Pearson Education India.
8.
Hullett, K. & Whitehead, J. (2010). Design patterns in FPS levels. In Proceedings of the Fifth International Conference on the Foundations of Digital Games (pp. 78–85). ACM.
9.
Jordan, A., Scheftelowitsch, D., Lahni, J., Hartwecker, J., Kuchem, M., Walter-Huber, M. & Preuss, M. (2012). Beatthebeat music-based procedural content generation in a mobile game. In 2012 IEEE Conference on Computational Intelligence and Games (CIG) (pp. 320–327). IEEE.
10.
Khalifa, A., Perez-Liebana, D., Lucas, S.M. & Togelius, J. (2016). General video game level generation. In Proceedings of the Genetic and Evolutionary Computation Conference 2016 (pp. 253–259). ACM. doi:10.1145/2908812.2908920.
11.
Kimbrough, S.O., Koehler, G.J., Lu, M. & Wood, D.H. (2005). Introducing a feasible-infeasible two-population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch. March 14, 2005, (Working Paper).
12.
Nielsen, T.S., Barros, G.A., Togelius, J. & Nelson, M.J. (2015). General video game evaluation using relative algorithm performance profiles. In European Conference on the Applications of Evolutionary Computation (pp. 369–380). Cham: Springer.
13.
Perez-Liebana, D., Liu, J., Khalifa, A., Gaina, R.D., Togelius, J. & Lucas, S.M. (2018). General video game AI: A multi-track framework for evaluating agents, games and content generation algorithms. arXiv preprint. arXiv:1802.10363.
14.
Perez-Liebana, D., Samothrakis, S., Togelius, J., Schaul, T., Lucas, S.M., Couëtoux, A., Lee, J., Lim, C.-U. & Thompson, T. (2016). The 2014 general video game playing competition. IEEE Transactions on Computational Intelligence and AI in Games, 8(3), 229–243. doi:10.1109/TCIAIG.2015.2402393.
15.
Preuss, M., Liapis, A. & Togelius, J. (2014). Searching for good and diverse game levels. In 2014 IEEE Conference on Computational Intelligence and Games (pp. 1–8). IEEE.
16.
Schaul, T. (2013). A video game description language for model-based or interactive learning. In 2013 IEEE Conference on Computational Inteligence in Games (CIG) (pp. 1–8). IEEE.
17.
Shaker, N., Liapis, A., Togelius, J., Lopes, R. & Bidarra, R. (2016). Constructive generation methods for dungeons and levels. In Procedural Content Generation in Games (pp. 31–55). Cham: Springer. doi:10.1007/978-3-319-42716-4_3.
18.
Shaker, N., Nicolau, M., Yannakakis, G.N., Togelius, J. & O’neill, M. (2012). Evolving levels for super mario bros using grammatical evolution. In 2012 IEEE Conference on Computational Intelligence and Games (CIG) (pp. 304–311). IEEE.
19.
Sharif, M., Zafar, A. & Muhammad, U. (2017). Design patterns and general video game level generation. International Journal of Advanced Computer Science and Applications, 8(9). doi:10.14569/IJACSA.2017.080952.
20.
Sorenson, N. & Pasquier, P. (2010). Towards a generic framework for automated video game level creation. In European Conference on the Applications of Evolutionary Computation (pp. 131–140). Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-12239-2_14.
21.
Summerville, A., Snodgrass, S., Guzdial, M., Holmgard, C., Hoover, A.K., Isaksen, A., Nealen, A. & Togelius, J. (2018). Procedural content generation via machine learning (pcgml). IEEE Transactions on Games, 10(3), 257–270. doi:10.1109/TG.2018.2846639.
22.
Togelius, J., Yannakakis, G.N., Stanley, K.O. & Browne, C. (2011). Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 172–186. doi:10.1109/TCIAIG.2011.2148116.
23.
Van Der Linden, R., Lopes, R. & Bidarra, R. (2014). Procedural generation of dungeons. IEEE Transactions on Computational Intelligence and AI in Games, 6(1), 78–89. doi:10.1109/TCIAIG.2013.2290371.
24.
Whitley, D. (1994). A genetic algorithm tutorial. Statistics and computing, 4(2), 65–85. doi:10.1007/BF00175354.
