# Querying game objects in real-time

I'm thinking about working on a game where I need to find all the objects matching certain properties.

For instances I might need to look up all the objects...

• Producing gold.
• Whose level is 5 or higher.
• Within 10 meter from a point.
• Currently fighting.
• That have anything to do with metal (e.g. producing, consuming, made of, wearing, standing on etc).

And so on and so forth. I would also like to be able to add new objects with new properties without having to change everything else.

Ideally I would need to run multiple queries per frame (hundreds or thousands per second). I'll probably rely on some properties way more than others, but this kind of usage pattern is likely to change over time.

Is there any data structure, design pattern, method or idea to help me implement an efficient real-time query system?

I've been thinking about assigning to each object a dynamic set of tags with properties, then recursively partition the space storing in each partition a mapping from those tags to the objects. It might work, but I'd like to hear about existing solutions before wasting efforts.

• Ever thought of using something like SQLite? – Vaillancourt Dec 13 '19 at 2:01
• Updating the database's set of tags, for every object, on every frame, sounds like a significant trade-off for faster queries; I wouldn't hastily rush to using a database. – Mr. Smith Dec 14 '19 at 11:09

It all depends on the query types, but broadly speaking...

If world is very large, as in an MMO, use a database, whether SQL or noSQL style is up to you, but it is a lot simpler to read (with your own eyes) the output of noSQL DBs which serve JSON output natively (GraphQL, MongoDB). Database tech is designed by specialists to cope admirably with large quantities of data, i.e. in the hundreds of thousands to millions of entries per table.

Even though the database may get millions of results very quickly once it receives that query, latency to send query and retrieve results can impact performance due to interprocess communication overhead. So you'd ideally queries out as soon as possible, at end of last frame.

A database's fixed interface can make it easier for secondary systems to operate against, e.g. level editors, without being broken by breaking changes to your game's core. On a secure remote server, it can also keep things safe from player's prying eyes / fingers.

Persistence these days can be achieved with something as simple as LocalStorage in Unity or HTML5, so this is not a reason in itself to use a DB.

Ordinarily in games, we'd split entities up into some kind of spatial bucketing system. For example, if we have a 2D grid, then we'd sort entities each frame into grid cell buckets, and then when checking entities against each other, we'd only compare against entities in the same cell or one of its eight neighbours. Dimensions of each cell (typically the same across 2 or 3 dimensions) depend on the maximum distance across wish you which to compare entities in your queries.

To create the grid (I assume C# as you have not specified):

const int X = 0;
const int Y = 0;
const int CELLWIDTH = 32;
var grid = new GridCell[,] //x, y or y, x

for (int y = 0; y < grid.GetLength(X); y++)
for (int x = 0; x < grid.GetLength(Y); x++)
grid[x, y] = new GridCell(cellWidth, etc);
//GridCell has an empty array of entities created in its constructor.
//Instead of GridCell here, can even just use a 1D array of entity indices.


Sort entities into these, at end of each frame or start of next frame like

//clear each GridCell's .entities first! left to the reader

//fresh sort into grid cells
foreach (Entity entity in world.entities)
{
int xGrid = entity.pos.x / CELLWIDTH;
int yGrid = entity.pos.y / CELLWIDTH;
grid[xGrid, yGrid].entities.push(entity);
}


You now have all your entities sorted spatially, and can use as

GridCell cell = grid[entity.pos.x, entity.pos.y];
//...now you can consider all other entities in this cell

//or even use some simple arithmetic on x and y to get all GridCell neighbours, too...
GridCell[] cells = grid.getCellNeighbourhoodAround(entity.pos); //this cell + all 8 neighbours


Use LINQ

If you are using C#, LINQ can do this very efficiently both in terms of code brevity and performance:

var results = from entity in gridCell.entities
where (entity.pos - other.pos).magnitude < 10 //distance check
select entity.Key; //returns a list of IDs


Rather than using gridCell.entities, you could query across all entities in a neighbourhood of 3x3 cells for instance, by assembling each .entities into a single, larger array to be queried, or you could query the whole world using the complete (non-bucketised) world.entities.

Conclusion

In games, a database usually won't replace the core data structures. It typically acts in addition to those, and only where required. This is out of necessity, for performance reasons.

• The world is small: dozens to hundreds of entities. The structures you suggested (well, except for full blown databases) must be queried with exact values. I wouldn't know how to use them to "look for an object with a property larger than 3.0" or "an object within 5.0 meters from a point". – peoro Dec 14 '19 at 23:48
• @peoro Fair enough. I've substantially improved my answer with better options. – Engineer Dec 15 '19 at 8:40
• I appreciate the time you put into this answer, and I hope I'm not sounding ungrateful, but... I've been mentioning the idea of partitioning the space in the original question. The position of an entity is only one of the properties I'm interested in: that's one example out of the 5 in the question. I was thinking about combining multiple indices/structures to speed up the search, but would like to find existing solutions or research, to better understand the whole problem, to take inspiration, to come up with a nice API etc. – peoro Dec 15 '19 at 10:46

Your solution sounds a lot like indexing, and in truth I'd go the same route as well. Just remember that this will eat up quite a lot of RAM if you your world's really big. Try dynamically calculating your indexes, maybe using a quad tree. i.e. you only index the tagged elements in a certain region around the player, this way you will be able to reduce how much RAM your world chews up.

Below I've made a working example of this in JS, though I have not added any way to only query entities close to the player, but I'm guessing you can create your own little algorithm. Maybe even check each step if the entity is close to the player and if so, then add the close-to-player tag.

// Used to create entities that we can index and query later on
function Entity(type, tags) {
this.type = type;
// Add the type to the tags
tags.push(type);
this.tags = tags;

// The Query system that this entity belongs to (we set this later
this.qs = {};
}

//
function Query(entities) {
this.entities = entities;
// This is where we link the entities to the corresponding tag
this.init();
}

Query.prototype.init = function() {
// Keep a reference to 'this' object
var that = this;

// Initialize the tags object
this.tags = {};

this.entities.forEach(function(entity) {
// First set the entities' qs property to this query system
entity.qs = that;

// Now loop through the entity list and link the entities to the corresponding tag
entity.tags.forEach(function(tag) {
// If the tag doesn't exist then create it
if (!that.tags[tag]) {
that.tags[tag] = [];
}

// Add the entity to
that.tags[tag].push(entity);
});
});
};

// Allows you to query based on tags
Query.prototype.get = function(tag) {
return this.tags[tag];
};

// Entities in a MOBA
var entities = [
// By the way, I think it would be better to use objects for tags instead of using strings, or maybe even using an object/map instead of a list for the tags param.
// This will allow you to have a 'tags' param like so { lvl: 7, 'prd-gold': true, 'has-gold': true }
// You can then run more complex queries using '<=' or '>=' (e.g. query..
// Anyways moving on...
new Entity('player', ['lvl7', 'prd-gold', 'has-gold', 'prd-health', 'has-sword', 'armed']),
new Entity('minion', ['lvl4', 'has-gold', 'prd-health', 'fighting', 'has-club', 'armed']),
new Entity('monster', ['lvl3', 'has-gold', 'prd-health', 'idle'])
];

var qs = new Query(entities);
window.qs = qs;
console.log('Query System:', qs);
console.log("Query.get player:", qs.get('player'));
console.log("Query.get prd-gold:", qs.get('prd-gold'));
console.log("Query.get has-gold:", qs.get('has-gold'));

Check your browser's console for result.