PDA

View Full Version : Efficient way to iterate through all entities in map



w00tguy123
07-02-2016, 04:55 PM
I need an effecient way to iterate through all entitites in a map. This method is too slow:



CBaseEntity@ ent = null;
do {
@ent = g_EntityFuncs.FindEntityByClassname(ent, "*");

if (ent !is null)
{
// do nothing
}
} while (ent !is null);


That brings me down to 150 fps from 450 on a map with about 400 entities.

This way is even worse, bringing me down to 15 fps:

for (int i = 0; i < 8192; i++) // or whatever the max limit is
{
edict_t@ ent = g_EngineFuncs.PEntityOfEntIndex(i);
if (ent !is null)
{
// do nothing
}
}

Is there some way to get a list of entities that I can iterate without these massive performance penalties?

Why I want this:
I'm looking for all entities that are near one of about 100 custom portals in a map.

Why I'm not just using FindEntityInSphere():
It's too slow for my plugin. Not all entities will use the same sphere collision detection because of differences in origin positions (e.g. monster on ground, all others in middle), so FindEntityInSphere() is done twice at each portal to account for that. In total, the engine will need to iterate all map entities 200 times. It should be much faster if I just do it once myself, handling any special cases that come up

Silencer
07-02-2016, 05:06 PM
Is the performance this poor with or without the distance check you mentioned? The average 3 GHz of a modern CPU divided by your 8000x100 operations make 3750, which would need to be divided further by the actual instruction count per iteration, which will quickly drive you into tens of fps if they are more than a dozen, which you likely have if you are doing any kind of pythagorean math.

tl;dr: There is no way you are doing exactly what you asked every frame without significant performance loss. Make a list of the entities you actually need to check and keep it updated instead of iterating everything.

Solokiller
07-02-2016, 05:16 PM
^That.

If you really want to iterate over all entities (and you usually don't), you should do this:


for( int i = 0; i < g_Engine.maxEntities; ++i )
{
edict_t@ pEdict = g_EngineFuncs.PEntityOfEntIndex( i );

if( pEdict !is null && pEdict.free != 0 )
{
CBaseEntity@ pEntity = g_EntityFuncs.Instance( pEdict );
//Do something
}
}


The big difference here is that maxEntities is not set to num_edicts, but rather the highest entity index in use + 1. Instead of 8192, it's usually below 1000. It fluctuates constantly, so don't store it.

w00tguy123
07-02-2016, 05:27 PM
Make a list of the entities you actually need to check and keep it updated instead of iterating everything.

Hadn't thought of that, but I think the problem will still be there once I test this on a map with 400 portal-worthy ents. Or, maybe that's really rare and this is good enough.

FindEntityInSphere() has given the best general performance so far, but a lot of those sphere checks are done needlessly for ents that I don't care about. I guess I could start using classnames instead of "*", but I'm worred that calling that function ~50 more times for each class will negate any boost I get from the fewer sphere checks. I'll try FindEntityByClassname() first.


If you really want to iterate over all entities (and you usually don't), you should do this:

[code]

Unfortuantely I get 15 fps with that code, which is weird because I would expect that to perform better than FindEntityByClassname(), which does a classname check on each entity. It looks like I just have to shrink the list as much as possible.

Solokiller
07-02-2016, 05:46 PM
If it's being executed every frame it will cause serious performance issues.

w00tguy123
07-02-2016, 05:59 PM
If it's being executed every frame it will cause serious performance issues.

Yeah, but for a while I wasn't having any problems with it. I can (and should) stop doing this every frame, but I think something weird is going here.

What I want to know is this - how is it possible that this code:

for( int i = 0; i < g_Engine.maxEntities; ++i )
{
edict_t@ pEdict = g_EngineFuncs.PEntityOfEntIndex( i );

if( pEdict !is null && pEdict.free != 0 )
{
// Do nothing
}
}

is a bajillion times slower than this code:

CBaseEntity@ ent = null;
do {
@ent = g_EntityFuncs.FindEntityByClassname(ent, "*");

if (ent !is null)
{
// do nothing
}
} while (ent !is null);

I don't know how the engine is implemented, but if I were to guess, I would say that the first method is just dumbly returning an entity from some table or list, if the index is valid. That should be pretty fast. For some reason though, this slows my game down to 15 fps.

Now, the second method seems more complex to me. Now we're iterating through every entity in the list, and not only that, it's doing string comparisons on each one. Somehow, that's much faster (150 fps).

Edit:
Nevermind. g_Engine.maxEntities is returning 8222, and FindEntityByClassname() stops at 427.

Solokiller
07-02-2016, 06:24 PM
It could just be that Angelscript is much worse at iterating this than C++. It has to make a system call every time you ask for an entity, after all.

w00tguy123
07-02-2016, 06:27 PM
It could also be that I'm a bad programmer and forgot to count the iterations of each method.

g_Engine.maxEntities = 8222
FindEntityByClassname() stopped at 427

Setting the forloop condition to 427 resulted in equal performance. :D

Solokiller
07-02-2016, 06:33 PM
I must be mistaken then. There is a variable that contains the current highest entity index. Perhaps it's an engine function.

Solokiller
08-02-2016, 06:10 AM
Turns out there is such a variable (svgame.numEntities), but it's not accessible by game code. We should add that.

w00tguy123
08-02-2016, 01:08 PM
^ That would be nice to have.

For anyone curious:

I tried making a smaller entity list for the portals but I couldn't make it work. The problem was that this list needed to be updated within a few frames for newly added entitites, or else your spore launcher or grenade or whatever would fly through a portal. There are no hooks like EntityAdded or EntityRemoved, so updating that list fast enough (100ms or so) was a big performance hit because I had to iterate through every entity in the map.

My other idea was to flag entities that should ignore portals when encountered, but because you can't later find an entity based on a value that it doesn't match ("noise3" != "dont-tele-me"), this didn't work. You also can't find entities based on integer values it seems, which would have solved that problem.

I also found that calling FindEntityInSphere() for each classname you want is slower than just using "*" and filtering yourself.

My current solution is to spread the workload out across multiple frames.