Visual Exploration of Tile Level Datasets

Abstract

Datasets of game levels are increasingly used, for example as training data for PCGML algorithms, outputs from exhaustive PCG, or pre-computed parts of larger levels. However, tools for exploring these datasets are limited. In this work we describe an interactive tool for visual exploration of large tile level datasets. The level explorer currently supports level elements including both image- and text-based tile grids, path graph edges, and string tags. The level explorer visualizes the levels and allows the user to select elements that they would like to be present, and filters the dataset to find all levels consistent with the user's selection. We also describe an eficient encoding scheme used for level filtering, along with example cases of several games, demonstrating handling of datasets consisting of up to millions of levels.

Keywords

• eol>levels
• datasets
• visualization

-

1. Introduction AIIDE Workshop on Experimental Artificial Intelligence in Games, October 08, 2023, University of Utah, Utah, USA $ [e-mail] (S. Cooper); [e-mail] (F. Abutarab); [e-mail] (E. Halina); [e-mail] (N. Sturtevant)

0000-0003-4504-0877 (S. Cooper); 0009-0004-3408-7092 (E. Halina); 0000-0003-4318-2791 (N. Sturtevant)

© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License allows designers to manually place tiles, and a side panel CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) that shows the tiles possible for the cell the designer is - - - { - - } X X X X - - - - block { - X } X X X X - - { - } X X X Levels Encoding

Visualization hovered over. Our tool also allows users to see which process takes all the levels to be encoded as input, as certiles are possible at each cell, but we present it in a difer- tain properties of the encoding need to know information ent manner. The way we show what tiles are possible in about all levels (e.g. all the edges and tags used across each cell is influenced by Oskar Stålberg, who visualized all levels). The encoding process outputs the bitstring WFC by displaying all tiles available in each cell [18]. The encoding of each level, as well as metadata needed to Anhinga level editor [19] uses exhaustive PCG to search decode the bitstrings back into levels. An example of the though and evaluate all possible single-tile changes from encoding technique is shown in Figure 1, showing three the current level. levels, parts of their encodings, and how they would be

The level explorer also allows designers to filter levels visualized. The level representation is based on that used by gameplay—that is, they can specify that levels must by the Sturgeon level generation system [ 28 ] but is flexicontain (partial) paths as a solution. This allows design- ble enough to support a variety of tile-based games. Level ers to work backwards from a path to a level design that elements are encoded into the bitstring as follows. can be solved by the specified full or partial path. Existing Tile grids: Levels are defined by a 2D grid of tiles. Each work has looked at generating levels from gameplay spec- tile can be associated with an image and/or text “function” ifications (such as beat structure [ 20], streamlines that (e.g. start, goal, solid, passable, etc). During encoding, represent player traces [ 21 ], or taking path constraints each location in the grid gets its own bit substring. In a as input to a generator [ 22 ]) and evolving gameplay spec- location’s substring, each bit can represent an image, text, ifications to create levels [ 23 ]. or both. The encoding is done such that any tiles that have a unique image-text pair get both encoded in single bit, but tiles that share their image or text with another 3. Description tile have each encoded as a separate bit. In the example, the sky image and - text only ever occur together, and Here we give a general description of the level explorer, thus are encoded together as a single bit. However, the including level encoding, filtering, and visualization. X text can occur with either the ground or block Level Encoding — For eficient filtering by level ele- images, and so each of these text or image possibilities ments, levels are encoded as bitstrings. The encoding gets its own bit (3 in all). Thus, when present in a level,

Initial view.

boxoban witness

User selects a tile (pipe top-right ) and the “No gap” tag; mouses over path edge (pink).

User selects edge, remaining edges appear.

Paths are directed sequences of edges through the level grid (although they do not have to use integer coordiUser selects more tiles (Mario , flag , and ? block ). nates), typically used to represent a possible solution to the level. During the encoding, unique edges across all Figure 2: Sample mario interaction. levels are tracked. Each edge gets its own bit, set to 1 if present in the level.

Tags: Levels can also be tagged with strings. In the tiles encoded as a single bit will have that bit set to 1, and example, the second level was tagged with “block” since those that have their text and image in diferent bits will there is a block in it. Similar to edges, during encoding have both corresponding bits set to 1. Variable level sizes each unique tag gets its own bit, set to 1 if present in the are handled by padding the grid with a special void tile, level. which gets its own bit. Level Filtering — Once levels have been encoded into

Path edges: Levels can also be associated with paths. bitstrings, the level explorer can filter them to select levels that contain certain elements. An eficient implementa- Algorithm 1 Filtering level bit strings tion is built in Python using numpy [ 30 ]. In: : bitstring of selected elements

The core of the filtering algorithm is shown in Algo- : array of level bitstrings rithm 1. It takes as input a bitstring-encoded selection Out: : array of remaining levels () of elements to be present in the levels, along with : bit string of remaining elements the level bitstrings themselves (). First, all level bit- ← ( (, ), ) strings are bitwise AND-ed with, and compared to, the ← ( × ) selection. This results in a Boolean array with True corresponding to levels that pass the filter ( ). This array is then multiplied with the level bitstrings and the text), or selected by finishing the level. The number of result is bitwise OR-ed together. This results in a bitstring remaining levels is also shown. with 1s set for elements that exist in any remaining level ().

Level Visualization — The visualization displays the 4. Datasets bitstring representing all the possible elements that remain. For example, a single location can have multiple Here we describe some sample datasets we have used tiles remaining. The level explorer visualization is interac- with the level explorer. A video of interactions with the tive, and the basic form of interaction is using the mouse datasets is available at https://osf.io/fcyjt/. to select or de-select level elements, which launches a mario: Super Mario Bros. [ 25 ] levels generated by ifltering based on the new selection and an update of enumerating all possible via a 3-gram [ 31 ] based on level the display. As filtering is not instantaneous for larger 1-1 from the VGLC [7], resulting in around 8 million levdatasets, the computation happens in a thread, and re- els. Paths through levels were added using A* pathfindcent selections are cached. Here we describe the basic ing [ 32 ], and tags were added for the presence and abapproach to visualization. sence of some tiles and level and path features.

Tile grids: At each location in the grid, all the possible boxoban: The boxoban [8] dataset of around 1.5 miltiles at that location are shown as a subgrid. Separate lion Sokoban [ 26 ] levels; image tiles from Kenney [ 24 ]. grids are displayed for image and text grids; however, if witness: Black and white square puzzles based on all the tiles are unique image-text pairs, only the image The Witness [ 27 ]. Levels 4 × 4 and smaller, going from grid is shown by default. If there are too many tiles in bottom-left to top-right, with exactly one solution were one location, they are shown as an abstracted tile. If an enumerated [4], resulting in around 750 thousand levels. abstracted location is moused over, all the tiles at that In this dataset, path edges go along the borders between location are shown again so they can be selected. tiles. To make it look more like puzzles in the game, a

Path edges: Directed edges are shown as arrows over border of “padding” tiles was added around each level. the grid. If there are too many edges in the entire visual- cave: A custom cave exploration game. Levels were ization to show at once, all edges are abstracted by only generated by Sturgeon [ 28 ], generating a thousand levels showing edge “source” positions as dots. If the mouse each with rows and columns ranging from 10–15, resultgets close to a dot, the edges coming out of that dot are ing in 36 thousand levels. Generated levels also provide shown. a solution path, though not necessarily the shortest. The

Tags: Tags are shown as checkboxes in the interface. solid text tile X has a several image tiles depending on Checkboxes that do not correspond to remaining bits in its location relative to other solid tiles. Image tiles from the filtered levels are greyed out. Kenney [ 24 ].

Additionally, the interface contains buttons to clear the lode: As a smaller dataset, the VGLC [7] Lode Runselection, undo/redo, make a random selection, or finish ner [ 29 ] dataset, consisting of 150 levels. the level by selecting a remaining level at random. The A sample interaction with the mario dataset is shown user can also change modes and displays, which impacts in Figure 2. Initial views for the other games are shown how tiles and edges are shown and selected. The filtered in Figure 3. A summary of the datasets, including time levels can also be exported. to encode and filter them during interaction, is provided

As the user mouses over the level visualization, ele- in Table 1. ments that would be selected are highlighted. The user’s tile and edge selection is shown as dotted lines at the 5. Discussion and Conclusion location of the tile or edge. For tiles, the lines are diferent depending on if it was directly selected by the user, indirectly selected by selecting a tile of another type (e.g. an image that is indirectly selected by the selection of Thus far we have implemented the level explorer, worked out some technical aspects of the user interface, and supported datasets into the millions of levels. When interacting with the level explorer, we found that it can [8] A. Guez, M. Mirza, K. Gregor, R. Kabra, S. Racaniere, be useful for a quick visual summary of datasets; for T. Weber, D. Raposo, A. Santoro, L. Orseau, T. Ecexample, what areas are reachable by paths, available cles, G. Wayne, D. Silver, T. Lillicrap, V. Valdes, An pipe heights in mario, and the fact that there are never investigation of model-free planning: boxoban levboxes in corners in boxoban. We found that in smaller els, https://github.com/deepmind/boxoban-levels/, datasets (i.e. lode) it is possible to very quickly end up 2018. with only one level remaining, e.g. when selecting player [9] thefifthmatt, The Windmill, https://windmill. location. Thus a tool like this may be more useful when thefifthmatt.com/, 2023. datasets are larger, or benefit from indicating how many [10] A. Zafar, S. Hassan, Q. S. uddin, Corpus for Angry remaining levels contain each element. In the current Birds Level Generation, in: 2019 2nd International setup, the level explorer only determines which elements Conference on Computing, Mathematics and Engiremain, but not how many remaining levels each element neering Technologies, 2019, pp. 1–4. is in; though possible, we we found counting remaining [11] I. Karth, A. M. Smith, Addressing the fundamental levels for each element to be notably slower. We are also tension of PCGML with discriminative learning, in: interested in support for more complex filters, such as Proceedings of the 14th International Conference the absence of elements. In the future, we are interested on the Foundations of Digital Games, 2019, pp. 1–9. in a user study to understand the usefulness of the level [12] G. N. Yannakakis, A. Liapis, C. Alexopoulos, Mixedexplorer and how it compares to other tools. initiative co-creativity, in: M. Mateas, T. Barnes, I. Bogost (Eds.), Proceedings of the 9th International Conference on the Foundations of Digital Games, Acknowledgements 2014. [13] G. Lai, F. F. Leymarie, W. Latham, On mixedWe would like to thank Matthew Guzdial and Eugene initiative content creation for video games, IEEE Chen for their discussions and feedback on the project. Transactions on Games 14 (2022) 543–557. [14] D. Carpenter, J. T. Bacher, H. Crain, C. Martens, CaReferences sual creation of tile maps via authorable constraintbased generators, in: 1st Workshop on Program[1] A. Summerville, S. Snodgrass, M. Guzdial, ming Languages and Interactive Entertainment, C. Holmgård, A. K. Hoover, A. Isaksen, A. Nealen, 2021.

J. Togelius, Procedural Content Generation via [15] H. Crain, D. Carpenter, C. Martens, Evaluating a Machine Learning (PCGML), IEEE Transactions on casual procedural generation tool for tabletop roleGames 10 (2018) 257–270. playing game maps, in: 2022 IEEE Symposium on [2] M. C. Green, L. Mugrai, A. Khalifa, J. Togelius, Visual Languages and Human-Centric Computing Mario level generation from mechanics using scene (VL/HCC), IEEE, 2022, pp. 1–6.

stitching, arXiv:2002.02992 [cs] (2020). [16] T. S. L. Langendam, R. Bidarra, miWFC - designer [3] C. F. Biemer, S. Cooper, On linking level segments, empowerment through mixed-initiative wave funcin: 2022 IEEE Conference on Games (CoG), 2022, tion collapse, in: Proceedings of the 17th Internapp. 199–205. tional Conference on the Foundations of Digital [4] N. R. Sturtevant, M. J. Ota, Exhaustive and semi- Games, 2022, pp. 1–8.

exhaustive procedural content generation, AAAI [17] I. Karth, A. M. Smith, WaveFunctionCollapse is conConference on Artificial Intelligence and Interac- straint solving in the wild, in: Proceedings of the tive Digital Entertainment; Fourteenth Artificial 12th International Conference on the Foundations Intelligence and Interactive Digital Entertainment of Digital Games, 2017, pp. 1–10.

Conference (2018). [18] O. Stålberg, Wave Function Collapse in Bad [5] G. Smith, J. Whitehead, Analyzing the expressive North, url: https://www.youtube.com/watch?v= range of a level generator, in: Proceedings of the 0bcZb-SsnrA, 2018. 2010 Workshop on Procedural Content Generation [19] N. R. Sturtevant, N. Decroocq, A. Tripodi, C. Yang, in Games, PCGames ’10, 2010, pp. 1–7. M. Guzdial, A demonstration of Anhinga: A mixed[6] D. Gravina, A. Khalifa, A. Liapis, J. Togelius, initiative epcg tool for snakebird, in: Artificial G. N. Yannakakis, Procedural Content Generation Intelligence and Interactive Digital Entertainment, through Quality Diversity, in: 2019 IEEE Confer- 2020, pp. 328–330.

ence on Games (CoG), 2019, pp. 1–8. [20] G. Smith, J. Whitehead, M. Mateas, Tanagra: A [7] A. J. Summerville, S. Snodgrass, M. Mateas, S. On- mixed-initiative level design tool, in: Proceedings tañón, The VGLC: The Video Game Level Corpus, of the Fifth International Conference on the FounarXiv:1606.07487 [cs] (2016). dations of Digital Games, 2010, pp. 209–216.

References

[21] L. N. Ferreira , Streamlevels: Using visualization to generate platform levels , ACM Computers in Entertainment ( 2015 ).

[22] S. Cooper , M. Guzdial , path2level: Constraint-based level generation from paths , in: 2023 IEEE Conference on Games (CoG) , 2023 .

[23] D. Karavolos , A. Liapis , G. N. Yannakakis , Evolving missions to create game spaces , in: 2016 IEEE Conference on Computational Intelligence and Games , IEEE, 2016 , pp. 1 - 8 .

[24] Kenney , Free game assets, https://www.kenney.nl/ assets, 2022 .

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

[26] Thinking Rabbit , Sokoban, 1928 . Game.

[27] Thekla , Inc. , The Witness , 2016 . Game.

[28] 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 .

[29] D. Smith , Lode Runner , 1983 . Game.

[30] C. R. Harris , K. J. Millman , S. J. van der Walt , R. Gommers, P. Virtanen , D. Cournapeau , E. Wieser , J. Taylor , S. Berg, N. J. Smith , R. Kern , M. Picus , S. Hoyer , M. H. van Kerkwijk , M. Brett , A. Haldane , J. F. del Río , M. Wiebe , P. Peterson , P. Gérard-Marchant , K. Sheppard , T. Reddy , W. Weckesser , H. Abbasi , C. Gohlke , T. E. Oliphant , Array programming with NumPy , Nature 585 ( 2020 ) 357 - 362 .

[31] S. Dahlskog , J. Togelius , M. J. Nelson , Linear levels through n-grams , in: Proceedings of the 18th International Academic MindTrek Conference: Media Business, Management, Content & Services , 2014 , pp. 200 - 206 .

[32] A. J. Summerville , S. Philip , M. Mateas, MCMCTS PCG 4 SMB: Monte Carlo tree search to guide platformer level generation , Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment ( 2015 ).