   Querying across Game Entities
  I am in the beginning stages of creating my own space fleet combat sim (I'm writing it in Scala). At the moment I have a traditional GameEntity hierarchy. I also have an EntityManager that contains a list of all of the GameEntities  indexed by a unique identifier as described in Max Buckland's book.The problem is that I am often wanting to run queries across my GameEntities to get subsets. As an example, fighters can be out in space, or in the hangar deck of a capital ship. Only fighters that are out in space need to be rendered.As another example, let's say that a fighter has been given the order to engage nearby enemy fighters. In selecting the next target, the fighter should ignore, friendly fighters, capital ships, and enemy fighters still in their hangar bays. What I am doing now is implementing a combination of:1) Loop through *all* of the game entities and do checks for entity type, location, etc., throwing out most.2) Implement various sub lists (TeamAFightersInSpace, RenderableEntities).(1) seems a waste and (2) is turning into an ad-hoc mishmash of lists a data structures.I have starting playing with a more data-centric and systematic approach, where each possible attribute would have a value indexed to the list of game entity ids. For instance, there would be a EntityType hash that would be a HashMap that maps the GameEntity type to a list of the Game Entity IDs who have that type.How do other people handle querying across GameEntities?Michael   
  You have many requirements, and as so often, it is better, atleast performance wise, to have special solutions for special requirements :-)Quote:Original post by the456I am in the beginning stages of creating my own space fleet combat sim (I'm writing it in Scala). At the moment I have a traditional GameEntity hierarchy. I also have an EntityManager that contains a list of all of the GameEntities  indexed by a unique identifier as described in Max Buckland's book.The problem is that I am often wanting to run queries across my GameEntities to get subsets. As an example, fighters can be out in space, or in the hangar deck of a capital ship. Only fighters that are out in space need to be rendered.As another example, let's say that a fighter has been given the order to engage nearby enemy fighters. In selecting the next target, the fighter should ignore, friendly fighters, capital ships, and enemy fighters still in their hangar bays. What I am doing now is implementing a combination of:1) Loop through *all* of the game entities and do checks for entity type, location, etc., throwing out most.2) Implement various sub lists (TeamAFightersInSpace, RenderableEntities).(1) seems a waste and (2) is turning into an ad-hoc mishmash of lists a data structures.I have starting playing with a more data-centric and systematic approach, where each possible attribute would have a value indexed to the list of game entity ids. For instance, there would be a EntityType hash that would be a HashMap that maps the GameEntity type to a list of the Game Entity IDs who have that type.How do other people handle querying across GameEntities?MichaelWell, you have the following requirements:1. choose entities which should be rendered2. decide if an entity is "free" or attached to an other3. choose all entities which are in a certain area4. which entities are in the same squad Starting with 2. & 4:Your entity hierachy is a good solution for this task. This is all about game structure and game logic. An example:- space - alliance  - fleet 1    - carrier 1 - squad Bravo   - fighter 1   - fighter 2    - squad Charlie- fighter 3- fighter 4Now a simple depth test (space=0, alliance=1,fleet=2,...) is enought to decide if an squad, single fighter or carrier is in space (depth = 3) or "attached" to an other entity (depth>3).Well, rendering is just a view of the game world. Think about your game logic running on a server and your client is just rendering which is currently visible to the player. So, you dont want to restrict you server code by some data structure which is better for rendering. Try to separate rendering (view) from game logic (model). Best to use a data structure which helps you to cull your entities. A good start for a space game would be an oct-tree or sweep and prune.At last, choose entites, which are inside a certain area. This is similar to rendering. An spartial partion datastructure like octree or sweep'n'prune will help you to select entities in a certain area (sphere or box) very fast. So, just select all entities in this area and run your filters on it (same team, is fighter, etc.). In this case you could use the same data structure for culling entities for rendering or for game logic. Well, this is what I'm doing in my game engine:- use hierachy to group entities- use sweep'n'prune for rendering and area-specific selection of entities.- rebuild sweep'n'prune each frame after all entities has been moved by the physics engine.   ;  I think you might get more benefit from implementing two data structures:One is a structure that is owned 'per team', and has a list for each type of ship. This simplifies the process of 'selecting all of the frigates' of a team. You can iterate over all of the lists if you ever need to traverse the entire fleet (expensive, but once and awhile required). I feel you would rarely use this structure, and it could really just be a doubly-linked list of all the ships a player owns.The second structure is a spatial grid that allows you to do localised queries very fast. You want to perform actions like this:Find all the fighters that are visible to render - Intersect the frustum with your spatial grid, collect all the entities, render them. Rendering doesn't care about who owns what ship.Engage nearby fighters - Intersect a sphere with a given radius with the spatial grid, collection all the entities. Filter out friendlies and capital ships, sort the result by 'priority of attack' and go.You'll want your query functions to take a function object that lets you test whether the object should be returned or not, allowing you to pass in filters for enemy v. friendly.You could also break each grid cell into friendly vs. enemy lists to minimize the filtering of each type, but there I would probably do some profiling first.As far as the grid goes, you might want to use a uniform grid, quad tree, octree or a more dynamic system like a collision detection's sweep-and-prune. Ultimately, the cost of moving the objects from cell to cell must be low, with the emphasis on speeding up the queries. If you use some of the 'loose' versions of grids or quadtrees, you end up spending a lot less time rebuilding the tree/moving entities.If your ships, when created, are put into the first list, and whenever they move, they are moved inside the grid, you'll get both cases handled.I think with these two structures, you'll get everything you need out of the data.S>   