Analyzing Procedural Terrain Generation in Games from a Constraint Programming Perspective
Resumo
A geração procedural de terrenos bidimensionais se apresenta como uma estratégia fundamental no desenvolvimento de muitos jogos digitais. Em 2016, o algortimo Wave Function Collapse (WFC) se destacou como uma técnica eficaz para a geração de terrenos de pequeno porte. Com o objetivo de abordar instâncias maiores, uma variante denominada Nested WFC (N-WFC) foi proposta em 2023. Este artigo apresenta uma análise do WFC e do N-WFC pela perspectiva do paradigma de Programação por Restrições, no qual as relações que definem a validade dos terrenos são modeladas por meio de restrições. Uma análise experimental, conduzida na Unreal Engine e em C++, com ambos algoritmos, indica que para conjuntos específicos de tiles a consistência de arco direcionada é suficiente para gerar o terreno sem efetuar backtracking.
Referências
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.
