John and Marcia Price College of Engineering
20 Group Theory for Procedural Content Generation: Towards Generating Objects from Mathematical Description
Jonas Knochelmann and Rogelio Cardona-Rivera
Faculty Mentor: Rogelio E. Cardona-Rivera (Division of Games, University of Utah)
Despite the highly technical nature of Procedural Content Generation (PCG), the holistic study of the discipline is minimal and qualitative. We argue that this gap exists because there is no formal framework to talk about PCG artifacts and algorithms and propose the mathematical field of group theory to serve as such a framework. Group theory is a well-established discipline that has been embraced in chemistry, physics, and art, with tools for analyzing, combining, and generating objects based on their structure. In our research, we’ve explored a specific method for applying group theory to PCG and explored a number of case studies in the hopes of developing a more unified formal framework for future study.
Overview
Procedural Content Generation (PCG) is a prevalent aspect of interactive digital entertainment generally categorized as a subdiscipline of Artificial Intelligence (AI). Unlike other areas of AI research, however, PCG does not have a solid formal foundation. That is, there does not exist any standard mathematical language to talk about PCG algorithms or artifacts. This makes discourse between PCG practitioners difficult when they venture outside of standard techniques, and it limits the impact of general-purpose analysis methods. In particular, there exists no standard method to describe a PCG artifact in a way that lends itself to being generated. This creates a link between an artifact and the details of the algorithm that generated it. This is a problem because two PCG practitioners might use completely different algorithms to create the same artifact, making communication between the two unnecessarily difficult. Further, the algorithms will likely differ in their parameters, expandability, and possibility space. The end result is that each practitioner is ultimately limited by the arbitrary specifics of their implementation and that future work has a limited ability to take advantage of past work.
