{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T18:28:09Z","timestamp":1774549689681,"version":"3.50.1"},"reference-count":38,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2014,6,1]],"date-time":"2014-06-01T00:00:00Z","timestamp":1401580800000},"content-version":"vor","delay-in-days":31,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Computer Graphics Forum"],"published-print":{"date-parts":[[2014,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The design of video game environments, or levels, aims to control gameplay by steering the player through a sequence of designer\u2010controlled steps, while simultaneously providing a visually engaging experience. Traditionally these levels are painstakingly designed by hand, often from pre\u2010existing building blocks, or space templates. In this paper, we propose an algorithmic approach for automatically laying out game levels from user\u2010specified blocks. Our method allows designers to retain control of the gameplay flow via user\u2010specified level connectivity graphs, while relieving them from the tedious task of manually assembling the building blocks into a valid, plausible layout. Our method produces sequences of diverse layouts for the same input connectivity, allowing for repeated replay of a given level within a visually different, new environment. We support complex graph connectivities and various building block shapes, and are able to compute complex layouts in seconds. The two key components of our algorithm are the use of configuration spaces defining feasible relative positions of building blocks within a layout and a graph\u2010decomposition based layout strategy that leverages graph connectivity to speed up convergence and avoid local minima. Together these two tools quickly steer the solution toward feasible layouts. We demonstrate our method on a variety of real\u2010life inputs, and generate appealing layouts conforming to user specifications.<\/jats:p>","DOI":"10.1111\/cgf.12314","type":"journal-article","created":{"date-parts":[[2014,6,2]],"date-time":"2014-06-02T03:57:49Z","timestamp":1401681469000},"page":"95-104","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Game level layout from design specification"],"prefix":"10.1111","volume":"33","author":[{"given":"Chongyang","family":"Ma","sequence":"first","affiliation":[{"name":"University of British Columbia"},{"name":"University of Southern California"}]},{"given":"Nicholas","family":"Vining","sequence":"additional","affiliation":[{"name":"University of British Columbia"}]},{"given":"Sylvain","family":"Lefebvre","sequence":"additional","affiliation":[{"name":"ALICE\/INRIA"}]},{"given":"Alla","family":"Sheffer","sequence":"additional","affiliation":[{"name":"University of British Columbia"}]}],"member":"311","published-online":{"date-parts":[[2014,6]]},"reference":[{"key":"e_1_2_7_2_1","first-page":"496","volume-title":"Proceedings of the 4th International Conference on Entertainment Computing","author":"Aarseth E.","year":"2005"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2011.2138707"},{"key":"e_1_2_7_4_1","volume-title":"Legend of Zelda: Skyward Sword (Prima Official Game Guide)","author":"Ashby A.","year":"2011"},{"key":"e_1_2_7_5_1","volume-title":"Designing Virtual Worlds","author":"Bartle R.","year":"2003"},{"key":"e_1_2_7_6_1","volume-title":"Skyrim's modular approach to level design","author":"Burgess J.","year":"2013"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461977"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360702"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01386.x"},{"key":"e_1_2_7_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00020-D"},{"key":"e_1_2_7_11_1","volume-title":"Chris Crawford on Interactive Storytelling","author":"Crawford C.","year":"2004"},{"key":"e_1_2_7_12_1","unstructured":"[Gas11]\u00a0\u00a0Gaslamp Games Inc.:Dungeons of dredmor 2011. URL:http:\/\/www.gaslampgames.com. 2."},{"key":"e_1_2_7_13_1","volume-title":"Elder Scrolls V: Skyrim Revised and Expanded: Prima Official Game Guide","author":"Hodgson D.","year":"2012"},{"key":"e_1_2_7_14_1","unstructured":"[Hed13]\u00a0\u00a0HedengrenJ.:Simmulated annealing tutorial 2013. URL:http:\/\/apmonitor.com\/me575\/index.php\/Main\/SimulatedAnnealing.6."},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1177\/027836498400300405"},{"key":"e_1_2_7_16_1","doi-asserted-by":"crossref","unstructured":"[JYT10]\u00a0\u00a0JohnsonL. YannakakisG.N. TogeliusJ.:Cellular automata for real\u2010time generation of infinite cave levels. InProc. 2010 Workshop on Procedural Content Generation in Games(2010) pp.10:1\u201310:4. 2.","DOI":"10.1145\/1814256.1814266"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944846.1944854"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"e_1_2_7_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024217"},{"key":"e_1_2_7_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0926-5805(99)00005-9"},{"key":"e_1_2_7_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676196"},{"key":"e_1_2_7_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-013-0825-1"},{"key":"e_1_2_7_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409111"},{"key":"e_1_2_7_24_1","volume-title":"The geometry of environment: an introduction to spatial organization in design","author":"March L.","year":"1974"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882261.1866203"},{"key":"e_1_2_7_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141931"},{"key":"e_1_2_7_27_1","doi-asserted-by":"publisher","DOI":"10.1142\/5648"},{"key":"e_1_2_7_28_1","unstructured":"[Per02]\u00a0\u00a0PerryL.:Modular level and component design.Game Developer Magazine(2002). 1 2."},{"key":"e_1_2_7_29_1","doi-asserted-by":"crossref","unstructured":"[PM01]\u00a0\u00a0ParishY. I. H. M\u00fcllerP.:Procedural modeling of cities. InProc. SIGGRAPH(2001) pp.301\u2013308. 3.","DOI":"10.1145\/383259.383292"},{"key":"e_1_2_7_30_1","first-page":"191","volume-title":"Principles of computer\u2010aided design: computability of design","author":"Shaviv E.","year":"1987"},{"key":"e_1_2_7_31_1","volume-title":"Algorithms for VLSI Physcial Design Automation","author":"Sherwani N.A.","year":"1998"},{"key":"e_1_2_7_32_1","volume-title":"Procedural Content Generation in Games: A Textbook and an Overview of Current Research","author":"Shaker N.","year":"2014"},{"key":"e_1_2_7_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2011.2166267"},{"key":"e_1_2_7_34_1","volume-title":"Rules of Play: Game Design Fundamentals","author":"Salen K.","year":"2003"},{"key":"e_1_2_7_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2011.2148116"},{"key":"e_1_2_7_36_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03047.x"},{"key":"e_1_2_7_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882324"},{"key":"e_1_2_7_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2009.9"},{"key":"e_1_2_7_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185552"}],"container-title":["Computer Graphics Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1111%2Fcgf.12314","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/cgf.12314","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T05:47:53Z","timestamp":1746251273000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1111\/cgf.12314"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["10.1111\/cgf.12314"],"URL":"https:\/\/doi.org\/10.1111\/cgf.12314","archive":["Portico"],"relation":{},"ISSN":["0167-7055","1467-8659"],"issn-type":[{"value":"0167-7055","type":"print"},{"value":"1467-8659","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5]]},"assertion":[{"value":"2014-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}