Image via olia danilevich.
Introduction
Hello, I am Jitesh Mulchandani, a senior gameplay engineer at Super Evil Megacorp. Spatial query systems have become an essential tool for enabling intelligent AI behaviors in complex game environments. They allow AI characters to dynamically analyze their surroundings and find optimal locations for tasks like taking cover, choosing targets, flanking the player, surrounding enemies, or adapting to changes in the environment during combat.
Popularized by games like Crysis with its Tactical Point System and now freely available in engines like CryEngine and Unreal Engine 4, spatial queries bring game AI to life by letting them evaluate the game world in real-time instead of relying on predefined points. This leads to more adaptable, situationally-aware AI that can function in dynamic, destructible environments.
The Spatial Query System, a powerful and flexible tool for creating intelligent, adaptive AI, is a core component of the EVIL engine - the proprietary game development platform used by Super Evil Megacorp. Our engine is designed to deliver high-performance, real-time multiplayer experiences across a wide spectrum of devices, from high-end consoles to mobile devices with more limited resources, the EVIL engine is built on a modular architecture that allows for seamless integration and scalability of new systems. This modularity enables the Spatial Query System to be easily incorporated into the engine's existing AI frameworks, empowering developers to create complex, dynamic AI behaviors that can navigate and interact with intricate game worlds. With its ability to optimize performance across diverse hardware configurations, and its seamless integration with other engine subsystems, the Spatial Query System exemplifies the EVIL engine's commitment to providing cutting-edge tools for crafting immersive, engaging gaming experiences.
In this article, we'll walk through the key concepts and components required to build your own spatial query system. We'll cover:
Generating potential query points in the world
Evaluating points based on the current game state
Filtering points to find ideal candidates
Optimizing queries for performance
By the end, you'll have a solid foundation for developing a spatial query system that enables richer, more realistic AI behaviors. Let's get started!
Overview
A spatial query system allows game AI to efficiently analyze the game environment and select optimal locations for specified behaviors. The key components of a spatial query system work together in a typical flow: sample points are generated, tests are applied to each point to determine its suitability, scores are calculated based on the test results, and the final query result is selected based on the scores.
Sample point generation: Methods to produce a set of candidate locations to evaluate, such as points on a grid, in a ring, or at marker locations. The goal is to generate points in a way that minimizes bias and ensures good coverage of the relevant search space. Common approaches include:
Generating sample points on a 2D grid along the navigation mesh
Generating rings of points around key locations
Using pre-placed marker locations as sample points
Tests and scoring: Criteria to measure the suitability of each sample point for the desired behavior. Simple tests can be combined and weighted to create more complex query behaviors. Common test types include:
Visibility tests to/from key entities
Distance ranges to/from key entities
Path finding tests to check reachability
Dot product tests to check relative angles/facing
Angle range tests to check orientation Each test can be used to either reject invalid points (filtering) or produce a normalized score. Scores from multiple weighted tests are typically combined to rank points.
Query execution: Methods to efficiently run the sample generation and testing/scoring logic, usually in an asynchronous manner to avoid hitches. Spatial queries can be integrated with behavior trees or other decision-making systems to enable more dynamic AI behaviors. Key optimizations:
Order cheap tests before expensive ones
Avoid unnecessary tests when query success is impossible
Normalize test results to a consistent range like [0,1]
Time-slice query execution over multiple frames
Perform early rejection of invalid points
Results selection: Choosing the final query result from the remaining valid sample points based on score. The choice of selection strategy involves tradeoffs between determinism and variability. Options include:
Selecting the single highest scoring point
Selecting the top N points by score
Randomly selecting from top N percent of points by score
Debugging and visualization: Tools and techniques to help understand and debug the behavior of spatial queries, such as:
