Generating layout for complex cave-like levels with schematic maps and Cellular Automata

Main Article Content

Izabella Antoniuk

Keywords : Cellular Automata, computer games, Diamond-Square, procedural cave generation, procedural level generation, schematic maps

In this paper an algorithm for creating cave-like, user-guided layout is presented. In applications such as computer games, underground structures offer unique challenges and interesting space for player actions. Preparation of such areas can be time consuming and tiresome, especially during the design process, when many ideas are often scrapped. Presented approach aims at improving this process. Schematic input is used so the user can quickly define the general layout. Cave system is divided into levels and tiles - easily-parallelizable modules for the following method stages. Cellular automata are used to extend initial system sketch with interesting shapes while the diamond-square algorithm spreads the final terrain heights. Each stage uses the results of the previously performed operations as input, providing space for alterations. Input maps can be reused to obtain different variations of the same system. The final structure is represented as a 3D point cloud. Chosen representation supports multilevel systems and can be used either as a base for further algorithms, or as a final mesh. The presented approach can be easily incorporated into game design process, while visualizing initial layouts and speeding up preparation of unique, interesting and challenging game spaces for the players to traverse.

Article Details

How to Cite
Antoniuk, I. (2023). Generating layout for complex cave-like levels with schematic maps and Cellular Automata. Machine Graphics and Vision, 32(2), 45–65.

D. B. Adams. Feature-based Interactive Terrain Sketching. Master's thesis, Brigham Young University, 2009.

I. Antoniuk, P. Hoser, and D. Strzęciwilk. L-system application to procedural generation of room shapes for 3D dungeon creation in computer games. In: Proc. Int. Multi-Conf. Advanced Computer Systems, pp. 375-386. Springer, 2018. (Crossref)

I. Antoniuk and P. Rokita. Feature-based procedural generation of adjustable game content. Challenges of Modern Technology, 5(4):21-26, 2014.

I. Antoniuk and P. Rokita. Procedural generation of adjustable terrain for application in computer games using 2D maps. In: Pattern Recognition and Machine Intelligence: Proc. 6th Int. Conf., PReMI 2015, vol. 9124 of Lecture Notes in Computer Science, pp. 75-84. Springer, Warsaw, Poland, Jun 30-Jul 2015. Article No. 10. (Crossref)

I. Antoniuk and P. Rokita. Generation of complex underground systems for application in computer games with schematic maps and L-systems. In: Proc. Int. Conf. Computer Vision and Graphics, pp. 3-16. Springer, 2016. (Crossref)

I. Antoniuk and P. Rokita. Procedural generation of underground systems with terrain features using schematic maps and L-systems. Challenges of Modern Technology, 7(3):8-15, 2016. (Crossref)

I. Antoniuk and P. Rokita. Procedural generation of multiclevel dungeons for application in computer games using schematic maps and L-system. In: Intelligent Methods and Big Data in Industrial Applications, pp. 261-275. Springer, 2019. (Crossref)

D. Ashlock, C. Lee, and C. McGuinness. Search-based procedural generation of maze-like levels. IEEE Transactions on Computational Intelligence and AI in Games, 3(3):260-273, 2011. (Crossref)

Blender Reference Manual, version 3.5., Accessed: 22.04.2023.

M. Boggus and R. Crawfis. Explicit generation of 3D models of solution caves for virtual environments. In: Proc. 2009 Int. Conf. Computer Graphics & Virtual Reality (CGVR), pp. 85-90. Las Vegas, Nevada, USA, 2009.

M. Boggus and R. Crawfis. Procedural creation of 3D solution cave models. In: Proc. 20th IASTED Int. Conf. Modelling and Simulation, pp. 180-186. 6-8 Jul, Banff, Alberta, Canada 2009.

M. Boggus and R. Crawfis. Prismfields: A framework for interactive modeling of three dimensional caves. In: Proc. Int. Symp. Visual Computing, pp. 213-221. Springer, 2010. (Crossref)

J. Calderon. Dungeon Master., Accessed: 18.12.2023.

J. Cui, Y.-W. Chow, and M. Zhang. Procedural generation of 3D cave models with stalactites and stalagmites. IJCSNS, 11(8):94, 2011.

D. M. De Carli, C. T. Pozzer, F. Bevilacqua, and V. Schetinger. Procedural generation of 3D canyons. In: Proc. 2014 27th SIBGRAPI Conf. Graphics, Patterns and Images, pp. 103-110. IEEE, Rio de Janeiro, Brazil, 26-30 Aug 2014. (Crossref)

Dragon Age game series webpage., Accessed: 18.12.2023.

Elden Ring game webpage., Accessed: 18.12.2023.

K. Franke and H. Müller. Procedural generation of 3D karst caves with speleothems. Computers & Graphics, 102:533-545, 2022. (Crossref)

E. Galin, A. Peytavie, N. Maréchal, and E. Guérin. Procedural generation of roads. Computer Graphics Forum, 29(2):429-438, 2010. (Crossref)

M. N. Gamito and F. K. Musgrave. Procedural landscapes with overhangs. In: Proc. 10th Portuguese Computer Graphics Meeting, vol. 2. Lisbon, Porugal, 2001.

S. Greuter and A. Nash. Game asset repetition. In: Proc. 2014 Conf. Interactive Entertainment, pp. 1-5, 2014. (Crossref)

S. Greuter, J. Parker, N. Stewart, and G. Leach. Real-time procedural generation of `pseudo infinite' cities. In: GRAPHITE '03: Proc. 1st Int. Conf. Computer graphics and interactive techniques in Australasia and South East Asia, pp. 87-ff. ACM, Melbourne, Australia, 11-14 Feb 2003. (Crossref)

Legend of Grimrock game webpage., Accessed: 18.12.2023.

K. Hartsook, A. Zook, S. Das, and M. O. Riedl. Toward supporting stories with procedurally generated game worlds. In: Proc. 2011 IEEE Conf. Computational Intelligence and Games (CIG'11), pp. 297-304. IEEE, 2011. (Crossref)

M. Hendrikx, S. Meijer, J. Van Der Velden, and A. Iosup. Procedural content generation for games: A survey. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), 9(1):1-22, 2013. (Crossref)

R. Huijser, J. Dobbe, W. F. Bronsvoort, and R. Bidarra. Procedural natural systems for game level design. In: Proc. 2010 Brazilian Symp. Games and Digital Entertainment, pp. 189-198. IEEE, Florianopolis, Brazil, 08-10 Nov 2010. (Crossref)

L. Johnson, G. N. Yannakakis, and J. Togelius. Cellular automata for real-time generation of infinite cave levels. In: PCGames '10: Proc. 2010 Workshop on Procedural Content Generation in Games, pp. 1-4. Monterey, California, 18 Jun 2010. Article No. 10. (Crossref)

K. R. Kamal and M. Kaykobad. Generation of mountain ranges by modifying a controlled terrain generation approach. In: Proc. 2008 11th Int. Conf. Computer and Information Technology, pp. 527-532. IEEE, Khulna, Bangladesh, 24-27 Dec 2008. (Crossref)

A. Liapis. Multi-segment evolution of dungeon game levels. In: Proc. Genetic and Evolutionary Computation Conference, pp. 203-210, 2017. (Crossref)

R. Van der Linden, R. Lopes, and R. Bidarra. Designing procedurally generated levels. In: Proc. Ninth Artificial Intelligence and Interactive Digital Entertainment Conference, 2013. (Crossref)

B. Mark, T. Berechet, T. Mahlmann, and J. Togelius. Procedural generation of 3D caves for games on the GPU, 2015., Paper presented at Foundations of Digital Games.

E. A. Matthews and B. A. Malloy. Procedural generation of story-driven maps. In: Proc. 2011 16th Int. Conf. Computer Games (CGAMES), pp. 107-112. IEEE, 2011. (Crossref)

A. N. Palmer. Origin and morphology of limestone caves. Geological Society of America Bulletin, 103(1):1-21, 1991.<0001:OAMOLC>2.3.CO;2. (Crossref)

A. Peytavie, E. Galin, J. Grosjean, and S. Mérillou. Arches: A framework for modeling complex terrains. Computer Graphics Forum, 28(2):457-467, 2009. (Crossref)

Documentation for Point Processing Toolkit (pptk) Python library., Accessed: 22.04.2023.

P. Prusinkiewicz and A. Lindenmayer. The algorithmic beauty of plants. Springer Science & Business Media, 2012. (Crossref)

W. L. Raffe, F. Zambetta, and X. Li. Evolving patch-based terrains for use in video games. In: Proc. 13th Annual Conf. Genetic and Evolutionary Computation, pp. 363-370, 2011. (Crossref)

T. Roden and I. Parberry. From artistry to automation: A structured methodology for procedural content creation. In: Proc. Int. Conf. Entertainment Computing, pp. 151-156. Springer, 2004. (Crossref)

A. Santamaría-Ibirika, X. Cantero, S. Huerta, I. Santos, and P. G. Bringas. Procedural playable cave systems based on Voronoi diagram and Delaunay triangulation. In: Proc. 2014 Int. Conf. Cyberworlds, pp. 15-22. IEEE, 2014. (Crossref)

R. C. Silva, N. Fachada, D. De Andrade, and N. Códices. Procedural generation of 3D maps with snappable meshes. IEEE Access, 10:43093-43111, 2022. (Crossref)

The Elder Scrolls V: Skyrim, game webpage., Accessed: 18.12.2023.

R. Smelik, K. Galka, K. J. De Kraker, F. Kuijper, and R. Bidarra. Semantic constraints for procedural generation of virtual worlds. In: PCGames '11: Proc. 2nd Int. Workshop on Procedural Content Generation in Games, pp. 1-4, 2011. Article No. 9. (Crossref)

R. Smelik, T. Tutenel, K. J. De Kraker, and R. Bidarra. Integrating procedural generation and manual editing of virtual worlds. In: Proc. 2010 Workshop on Procedural Content Generation in Games, pp. 1-8, 2010. (Crossref)

R. M. Smelik, T. Tutenel, R. Bidarra, and B. Benes. A survey on procedural modelling for virtual worlds. Computer Graphics Forum, 33(6):31-50, 2014. (Crossref)

R. M. Smelik, T. Tutenel, K. J. De Kraker, and R. Bidarra. Declarative terrain modeling for military training games. International journal of computer games technology, 2010, 2010. (Crossref)

R. M. Smelik, T. Tutenel, K. J. de Kraker, and R. Bidarra. A declarative approach to procedural modeling of virtual worlds. Computers & Graphics, 35(2):352-363, 2011. (Crossref)

R. M. Smelik, T. Tutenel, K. J. de Kraker, R. Bidarra, et al. A proposal for a procedural terrain modelling framework. In: EGVE (Posters), 2008.

Speedtree documentation., Accessed: 22.04.2023.

Home of Unity Technologies project., Accessed: 22.04.2023.

Unreal Engine webpage., Accessed: 22.04.2023.

Unreal Engine 5.2 Roadmap., Accessed: 22.04.2023.

V. Valtchanov and J. A. Brown. Evolving dungeon crawler levels with relative placement. In: C3S2E '12: Proc. Fifth International C* Conf. Computer Science and Software Engineering, pp. 27-35. Montreal, Quebec, Canada, 27-29 Jun 2012. (Crossref)

B. M. F. Viana and S. R. dos Santos. Procedural dungeon generation: A survey. Journal on Interactive Systems, 12(1):83-101, 2021. (Crossref)

The Witcher game series webpage., Accessed: 18.12.2023.

H. Yin and C. Zheng. A parametrically controlled terrain generation method. In: Proc. 2012 7th Int. Conf. Computer Science & Education (ICCSE), pp. 775-778. IEEE, 2012. (Crossref)

Y. Zhang, G. Zhang, and X. Huang. A survey of procedural content generation for games. In: Proc. 2022 Int. Conf. Culture-Oriented Science and Technology (CoST), pp. 186-190. IEEE, 2022. (Crossref)



Download data is not yet available.
Recommend Articles
Most read articles by the same author(s)