Angle-Based Multi-Objective Evolutionary Algorithm Based On Pruning-Power Indicator for Game Map Generation

This paper presents a multi-objective search-based approach to generate balanced maps for real-time strategy games. First, an angle-based pruning-power indicator guided evolutionary algorithm is proposed to solve the many-objective optimization problems. This algorithm divides the hyper-spherical coordinate space into a set of local partitions, where the pruning power indicator is used to access the dominance ability of the solution over its located partition, and the radius-penalized angle calculation indicator aims to guide the evolution of population along specific partition direction. In this way, both the convergence and diversity of solutions are considered, and the selection pressure toward Pareto fronts is strengthened. We show the effectiveness of the proposed strategies on a set of many-objective benchmark functions. Then, the proposed algorithm is used to generate game maps –a real-world problem derived from the procedural content generation, in which there are four objective functions to guide the map generation of MegaGlest based on the principle of fairness, playability, strategy, and interestingness of games. Experimental results on four map generation instances verify the competitiveness and effectiveness of the proposed algorithm.