Emily Halina: New Levels from a Single Example via Tree-based Reconstructive Partitioning (TRP)
19This talk is on Tree-based Reconstructive Partitioning (TRP), a level generation approach which can generate a suite of diverse, structurally sound levels based on a single example level. On a high level, TRP leverages a general game playing agent (Monte Carlo Tree Search) to create a representation of a level in terms of playable and unplayable areas, then recombines playable and unplayable areas from the input level to make new ones. TRP outperforms popular approaches like WaveFunctionCollapse in terms of plagiarism and playability. In this talk, I’ll showcase the TRP approach. I’ll delve into how the algorithm itself works, show several examples across multiple game domains, and provide comparisons against several other popular low-data level generation approaches. The talk will end with a description of how to implement TRP via an example Godot implementation, along with exploring the challenges and issues with the algorithm and the future work that aims to address these concerns. I’m particularly excited about this approach because of both the coherency of the output levels in comparison to other low data level generation approaches and the overall elegance of the algorithm. I hope to see you there!