Analyzing Procedural Terrain Generation in Games from a Constraint Programming Perspective
Abstract
Procedural generation of two-dimensional terrains serves as a fundamental strategy in the development of many digital games. In 2016, the algorithm Wave Function Collapse (WFC) stood out as an effective technique for generating small-scale terrains. Aiming to address larger instances, a variant called Nested WFC (N-WFC) was proposed in 2023. This paper presents an analysis of both WFC and N-WFC from the perspective of the Constraint Programming paradigm, in which the relations that define the terrain validity are modeled by constraints. An experimental analysis, conducted in Unreal Engine and in C++ with both algorithms indicates that for specific tilesets the directed arc consistency is sufficient to generate the terrain without performing backtracking.
References
Freuder, E. C. (1982). A sufficient condition for backtrack-free search. J. ACM, 29(1):24–32.
Gumin, M. (2016). Wave function collapse. Disponível em [link]. Acessado em 26/05/2025.
Kubi, G. (2021). Road tiles. Disponível em [link]. Acessado em 18/06/2025.
Mackworth, A. K. (1977). Consistency in networks of relations. Artif. Intell., 8(1):99–118.
Market.US (2024). Global generative ai in gaming market. Disponível em: [link]. Acessado em 26/05/2025.
Mehta, N. (2025). The role of ai in game development and player experience. In Proceedings of the International Conference on Innovative Computing Communication (ICICC 2024).
Merrell, P. C. (2021). Comparing model synthesis and wave function collapse. Disponível em [link]. Acessado em 18/06/2025.
Nie, Y., Zheng, S., Zhuang, Z., and Song, X. (2023). Extend wave function collapse algorithm to large-scale content generation. arXiv preprint arXiv:2308.07307.
Rose, T. J. and Bakaoukas, A. G. (2016). Algorithms and approaches for procedural terrain generation - a brief review of current techniques. In 8th International Conference on Games and Virtual Worlds for Serious Applications (VS-GAMES), pages 1–2.
Rossi, F., van Beek, P., and Walsh, T., editors (2006). Handbook of Constraint Programming. Elsevier.
Russell, S. and Norvig, P. (2010). Artificial Intelligence: A Modern Approach. Prentice Hall.
Shaker, N., Togelius, J., and Nelson, M. J. (2016). Procedural Content Generation in Games: A Textbook and an Overview of Current Research. Springer.
Togelius, J., Yannakakis, G. N., Stanley, K. O., and Browne, C. (2011). Search-based procedural content generation. IEEE Transactions on Computational Intelligence and AI in Games, 3(3):172–186.
