Learning Constrained Graph Layout for Content Generation

Abstract

Graphs are a common format for procedurally generated content in games. However, many graph-based approaches require grammars to be manually authored or additional processing to add spatial layout information. In this work, we extend an existing system for constrained graph generation that learns from examples. The main extension is adding graph layout information directly into the graph learning and generation constraint problem by incorporating spatial transforms. We demonstrate the approach in several level generation applications and potential use in citizen science games.

Keywords

• eol>graphs
• procedural content generation
• constraints

1. Background

In this work, we extend the existing Sturgeon-GRAPH system [ 15 ] for constrained graph generation. SturgeonGraphs are one of many representations for procedurally GRAPH learns local patterns from example graphs and generated content [ 1 ] in games. When using graphs, uses them to generate new graphs; however, prior to grammars are a popular technique [ 2, 3, 4, 5, 6 ]. However, this work, it did not use spatial information, only learnmany graph-based approaches require these grammars ing connectivity. Here, we incorporate relative spatial to be manually authored or additional processing to add relationships between nodes in the patterns learned by spatial layout information. Dormans’s work [ 7 ], for ex- Sturgeon-GRAPH. These spatial relationships are then ample, uses a two-pass system of grammars, one that incorporated into the graph generation constraint probifrst generates an abstract “mission” graph, which is then lem. Thus, the solution to the problem generates both used by a shape grammar to create the “space” for the the graph connectivity structure and the spatial layout of level. the nodes. We also use some other extensions in support

A few approaches have learned graph generation from of this goal, including an alternate graph connectivity examples, which can be considered a form of Procedural constraint and pattern definitions. We demonstrate the Content Generation via Machine Learning (PCGML) [ 8 ]. approach in level generation and possible use as a tool For example, Londoño and Missura’s [9] work used ex- in molecular citizen science games. ample Super Mario Bros. levels to learn graph patterns and grammars. The approach of Hauck and Aranha [10] learns a grammar for generating Super Mario Bros. levels, 2. Overview but is highly tailored to that game’s tile grid structure.

Merrell and Manocha’s [11] work on continuous model synthesis can also be considered learning to generate graphs with layout from examples, though relies on constructing arrays of intersecting lines or planes and using these for node and edge placement. Merrell’s [ 12 ] more recent work can also be considered learning graph layout from examples, and uses grammars.

In terms of graph layout, a wide variety of algorithms have been developed, many incorporated into packages such as GraphViz [ 13 ] and Tulip [ 14 ]. These generally take an existing graph as input, rather than generating a graph and layout simultaneously.

This work extends the existing Sturgeon-GRAPH system [ 15 ] for constrained graph generation from examples. That system, built on the Sturgeon constraint-based PCG system [ 16 ], first extracts a graph description, consisting of distinct local patterns of labelled nodes and edges, from example graphs. This graph description is then used to set up a system of Boolean constraints, the solution of which is a graph in which all patterns exist in the example graphs. For eficiency, the system only considers a subset of edges as potential edges for the solution, rather than all possible edges between every pair of nodes (e.g. band-n edges only consider edges between nodes from id up to id + ).

AIIDE Workshop on Experimental Artificial Intelligence in Games, Previously, Sturgeon-GRAPH used a constraint probOctober 08, 2023, University of Utah, Utah, USA lem that handled graph generation, where layout was a b$alesem.caoeo@[e-mail](rEn..eBdaule(mS.aC)ooper); separate post-processing step. In this work, we extend 0000-0003-4504-0877 (S. Cooper) the Sturgeon-GRAPH system to incorporate layout in© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License formation into the same constraint problem along with CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) graph generation. This way, graph generation and layout bottom row implicitly (0, 0, 1). This function is used to are solved in a single problem. This is done by including allocate a transform variable for each node. constraints on relative spatial transforms, with support GetVarPosXform() — Get the position associated with for two types of 2D transformations (discussed below). the given transform variable . In our implementation, For the use of relative transformations, the proposed is just the two variables, while ℛ is the translation part approach works only with directed dtree or dag graph of the matrix. This function is used to get the positions types. of the nodes out of the solution.

CnstrImpliesXform(, 0, 1, , ) — Add a 2.1. Graph Description Learning constraint that if the Boolean variable is true, then transform variable 1 is constrained to be the result of When learning the graph description, before extracting the constant applied to transform variable 0 (in the laorceaaldpdaettdertnosthfreom(ditrheectgerda)pehd,greeslaotifvtehsepgartiaaplhtr—atnhseforremlas- cmauseltiopflica,titohnis). isIf atdhdeitcioonns,tianntthecaseofis fℛal,sem, athtreinx tive transform from the edge source to destination. This only the positional part of 1 is constrained to be a small is done by starting at the root of the graph and proceed- distance around the transformed location. This function ing breadth-first through the graph, adding the relative is used to set up constraints such that if an edge is present transform from the source to the destination to each edge. in the solution, its relative transform is applied from its

The two types of 2D transforms currently supported source to its destination. are translation-only ( ) and translation-rotation ( ℛ).

For transforms, the relative transform on an edge is CnstrIdentityDistXform(, , ) — Add just the relative x and y delta of the nodes. For ℛ constraints that the positional parts of the transform varitransforms, relative transforms are stored in the graph ables , corresponding to the Boolean variables description as polar coordinates: a magnitude, and rela- (which are variables for missing nodes) that are false, are tive angle from the incoming primary edge. As dags can at least distance apart. Also, add a constraint have nodes with more than one incoming edge, when that the first transform variable in is the identity transusing ℛ one of the incoming edges (from the node with form and the first variable in is false. This function lowest ID) is set as the primary incoming edge and used is used to initialize basic positional constraints on the for relative transforms. transforms for nodes that are present in the solution.

After adding transform information to edges, pattern learning from the example graphs proceeds much as be- 2.3. Additional Extensions fore, except that the transform information is also considered when finding unique patterns.

In support of this work, we added a few other extensions to Sturgeon-GRAPH.

First, we added support for diferent pattern definitions. 2.2. Constrained Graph Generation In the original Sturgeon-GRAPH, a pattern consists of a The relative transform information along edges is incor- key node, the edges connected to that node, and the nodes porated into the constraint problem to solve for global connected to those edges, i.e. immediate neighbors (edgetransforms for each of the nodes. In order to incorpo- node patterns). In this work we added a pattern definition rate spatial transforms into the constraint problem, Stur- that only includes the key node and its connected edges, geon’s solver API needed to be extended to support real- ignoring the labels of the connected nodes (edge-only valued variables and some constraints on them. The patterns). existing API only supported Boolean variables; this al- We also added a new type of edges to consider, lowed for a wide variety of low-level solvers to be used, stripe-n1,n2,...,nm, which, for a node with id , considers including those that do not support real-valued variables. only edges to nodes with ids + 1, + 2, ..., + . Thus, the following extensions to the API were only im- We also added an alternative method for constrainplemented in the low-level Z3 solver [ 17 ]. Also here for ing graphs to be connected (i.e., not split into multiple simplicity, we use the ∞ distance (e.g. square). The graphs). The previous method added a single “reachabilfollowing functions were added to the solver API: ity” variable for each node, started from a single reachable root node, and followed directed edges out to make sure MakeVarXform() — Create a new transform vari- all nodes in the graph were reachable from the root node. able of type ( or ℛ). This may correspond to The use of directed edges prevented independent cycles more than one variable in the underlying low-level solver. from being found as connected but also limited generated In our implementation, type uses two real variables, graphs to a single root node. In this work, we added an and type ℛ uses six real variables representing the top approach where connectivity is computed using “reachtwo rows of a 3 × 3 homogeneous transform matrix, with ability layers”. There are layers, and each node has

X

X S X X X X X

X X > ]

X X X a Boolean reachability variable in each layer. In layer 0, exactly 1 node is reachable. If a node is not reachable in layer − 1, and not connected (either as source or destination) to a reachable node in layer − 1, it is not reachable in layer . All nodes must either be reachable by the final layer, or missing from the generated graph.

Finally, we added support for unique undirected cycle labeling. The aim of this is for cycles (or, what would be cycles in the undirected version of the graphs) to be learned as complete units. To accomplish this, we find the cycle basis of the undirected graphs and augment the label of each edge in a basis with the index of its basis and index within its basis.

3. Applications

Here we describe a few applications of the system. For each application, we generated ten graphs, to get timing information and select samples for figures.

mario: This application is based on a version of Super Mario Bros. 1-1 [ 18 ] from the VGLC [ 19 ], converted into a grid graph. Node labels are the tile text from the level. This is similar to the example application in previous Sturgeon-GRAPH work [ 15 ], except it considers stripe-1,8 edges and learns the relative node positions from the example, using them in the graph generation process. Thus the grid layout can be handled without the selected examples specialized grid approach used previously.

This application used transforms with edge-node patterns, and generated graphs between 60–80 nodes with stripe-1,8 edges and at least one of each node label. and at most one e and g node label. The example graph Sample generated graphs are shown in Figure 1. Average and some sample generated graphs are shown in Figure 2. generation time was 52.0s (SD=17.3s). Average generation time was 35.7s (SD=40.2s).

Notably, the graphs are not required to be rectangular. fract: Based on the math educational game, RefracThis could present interesting challenges or opportunities tion. In the game, lasers with numerical values come out for gameplay. of sources. Lasers can be manipulated by various pieces dungeon: This application is a graph with branches such as splitters, which split lasers into fractional parts, and turns, representing a simple dungeon game. It is or benders, which redirect lasers. The goal is to get lasers based on a manually-constructed example level, with with specific values to spaceships to power them up. The nodes labeled for the type of room represented: en- game has been used for constraint-based level generation trance (e), goal (g), branch (b), right turn (r), left turn before [ 20 ]. (l), straight hallway (h), and dead end (d). In this application, we manually created several small

This application used ℛ transforms with edge-only example graphs demonstrating how pieces work. These patterns, and generated graphs between 10–15 nodes included labeled nodes for sources (□ >), spaceships (>□ ), with band-3 edges and at least one of each node label, splitters (s), benders (b), and mergers (m); we also in

Acnowledgements

Part of this material is based upon work supported by the National Science Foundation under under Grant No. 1950697, and the Rosetta Commons REU Program. cluded nodes for spaces with lasers repeating (r) and crossing (x) so that other pieces would not be placed in their way. Edge labels represent the fractional value of the laser.

This application used transforms with edge-only patterns. To increase variety, the example graphs were rotated 90, 180, and 270 degrees. Generated graphs between 10–15 nodes with band-4 edges and at least one m and s node labels and two 1> node labels. Sample example and generated graphs are shown in Figure 3. Average generation time was 15.2s (SD=1.1s).

mol: Based on small molecule structures. Recently deep learning methods have been proposed for generating small molecules, for example using SMILES string representations [ 21 ] or directly on graphs [ 22, 23 ]; however, these learning approaches often use large training datasets. In this application, seven 2D small molecule PDBs from SMPDB [ 24 ] were converted to graph format. Node labels were atomic types. Other information, such as bond order (i.e. single/double/triple), was not used, but could potentially be incorporated into labels in the future. This application shows the flexibility of the approach, and we imagine it might be useful as a player tool for molecular design in citizen science games such as Foldit [ 25 ].

This application used ℛ transforms with edge-node patterns. Undirected cycle labeling was used. Generated graphs were between 5–10 nodes with band-5 edges. We generated graphs that both forbid and required undirected cycles. Sample examples and generated graphs are shown in Figure 4. Average generation time was 5.3s (SD=3.7s) with cycles forbidden and 211.8s (SD=149.5s) with cycles required.

Given the small size and small number of undirected cycle examples, there was little variety in the graphs requiring undirected cycles, often reproducing ringed examples or very similar. They also took substantially longer to generate.

References

[1] N. Shaker , J. Togelius , M. J. Nelson , Procedural Content Generation in Games, Springer, 2016 .

[2] J. M. Font , R. Izquierdo , D. Manrique , J. Togelius , Constrained level generation through grammarbased evolutionary algorithms , in: G. Squillero, P. Burelli (Eds.), Applications of Evolutionary Computation, Lecture Notes in Computer Science , Springer International Publishing, Cham, 2016 , pp. 558 - 573 .

[3] J. Valls-Vargas , J. Zhu , S. Ontañón , Graph grammarbased controllable generation of puzzles for a learning game about parallel programming , in: Proceedings of the 12th International Conference on the Foundations of Digital Games , 2017 , pp. 7 : 1 - 7 : 10 .

[4] R. van Rozen , Q. Heijn , Measuring quality of grammars for procedural level generation , in: Proceedings of the 13th International Conference on the Foundations of Digital Games , 2018 , pp. 1 - 8 .

[5] C. Jemmali , C. Ithier , S. Cooper , M. S. El-Nasr , Grammar based modular level generator for a programming puzzle game , in: Proceedings of the Experimental AI in Games Workshop , 2020 , p. 7 .

[6] A. Madkour , S. Marsella , C. Harteveld , M. Seif ElNasr , J.-W. van de Meent, Guiding generative graph grammars of dungeon mission graphs via examples , in: Experimental AI in Games Workshop , 2021 .

[7] J. Dormans , Adventures in level design: Generating missions and spaces for action adventure games , in: Proceedings of the 2010 Workshop on Procedural Content Generation in Games , 2010 , pp. 1 - 8 .

[8] A. Summerville , S. Snodgrass , M. Guzdial, 4 . Conclusion C. Holmgård , A. K. Hoover , A. Isaksen , A. Nealen , J. Togelius , Procedural Content Generation via In this work, we present an approach to learning con- Machine Learning (PCGML), IEEE Transactions on strained graph layouts from example graphs . This was ap- Games 10 ( 2018 ) 257 - 270 .

proached by adding transform information to the graph [9 ] S. Londoño , O. Missura , Graph grammars for Super description and constraints using the Sturgeon-GRAPH Mario Bros levels , in: Sixth FDG Workshop on system [15]. Procedural Content Generation , 2015 . In the future, we are interested in exploring other con- [10] E. Hauck , C. Aranha , Automatic generation of Sustraints on spatial positions, such as nodes being at cer- per Mario levels via graph grammars, in: 2020 IEEE tain locations, as well as expanding scalability to larger Conference on Games (CoG ), 2020 , pp. 297 - 304 .

graphs and 3D transformations . We would also like to [11] P. Merrell , D. Manocha , Continuous model synmore thoroughly evaluate the generator, such as with an thesis , ACM Transactions on Graphics 27 ( 2008 ) expressive range [26] or playability analysis . 158 : 1 - 158 : 7 .

[12] P. Merrell , Example-based procedural modeling using graph grammars , ACM Transactions on Graphics 42 ( 2023 ) 60 : 1 - 60 : 16 .

[13] J. Ellson , E. R. Gansner , E. Koutsofios , S. C. North, G. Woodhull, Graphviz and Dynagraph - Static and Dynamic Graph Drawing Tools , in: M. Jünger , P. Mutzel (Eds.), Graph Drawing Software, Mathematics and Visualization , 2004 , pp. 127 - 148 .

[14] D. Auber , Tulip - A Huge Graph Visualization Framework , in: M. Jünger , P. Mutzel (Eds.), Graph Drawing Software, Mathematics and Visualization , Springer, Berlin, Heidelberg, 2004 , pp. 105 - 126 .

[15] S. Cooper , Sturgeon-GRAPH: Constrained Graph Generation from Examples , in: Proceedings of the 18th International Conference on the Foundations of Digital Games , 2023 , pp. 1 - 9 .

[16] S. Cooper , Sturgeon: Tile-based procedural level generation via learned and designed constraints , Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 18 ( 2022 ) 26 - 36 .

[17] L. de Moura , N. Bjørner, Z3: An eficient SMT solver , in: C. R. Ramakrishnan, J. Rehof (Eds.), Tools and Algorithms for the Construction and Analysis of Systems, Lecture Notes in Computer Science , 2008 , pp. 337 - 340 .

[18] Nintendo , Super Mario Bros., 1985 . Game [NES].

[19] A. J. Summerville , S. Snodgrass , M. Mateas , S. Ontañón , The VGLC : The Video Game Level Corpus , arXiv: 1606 .07487 [cs] ( 2016 ).

[20] A. M. Smith , E. Andersen , M. Mateas , Z. Popović , A case study of expressively constrainable level design automation tools for a puzzle game , in: Proceedings of the International Conference on the Foundations of Digital Games , 2012 , pp. 156 - 163 .

[21] E. Mazuz , G. Shtar , B. Shapira , L. Rokach, Molecule generation using transformers and policy gradient reinforcement learning , Scientific Reports 13 ( 2023 ) 8799 .

[22] Q. Liu , M. Allamanis , M. Brockschmidt , A. L. Gaunt , Constrained graph variational autoencoders for molecule design , in: Proceedings of the 32nd International Conference on Neural Information Processing Systems , 2018 , pp. 7806 - 7815 .

[23] O. Mahmood , E. Mansimov, R. Bonneau , K. Cho , Masked graph modeling for molecule generation , Nature Communications 12 ( 2021 ) 3156 .

[24] A. Frolkis , C. Knox , E. Lim, T. Jewison , V. Law , D. D. Hau , P. Liu, B. Gautam , S. Ly , A. C. Guo , J. Xia , Y. Liang , S. Shrivastava , D. S. Wishart , SMPDB : The Small Molecule Pathway Database , Nucleic Acids Research 38 ( 2010 ) D480 - 487 .

[25] B. Koepnick , J. Flatten , T. Husain , A. Ford , D.- A. Silva , M. J. Bick , A. Bauer , G. Liu, Y. Ishida , A. Boykov , R. D. Estep , S. Kleinfelter , T. NørgårdSolano, L. Wei , F. Players , G. T. Montelione , F. DiMaio , Z. Popović , F. Khatib , S. Cooper , D. Baker , De novo protein design by citizen scientists , Nature 570 ( 2019 ) 390 - 394 .

[26] G. Smith , J. Whitehead , Analyzing the expressive range of a level generator , in: Proceedings of the 2010 Workshop on Procedural Content Generation in Games , 2010 , pp. 1 - 7 .