Best way to sort through giant lists?

Game Mechanics
#1

I have a list of about 1000 entities that i need to go through on a regular basis and see which ones are in a certain range. However, looking through the list every time I need to get the new list seems a bit inefficient. Is there a better way to do this? This is somewhat of what I’m using now.


public ArrayList<Entity> getEntitiesInRage(int range, Entity center){
     ArrayList<Entity> inRange = new ArrayList<Entity>();
     for(Entity e: fullList){
          if(e.getDistanceTo(center) >= range)
               inRange.add(e);
     }
     return inRange();

}
#2

[icode]getEntitiesInRage[/icode] lol. ;D

Anyway:

The only way to optimise such a method is to put the entities into a large-scale grid*. Then you can work out the maximum amount of grid squares you could go and still be in that range. Then you check all the entities within those grid squares, and do the final check on only those entities.

You would have to store which entities are in which grid. And make sure that when one moves, it is removed from the previous square and added to the next.

*Grid or Tree

#3

Lol, that was just some psuedocode. I didn’t even catch the ‘Rage’. Anyway, I don’t think that there is any real way that I could get them into a grid system.

#4

You could if you really wanted to. :slight_smile:

#5

Instead, I’ve just decided to reduce to list size to 250 and whenever the size gets any smaller, it just adds some to fill in the gaps.

#6

That’s good, because the logic’s back to front as well.

Do you really need to find all entities within range, or would you be better using something like k-nearest, which is a well-discussed computational geometry problem?