Featured Blog | Creating a Spatial Query System

Introduction

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:
Visualizing sample points, test results, and final query results

Providing debug draw options to selectively view specific aspects of the query process

Capturing and inspecting the state of the query at different stages of execution

The article will dive deeper into considerations and best practices for each of these components, using code snippets to illustrate key concepts. The goal is an efficient, flexible system that allows designers to easily author queries as data to enable richer, more dynamic AI behaviors.

Generators

Generators are responsible for creating the initial set of sample points that will be evaluated by the spatial query system. The choice of generator can significantly impact the performance and quality of query results. Let’s take a look at two common generator types and how to extend the system with a new generator.

Grid Generator

The GridGenerator creates a uniform grid of sample points within a specified area. It’s a simple but effective way to cover a space evenly. Here’s the implementation:

 GridGenerator::generate( SpatialSamplingQuery::Context& context, Base::Array& samples) 
{
    Math::Vector3 center = mCenter;
     size = mSize;
     spacing = mSpacing;

     halfSize = (size - ) * spacing * f;
    Math::Vector3 start = center - Math::Vector3(halfSize, f, halfSize);

     (unsigned  i = ; i < size; ++i)
    {
         (unsigned  j = ; j < size; ++j)
        {
            Math::Vector3 currentPoint = start + Math::Vector3(i * spacing, f, j * spacing);
            (Navigation::getClosestPoint2D(context.getNavHandle(), currentPoint, .f, &currentPoint))
            {
                samples.push_back({ currentPoint });
            }
        }
    }
     ;
}

The GridGenerator takes parameters for the center point, size (number of points along each axis), and spacing between points. It calculates the starting corner of the grid and iterates along each axis, adding valid navigation mesh points to the samples array

Ring Generator

The RingGenerator creates concentric rings of sample points around a center location. This is useful for radial queries like finding cover points at specific distances from a target. Here’s the implementation:

RingGenerator::generate( SpatialSamplingQuery::Context& context, Base::Array& samples) 
{
     angleStep =  * M_PI / mPointsPerRing;
     radiusStep = (mOuterRadius - mInnerRadius) / Math::Max((mNumberOfRings - ), );

    Math::Vector3 center = mCenter;

     (  i = ; i < mNumberOfRings; ++i)
    {
         currentRadius = mInnerRadius + radiusStep * i;
         (  j = ; j < mPointsPerRing; ++j)
        {
             angle = angleStep * j;
             x = center.x + currentRadius * (angle);
             z = center.z + currentRadius * (angle);
            Math::;
            (Navigation::getClosestPoint2D(context.getNavHandle(), currentPoint, f, &currentPoint))
            {
                samples.push_back({ currentPoint });
            }
        }
    }
     ;
}

The RingGenerator takes parameters for the center point, inner radius, outer radius, number of rings, and points per ring. It calculates the angle and radius step sizes, then iterates over each ring and angle to generate points at the appropriate locations, adding valid navigation mesh points to the samples array.

Evaluators

Evaluators are the components responsible for assessing the suitability of each sample point generated by the generators. They assign scores to the points based on various criteria and can also filter out points that don’t meet certain requirements. Evaluators are the key to making spatial queries context-aware and adaptable to different situations.

Distance Evaluator

The DistanceEvaluator scores sample points based on their distance from a reference location, such as the querying entity or a target. It can be used to prefer closer points, farther points, or points within a specific distance range.

  DistanceEvaluator :  Evaluator
{
:
    DistanceEvaluator( Gameplay::CActor* pActor,  minDistance = f,  maxDistance = f)
        : mpActor(pActor), mMinDistance(minDistance), mMaxDistance(maxDistance) {}

      apply( SpatialEvaluationQuery::Context& context, Base::Array& evaluationDataArray)  override
    {
         (mpActor == nullptr)
            ;

         (  i = ; i < evaluationDataArray.(); ++i)
        {
            SpatialQueryEvaluationData&  = evaluationDataArray[i];
             distance = Math::Distance(.mLocation, mpActor->getPosition());
             isWithinMinDistance = mMinDistance < f || distance >= mMinDistance;
             isWithinMaxDistance = mMaxDistance < f || distance <= mMaxDistance;

             (isWithinMinDistance && isWithinMaxDistance)
            {
                 (mMinDistance >= f && mMaxDistance >= f)
                {
                    .mScore = ((distance - mMinDistance) / (mMaxDistance - mMinDistance));
                }
                  (mMinDistance >= f)
                {
                    .mScore = f - ((distance - mMinDistance) / (distance + Math::kEpsilonDiv));
                }
                  (mMaxDistance >= f)
                {
                    .mScore = distance / mMaxDistance;
                }
            }

             ((mMaxDistance > f && distance > mMaxDistance) || 
                (mMinDistance > f && distance < mMinDistance) ||
                (.mScore <= f))
            {
                .mScore = f;
                .mFilteredOut = true;
            }    
        }
        Base::std_sort(evaluationDataArray.(), evaluationDataArray.(), []( SpatialQueryEvaluationData& a,  SpatialQueryEvaluationData& b) {  (a.mScore > b.mScore); });
    }

:
     Gameplay::CActor* mpActor;
     mMinDistance;
     mMaxDistance;
};

Angle Evaluator

The AngleEvaluator checks whether each sample point is within the specified angle from the given direction. For example, It can be used to prefer points which are within 30 degrees of an actor’s forward direction.

 void (const  context,  evaluationDataArray) const
{
     btPerception = context.getBtPerception();
    if (!btPerception)
        ;

    evaluationDataArray.erase_if(
        [&](SpatialQueryEvaluationData& point)
        {    
             directionToPoint = (point.mLocation - btPerception->getMarkedActor()->getPosition());
             playerForward = (mDirection);
            float dotp = ((playerForward, directionToPoint), -f, f);
            float arcos = (dotp);
            float deg = (arcos);
            point.mScore = deg / mAngle;
            bool bWithinAngle = deg <= mAngle;
            point.mFilteredOut = !bWithinAngle;
             ;
             !bWithinAngle;
        });
}

These are just a few examples of evaluators that can be used to score and filter sample points based on different criteria. Other common evaluators might include:

Reachability Evaluator: Scores points based on whether they are reachable from the querying entity’s current location, using pathfinding or navigation mesh queries.
Visibility Evaluator: Scores points based on whether they are within line of sight from the specified location
Occupancy Evaluator: Filters out points that are already occupied by other entities or obstacles.
Cover Evaluator: Scores points based on their suitability as cover positions, considering factors like proximity to walls, height of cover, and exposure to enemy fire.

Evaluators can be combined and weighted to create complex scoring functions that take multiple criteria into account. For example, you might use a combination of distance, visibility, and cover evaluators to find the best position for an AI agent to take cover from an enemy while still being able to engage them effectively.

The key to designing effective evaluators is to identify the specific criteria that are important for your AI agents’ decision making and to create scoring functions that accurately reflect those priorities. By encapsulating these scoring functions in modular evaluator classes, you can easily mix and match them to create custom query behaviors tailored to different situations.

Query Execution

Query execution is the process of running a spatial query to generate and evaluate sample points based on the specified criteria. It involves setting up the query context, executing the query using the chosen generators and evaluators, and retrieving the final result set. Let’s dive into the details of the query execution process.

Query Context Setup

The first step in executing a spatial query is setting up the query context. The query context provides relevant information to the generators and evaluators, such as the querying entity, navigation handle, and other necessary data.

In the provided code, the SpatialSamplingQuery::Context and SpatialEvaluationQuery::Context classes represent the query contexts for sampling and evaluation queries, respectively.

class SpatialSamplingQuery::Context
{
public:
    (::* ,   ,  ::<::> )
        : mBtPerception(), mBtPosition(::<::>()), mNavHandle(), mpActor() {}
    // ...
};

 ::
{
public:
    Context(Gameplay::BtPerception* btPerception, unsigned int navHandle, const Game::RefTyped contextActor)
        : mBtPerception(btPerception), mBtPosition(Gameplay::BtValueCalculator()), mNavHandle(navHandle), mpActor(contextActor) {}
    // ...
};

class SpatialEvaluationQuery::Context
{
public:
    Context(Gameplay::BtPerception* btPerception, SpatialSamplingQuery::Handle samplingQueryHandle, unsigned int navHandle, const Game::RefTyped contextActor)
        : mBtPerception(btPerception), mSamplingQueryHandle(samplingQueryHandle), mNavHandle(navHandle), mpActor(contextActor) {}
    // ...
};

These context classes store relevant information such as the behavior tree perception, navigation handle, and context actor, which can be accessed by the generators and evaluators during the query execution.

Requesting and Executing Queries

Once the query context is set up, the next step is to request and execute the spatial query. The SpatialQueryManager class provides methods for requesting and executing both sampling and evaluation queries.

To execute a sampling query, you call the RequestSpatialSamplingImmediate method of the SpatialQueryManager, passing in the query context and the desired generators. The method returns a handle to the executed query.

  (const  context, const  generators)
{
    SpatialSamplingQuery* newQuery = mSpatialSamplingQueryAllocator.allocate();
    newQuery->init(context);
    newQuery->setGenerators(generators);
    newQuery->execute();
     mSpatialSamplingQueryAllocator.convertPtrToIndex(newQuery);
}

Similarly, to execute an evaluation query, you call the RequestSpatialEvaluationImmediate method, passing in the query context, the desired evaluators, and a debug flag. The method returns a handle to the executed query.

  (const  context, const  evaluators, bool debug)
{
    SpatialEvaluationQuery* newQuery = mSpatialEvaluationQueryAllocator.allocate();
    newQuery->init(context);
    newQuery->setEvaluators(evaluators);
    newQuery->execute(debug);
     mSpatialEvaluationQueryAllocator.convertPtrToIndex(newQuery);
}

Retrieving Query Results

After executing a query, you can retrieve the query results using the query handle returned by the RequestSpatialSamplingImmediate or RequestSpatialEvaluationImmediate methods.

To retrieve the results of a sampling query, you call the GetSamplingQuery method of the SpatialQueryManager with the query handle, and then access the samples using the GetSamples method of the returned SpatialSamplingQuery object.

 SpatialSamplingQuery* samplingQuery = ().GetSamplingQuery(samplingQueryHandle);
const  samples = samplingQuery->GetSamples();

Similarly, to retrieve the results of an evaluation query, you call the GetEvaluationQuery method of the SpatialQueryManager with the query handle, and then access the evaluated samples using the GetResults method of the returned SpatialEvaluationQuery object.

 SpatialEvaluationQuery* evaluationQuery = ().GetEvaluationQuery(evaluationQueryHandle);
const  evaluatedSamples = evaluationQuery->GetResults();

The SpatialQueryNavMeshSample struct represents a generated sample point, while the SpatialQueryEvaluationDatastruct represents an evaluated sample point with additional information such as the score and whether it was filtered out.

Releasing Query Resources

After retrieving the query results and using them as needed, it’s important to release the query resources to avoid memory leaks. The SpatialQueryManager provides methods for releasing sampling and evaluation queries.

 SpatialQueryManager::Get().ReleaseSamplingQuery(samplingQueryHandle);
SpatialQueryManager::Get().ReleaseEvaluationQuery(evaluationQueryHandle);

These methods deallocate the query objects and free up the associated resources.

Debugging and Visualization

The provided code includes a SpatialQueryDebugger class that allows for debugging and visualization of spatial queries. The debugger can be used to record the state of the evaluation query at each step and visualize the sample points, scores, and other relevant information.

To enable debugging, you pass true as the debug flag when requesting an evaluation query. The debugger will record the evaluation state for each sample point at each evaluator step.

 SpatialEvaluationQuery::Handle evaluationQueryHandle = SpatialQueryManager::Get().RequestSpatialEvaluationImmediate(context, evaluators, );

You can then use the SpatialQueryDebugger methods to visualize the query results, such as drawing the sample points, scores, and evaluator information.

 SpatialQueryDebugger::Get().draw();

The SpatialQueryDebugger class provides various visualization options, such as drawing only the selected sample point, showing the evaluator scores, and filtering the displayed information based on camera parameters.

By leveraging the debugging and visualization capabilities of the SpatialQueryDebugger, you can gain insights into the behavior of your spatial queries and optimize them for better performance and results.

That covers the key aspects of query execution in the provided code. By setting up the query context, requesting and executing queries, retrieving the results, and properly releasing the query resources, you can effectively utilize the spatial query system to generate and evaluate sample points based on your specified criteria.

Integration and Usage

Integrating the spatial query system into your game or AI system allows you to leverage its capabilities for intelligent decision-making and efficient spatial reasoning. This section provides an overview of how to integrate and use the spatial query system effectively.

Integration with Game Systems

To integrate the spatial query system, you need to instantiate and initialize the necessary components. The SpatialQueryManager class serves as the central hub for managing and executing spatial queries. You can create an instance of the SpatialQueryManager and use it to request and execute queries from various parts of your game logic, such as AI behavior trees, navigation systems, or game world management.

Defining Query Criteria

When using the spatial query system, you need to define the criteria for your queries based on your game-specific requirements. This involves selecting the appropriate generators and evaluators to achieve the desired query behavior. Consider the specific spatial reasoning tasks you need to perform, such as finding cover points, selecting targets, or navigating to specific locations.

Triggering Queries

Spatial queries can be triggered in different ways depending on your game’s requirements. You can initiate queries periodically, based on specific events, or when certain conditions are met. For example, you might trigger a query to find cover points when an AI agent is under attack or initiate a navigation query when a character needs to move to a new location.

Handling Query Results

Once a query is executed, you can retrieve the query results and use them to make decisions or update the game state. The query results provide evaluated sample points that meet the specified criteria. You can process these results further by filtering, sorting, or interpreting them based on your game logic.

Performance Considerations

Spatial queries can have an impact on game performance, especially when dealing with large numbers of sample points or complex evaluation criteria. To optimize the performance of spatial queries, consider techniques such as caching query results, limiting the number of active queries, or adjusting the query parameters dynamically based on the current game state.

Debugging and Testing

When working with spatial queries, it’s important to have proper debugging and testing mechanisms in place. The SpatialQueryDebugger class provides functionality for visualizing query results and diagnosing issues. You can use the debugger to inspect the generated sample points, evaluator scores, and other relevant information.

By following these guidelines and leveraging the provided spatial query system, you can effectively integrate spatial reasoning capabilities into your game or AI system. Remember to design your queries carefully, consider performance implications, and test thoroughly to ensure the desired behavior is achieved.

Summary

In summary, spatial query systems are a powerful tool for creating intelligent, dynamic AI that can adapt to complex, ever-changing game environments. By breaking down the query process into modular, reusable components like generators and evaluators, you can build queries that are both flexible and efficient. Careful consideration of sample point distribution, evaluator design, and performance optimization allows you to create AI behaviors that are not only effective, but also scalable to the demands of modern gaming. Whether you’re looking to create more realistic NPC behaviors, enable dynamic navigation and pathfinding, or build immersive, reactive worlds, spatial queries are an indispensable addition to any game AI developer’s toolkit. So dive in, experiment, and start pushing the boundaries of what’s possible in game AI!

About the Author(s)

Jitesh Mulchandani is a Senior Gameplay Engineer at Super Evil Megacorp with over ten years of experience. Previously, he worked at Sony’s Pixelopus studio, contributing to games like Entwined and Concrete Genie for the PS3, PS4, and PS5. Jitesh’s experience spans various aspects of game development, including UI, character controls, combat, camera, and AI, demonstrating his versatility in gameplay engineering. He is dedicated to crafting engaging player experiences and advancing game mechanics, making him an invaluable contributor to the game development industry.

https://linkedin.com/in/jitesh-mulchandani-5b227437
https://twitter.com/jiteshvm