Automated Decomposition of Game Maps

Authors

  • Kári Halldórsson Reykjavik University
  • Yngvi Björnsson Reykjavik University

DOI:

https://doi.org/10.1609/aiide.v11i1.12796

Keywords:

map decomposition, heuristic search, video games, pathfinding

Abstract

Video game worlds are getting increasingly large and complex. This poses challenges to the game AI for both pathfinding and strategic decisions, not least in real-time strategy games. One way to alleviate the problem is to manually pre-label the game maps with information about regions and critical choke points, which the game AI can then take advantage of. We present a method for automatically decomposing game maps into non-uniform sized regions. The method uses a flooding algorithm at its core and has the benefit, in addition to its effectiveness, to be relatively intuitive both conceptually and in implementing. Empirical evaluation on game maps shows that the automatic decomposition results in intuitive regions of a comparable standard to human-made labeling. Furthermore, we show that our automatic decomposition, when used by a pathfinding algorithm capable of taking advantage of pre-labeled regions, significantly improves search effectiveness.

Downloads

Published

2021-06-24

How to Cite

Halldórsson, K., & Björnsson, Y. (2021). Automated Decomposition of Game Maps. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 11(1), 122-127. https://doi.org/10.1609/aiide.v11i1.12796