Efficient Object Search in Game Maps

Jinchun Du, Bojie Shen, Shizhe Zhao, Muhammad Aamir Cheema, Adel Nadjaran ToosiIJCAI 2023 · DOI

TL;DR

This paper introduces "Grid Tree," a novel indexing structure designed for efficient object search in dynamic video game environments. It significantly improves update times for moving objects compared to existing methods, while maintaining competitive query performance, making it ideal for real-time game applications.

What Problem Does This Paper Address?

Video games are characterized by dynamic worlds where objects like characters, items, and vehicles constantly change their positions and properties. Efficiently searching for nearby objects that also match specific textual descriptions (e.g., "find the nearest healing unit") is crucial for game AI, player interaction, and various game engine functionalities. Existing spatial indexing techniques, while effective for static data, struggle with the high frequency of updates in game environments, leading to performance bottlenecks. The challenge lies in developing an index that can handle rapid object movements and updates while still providing fast query responses for complex spatio-textual queries.

Methods

The core contribution of this paper is the Grid Tree, a lightweight and efficient indexing structure. Unlike traditional spatial indexes that dynamically restructure themselves, the Grid Tree uses a fixed, hierarchical grid.

  • Grid Tree Structure: The entire game map is recursively divided into four equal quadrants until leaf nodes reach a predefined minimum size. These leaf nodes form a uniform grid. Each node in the tree stores a keyword list (tracking keywords and their frequencies within its subtree), while only leaf nodes store object lists.
  • Efficient Updates:
    • Object Movement: When an object moves, its entry is removed from the old leaf node's object list and added to the new one. The keyword lists of affected nodes (from the leaf up to the common ancestor of the old and new leaf nodes) are updated by adjusting keyword frequencies. Crucially, if an object moves within the same leaf node, no structural update is needed, leading to O(1) update time in this common scenario.
  • Insertions/Deletions: These involve updating the object list of the relevant leaf node and propagating keyword list updates up the tree.
  • Textual Changes: Similar to movement, these updates involve modifying keyword lists in affected nodes.
  • Query Processing: The paper proposes a boolean kNN query algorithm that uses a min-heap to explore the Grid Tree. It prioritizes nodes and objects based on a lower bound distance to the query location. The algorithm prunes branches that cannot yield results closer than the current k-th nearest neighbor. For shortest path distances, it leverages the state-of-the-art Euclidean Hub Labeling (EHL) algorithm.

Datasets

The authors evaluated their approach on widely used game map benchmarks from four popular games: Dragon Age II (DA), Dragon Age Origins (DAO), Baldur's Gate II (BG), and StarCraft (SC). These benchmarks consist of 373 maps represented as grid maps. Objects, their keywords, and queries were generated procedurally:

  • Object Generation: Initial locations were random. Object density was varied (0.1% to 10%), and mobility (percentage of moving objects) was varied (10% to 100%).
  • Keyword Generation: Keywords were derived from item descriptions obtained using ChatGPT, then processed with NLP techniques.
  • Query Generation: Queries included varying numbers of keywords (0 to 3) and k values (1 to 10).

Key Insights and Ideas

  • Fixed Grid Advantage: The key innovation is the use of a fixed grid structure. This avoids the costly rebalancing operations common in dynamic spatial indexes like R-trees when objects move, leading to significantly faster updates.
  • Hierarchical Keyword Aggregation: Aggregating keyword frequencies at each node allows for efficient pruning during keyword-based queries. A node is only explored if its aggregated keyword list contains all query keywords.
  • Leveraging Existing Pathfinding: The Grid Tree's query processing benefits from state-of-the-art shortest path algorithms like EHL, ensuring accurate distance calculations in complex game environments.
  • Trade-off between Leaf Size and Performance: The experiments reveal a trade-off: larger leaf nodes (smaller tree height) improve update performance but can degrade query performance at very high object densities. The optimal leaf size depends on the specific game environment.

Key Results

  • Update Performance: Grid Tree achieved up to 2 orders of magnitude faster update times for moving objects compared to IER-Polyanya and IER-EHL. Its update cost was comparable to Interval Heuristic (IH), being faster for object movements.
  • Query Performance: Grid Tree's query performance was similar to or better than IER-tree and up to 2 orders of magnitude faster than IH. It was several times faster than IER-Polyanya.
  • Scalability: The Grid Tree scales well with object density and mobility, with larger leaf node sizes generally leading to better update performance.

Limitations and Future Work

  • Object Density Impact: While Grid Tree generally excels, query performance can degrade at very high object densities when leaf nodes become too crowded. The paper suggests that choosing an appropriate leaf node size (e.g., GT(64)) can mitigate this.
  • Insertions/Deletions vs. Movements: While Grid Tree is highly efficient for object movements (especially within the same leaf node), its update cost for insertions/deletions is higher than IH, though still significantly better than IER-EHL in terms of query performance.
  • Future Work: The paper mentions that the Grid Tree can be extended to handle other variants of spatial keyword queries, such as "at least n keywords" queries and top-k spatial keyword queries with scoring functions. The authors also suggest exploring different lower bound distance calculations for query optimization.

Summary updated

BibTeX
@inproceedings{du2023efficient,
  author = {Jinchun Du and Bojie Shen and Shizhe Zhao and Muhammad Aamir Cheema and Adel Nadjaran Toosi},
  title = {{Efficient Object Search in Game Maps}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/618},
}
Figure