Jump to content
  • Advertisement
Sign in to follow this  
freeworld

querering a list of objects every frame

This topic is 2521 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

While I wait for my new windows disc, I'm stuck with internet explorer and pen-n-paper theories. I'm looking for a cleaner way to filter out objects and get a list of only the ones that matter. So querying a central registry is what I'm thinking about.

example, in a rts setting, you have hundreds of units running around the map. If I have a central registry that all units have to register with. This basically just saves a pointer to all the units, so I don't have to querery multiple players or multiple unit containers. I'd then like to be able to ask that registery for a list of all units within a range.

registry->GetUnitsInRange(location, range, listToFill&);

The registry would then run whatever filter it needs to and any units that fit the criteria would be placed into the list. Then whatever needs to deal with those units can focus on the ones that actual matter without having to do the error checking it'self.

Now if this is happening every frame, is building a list everytime worth it compared to every unit checking every unit itself. I could see it saving time on situation like so...

Unit A is being protected by Unit B.
Unit A gets a list of all targets that are attacking it.
Unit A uses that to accquire its own target.
The same list can then be used over again by Unit B to get a target of it's own.

Range isn't the only parameter that I'd search for. I would also allow further pruneing an already created list ie

registry->GetUnitsInRange(location, range, listToFill&); // to get the units in range
registry->GetUnitWithLowestHealth(listToFill, unit&); // ofcourse an overloaded version would search the entire registry instead.


A few numbers to throw out there too
for my current sceneraio, I don't expect the registry to grow farther than 500 elements, and a qued list typically would only grab 10-50 elements, at most it might grab 200-300 depending on the filter used.

any ideas? I don't know if this is too brute force or if it's completely exceptable.

Share this post


Link to post
Share on other sites
Advertisement
A list of 500 elements is really very small. Even if each unit had to iterate over every other unit, it would still take a tiny amount of time on a modern processor.

On the other hand, its fun to optimize biggrin.png

In modern games, the amount of memory used for code-data is tiny compared to the amount used for art assets, so you can easily afford to have multiple representations of all of the units. For spatial queries (all units within x distance) you want some sort of specialized structure that can do them quickly. For health queries, have a sorted array of all units by health. For attackers, each unit could maintain a list of the units that are attacking it.

Share this post


Link to post
Share on other sites
Each of your units are an entity in the game world. If you separate your entity representation into a key, set of traits with values associated to those traits (components), and game logic systems that operate on those components (subsystems), then you can easily model this how turch described.

In your scenario, entity A and B both are created with a threat component. This component is managed by the threat subsystem to keep a list of entities that have attacked that given entity and who has built up the most threat. Each entity also have a target component, managed by the target system for knowing who is attacking whom.

So an attack/threat system keeps the list of those attacking entity A. This system is quiered to get the list of entities attacking. Entity A can then use that list to pop the highest threat off the list and then use that entity's ID to set it's target accordingly for the target system. Now when Entity B is notified that combat has engaged, it simply asks the target system what is Entity A's current target or asks the threat system what is Entity A's highest threat entity? From that, it can deduse what it's target should be and sets it's own target accordingly for the target system to manage.

So by using feature-specific representations of the data, we can design small systems to handle a specific facet of the game world. The data is kept small enough that it can be managed and queried efficiently, changes made to those core systems are centralized, and your game API is modular. Now if you need to change how attacks or threat work, you could easily do so in your subsystem, minimizing maintenance efforts downstream.

Share this post


Link to post
Share on other sites
For the range-specific queries, would a quasi spatial-hash help in this situation? As each entity moves through your world, they pass through your spatial grid. When the entity moves from one grid to another, it updates its grid position in the registry, and when you query the registry, it can just get units in the grids surrounding the location queried.

It's just a though, and I've never tried it, but thought I'd throw it out there.

Share this post


Link to post
Share on other sites
So I actually suggest a little bit of a rethink on this. While you might end up implementing the initial version of things with simple O(n2) object to object comparisons, you don't really want to be doing per object searching and filtering every frame no matter what your underlying implementation is. The reason I suggest the rethink is that you are going to end up with AI sociopath problems (this effects most AI types, I'll discuss in terms of a state engine though) unless you do a lot more work than you are outlining. So, let me first break down the problem I'm suggesting you want to avoid:

1. Objects a and b have the associations you mention.
2. Object a makes a list of all the objects around it.
3. Is the list of objects stable? I.e. as they move around you and 'a' moves around, will they always come back in the same order? Probably not, so you will likely need to sort them in some manner.
4. Is the resulting sorted list stable? Probably not unless you sort with a per object unique identifier as part of the sorting process. Without this your AI will likely say one tank is as good as another to attack and as the list keeps reordering the AI will keep changing target and look pretty silly. (Not to mention die without doing much because it spread it's fire instead of concentrating it.) So, you want to keep the unique identifier of objects in mind when looking for AI objectives.
5. Is it a new object, an object you've seen recently etc. In some cases it makes sense for the AI to consider new targets even when focused on another target. If a new object comes into view you might want to say, I do massive damage against tanks as it is the object types primary role, so a new object shows up and you might want to balance between 1 shot should kill my current target and that's a tank, I should focus on it as my primary target. Take the shot to kill the current target and "then" focus on the tank or immediately switch etc.

Given the above, I suggest you go straight to a spacial awareness management system which "allows" the api you are talking about but you would only use the direct query for special cases. What I mean by this is that instead of feeding the AI of your objects with new lists every frame via the query, the spacial awareness system will feed the AI 4 different events only as they happen and then the AI can do whatever it wants without the sociopath issues. (For the most part. :)) The events are: object entered, left range, object appeared, disappeared in range. The differences between the two variations are that in one they moved into/out of range and the other version is that they simply appeared/disappeared within vision range. (The second case could also be: spawned/died.)

What this does for you is that per object you can maintain a list of potential targets in range, you can reorder them as desired (at the per object AI level) and you know which object is which even if they are all the same type and don't have unique id's you can check, because the AI has control of the list. Now, with this the items #3 and #4 are up to the AI to decide how to deal with it since it maintains the list and just has to add/remove items according to the event. There are some sorts of things which simply don't care and always go after the closest item and when it gets a new enter/appear it just adds that to the potential target list, resorts and goes for the closest. On the other hand, most things will look much smarter if they continue to attack a single enemy even if other enemies end up moving a bit closer, constantly changing targets is dumb looking in most cases. (Axiom of AI in my opinion: AI doesn't have to be really smart, it just can't look stupid constantly.)

The answer to number 5 is rather simple, once visible it remains visible unless it goes beyond say 105% of range or is out of range for more than a couple frames. A little slop on the "left range" side of things is not horrible and prevents a lot of issues.

As to performance though, even with only 500 items a simple solution of recomputing is an O(n2) problem. As such even that few number of objects could show significant performance degradation as you approach your limit. (Worse, it can cause computation spikes given the amount of memory it has to touch in disparate places.) I would suggest starting with a simple spacial hash solution and if that's not enough, a quadtree and if that's not enough, go all out and do a full sweep/prune solution. I use a sweep/prune system almost all the time but that's because I did the others and ran into problems due to the stupid number of objects I was trying to maintain. The sweep/prune system is very difficult to get correct and if you don't need it, don't do it. (Lots of little edge cases when you start adding in "slop" for exit, very very painful. The other solutions "should" work for you easily though.)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!