Fair Partitioning of Procedurally Generated Game Maps for Grand Strategy Games

Sammanfattning: Due to the high cost of manual content creation within the game development industry, methods for procedural generation of content such as game maps and levels have emerged. However, methods for generating game maps have remained relatively unexplored in competitive multiplayer contexts. Presumably, this is due to the opposing goals of generating game maps that are both interesting and fair. This study aims to explore the possibility of satisfying both these goals simultaneously by separating the generative phase from the phase that enforces fairness. In this endeavor, simple game maps for a generic multiplayer grand strategy game are generated using noise-based methods. The task of partitioning the game map fairly between the players is then modeled as a constrained categorical multiobjective minimization problem that is subsequently solved by two genetic algorithms, the reference-point-based algorithm NSGA-III and the decomposition-based algorithm MOEA/D-IEpsilon. In a primary study, the proposed partitioning method is evaluated based on the quality of the solutions produced, its scalability, and its ability to find symmetrical partitions of symmetrical game maps. The results show that the proposed method makes significant improvement from the initial guess but fails to produce completely fair partitions in general. Explanations and possible solutions to this are presented. The timing results indicate that the proposed method is not applicable in real-time contexts. However, the proposed method might still be applicable in online contexts if smaller game maps are considered and in offline contexts if larger game maps are considered. Finally, the partitioning results show that the proposed method successfully finds fair partitions of symmetrical game maps but fails to find the obvious symmetrical partitions. In a secondary study, the two genetic algorithms are compared to determine which algorithm produces dominating solutions and which algorithm produces most diverse solution. The results indicate that, for the partitioning problems considered in this study, the reference-point-based algorithm is both dominant and produces the most diverse solutions.