Terrain Analysis in Real-Time Strategy Games: An Integrated Approach to Choke Point Detection and Region Decomposition

Authors

  • Luke Perkins Rensselaer Polytechnic Institute

DOI:

https://doi.org/10.1609/aiide.v6i1.12405

Keywords:

Terrain Analysis, Spatial Reasoning, Real-time Strategy, RTS, Real-time Strategy Game, Choke Point Detection, Choke Point, Chokepoint, Region Decomposition, Starcraft: Broodwar, Starcraft, Brood War Terrain Analyzer, BWTA

Abstract

Autonomous agents in real-time strategy (RTS) games lack an integrated framework for reasoning about choke points and regions of open space in their environment. This paper presents an algorithm which partitions the environment into a set of polygonal regions and computes optimal choke points between adjacent regions. This representation can be used as a component for AI agents to reason about terrain, plan multiple routes of attack, and make other tactical decisions. The algorithm is tested on a set of popular maps commonly used in international Starcraft competitions and evaluated against answers made by human participants. The algorithm identified 97% of the choke points that the participants found and also identified a number of bottlenecks that human participants did not recognize as choke points.

Downloads

Published

2010-10-10

How to Cite

Perkins, L. (2010). Terrain Analysis in Real-Time Strategy Games: An Integrated Approach to Choke Point Detection and Region Decomposition. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 6(1), 168-173. https://doi.org/10.1609/aiide.v6i1.12405