New method enables procedural generation of graph-based game content using reinforcement learning
Florian Rupp and Kai Eckert present “G-PCGRL: Procedural Graph Data Generation via Reinforcement Learning” at the 2024 IEEE Conference on Games (CoG).
The Ubiquity of Graph Structures in Games
Graph data structures are omnipresent in game development, representing diverse game elements including:
- Game economies with interconnected resources and crafting systems
- Skill trees defining character progression paths
- Complex, branching quest lines with multiple outcomes
- Social networks between NPCs and factions
- Level connectivity and world geography
Despite their prevalence, generating these structures algorithmically has remained challenging, particularly when specific constraints and balance requirements must be met.
Introducing G-PCGRL
This research proposes G-PCGRL, a novel and controllable method for procedural generation of graph data using reinforcement learning. The approach adapts and extends the successful PCGRL (Procedural Content Generation via Reinforcement Learning) framework, originally designed for tile-based content, to the domain of graph structures.
Framing Graph Generation as an MDP
The key innovation lies in framing graph data generation as a Markov decision process (MDP) that manipulates a graph’s adjacency matrix to fulfill specified constraints. This formulation allows the application of reinforcement learning techniques while maintaining control over the properties of generated graphs.
Novel Representations
The research introduces new representations specifically designed for graph generation that differ from traditional PCGRL approaches. These representations acknowledge the unique challenges of graph structures, where:
- Connectivity patterns must be carefully managed
- Global properties emerge from local changes
- Valid graphs must satisfy structural constraints
Unlike traditional PCGRL’s swap-based representations that modify existing content, G-PCGRL can generate entirely new graph structures from scratch.
Controllable Generation
Controllability in G-PCGRL is provided through configuration of the initial adjacency matrix and specification of constraints. This allows designers to:
- Define desired graph properties (connectivity, density, specific patterns)
- Enforce gameplay-relevant constraints
- Guide generation toward particular structural characteristics
- Balance competing objectives
Advancing Procedural Content Generation
G-PCGRL represents an appraoch in expanding PCGRL to handle graph data structures. By successfully applying reinforcement learning to graph generation, the work opens new possibilities for automated content creation in game development and beyond.
Citation: Florian Rupp, Kai Eckert (2024): G-pcgrl: Procedural graph data generation via reinforcement learning. In 2024 IEEE Conference on Games (CoG).