1 Topic by Mr Spy

  • Mr Spy
  • Moderator
  • Offline
  • From: Netherlands
  • Registered: December 14th, 2003
  • Posts: 598

Topic: Efficient way to iterate over players and monsters within a radius

Provide a more efficient way to iterate over players and monsters within a given radius.

For some script and spell effects it is neccesary to iterate over all players and monsters in a radius to apply some effect. Currently this requires iterating over all possible 255 players, and the 2048 monster slots on a map. This makes it slow, so it is not used much.

Does the server hold this information on a sector level, or provide some other data structure to query this from? If so, could some more efficient way of getting a list of monsters and players in a radius be added?

Some pseudo code:

gsGetEntitiesInRadius(entity_out[], x, y, mapid, radius, filter); // returns number of entities found

new entities[MAX_ENTITIES];
new entityCount = gsGetEntitiesInRadius(entities, x, y, m, 50, FILTER_PLAYERS | FILTER_MONSTERS);

for(new i = 0; i < entityCount; i++) {
  new id = entities[i];
  // do things with the entity
}
  • James
  • Administrator
  • Offline
  • From: Ohio
  • Registered: June 15th, 2003
  • Posts: 545

Re: Efficient way to iterate over players and monsters within a radius

Not at map-sector level (32x32), but yes, it holds this information at projectile-sector level (8x8).
Can't promise it this week but that is a very good idea. I will look into it. Not only does the current approach make the scan slow, it also ends up hard-coding player ID and monster ID restrictions that we may want to change in the future.

James's Website

3 Reply by Catbert

  • Catbert
  • meow
  • Offline
  • From: Midwest
  • Registered: June 15th, 2003
  • Posts: 231

Re: Efficient way to iterate over players and monsters within a radius

Perhaps it could allow you to pass in a sector ID?

Catbert's Website

4 Reply by Catbert

  • Catbert
  • meow
  • Offline
  • From: Midwest
  • Registered: June 15th, 2003
  • Posts: 231

Re: Efficient way to iterate over players and monsters within a radius

Perhaps it could allow you to pass in a sector ID?

Catbert's Website

5 Reply by James

  • James
  • Administrator
  • Offline
  • From: Ohio
  • Registered: June 15th, 2003
  • Posts: 545

Re: Efficient way to iterate over players and monsters within a radius

In the next server update, the syntax will be:

new entities[MAX_ENTITIES];
new count = gsGetEntities(entities, FILTER_MONSTERS|FILTER_PLAYERS, map, x1, x2, y1, y2, z1, z2);
or
new count = gsGetEntities(entities, FILTER_MONSTERS|FILTER_PLAYERS, map, x1, x2, y1, y2);
or
new count = gsGetEntities(entities, FILTER_MONSTERS|FILTER_PLAYERS, map);
or
new count = gsGetEntities(entities, FILTER_PLAYERS); // FILTER_MONSTERS only does anything if map is specified

I've defined MAX_PLAYERS, MAX_MONSTERS, and MAX_ENTITIES. If you expect far less than the maximum possible, it's a tiny bit faster to use a smaller array since Pawn won't have to initialize the array elements, but it's not much. If the array is too small, it just won't return more.

(From my tests, doing a heal effect on every single monster on the map is actually still quite slow. So, you still need to restrain yourself a little bit. But it's all faster than before.)

(I could add a radius version, but there's a question of what you do with the Z axis there.)

James's Website