Pathfinding Agents for Platformer Level Repair Seth Cooper and Anurag Sarkar Northeastern University se.cooper@northeastern.edu, sarkar.an@northeastern.edu Abstract the generation process no matter how the agent failed to complete the level. However, not all unplayable levels are A key concern for procedural level generation is ensuring that generated the same, and a simple set of modifications might generated levels are in fact playable. One approach for deter- mining playability is using pathfinding agents to test if gener- be enough to render some of them playable without having ated levels can be completed. This typically involves follow- to regenerate them from scratch. Additionally, such mod- ing an iterative loop of generating candidate levels until the ifications could be determined by leveraging information agent is able to successfully complete a playthrough, discard- about where and how the agent would need to do something ing the failed level and starting the generation process over impossible to complete the level and thus the ability to repair each time the agent fails. In this paper, we present a new ap- an unplayable level could be incorporated into the pathfind- proach for generating playable levels that leverages pathfind- ing agent itself, thereby aiming to replace the generate-and- ing agents, not to simply test levels for playability, but to per- test loop with a single generate-and-fix pass, or increase the form level repair to fix generated levels that are unplayable. likelihood of the test passing. By augmenting a simple pathfinding agent to be able to take In this paper, we introduce a new pathfinding agent ca- moves that would require modifying the level, our approach can fix unplayable levels without having to regenerate a new pable of repairing levels as part of testing levels for playa- level from scratch. We compared our repair agent to a default bility. The agent is able to make some impossible moves as agent on three PCGML level generators each for Super Mario it searches for a path through the level, and, if the resulting Bros. and Kid Icarus, and found the repair agent was able to path includes these moves, they are used to modify the level fix the majority of levels, taking time that ranged from similar in an attempt to repair it. In our approach, the level remains to the default agent to around 4x its time. unmodified as the agent searches for a path, which can lead to finding paths with contradictions in them, such as both moving through a non-solid tile and then jumping off of it Introduction as if it were solid. We attempt to guide the agent away from Procedural content generation (PCG) refers to a set of ap- such moves. proaches for algorithmically generating content for games. For evaluation, we compared our repair agent to a default An important consideration for PCG methods is ensuring agent on three different PCGML level generators (two n- functionality of generated content, which in the specific con- grams and one VAE) each for Super Mario Bros. and Kid text of game level generation means ensuring that gener- Icarus, and found the repair agent to be able to repair the ated levels are playable. One approach for doing so, par- majority of levels. The execution time for the repair agent ticularly for techniques involving search-based PCG (To- ranged from being similar to that of the default agent to ap- gelius et al. 2011) and PCG via machine learning (PCGML) proximately 4x its time. (Summerville et al. 2018), is to follow a generate-and-test methodology. Here, as the name suggests, a test is used to Related Work check if a generated level satisfies desired constraints (such A body of prior PCG research has utilized pathfinding as playability). If this test fails, the level is discarded, a new agents, specifically based on A∗ search, to help generate level is generated, and the process continues until a desired playable levels. This has been particularly popular in search- number of valid levels has been generated. based PCG techniques (Togelius et al. 2011) where playabil- A commonly used test in such approaches is the use of ity as determined by the A∗ agent is incorporated into the ob- pathfinding agents to check for playability, filtering out those jective function being optimized to search for levels. Addi- generated levels that the agents fail to complete. As dis- tionally, use of A∗ agents has also been popular in PCGML cussed in the related work, this approach has been used by techniques where these agents have been used to annotate several prior works for generating playable levels; it restarts levels with A∗ paths with the hope that models trained on Copyright c 2020 for this paper by its authors. Use permitted un- them will generate levels with such traversable paths as well. der Creative Commons License Attribution 4.0 International (CC Overall, there have been two popular approaches to BY 4.0). pathfinding agents that have been used in a number of works modifications for evaluating level playability and generating playable lev- level playable (in repaired levels) agent time (ms) els. First, Robin Baumgarten’s physics-simulation agent w/o with rep. rep. not min med max default repair (Togelius, Karakovskiy, and Baumgarten 2010), used with Markov models (Snodgrass and Ontañón 2014), GANs SMB N1-1 995 5 0 1 1 1 282 (40) 338 (46) (Volz et al. 2018), Quality-Diversity algorithms (Withing- SMB N1-3 782 218 0 1 1 2 235 (47) 333 (82) ton 2020), the GVG-AI domain (Green et al. 2018; 2020) SMB VAE 953 47 0 1 1 3 259 (47) 320 (55) and the Mario AI framework (Khalifa et al. 2019). Sec- KI N1 6 893 101 1 7 22 150 (55) 612 (137) ond, Adam Summerville’s tile-based agent (Summerville, KI N4 1 801 198 1 7 24 156 (49) 609 (156) Philip, and Mateas 2015), used with LSTMs (Summerville KI VAE 31 840 129 1 4 19 177 (83) 583 (140) and Mateas 2016), Markov models (Snodgrass and Ontañón 2016; 2017) and VAEs (Sarkar et al. 2020). Note that in all Table 1: Summary of results for attempting to repair 1000 these cases, the agent is used to determine whether a gener- generated levels for each generator. The number of levels ated level is playable or not rather than to modify the level. that were playable without repair, with repair, and were not Our work differs in that our agent can actively attempt to playable after attempted repair; the minimum, median, and repair a generated level if it is not playable. maximum number of modifications used in levels that were A number of prior works have focused on repairing gen- repaired; and the mean and standard deviation of time taken erated levels. Jain et al. (2016) trained autoencoders to gen- by the default agent and the repair agent. erate and repair Mario levels while both Mott, Nandi, and Zeller (2019) and Shu et al. (2020) attempted to repair de- fective GAN-generated Mario levels, with the former using on which tiles have already been visited by the pathfinding LSTMs and the latter using a hybrid approach combining search. These include preventing the agent from walking on a multi-layer perceptron and genetic algorithms. We also at- solid tiles that have been visited, or starting a jump above tempt to fix defective generated levels in this work but utilize solid or non-solid tiles that have been visited. We also pre- our pathfinding agent, instead of a trained model, to make vent moves that would modify the start and goal tiles and repairs. those under them. Notably, this does mean that the agent will have different moves available depending on the order Method in which nodes (and thus tiles) are visited by the pathfinding Here we describe the basic approach we used to allow a search; thus we do not expect the agent to find an optimal pathfinding agent to attempt to repair a platformer level. set of modifications. To check if the level is playable by the For pathfinding, we started with the pathfinding agent default agent with the modifications, we confirm the default provided by the Video Game Level Corpus (VGLC) (Sum- agent can follow the path the repair agent took after applying merville et al. 2016). This tile-based pathfinding agent con- modifications. siders two types of tiles: solid and non-solid. We made a If the repair agent can find a path through the level, and few minor updates, such as adding support for start and goal the default agent can follow that path after applying modifi- tiles, and removing some shortcuts the agent could take to cations, we consider the level repaired. move through solid tiles. We refer to this as the default agent. Running this agent on a level gives a path from the Analysis and Discussion start to the goal, if there is one, which determines if the level is playable. To evaluate the performance of this approach, we ran the We augmented the default agent to create the repair agent. repair agent and the default agent on levels generated via two The repair agent can take additional actions: in some cases PCGML approaches, trained using levels from the games it can move through solid blocks or jump while above non- Super Mario Bros. (SMB) and Kid Icarus (KI), taken from solid blocks. However, these actions have a very high cost, the VGLC (Summerville et al. 2016). high enough that the agent will not take them unless neces- First, we used n-grams (Dahlskog, Togelius, and Nel- sary. After the repair agent has found a path, it goes back son 2014). For SMB, we generated levels using trigrams; through the path and looks for any high cost moves. If it one trained on level 1-1 (SMB N1-1) and one on level 1- finds any, it then modifies the level appropriately: modify- 3 (SMB N1-3). For KI, we generated levels using bigrams, ing a solid tile to be non-solid if it was moved through, and one trained on level 1 (KI N1) and one on level 4 (KI N4). modifying a non-solid tile to solid if it was jumped off of. Levels generated were 100 columns/rows for SMB/KI. While this approach is relatively quick, it can result in the Second, we used variational autoencoder (VAE)-based se- repair agent making contradictory moves and modifications. quential level generation models for SMB (SMB VAE) and For example, the agent can jump up through a non-solid tile, KI (KI VAE) as described in Sarkar and Cooper (2020). The and then jump again from above that same tile, which would model for each game was trained on 16x16 level segments result in a modification to place a solid tile, even though if of that game extracted from all their levels in the VGLC and that solid tile had been there originally, the first jump would is capable of generating whole, continuous levels consisting not have been possible. of these 16x16 segments. Levels contained 6 segments each, To reduce the chance of these kinds of contradictory resulting in 96 columns/rows for SMB/KI. moves, we prevent the agent from making some moves in For each generator, we generated 1000 levels. We ran the cases that seem likely to introduce contradictions, based default agent and repair agent on each to see which lev- -----------------------------....------------------------------------------------------------------- ----------------------------..---.------------------------------------------------------------------ ---------------------------..-----.----------------------------------------------------------------- ------....----------------..-------.---------------------------------------------------------------- -----..---.-------------...---------.....-------E------------------------------------------.......}- med ----..XX---.-----------..XX----------.XX-.---SSSSSS----------SSSQ-------------------------..--SSSSSS ---..XXX----.-------....XXX----------XXX--.----------------....--..-----------------..---..--------- --..XXXX-----.-----..--XXXX---------XXXX---.--------------..---...-.---------------..-.-..---------- -..XXXXX------.---..--XXXXX--------XXXXX----.------------..-----.---..------------..---..----------- -{XXXXXX-------.-..--XXXXXX-------XXXXXX-----.----------..X-----S--<>-.--Q--Q---...---<>^----------- -XXXXXXX--------..--XXXXXXX------XXXXXXX------.--------..XX--------[]--.--------.<>---[]------------ XXXXXXXX--------<>-XXXXXXXX--<>-XXXXXXXX-------.------..XXX--------[]---.-------.[]---[]------------ SMB N1-1 XXXXXXXX--------[]XXXXXXXXX--[]XXXXXXXXX--------.......XXXX------E-[]----........[]-E-[]------------ XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-- ---------------------------------------------------------------------------------------....--------- --------------------------------------------------------------------------------------..---.-------- -------------------------------------------------------------------------------------..-----.------- ---------------------------------------------------------------------------------..-..-------.------ ---------------------------------------------------------------E-----E------......-..---------....}- max -----------------------------------------------------------SSSSSSSSSSSSSSQ-..---.--SS-------SSSSSSS- --------------....--------------------------------------------------------..----^------------------- -------------..---.------------------------------------------------------..------------------------- ------S-----..-----..---------------------------------------------------..-------------------------- ---Q-------..-----XX-.----------Q----Q-------------Q--------------------.S-------------------------- ---------...-----XXX--.----------------------..-------------------------.--------------------------- --------..<>----XXXX---.--------------------..-.------------------------.--------------------------- X{.......-[]---XXXXX----.....................---.........................-E-E--------EE-E----------- XXXXXXXXXXXXXXXXXXXX--XXXXXXXXXXXXXXXXXXXXXXX--XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--- ---------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------- ------------------------------------------------------------------..---------------....------------- -----------------------------------------------------------------..-.------..-----..---.------------ ---------oo--oo-------------------oo----------------..-----E......---.----..-.---..-----.------E---- med ------..------------------E------------..----------..-.----..-E-.-----.....---.-..-E-----.o----E---- -----..-.----------------XXXXX--------..-...........---.--..-XXXX----XXXXXX----..---------.------XXX ---...---.-------------..------....--..-XXXXXXXXXXXX----...-------------------XXX----------.-------- ---.XX----....--------..-.----..---...-------------------.----------------------------------...----- X--.------XXX-.------..---.--..----XXX------------------XX---------------------------XXXX--XXX-.---- ---.-----------.......-----...------------------------------------------------------------------.--- -{..----------XXXXXXXX------.--------------------------------------------------------------------.-- SMB N1-3 -XXX------------------------^------------------------ooo--------------------------ooo-------------}- -----------------------------------------------------XXX--------------------------XXX-------------XX ---------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------- ------------------------------------------------------------------..-------------------------------- ------oooooo-----------------------....---------oo--------....---..-.----------------------..------- max ------XXXXXX------------E---------..---.E----------------..E--....---.o---------------oo--..-.o----- -----------------------XXXXX-----..-----.---------------..XXXXXXXX----.------------------..---.----- --------------------------------..--XX---.-------------..--------------...------------....-----.}--- -----------------------....--....---------.......-----..--------------XXX-.----------..XXX----XXX--- -{.....---------------..---...XXX---------XXXXXX-.---..^-------------------.--------..-------------- -XXXX?-.-------------..-----.---------------------....----------------------.------..--------------- --------.--..--...--..------^--------------------XXXXX-----------------------.......---------------- ---------...-...X-...------------------ooo---------------------------------XXXXXXXXX---------------- -----XXXXXXX-XXXXXXXX------------------XXX---------------------------------------------------------- ------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------ --------------------------------------------....------------------------------------------------ -------------------------------------------..---............................................---- ------------------------------------....--..----SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS-.--- -----------------------------------..---...-----------SSSSSSSSSSSSSSSSSSSSSSSSSSSS-----------.}- med ----------------------------------..-----.------------SSSSSSSSSSSSSSSSSSSSSSSSSSSS-----------XXX -----....------------------------..XX----^------------SSSSSSSSSSSSSSSSSSSSSSSSSSSS--QQ---------- ----..-X-.----------------------..XXX----------------------------------------------------------- ---..-XX--.--------------------..XXXX----------------------------------------------------------- --..-XXXS--.------------------..XXXXX-------------------------?-------------EEE----------------- -..--XXX----.----------------..XXXXXX---S---------------SSSSSS??SSSSSSSSSSSSSSSSSS--QQ--QQQ----- -.X-XXXX-----.--------------..XXXXXXX-------------------SSSSS---SSSSSSSSSSSSSSSSSS-------------- -.XXXXXX------.------------..XXXXXXXX-------------------SSSSS---SSSSSSSSSSSSSSSSSS-------------- SMB VAE -{X--XXX-------.............XXXXXXXXX--------X---------------oooSSSSSSSSSSSSSSSSSS-------------- XXXXXXXX-XX--XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--X---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----- ------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------ ---------------------------..------------------------------------------------------------------- --------------------..----..-.--------oo-----------------------....----------------------------- -----------E-------..-.--..---.------X------------------------..---.---------------------------- max E--o--....------....---...--o--.------------------------...--..-----.------.-------------..----- --E--..---.----..--^---XXX------.----------------------..--...---o---.----...-----------..-.---- ----..-----.--..-----------------.-----------XX-------..----.---------.--..--.--.........---.--- ---..-------...-----------X-------.------------------..-----X----------...----...XXXXXXXX----.-- --..---------.--------------X------.------..------....------------------.------.--------------}- -X.X---------^--------------------X-.......-..--X..--^------------------X------X-------------XXX --.-------------------------------XXXXXXXXX-X.--..---------------------------------------------- -..-------------------------------------------...-------------XX-------------XX----------------- -{---S-----------------------------------------.------------------------------------------ooo--- XX---------------------X----------------X------X---------------------------X--------------XXX--- Figure 1: Example generated Super Mario Bros. levels using each generator with the median and maximum number of modifi- cations (most of which are 1). Paths are shown as dots; removed solids are cyan + and added solids are magenta ˆ. ####----------## ####----------D# --.------TTT---- ------------##-- ####---.}-----D# ####-}.-######## --.}------------ ----------####-- ####---.######## ---#-#.--------- --.#------------ ---------------- ---#-#-.-------- ---#--.--------- --..-----#------ -----.}--------- ---#---.-------- ###---.....---## ---..----------- -----.TTT------- ##----------...# #TTTTTTT----#### ###----....---## ##########.---## ---#.----------- -----.---------- ####-------.+#}# ####--------#### ##########.---## ##--------.---## ----.----------- ----#.---------- ---#------..#### ####-----.}-#### ##--------.---## ##----...-.---## TTTT.----------- -----..--------- T#-#--#D-..-###- ####-----.TTT### ##--------.---## ###++++#-..---## ----....-------- -----#..-------- -#------..T----- ####-----.--#### ########--..--## ##..--#####---## ---####.-TTT---- -------..--#---- -------..---#### ####-.....--#### ##----#####.--## #+.-----------## ---####..-####-- --------..------ -#----..----#-## ####-.########## #D---------.--## ++------------## -TTT###..-####-- -------TT..----- M#----.T---T#T## ####-.------#### #####---....#### ++..----------## ---#####..####-- ---------#.----- T-----.--------- ####-..-----#### ########+####### #D-..---------## ----####..####-- ----------.----- ##----.--------- ##TTTT..----#### ####---#+###-### #D--..--------## ----#TTTT.####-- -------#--.#---- T#TTT-..----#--# ####---..---D### #------..----### #D---..-------## --------..####-- ----------...--- ##--TTT..--T---- ####---..---D### #-----..------D# #D----..------## -------..TTT##-- ---D###--TTT...- --------...----# ####---.######## #--....#---#--D# #D----^..-----## ------..-------- ---D###---####.- -----T-TTT..---- ####---.----#### #-..############ #D------..----## MMMMM..MMMMMMMMM -TTT###---####.- -----------..--- ####---..---#### #-.############# #####---..--#### -----..--------- ---#####--####.- -----------..--- #TTTTTTT.---#### ##.#------------ ########+####### -----#..-------- ...-####--####.. ####-------.#### ####----.####--- ##.#--...------- ####---#+###-### -------..--#---- --..####--####^- ##---------..-#- ####----.---#### #-....-#....---# #------..----### -------...------ ---.+TTTT-####-- ##----#--#-#..## ####---..---#### ########-.-.---# #-----..------D# ------..-.------ ----....--####-- ##-----#---...## #-----..^---D### ####---####.---# #--....#---#--D# -----..-TTTT---- -----.-..-####-- ##---------.#### #--....-----D### ----------..---# #-..############ -----...-------- -----^--..####-- ######-----.#### #-..--^######### ----------.TT--# #-.############# -----#-.-------- --------..####-- ####-------.#### #..------------# ----------.----# ##.#------------ -------..--#---- -------..TTT##-- --------....##-# +.-------------# ----------.-#### ##.#--...------- -------..------- ------..-------- ##-----..TTT-T-# ++#######------# ..------...-##-- #-....-#..-----# -------#.--#---- MMMMM..MMMMMMMMM ##-TT-..-------# #++#------------ .-.--....#####.. ########-...---# --------..------ -----...-------- ##----..------## #-..------------ ---.-.-.-##--..- ####---####.---# ------TTT.------ ---D###.-TTT---- ---TT-^..------- ---..----------- ----..#####...-- -----------.---# --------..------ ---D###..-####-- #MMMMM-M..MMMMMM ---..----------- -----.##--...--- -----------.#### TTTTTTTT..------ -TTT###..-####-- ---------..----- --..########---- ########-..-#### --------....##-- --------.TTTT--- ---#####.-####-- ----H----..--H-- -..--------#---- ---------..----- -------..#####-- --------...----- ----###+.-####-- MM-MM-M--.T-MMMM -..--------#---- ---------^..---- -----...-##----- --TTTTTTTT.----- ---.++++--####-- ##-##----.----#- ##.---------#### -----------..--- ----..#####----- ----------.----- --..####--####-- ####-----..---#- ##....---------- ------------..-- --...-##-------- TTTTTTTT...----- -..-####--####-- #--------^..---- ##.--..--------- ------------..-- -..#####-------- -------..TTTT--- ..--####-TTTTTT+ -----------...-- ####MM..MMMMMMMM -----------..^-- ..-##----....... ------..-------- .---####--####-. ------------..-- ####---..------- ---------...---- #####---..###### TTTT-..--------- .---####-TTTTTTT -------#----#.-- ####---..------- ------T--.TT---- ------...-##---- -----..--------- .---####--####-. ------------..-- ####---.#------- ---------.------ ------.#####---- -----#.--------- ..--####--####-. ----#-#T----.#-- -------.#------- --------T..----- ------.--------- ------.----#---- -..-####-TTTTTTT -----------T.--# ------..#------- ---------..----- --##--..-------- ------.--------- --..####--####-- -----------..--- ------..#------- #-----TTTT.TTTTT --#####..------- ------...------- --..####--####-- #----------.##-# ------^..------- #---------..---- -----##-...----- TTTTTTTT.------- -..^####--####-- -----------.-##- --------...----- #---------..---- -----#####..---- --------.TTTT--- ..--####-TTTTTT+ ----------..---- MMMMMMMM#M..M-MM #----..--..D#--- --------##-...-- --------.------- .---####--####-. ----------..---- -----------..--- #---..-...-D#--# --------#####..- --------..------ ..--####-TTTTTTT ----------^..--- ------------..-- #--..-########-# .....------##-.. ------TTT..----- -.--####--####-- --------##--..-- ####--------..## #--..-##-------# ####..-----##### ----------..---- -.--####--####-- ------------#.-- ###--------..### #--#+###-------# --##-...-------# -----#----..---- ..--####-TTTTTTT ---------#TT#.-- ##-#-----...---# #--#.----------# --#####..------# ----------.#---- .^--####--####.. -------------.-- #-##-----.###### #T-#.....------# -----##-....---# ----------.----- ----####-TTTT++T ..-----------... #--------.------ #--#####..-----# -----#####..---# ---------..----- ----####--###+.- -..------####### ---------..----- #--#-----.+##### ---------##.---# ---#-----..----- ----#TTTT-####.- --..------------ M-MMMMMMM^..MMMM #--#------..--## ---------#+.---# ---------#..---- ----------####.- ---..-####------ -----------..--- #T-#------..--## ---------#+.---# -----------..--- .--------TTT##.. ---..----------- ##---------..--- #--#-----..^--## ---------##..--# -----------..--- ..-----H------^- ---.TTT--------- ##---------.#### #T-#----..----## ---------##-..-# ####-------.#### -..------------- ---..---------H- ##---------.---- #--#---..-----## ------------..-# -----------.---- --..------------ ####..------#### -#---------...-- #T-#---..-----## ------------.TT# -----------..--- --..------------ -----..--------- ##-M-MMMMMM.M..M #--D####.-----## ------------..-# -------#---#.--- --.#------------ ------..-TTTT--- #----------#--.. #--D----.-----## ------------..-# ------------.--- --.------#------ -----...D------- ..---------#---. #-T#----.....--# -----------..TT# ---D###--TTT...- --..------------ ----..####------ #.T-TT---------# #--#----####.--# ----------..---# ---D###---####.- --^..----------- --...----------- -...------------ #--#--------.--# ---------..-#### -TTT###---####.- ----..---------- --.####--------- -.-..----------- #--#--------..## --------..--##-- ---#####--####.- -----..--------- --.------------- ##--..--#-----## #-T#--------..## -------..#####-- ..--####--####.. -----#.--------- ...------------. -#---..--------# #--#-----####.## -----...-##----- -..-####-TTTTTTT ------.----#---- #######-------.. -----..--------# #--#--------..## ----..#####----- --..####--####-- ------.....----- -------------..- ----..^--------- #-T#--------..## --...-##-------- ---.+###--####-- --TTTTTTTT..---- ------TTTT--..-- ---..----------- #--#-----####.## --.#####-------- ---.+###--####-- -----------..--- ------------..-- ---...---------- #--#----..--..## --.##----------- --..####--####-- -----------..--- ---------####.-- ####-.-----####- #-T#----.-...-## ...##--------... -..-####--####-- ####-------.#### -----------...-- #---..------#### #--#----.####-## ####--------..## -..-####--####-- -----------..--- ####------..#### ##--..------#### #--#---..-----## ####--------..D# -^..####--####-- ---D###--TTT...- -----H---..----- ##--.#-#----#### #T-#---..-----## ####----#####+## ---.+###--####-- .--D###---####.. ----TTT-..------ ####..#-----#### #--D####.-----## ---#-#-------..- ---.+###--####-- .+TT###---####-- --------.....--- ####..----###### #--D----.-----## ---#---------..- ---.####--####-- -..#####--####-- ------####--..-- ###+.^----####-- #-T#---..------# ###----------.## ---.#TTTT-####-- -..-####--####-- -------------..- ##++H-H-#-####-- #--#---.####---# ##########---.## --..------####-- ..^-####--####-. ---------####-.. #++#------###### #--#---.-------# ##----------..## --..------####-- ..--####--####-. -------------... ..----------.... #--#---.------## ##---------..^## --^..----TTT##-- -..-####-TTTTTTT ------------..-# ##----------..## #T-#---..-----## ##------....--## ----..-H-------- --..####--####-- ------#-----{--- ##---------..### #--D####.-----## ########.-.---## MMMMM..M..MMMMMM ---.+###--####-- ------------#--- ##--------...### #--D----.--..-## ##----##+##---## ------..-.------ ---.+###--####-- ---------------- #######---.-###- #-T#----...-.--# #D-----..-----## ------TTT.------ --..####--####-- ---------------- -####-----.####- #--#----####.--# #####-..----#### ---------..----- -..-####--####-- ---------------# -####----..####- #--#----.....--# ######+######### --TTTTTTTT.----- ..--####--####-- ---------------- #####---..#####- #-T#----.####--# ####--.#####-### ----------.----- ..--####-TTTTTTT #--------------- ##-----..---#-## #--#----.------# #----..------### -----TTTT-.----- ^..-####--####-- ---------------- ##-----...--#### #--#----.-----## #----..-------D# ---------..----- --..#TTTT-####-- #--------------- ##----##-..-#### #T-#----..----## #----^.#---#--D# -----#--..^----- ---..-..--####-- ---------------- ####------...### #--#-####.----## #---##+######### -------..--#---- ----..-.-------- ---------------- ####------##++## #--#-----.----## #--###++######## ------..-------- ----^TT+T------- ---------------- ####------###+.- #-T#-----{----## ##-#---{-------- ---{...--------- -------{-------- ---------------- ####--H#######{- #--#-----####-## #------#-------# ---D###--TTT---- -------#---#---- ---------------- ####------###### med max med max med max KI N1 KI N4 KI VAE Figure 2: Example generated Kid Icarus levels using each generator with the median and maximum number of modifications. Paths are shown as dots; removed solids are cyan + and added solids are magenta ˆ. els were playable by the default agent and which could be number, type, or location of modifications allowed before repaired to be playable by the repair agent, and gathered rejecting a level. The application of repair agents as a sup- modification and timing information. The agents were im- port tool for hand-authored levels, along with the types of plemented in Python. feedback they can provide to designers on their levels, may For KI, we updated the agents to allow wrapping around be an area for further study. the sides of the level; for simplicity, we considered one-way platforms as solid and moving platforms as non-solid, and References used the jump definitions from SMB. Dahlskog, S.; Togelius, J.; and Nelson, M. J. 2014. Linear A summary of the results is given in Table 1, with example levels through n-grams. In Proceedings of the 18th Inter- repaired SMB levels in Figure 1 and KI levels in Figure 2. national Academic MindTrek Conference: Media Business, In the analysis, we found that most levels were able to Management, Content & Services, 200–206. be repaired to be playable. The SMB levels generated were mostly playable already, but the repair agent was able to Green, M. C.; Khalifa, A.; Barros, G. A.; Nealen, A.; and make all of them playable. Only one or two modifications Togelius, J. 2018. Generating levels that teach mechanics. were needed to repair the levels, usually adding a solid tile In Proceedings of the 13th International Conference on the to make a jump possible. Foundations of Digital Games, 1–8. On the other hand, the KI levels generated were almost Green, M. C.; Mugrai, L.; Khalifa, A.; and Togelius, J. 2020. entirely unplayable initially. The repair agent was able to Mario level generation from mechanics using scene stitch- get to around 80-90% playable levels. Several modifications ing. arXiv:2002.02992 [cs]. were often needed to repair KI levels, sometimes carving out Jain, R.; Isaksen, A.; Holmgård, C.; and Togelius, J. 2016. several solid tiles to make a path. We suspect that these paths Autoencoders for level generation, repair and recognition. In may be due to certain modifying moves being prevented by Proceedings of the ICCC Workshop on Computational Cre- visited tiles, which the agent compensates for by modifying ativity and Games. solid tiles. It is possible that the low playability of the gen- Khalifa, A.; Green, M. C.; Barros, G.; and Togelius, J. erated KI levels was related to, for example, the simplicity 2019. Intentional computational level design. In Proceed- of the n-gram model creating large open vertical sections. ings of the Genetic and Evolutionary Computation Confer- Playability may also have been impacted by simplifying the ence, 796–803. platform mechanics and using SMB jumps; a higher-fidelity Mott, J.; Nandi, S.; and Zeller, L. 2019. Controllable and co- approximation of KI mechanics could have found the levels herent level generation: A two-pronged approach. In AIIDE to be more playable. Workshop on Experimental AI in Games. We found a moderate increase in the relative time taken by the repair agent, which appears to increase as the proportion Sarkar, A., and Cooper, S. 2020. Sequential segment- of initially playable levels decreases. For SMB N1-1, which based level generation and blending using variational au- had 99.5% initially playable levels, the repair agent took toencoders. In Proceedings of the 11th Workshop on Pro- only 120% of the time of the default agent. For KI N1, which cedural Content Generation in Games. had only 0.6% initially playable levels, the repair agent took Sarkar, A.; Summerville, A.; Snodgrass, S.; Bentley, G.; and 408% of the default agent’s time. We expect this is due to Osborn, J. 2020. Exploring level blending across platform- the relatively short time in which the unplayable levels can ers via paths and affordances. In Sixteenth Artificial Intelli- be rejected by the default agent. gence and Interactive Digital Entertainment Conference. Shu, T.; Wang, Z.; Liu, J.; and Yao, X. 2020. A novel CNet- Conclusion assisted evolutionary level repairer and its applications to In this work, we proposed a pathfinding agent that can at- Super Mario Bros. arXiv preprint arXiv:2005.06148. tempt to repair platformer levels by modifying solid tiles to Smith, G., and Whitehead, J. 2010. Analyzing the expres- be non-solid or vice versa. In an analysis of procedurally sive range of a level generator. In Proceedings of the 2010 generated levels, we found the repair agent can improve Workshop on Procedural Content Generation in Games. playability at the cost of an increase in time over an agent Snodgrass, S., and Ontañón, S. 2014. Experiments in map that only evaluates playability. generation using Markov chains. In Proceedings of the There are a variety of future directions and variations on 9th International Conference on the Foundations of Digital this work. Other types of modifications may be possible, Games. such as placing items, and other types of games could be explored with other tile types. Different pathfinding search Snodgrass, S., and Ontañón, S. 2016. Controllable proce- heuristics may influence the modifications made. More ac- dural content generation via constrained multi-dimensional curate models of player movement (than tile-based approx- Markov chain sampling. In Proceedings of the Twenty- imations) can also be explored. Future work could also ex- Fifth International Joint Conference on Artificial Intelli- amine the impact of repair on expressive range (Smith and gence, 780–786. Whitehead 2010), for example, comparing the expressive Snodgrass, S., and Ontañón, S. 2017. Learning to generate range of the generated levels pre- and post-repair. video game maps using Markov models. IEEE Transactions While we considered a level repaired with any number of on Computational Intelligence and AI in Games 9(4):410– modifications, designers might want to place a limit on the 422. Summerville, A., and Mateas, M. 2016. Super Mario as a string: Platformer level generation via LSTMs. In Proceed- ings of 1st International Joint Conference of DiGRA and FDG. Summerville, A. J.; Snodgrass, S.; Mateas, M.; and Ontañón, S. 2016. The VGLC: The video game level corpus. In Seventh Workshop on Procedural Content Generation at First Joint International Conference of DiGRA and FDG. Summerville, A.; Snodgrass, S.; Guzdial, M.; Holmgård, C.; Hoover, A. K.; Isaksen, A.; Nealen, A.; and Togelius, J. 2018. Procedural Content Generation via Machine Learning (PCGML). IEEE Transactions on Games 10(3):257–270. Summerville, A. J.; Philip, S.; and Mateas, M. 2015. MCM- CTS PCG 4 SMB: Monte Carlo tree search to guide plat- former level generation. In Eleventh Artificial Intelligence and Interactive Digital Entertainment Conference. Togelius, J.; Yannakakis, G. N.; Stanley, K. O.; and Browne, C. 2011. Search-based procedural content generation: A taxonomy and survey. Computational Intelligence and AI in Games, IEEE Transactions on 3(3):172–186. Togelius, J.; Karakovskiy, S.; and Baumgarten, R. 2010. The 2009 Mario AI competition. In IEEE Congress on Evolu- tionary Computation, 1–8. ISSN: 1941-0026. Volz, V.; Schrum, J.; Liu, J.; Lucas, S. M.; Smith, A.; and Risi, S. 2018. Evolving Mario levels in the latent space of a deep convolutional generative adversarial network. In Proceedings of the Genetic and Evolutionary Computation Conference, 221–228. ACM. Withington, O. 2020. Illuminating Super Mario Bros: quality-diversity within platformer level generation. In Pro- ceedings of the Genetic and Evolutionary Computation Con- ference Companion, 223–224.