Querying game objects in real-time

Question

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.

Answer 1

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.

Answer 2

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.