Optimizing distance checks

Discussion in 'Spigot Plugin Development' started by teegah, Aug 16, 2018.

  1. I am doing a large amount of distance checks per second (10k+ per second), and I want to optimize this process as much as possible. I am of course using .distanceSquared, but I wanted to know if it would be even more efficient to mix in getNearbyEntities with this.

    Code (Java):

    List<Sheep> sheepList = new ArrayList<Sheep>();
            List<Pig> pigList = new ArrayList<Pig>();
            List<Zombie> zombieList = new ArrayList<Zombie>();
         
            if(myZombie.getNearbyEntities(10,10,10).size() < zombieList.size()){
                //check instanceof Zombie against all entities in getNearbyEntities to see if zombie, then do whatever
            }else{
                //check distanceSquared against all zombies in zombieList, then do whatever
            }
    Basically, I think my question comes down to, is an instanceOf check at around the same efficiency as a distanceSquared check? Or is one much more expensive to call?
     
  2. I'm questioning if your initial approach is correct by itself, considering you do more than 10.000 distance checks per second. What is it you're trying to achieve?

    I'm not sure what you're using this for so giving an answer is fairly hard. But yes, if you want to get nearby entities in someway, writing a seperate method for that is a good idea.

    I'd recommend getting all entities in nearby chunks, then checking if they distance between your location and the entity is smaller or equal to your max distance. I'm not sure if getNearbyEntities has this implementation, or if they just loop through all entities in the world.
     
    • Like Like x 1
  3. MiniDigger

    Supporter

    I would imagine that instanceof is faster, not by much tho.
    #getNearbyEntities is what will kill your performance if you call that 10k times per second. if you need to do such a thing, your design is flawed.
     
    • Agree Agree x 1
    • Useful Useful x 1
  4. for a minigame. getNearbyEntities returns a list of entities from chunks though it includes all types of entities, I don't think it has distance checks which is why I'm wondering if its more efficient to call instanceOf vs. a distance check because I would need to use instanceOf to filter out entities I dont want, compared to using a distance check on a list of the entities I am keeping in memory. I would pick whichever list is smaller so there would be less iterations, and hopefully be more efficient assuming O( instanceOf ) = O( getNearbyEntities )

    Is there a certain part of #getNearbyEntities that kills performance? Could I rewrite the method with the same functionality but possibly circumvent the performance hogger? Basically I need to use instanceOf in combination with #getNearbyEntities to filter out the entity types I'm not looking for.
     
  5. What's the minigame? Do you spawn these entities yourself? If so, you might as well keep track of them when spawning them, and simply loop through a list.
     
    • Agree Agree x 1
  6. NathanWolf

    Supporter

    It does, effectively. It creates a bounding box using the x,y,z sizes you pass in and only returns entities within that bounding box. Doing distance checks on the collection of entities you get back will be redundant.

    As others have said, though, it's expensive. It depends a lot on the bounds you're using, though- it doesn't check against all entities in the world, it figures out which specific chunks it needs to check, iterates over them and does a bounding box check on each one.

    I'm still not certain why you would need to call this 10k per second, though, that seems very extreme. You would never need to update this more than once a tick for each query- do you have 500 zombies you're checking each tick?
     
  7. Not entirely redundant. getNearbyEntities will get all entities within a cube. Adding an additional distance check will limit it to a sphere.
     
    • Agree Agree x 1
  8. NathanWolf

    Supporter

    Fair enough! Not sure it's worth the extra overhead for such a fine point, especially 10k times a second, but still don't really know what OP is trying to accomplish :)
     
    • Agree Agree x 1