research-article

Talakat: bullet hell generation through constrained map-elites

Authors:

Julian TogeliusAuthors Info & Claims

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 1047 - 1054

https://doi.org/10.1145/3205455.3205470

Published: 02 July 2018 Publication History

Abstract

We describe a search-based approach to generating new levels for bullet hell games, which are action games characterized by and requiring avoidance of a very large amount of projectiles. Levels are represented using a domain-specific description language, and search in the space defined by this language is performed by a novel variant of the Map-Elites algorithm which incorporates a feasible-infeasible approach to constraint satisfaction. Simulation-based evaluation is used to gauge the fitness of levels, using an agent based on best-first search. The performance of the agent can be tuned according to the two dimensions of strategy and dexterity, making it possible to search for level configurations that require a specific combination of both. As far as we know, this paper describes the first generator for this game genre, and includes several algorithmic innovations.

References

[1]

Cameron Browne and Frederic Maire. 2010. Evolutionary game design. IEEE Transactions on Computational Intelligence and AI in Games 2, 1 (2010), 1--16.

[2]

Nathan Collman. 2014. MAKU: A Code Generator for Bullet Hell Games. Ph.D. Dissertation.

[3]

Kate Compton, Benjamin Filstrup, and others. 2014. Tracery: Approachable story grammar authoring for casual users. In Seventh Intelligent Narrative Technologies Workshop.

[4]

Fernando de Mesentier Silva, Scott Lee, Julian Togelius, and Andy Nealen. 2017. AI as Evaluator: Search Driven Playtesting of Modern Board Games. (2017).

[5]

Marc Ebner, John Levine, Simon M Lucas, Tom Schaul, Tommy Thompson, and Julian Togelius. 2013. Towards a video game description language. (2013).

[6]

Peter E Hart, Nils J Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4, 2 (1968), 100--107.

[7]

Erin J Hastings, Ratan K Guha, and Kenneth O Stanley. 2009. Evolving content in the galactic arms race video game. In Computational Intelligence and Games, 2009. CIG 2009. IEEE Symposium on. IEEE, 241--248.

Digital Library

[8]

Aaron Isaksen, Dan Gopstein, Julian Togelius, and Andy Nealen. 2017. Exploring Game Space of Minimal Action Games via Parameter Tuning and Survival Analysis. IEEE Transactions on Computational Intelligence and AI in Games (2017).

[9]

Aaron Isaksen, Drew Wallace, Adam Finkelstein, and Andy Nealen. 2017. Simulating strategy and dexterity for puzzle games. In Computational Intelligence and Games (CIG), 2017IEEE Conference on. IEEE, 142--149.

Digital Library

[10]

Martin Jennings-Teats, Gillian Smith, and Noah Wardrip-Fruin. 2010. Polymorph: dynamic difficulty adjustment through level generation. In Proceedings of the 2010 Workshop on Procedural Content Generation in Games. ACM, 11.

Digital Library

[11]

Ahmed Khalifa, Diego Perez-Liebana, Simon M Lucas, and Julian Togelius. 2016. General video game level generation. In Proceedings of the Genetic and Evolutionary Computation Conference 2016. ACM, 253--259.

Digital Library

[12]

Steven Orla Kimbrough, Gary J Koehler, Ming Lu, and David Harlan Wood. 2008. On a Feasible-Infeasible Two-Population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch. European Journal of Operational Research 190, 2 (2008), 310--327.

[13]

Antonios Liapis, Georgios N Yannakakis, and Julian Togelius. 2013. Sentient Sketchbook: Computer-aided game level authoring. In FDG. 213--220.

[14]

Antonios Liapis, Georgios N Yannakakis, and Julian Togelius. 2013. Towards a Generic Method of Evaluating Game Levels. In AIIDE.

Digital Library

[15]

Jean-Bap tiste Mouret and Jeff Clune. 2015. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909 (2015).

[16]

Thorbjørn S Nielsen, Gabriella AB Barros, Julian Togelius, and Mark J Nelson. 2015. Towards generating arcade game rules with VGDL. In Computational Intelligence and Games (CIG), 2015 IEEE Conference on. IEEE, 185--192.

[17]

Michael O'Neil and Conor Ryan. 2003. Grammatical evolution. In Grammatical Evolution. Springer, 33--47.

[18]

Tom Schaul. 2013. A video game description language for model-based or interactive learning. In Computational Intelligence in Games (CIG), 2013 IEEE Conference on. IEEE, 1--8.

[19]

Noor Shaker, Miguel Nicolau, Georgios N Yannakakis, Julian Togelius, and Michael O'neill. 2012. Evolving levels for super mario bros using grammatical evolution. In Computational Intelligence and Games (CIG), 2012 IEEE Conference on. IEEE, 304--311.

[20]

Noor Shaker, Julian Togelius, and Mark J Nelson. 2016. Procedural content generation in games. Springer.

Digital Library

[21]

Gillian Smith, Jim Whitehead, and Michael Mateas. 2011. Tanagra: Reactive planning and constraint solving for mixed-initiative level design. IEEE Transactions on Computational Intelligence and AI in Games 3, 3 (2011), 201--215.

[22]

Sam Snodgrass and Santiago Ontañón. 2014. Experiments in map generation using Markov chains. In FDG.

Cited By

Janmohamed HWolinska MSurana SPierrot TWalsh ACully ALi XHandl J(2024)Multi-Objective Quality-Diversity for Crystal Structure PredictionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654048(1273-1281)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654048
Gallotta RArulkumaran KSoros L(2024)Preference-Learning Emitters for Mixed-Initiative Quality-Diversity AlgorithmsIEEE Transactions on Games10.1109/TG.2023.326445716:2(303-316)Online publication date: Jun-2024
https://doi.org/10.1109/TG.2023.3264457
Charity MDave IKhalifa ATogelius J(2024)Baba is Y'all 2.0: Design and Investigation of a Collaborative Mixed-Initiative SystemIEEE Transactions on Games10.1109/TG.2022.322352716:1(75-89)Online publication date: Mar-2024
https://doi.org/10.1109/TG.2022.3223527
Show More Cited By

Index Terms

Talakat: bullet hell generation through constrained map-elites

Recommendations

A Constraint Based Structure Description Language for Biosequences

We report an investigation into how constraint solving techniques can be used to search for patterns in sequences (or strings) of symbols over a finite alphabet. We define a constraint-based structure description language for biosequences, and give the ...
A System for Generating Language-Oriented Editors

The authors seek to establish a simple and flexible framework for internal representation of language-dependent information, and the behavior of language-oriented tools for user's operations. They present a system for generating language-oriented ...
The treatment of data types in EL1

In constructing a general purpose programming language, a key issue is providing a sufficient set of data types and associated operations in a manner that permits both natural problem-oriented notation and efficient implementation. The EL1 language ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

July 2018

1578 pages

ISBN:9781450356183

DOI:10.1145/3205455

Editor:
Hernan Aguirre
Shinshu University
,
General Chair:
Keiki Takadama
The University of Electro-Communications

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '18

Sponsor:

SIGEVO

GECCO '18: Genetic and Evolutionary Computation Conference

July 15 - 19, 2018

Kyoto, Japan

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

58
Total Citations
View Citations
372
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)15

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Janmohamed HWolinska MSurana SPierrot TWalsh ACully ALi XHandl J(2024)Multi-Objective Quality-Diversity for Crystal Structure PredictionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654048(1273-1281)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654048
Gallotta RArulkumaran KSoros L(2024)Preference-Learning Emitters for Mixed-Initiative Quality-Diversity AlgorithmsIEEE Transactions on Games10.1109/TG.2023.326445716:2(303-316)Online publication date: Jun-2024
https://doi.org/10.1109/TG.2023.3264457
Charity MDave IKhalifa ATogelius J(2024)Baba is Y'all 2.0: Design and Investigation of a Collaborative Mixed-Initiative SystemIEEE Transactions on Games10.1109/TG.2022.322352716:1(75-89)Online publication date: Mar-2024
https://doi.org/10.1109/TG.2022.3223527
Pereira LViana BToledo C(2024)A System for Orchestrating Multiple Procedurally Generated Content for Different Player ProfilesIEEE Transactions on Games10.1109/TG.2022.321378116:1(64-74)Online publication date: Mar-2024
https://doi.org/10.1109/TG.2022.3213781
Zammit MLiapis AYannakakis G(2024)MAP-Elites with Transverse Assessment for Multimodal Problems in Creative DomainsArtificial Intelligence in Music, Sound, Art and Design10.1007/978-3-031-56992-0_26(401-417)Online publication date: 3-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-56992-0_26
Mouret JSilva SPaquete L(2023)Fast generation of centroids for MAP-ElitesProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3590726(155-158)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3590726
Sfikas KLiapis AYannakakis GSilva SPaquete L(2023)Controllable Exploration of a Design Space via Interactive Quality DiversityProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3590616(167-170)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3590616
Janmohamed HPierrot TCully ASilva SPaquete L(2023)Improving the Data Efficiency of Multi-Objective Quality-Diversity through Gradient Assistance and Crowding ExplorationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590470(165-173)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590470
Fontaine MNikolaidis SSilva SPaquete L(2023)Covariance Matrix Adaptation MAP-AnnealingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590389(456-465)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590389
Withington OTokarchuk L(2023)The Right Variety: Improving Expressive Range Analysis with Metric Selection MethodsProceedings of the 18th International Conference on the Foundations of Digital Games10.1145/3582437.3582453(1-11)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1145/3582437.3582453
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents