Best way to get nearby entities

Question

I've pondered over this problem for a long time, and was just wondering if there really was a better way to get nearby entities instead of looping through every entity in the world and testing their location?

For the plugin I'm developing, I'm using this every tick and in no way at all is it efficient.

public static List<Entity> getEntitiesAroundPoint(Location location, double radius) {
    List<Entity> entities = new ArrayList<Entity>();

    for (Entity entity : location.getWorld().getEntities()) {
        if (entity.getWorld() != location.getWorld()) {
            continue;
        } else if (entity instanceof Player && ((Player) entity).getGameMode().equals(GameMode.SPECTATOR)) {
            continue; //Don't want spectators
        } else if (entity.getLocation().distanceSquared(location) <= radius * radius) {
            entities.add(entity);
        }
    }
    return entity;
}

I don't have access to a player object so player.getNearbyEntities() isn't really an option (and I don't know if that is any better, either). I did wonder if location.getChunk().getEntities() would be any better to loop but again, I have no idea of the process behind that. Could anyone share some insight with me as to what might be a better way to go about this effeciently?

Thanks in advance.

Answer 1

Under the hood, the getNearbyEntities() method from org.bukkit.entity.Entity loops through all relevant chunks, so I would assume doing that is faster than looping through every entity in the world.

Unfortunately, the NMS getEntities method (and even some methods it calls) that getNearbyEntities uses internally requires an Entity as its first argument. You could write your own method that takes your two parameters and mirrors the behavior of the NMS method.

I don't know if I can post the exact source code of the NMS method here because of the Craftbukkit DMC takedown and the Stack Overflow rules, but the way I understand it the getEntities method takes an axis aligned bounding box, finds the chunks within that box and returns the entities in those chunks.

Since you're using a sphere and not a box as a perimeter, I would initially use the box and then do a distance check to see whether the entities are really in the given sphere.

Here is an example of what this might look like:

public static List<Entity> getEntitiesAroundPoint(Location location, double radius) {
    List<Entity> entities = new ArrayList<Entity>();
    World world = location.getWorld();

    // To find chunks we use chunk coordinates (not block coordinates!)
    int smallX = MathHelper.floor((location.getX() - radius) / 16.0D);
    int bigX = MathHelper.floor((location.getX() + radius) / 16.0D);
    int smallZ = MathHelper.floor((location.getZ() - radius) / 16.0D);
    int bigZ = MathHelper.floor((location.getZ() + radius) / 16.0D);

    for (int x = smallX; x <= bigX; x++) {
        for (int z = smallZ; z <= bigZ; z++) {
            if (world.isChunkLoaded(x, z)) {
                entities.addAll(Arrays.asList(world.getChunkAt(x, z).getEntities())); // Add all entities from this chunk to the list
            }
        }
    }

    // Remove the entities that are within the box above but not actually in the sphere we defined with the radius and location
    // This code below could probably be replaced in Java 8 with a stream -> filter
    Iterator<Entity> entityIterator = entities.iterator(); // Create an iterator so we can loop through the list while removing entries
    while (entityIterator.hasNext()) {
        if (entityIterator.next().getLocation().distanceSquared(location) > radius * radius) { // If the entity is outside of the sphere...
            entityIterator.remove(); // Remove it
        }
    }
    return entities;
}

This method might still be slightly slower than using getNearbyEntities because I'm not sure whether calling the Bukkit methods used here for retrieving a Chunk and entities inside it is as efficient as directly calling the NMS methods like the getNearbyEntities method does.