On using graph partitioning with isomorphism constraint in procedural content generation
Ahmed M. Abuzuraiq · 2017
This paper describes an algorithm to solve the problem of partitioning a planar graph with a constraint on which partitions should be adjacent or nonadjacent. We explore the applications of the algorithm in Procedural Content Generation in games which includes: the generation of political maps, distribution of terrain and converting or linking Mission Graphs to game spaces. We solve this problem using A-Star search with a heuristic for measuring graphs similarity and we suggest techniques such as graph coarsening to limit the search space. The algorithm sensitivity to the initial state is analyzed next and a restart policy is suggested to overcome that. Additionally, we present multiple constraints that can aid in better controlling the outcomes of the algorithm and we show how these constraints can help in the implementation of the displayed applications.