Level Graph – Incremental Procedural Generation of Indoor Levels using Minimum Spanning Trees
Authors:
- 1 August 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-7
Abstract
Procedural generation of virtual worlds is an important aspect of game development since decades, typically for increasing replayability or for speeding up the level creation process. However, the utilization of this potential has always been a great challenge due to the difficult controllability of the underlying algorithms or limitations to specific level geometries, like 2D regular structures. In this paper, we present a novel approach for semi-automatic generation of a wide variety of 2D/3D corridor and room systems. The underlying processing pipeline is based on a separation between a user-guided generation of a graph-based abstract level structure and a fully-automatic construction of the corresponding geometry using a pre-modeled component library. The core algorithm is built on the computation of an extended minimal spanning tree, which can be controlled by a set of intuitive vertex and edge parameters. First experimental results have shown that our incremental generation pipeline allows the efficient creation of complex indoor levels, minimizing limitations on level and game designers’ creativity.Keywords
This publication has 16 references indexed in Scilit:
- Mixed-initiative procedural generation of dungeons using game design patterns2017
- Procedural Generation of DungeonsIEEE Transactions on Computational Intelligence and AI in Games, 2013
- Procedural content generation for gamesACM Transactions on Multimedia Computing, Communications, and Applications, 2013
- Level design as model transformation2011
- Boolean operations on multi-region solids for mesh generationEngineering with Computers, 2011
- Search-Based Procedural Generation of Maze-Like LevelsIEEE Transactions on Computational Intelligence and AI in Games, 2011
- From Artistry to Automation: A Structured Methodology for Procedural Content Creation2004
- An optimal minimum spanning tree algorithmJournal of the ACM, 2002
- An efficient surface intersection algorithm based on lower-dimensional formulationACM Transactions on Graphics, 1997
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957