Análise de desempenho de heurísticas sintetizadas por fórmulas e memória para busca de caminhos em videogames
Resumo
Neste trabalho, apresenta-se uma análise comparativa experimental de estratégias de síntese de heurísticas para o Algoritmo A* em mapas de jogos digitais: a heurística de Manhattan, heurísticas baseadas em memória com pivôs e heurísticas baseadas em fórmulas geradas por algoritmo genético. Os experimentos foram conduzidos em 17 mapas do conjunto Dragon Age Origins, avaliando o desempenho estático e o comportamento dinâmico sob cinco padrões distintos de degradação estrutural progressiva. Os resultados reforçam o fato de que heurísticas de memória são superiores em cenários estáticos, mas apresentam degradação mais acentuada sob modificações dinâmicas, enquanto heurísticas de fórmulas mantêm desempenho mais estável nesses cenários, à custa de subotimalidade de caminho.Referências
Bulitko, V. (2020). Evolving initial heuristic functions for agent-centered heuristic search. In 2020 IEEE Conference on Games (CoG), pages 534–541.
Bulitko, V., Hernandez, S. P., and Lelis, L. H. (2021). Fast synthesis of algebraic heuristic functions for video-game pathfinding. In 2021 IEEE Conference on Games (CoG), pages 01–05.
Bulitko, V. and Lawrence, R. (2023). Game-map pathfinding with per-problem selection of synthesized heuristics. In 2023 IEEE Conference on Games (CoG), pages 1–4.
Bulitko, V., Wang, S., Stevens, J., and Lelis, L. H. S. (2022). Portability and explainability of synthesized formula-based heuristics. In Proceedings of the 15th International Symposium on Combinatorial Search (SoCS), volume 15, pages 29–37.
Gonzalez, T. F. (1985). Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306.
Hart, P. E., Nilsson, N. J., and Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100–107.
Rafiq, A., Abdul Kadir, T. A., and Ihsan, S. N. (2020). Pathfinding algorithms in game development. IOP Conference Series: Materials Science and Engineering, 769(1):012021.
Russell, S. J. and Norvig, P. (2020). Artificial Intelligence: A Modern Approach. Pearson, London, UK, 4th edition.
Saunders, P., Bulitko, V., Ondrčková, S., and Barták, R. (2024). Formula- and memory-based heuristics in video-game pathfinding. In 2024 IEEE Conference on Games (CoG), pages 1–4.
Sturtevant, N. R. (2012). Benchmarks for grid-based pathfinding. IEEE Transactions on Computational Intelligence and AI in Games, 4(2):144–148.
Sturtevant, N. R., Felner, A., Barrer, M., Schaeffer, J., and Burch, N. (2009). Memory-based heuristics for explicit state spaces. In Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI’09, page 609–614, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
Bulitko, V., Hernandez, S. P., and Lelis, L. H. (2021). Fast synthesis of algebraic heuristic functions for video-game pathfinding. In 2021 IEEE Conference on Games (CoG), pages 01–05.
Bulitko, V. and Lawrence, R. (2023). Game-map pathfinding with per-problem selection of synthesized heuristics. In 2023 IEEE Conference on Games (CoG), pages 1–4.
Bulitko, V., Wang, S., Stevens, J., and Lelis, L. H. S. (2022). Portability and explainability of synthesized formula-based heuristics. In Proceedings of the 15th International Symposium on Combinatorial Search (SoCS), volume 15, pages 29–37.
Gonzalez, T. F. (1985). Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306.
Hart, P. E., Nilsson, N. J., and Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100–107.
Rafiq, A., Abdul Kadir, T. A., and Ihsan, S. N. (2020). Pathfinding algorithms in game development. IOP Conference Series: Materials Science and Engineering, 769(1):012021.
Russell, S. J. and Norvig, P. (2020). Artificial Intelligence: A Modern Approach. Pearson, London, UK, 4th edition.
Saunders, P., Bulitko, V., Ondrčková, S., and Barták, R. (2024). Formula- and memory-based heuristics in video-game pathfinding. In 2024 IEEE Conference on Games (CoG), pages 1–4.
Sturtevant, N. R. (2012). Benchmarks for grid-based pathfinding. IEEE Transactions on Computational Intelligence and AI in Games, 4(2):144–148.
Sturtevant, N. R., Felner, A., Barrer, M., Schaeffer, J., and Burch, N. (2009). Memory-based heuristics for explicit state spaces. In Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI’09, page 609–614, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
Publicado
19/07/2026
Como Citar
PEREIRA, Alexandre; FREITAS, Rosiane de.
Análise de desempenho de heurísticas sintetizadas por fórmulas e memória para busca de caminhos em videogames. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 25. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 34-45.
ISSN 2595-6167.
DOI: https://doi.org/10.5753/wperformance.2026.23321.
