0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Ever thought of using something like SQLite? \$\endgroup\$ – Vaillancourt Dec 13 '19 at 2:01
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Mr. Smith Dec 14 '19 at 11:09
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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". \$\endgroup\$ – peoro Dec 14 '19 at 23:48
  • \$\begingroup\$ @peoro Fair enough. I've substantially improved my answer with better options. \$\endgroup\$ – Engineer Dec 15 '19 at 8:40
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – peoro Dec 15 '19 at 10:46
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.