Optimise nearby player retrieval

Instead of searching/testing every player online on the server,
we can instead use the nearby player tracking system to reduce
the number of tests per search.

2 files changed, 162 insertions, 426 deletions

diff --git a/patches/removed/1.20.2/0705-Optimise-nearby-player-lookups.patch b/patches/removed/1.20.2/0705-Optimise-nearby-player-lookups.patch
deleted file mode 100644
index a62fd88bd6..0000000000
--- a/patches/removed/1.20.2/0705-Optimise-nearby-player-lookups.patch
+++ /dev/null
@@ -1,426 +0,0 @@
-From 0000000000000000000000000000000000000000 Mon Sep 17 00:00:00 2001
-From: Spottedleaf <[email protected]>
-Date: Thu, 27 Aug 2020 16:22:52 -0700
-Subject: [PATCH] Optimise nearby player lookups
-
-Use a distance map to map out close players.
-Note that it's important that we cache the distance map value per chunk
-since the penalty of a map lookup could outweigh the benefits of
-searching less players (as it basically did in the outside range patch).
-
-diff --git a/src/main/java/net/minecraft/server/level/ChunkHolder.java b/src/main/java/net/minecraft/server/level/ChunkHolder.java
-index 4ae1ba645d9fdc1eb6d5a3e4f8ceed9b4841e003..e2202389a2c4133a183cca59c4e909fc419379ab 100644
---- a/src/main/java/net/minecraft/server/level/ChunkHolder.java
-+++ b/src/main/java/net/minecraft/server/level/ChunkHolder.java
-@@ -89,6 +89,12 @@ public class ChunkHolder {
-             this.chunkMap.needsChangeBroadcasting.add(this);
-         }
-         // Paper end - optimise chunk tick iteration
-+        // Paper start - optimise checkDespawn
-+        LevelChunk chunk = this.getFullChunkNowUnchecked();
-+        if (chunk != null) {
-+            chunk.updateGeneralAreaCache();
-+        }
-+        // Paper end - optimise checkDespawn
-     }
- 
-     public void onChunkRemove() {
-@@ -101,6 +107,12 @@ public class ChunkHolder {
-             this.chunkMap.needsChangeBroadcasting.remove(this);
-         }
-         // Paper end - optimise chunk tick iteration
-+        // Paper start - optimise checkDespawn
-+        LevelChunk chunk = this.getFullChunkNowUnchecked();
-+        if (chunk != null) {
-+            chunk.removeGeneralAreaCache();
-+        }
-+        // Paper end - optimise checkDespawn
-     }
-     // Paper end
- 
-diff --git a/src/main/java/net/minecraft/server/level/ChunkMap.java b/src/main/java/net/minecraft/server/level/ChunkMap.java
-index db40680bd9e026d9e98135355e4844c32e82fd51..153b82e4a3134ff0e40f267f1a005bc9184785ef 100644
---- a/src/main/java/net/minecraft/server/level/ChunkMap.java
-+++ b/src/main/java/net/minecraft/server/level/ChunkMap.java
-@@ -157,6 +157,12 @@ public class ChunkMap extends ChunkStorage implements ChunkHolder.PlayerProvider
-     public final ReferenceOpenHashSet<ChunkHolder> needsChangeBroadcasting = new ReferenceOpenHashSet<>();
- 
-     // Paper - rewrite chunk system
-+    // Paper start - optimise checkDespawn
-+    public static final int GENERAL_AREA_MAP_SQUARE_RADIUS = 40;
-+    public static final double GENERAL_AREA_MAP_ACCEPTABLE_SEARCH_RANGE = 16.0 * (GENERAL_AREA_MAP_SQUARE_RADIUS - 1);
-+    public static final double GENERAL_AREA_MAP_ACCEPTABLE_SEARCH_RANGE_SQUARED = GENERAL_AREA_MAP_ACCEPTABLE_SEARCH_RANGE * GENERAL_AREA_MAP_ACCEPTABLE_SEARCH_RANGE;
-+    public final com.destroystokyo.paper.util.misc.PlayerAreaMap playerGeneralAreaMap;
-+    // Paper end - optimise checkDespawn
- 
-     // Paper start - distance maps
-     private final com.destroystokyo.paper.util.misc.PooledLinkedHashSets<ServerPlayer> pooledLinkedPlayerHashSets = new com.destroystokyo.paper.util.misc.PooledLinkedHashSets<>();
-@@ -208,6 +214,7 @@ public class ChunkMap extends ChunkStorage implements ChunkHolder.PlayerProvider
-             trackMap.add(player, chunkX, chunkZ, Math.min(trackRange, io.papermc.paper.chunk.system.ChunkSystem.getSendViewDistance(player)));
-         }
-         // Paper end - use distance map to optimise entity tracker
-+        this.playerGeneralAreaMap.add(player, chunkX, chunkZ, GENERAL_AREA_MAP_SQUARE_RADIUS); // Paper - optimise checkDespawn
-     }
- 
-     void removePlayerFromDistanceMaps(ServerPlayer player) {
-@@ -217,6 +224,7 @@ public class ChunkMap extends ChunkStorage implements ChunkHolder.PlayerProvider
-         this.playerMobSpawnMap.remove(player);
-         this.playerChunkTickRangeMap.remove(player);
-         // Paper end - optimise ChunkMap#anyPlayerCloseEnoughForSpawning
-+        this.playerGeneralAreaMap.remove(player); // Paper - optimise checkDespawns
-         // Paper start - per player mob spawning
-         if (this.playerMobDistanceMap != null) {
-             this.playerMobDistanceMap.remove(player);
-@@ -248,6 +256,7 @@ public class ChunkMap extends ChunkStorage implements ChunkHolder.PlayerProvider
-             trackMap.update(player, chunkX, chunkZ, Math.min(trackRange, io.papermc.paper.chunk.system.ChunkSystem.getSendViewDistance(player)));
-         }
-         // Paper end - use distance map to optimise entity tracker
-+        this.playerGeneralAreaMap.update(player, chunkX, chunkZ, GENERAL_AREA_MAP_SQUARE_RADIUS); // Paper - optimise checkDespawn
-     }
-     // Paper end
-     // Paper start
-@@ -408,6 +417,23 @@ public class ChunkMap extends ChunkStorage implements ChunkHolder.PlayerProvider
-                 }
-             });
-         // Paper end - optimise ChunkMap#anyPlayerCloseEnoughForSpawning
-+        // Paper start - optimise checkDespawn
-+        this.playerGeneralAreaMap = new com.destroystokyo.paper.util.misc.PlayerAreaMap(this.pooledLinkedPlayerHashSets,
-+            (ServerPlayer player, int rangeX, int rangeZ, int currPosX, int currPosZ, int prevPosX, int prevPosZ,
-+             com.destroystokyo.paper.util.misc.PooledLinkedHashSets.PooledObjectLinkedOpenHashSet<ServerPlayer> newState) -> {
-+                LevelChunk chunk = ChunkMap.this.level.getChunkSource().getChunkAtIfCachedImmediately(rangeX, rangeZ);
-+                if (chunk != null) {
-+                    chunk.updateGeneralAreaCache(newState);
-+                }
-+            },
-+            (ServerPlayer player, int rangeX, int rangeZ, int currPosX, int currPosZ, int prevPosX, int prevPosZ,
-+             com.destroystokyo.paper.util.misc.PooledLinkedHashSets.PooledObjectLinkedOpenHashSet<ServerPlayer> newState) -> {
-+                LevelChunk chunk = ChunkMap.this.level.getChunkSource().getChunkAtIfCachedImmediately(rangeX, rangeZ);
-+                if (chunk != null) {
-+                    chunk.updateGeneralAreaCache(newState);
-+                }
-+            });
-+        // Paper end - optimise checkDespawn
-     }
- 
-     protected ChunkGenerator generator() {
-diff --git a/src/main/java/net/minecraft/server/level/ServerLevel.java b/src/main/java/net/minecraft/server/level/ServerLevel.java
-index fb9cf86250939fbc9cf1bfb90f6a1a7f4a489460..84ef33f700d3205d934802dceb4a2279df00adb0 100644
---- a/src/main/java/net/minecraft/server/level/ServerLevel.java
-+++ b/src/main/java/net/minecraft/server/level/ServerLevel.java
-@@ -562,6 +562,84 @@ public class ServerLevel extends Level implements WorldGenLevel {
-     }
-     // Paper end
- 
-+    // Paper start - optimise checkDespawn
-+    public final List<ServerPlayer> playersAffectingSpawning = new java.util.ArrayList<>();
-+    // Paper end - optimise checkDespawn
-+    // Paper start - optimise get nearest players for entity AI
-+    @Override
-+    public final ServerPlayer getNearestPlayer(net.minecraft.world.entity.ai.targeting.TargetingConditions condition, @Nullable LivingEntity source,
-+                                               double centerX, double centerY, double centerZ) {
-+        com.destroystokyo.paper.util.misc.PooledLinkedHashSets.PooledObjectLinkedOpenHashSet<ServerPlayer> nearby;
-+        nearby = this.getChunkSource().chunkMap.playerGeneralAreaMap.getObjectsInRange(Mth.floor(centerX) >> 4, Mth.floor(centerZ) >> 4);
-+
-+        if (nearby == null) {
-+            return null;
-+        }
-+
-+        Object[] backingSet = nearby.getBackingSet();
-+
-+        double closestDistanceSquared = Double.MAX_VALUE;
-+        ServerPlayer closest = null;
-+
-+        for (int i = 0, len = backingSet.length; i < len; ++i) {
-+            Object _player = backingSet[i];
-+            if (!(_player instanceof ServerPlayer)) {
-+                continue;
-+            }
-+            ServerPlayer player = (ServerPlayer)_player;
-+
-+            double distanceSquared = player.distanceToSqr(centerX, centerY, centerZ);
-+            if (distanceSquared < closestDistanceSquared && condition.test(source, player)) {
-+                closest = player;
-+                closestDistanceSquared = distanceSquared;
-+            }
-+        }
-+
-+        return closest;
-+    }
-+
-+    @Override
-+    public Player getNearestPlayer(net.minecraft.world.entity.ai.targeting.TargetingConditions pathfindertargetcondition, LivingEntity entityliving) {
-+        return this.getNearestPlayer(pathfindertargetcondition, entityliving, entityliving.getX(), entityliving.getY(), entityliving.getZ());
-+    }
-+
-+    @Override
-+    public Player getNearestPlayer(net.minecraft.world.entity.ai.targeting.TargetingConditions pathfindertargetcondition,
-+                                   double d0, double d1, double d2) {
-+        return this.getNearestPlayer(pathfindertargetcondition, null, d0, d1, d2);
-+    }
-+
-+    @Override
-+    public List<Player> getNearbyPlayers(net.minecraft.world.entity.ai.targeting.TargetingConditions condition, LivingEntity source, AABB axisalignedbb) {
-+        com.destroystokyo.paper.util.misc.PooledLinkedHashSets.PooledObjectLinkedOpenHashSet<ServerPlayer> nearby;
-+        double centerX = (axisalignedbb.maxX + axisalignedbb.minX) * 0.5;
-+        double centerZ = (axisalignedbb.maxZ + axisalignedbb.minZ) * 0.5;
-+        nearby = this.getChunkSource().chunkMap.playerGeneralAreaMap.getObjectsInRange(Mth.floor(centerX) >> 4, Mth.floor(centerZ) >> 4);
-+
-+        List<Player> ret = new java.util.ArrayList<>();
-+
-+        if (nearby == null) {
-+            return ret;
-+        }
-+
-+        Object[] backingSet = nearby.getBackingSet();
-+
-+        for (int i = 0, len = backingSet.length; i < len; ++i) {
-+            Object _player = backingSet[i];
-+            if (!(_player instanceof ServerPlayer)) {
-+                continue;
-+            }
-+            ServerPlayer player = (ServerPlayer)_player;
-+
-+            if (axisalignedbb.contains(player.getX(), player.getY(), player.getZ()) && condition.test(source, player)) {
-+                ret.add(player);
-+            }
-+        }
-+
-+        return ret;
-+    }
-+    // Paper end - optimise get nearest players for entity AI
-+
-     // Add env and gen to constructor, IWorldDataServer -> WorldDataServer
-     public ServerLevel(MinecraftServer minecraftserver, Executor executor, LevelStorageSource.LevelStorageAccess convertable_conversionsession, PrimaryLevelData iworlddataserver, ResourceKey<Level> resourcekey, LevelStem worlddimension, ChunkProgressListener worldloadlistener, boolean flag, long i, List<CustomSpawner> list, boolean flag1, @Nullable RandomSequences randomsequences, org.bukkit.World.Environment env, org.bukkit.generator.ChunkGenerator gen, org.bukkit.generator.BiomeProvider biomeProvider) {
-         // IRegistryCustom.Dimension iregistrycustom_dimension = minecraftserver.registryAccess(); // CraftBukkit - decompile error
-@@ -687,6 +765,14 @@ public class ServerLevel extends Level implements WorldGenLevel {
-     }
- 
-     public void tick(BooleanSupplier shouldKeepTicking) {
-+        // Paper start - optimise checkDespawn
-+        this.playersAffectingSpawning.clear();
-+        for (ServerPlayer player : this.players) {
-+            if (net.minecraft.world.entity.EntitySelector.PLAYER_AFFECTS_SPAWNING.test(player)) {
-+                this.playersAffectingSpawning.add(player);
-+            }
-+        }
-+        // Paper end - optimise checkDespawn
-         ProfilerFiller gameprofilerfiller = this.getProfiler();
- 
-         this.handlingTick = true;
-diff --git a/src/main/java/net/minecraft/world/entity/Mob.java b/src/main/java/net/minecraft/world/entity/Mob.java
-index 90d95dc95fe8868a4c0298acb0e1c6ce7bd883cb..3d5c967dbccb2a288092a3bf950ab4bfda7a3bb4 100644
---- a/src/main/java/net/minecraft/world/entity/Mob.java
-+++ b/src/main/java/net/minecraft/world/entity/Mob.java
-@@ -858,7 +858,12 @@ public abstract class Mob extends LivingEntity implements Targeting {
-         if (this.level().getDifficulty() == Difficulty.PEACEFUL && this.shouldDespawnInPeaceful()) {
-             this.discard();
-         } else if (!this.isPersistenceRequired() && !this.requiresCustomPersistence()) {
--            Player entityhuman = this.level().findNearbyPlayer(this, -1.0D, EntitySelector.PLAYER_AFFECTS_SPAWNING); // Paper
-+            // Paper start - optimise checkDespawn
-+            Player entityhuman = this.level().findNearbyPlayer(this, level().paperConfig().entities.spawning.despawnRanges.get(this.getType().getCategory()).hard() + 1, EntitySelector.PLAYER_AFFECTS_SPAWNING); // Paper
-+            if (entityhuman == null) {
-+                entityhuman = ((ServerLevel)this.level()).playersAffectingSpawning.isEmpty() ? null : ((ServerLevel)this.level()).playersAffectingSpawning.get(0);
-+            }
-+            // Paper end - optimise checkDespawn
- 
-             if (entityhuman != null) {
-                 double d0 = entityhuman.distanceToSqr((Entity) this);
-diff --git a/src/main/java/net/minecraft/world/level/Level.java b/src/main/java/net/minecraft/world/level/Level.java
-index 270ce3995229aa79074e981bb45e5480a5e924d4..fb2e1d6954d244a82c70730241046efad927fc14 100644
---- a/src/main/java/net/minecraft/world/level/Level.java
-+++ b/src/main/java/net/minecraft/world/level/Level.java
-@@ -207,6 +207,69 @@ public abstract class Level implements LevelAccessor, AutoCloseable {
-         return this.getChunkIfLoaded(chunkX, chunkZ) != null;
-     }
-     // Paper end
-+    // Paper start - optimise checkDespawn
-+    public final List<net.minecraft.server.level.ServerPlayer> getNearbyPlayers(@Nullable Entity source, double sourceX, double sourceY,
-+                                                                                double sourceZ, double maxRange, @Nullable Predicate<Entity> predicate) {
-+        LevelChunk chunk;
-+        if (maxRange < 0.0 || maxRange >= net.minecraft.server.level.ChunkMap.GENERAL_AREA_MAP_ACCEPTABLE_SEARCH_RANGE ||
-+            (chunk = (LevelChunk)this.getChunkIfLoadedImmediately(Mth.floor(sourceX) >> 4, Mth.floor(sourceZ) >> 4)) == null) {
-+            return this.getNearbyPlayersSlow(source, sourceX, sourceY, sourceZ, maxRange, predicate);
-+        }
-+
-+        List<net.minecraft.server.level.ServerPlayer> ret = new java.util.ArrayList<>();
-+        chunk.getNearestPlayers(sourceX, sourceY, sourceZ, predicate, maxRange, ret);
-+        return ret;
-+    }
-+
-+    private List<net.minecraft.server.level.ServerPlayer> getNearbyPlayersSlow(@Nullable Entity source, double sourceX, double sourceY,
-+                                                                               double sourceZ, double maxRange, @Nullable Predicate<Entity> predicate) {
-+        List<net.minecraft.server.level.ServerPlayer> ret = new java.util.ArrayList<>();
-+        double maxRangeSquared = maxRange * maxRange;
-+
-+        for (net.minecraft.server.level.ServerPlayer player : (List<net.minecraft.server.level.ServerPlayer>)this.players()) {
-+            if ((maxRange < 0.0 || player.distanceToSqr(sourceX, sourceY, sourceZ) < maxRangeSquared)) {
-+                if (predicate == null || predicate.test(player)) {
-+                    ret.add(player);
-+                }
-+            }
-+        }
-+
-+        return ret;
-+    }
-+
-+    private net.minecraft.server.level.ServerPlayer getNearestPlayerSlow(@Nullable Entity source, double sourceX, double sourceY,
-+                                                                         double sourceZ, double maxRange, @Nullable Predicate<Entity> predicate) {
-+        net.minecraft.server.level.ServerPlayer closest = null;
-+        double closestRangeSquared = maxRange < 0.0 ? Double.MAX_VALUE : maxRange * maxRange;
-+
-+        for (net.minecraft.server.level.ServerPlayer player : (List<net.minecraft.server.level.ServerPlayer>)this.players()) {
-+            double distanceSquared = player.distanceToSqr(sourceX, sourceY, sourceZ);
-+            if (distanceSquared < closestRangeSquared && (predicate == null || predicate.test(player))) {
-+                closest = player;
-+                closestRangeSquared = distanceSquared;
-+            }
-+        }
-+
-+        return closest;
-+    }
-+
-+
-+    public final net.minecraft.server.level.ServerPlayer getNearestPlayer(@Nullable Entity source, double sourceX, double sourceY,
-+                                                                          double sourceZ, double maxRange, @Nullable Predicate<Entity> predicate) {
-+        LevelChunk chunk;
-+        if (maxRange < 0.0 || maxRange >= net.minecraft.server.level.ChunkMap.GENERAL_AREA_MAP_ACCEPTABLE_SEARCH_RANGE ||
-+            (chunk = (LevelChunk)this.getChunkIfLoadedImmediately(Mth.floor(sourceX) >> 4, Mth.floor(sourceZ) >> 4)) == null) {
-+            return this.getNearestPlayerSlow(source, sourceX, sourceY, sourceZ, maxRange, predicate);
-+        }
-+
-+        return chunk.findNearestPlayer(sourceX, sourceY, sourceZ, maxRange, predicate);
-+    }
-+
-+    @Override
-+    public @Nullable Player getNearestPlayer(double d0, double d1, double d2, double d3, @Nullable Predicate<Entity> predicate) {
-+        return this.getNearestPlayer(null, d0, d1, d2, d3, predicate);
-+    }
-+    // Paper end - optimise checkDespawn
- 
-     public abstract ResourceKey<LevelStem> getTypeKey();
- 
-diff --git a/src/main/java/net/minecraft/world/level/NaturalSpawner.java b/src/main/java/net/minecraft/world/level/NaturalSpawner.java
-index 7bfc95b2a4fd94bcb0347fd7aff9fe0e9b54daf1..9ae2bd64514a83dbd8c22cc35a9ca4c39add5142 100644
---- a/src/main/java/net/minecraft/world/level/NaturalSpawner.java
-+++ b/src/main/java/net/minecraft/world/level/NaturalSpawner.java
-@@ -260,7 +260,7 @@ public final class NaturalSpawner {
-                             blockposition_mutableblockposition.set(l, i, i1);
-                             double d0 = (double) l + 0.5D;
-                             double d1 = (double) i1 + 0.5D;
--                            Player entityhuman = world.getNearestPlayer(d0, (double) i, d1, -1.0D, false);
-+                            Player entityhuman = (chunk instanceof LevelChunk) ? ((LevelChunk)chunk).findNearestPlayer(d0, i, d1, 576.0D, net.minecraft.world.entity.EntitySelector.NO_SPECTATORS) : world.getNearestPlayer(d0, (double) i, d1, -1.0D, false); // Paper - use chunk's player cache to optimize search in range
- 
-                             if (entityhuman != null) {
-                                 double d2 = entityhuman.distanceToSqr(d0, (double) i, d1);
-@@ -334,7 +334,7 @@ public final class NaturalSpawner {
-     }
- 
-     private static boolean isRightDistanceToPlayerAndSpawnPoint(ServerLevel world, ChunkAccess chunk, BlockPos.MutableBlockPos pos, double squaredDistance) {
--        return squaredDistance <= 576.0D ? false : (world.getSharedSpawnPos().closerToCenterThan(new Vec3((double) pos.getX() + 0.5D, (double) pos.getY(), (double) pos.getZ() + 0.5D), 24.0D) ? false : Objects.equals(new ChunkPos(pos), chunk.getPos()) || world.isNaturalSpawningAllowed((BlockPos) pos));
-+        return squaredDistance <= 576.0D ? false : (world.getSharedSpawnPos().closerToCenterThan(new Vec3((double) pos.getX() + 0.5D, (double) pos.getY(), (double) pos.getZ() + 0.5D), 24.0D) ? false : Objects.equals(new ChunkPos(pos), chunk.getPos()) || world.isNaturalSpawningAllowed((BlockPos) pos)); // Paper - diff on change, copy into caller
-     }
- 
-     // Paper start
-diff --git a/src/main/java/net/minecraft/world/level/chunk/LevelChunk.java b/src/main/java/net/minecraft/world/level/chunk/LevelChunk.java
-index 4d052f4cde791100f04b822899f0f436feaa23ea..4ff0d2fc9fd76e92e64abd69f2c9e299aa08ac32 100644
---- a/src/main/java/net/minecraft/world/level/chunk/LevelChunk.java
-+++ b/src/main/java/net/minecraft/world/level/chunk/LevelChunk.java
-@@ -221,6 +221,98 @@ public class LevelChunk extends ChunkAccess {
-         }
-     }
-     // Paper end
-+    // Paper start - optimise checkDespawn
-+    private boolean playerGeneralAreaCacheSet;
-+    private com.destroystokyo.paper.util.misc.PooledLinkedHashSets.PooledObjectLinkedOpenHashSet<net.minecraft.server.level.ServerPlayer> playerGeneralAreaCache;
-+
-+    public com.destroystokyo.paper.util.misc.PooledLinkedHashSets.PooledObjectLinkedOpenHashSet<net.minecraft.server.level.ServerPlayer> getPlayerGeneralAreaCache() {
-+        if (!this.playerGeneralAreaCacheSet) {
-+            this.updateGeneralAreaCache();
-+        }
-+        return this.playerGeneralAreaCache;
-+    }
-+
-+    public void updateGeneralAreaCache() {
-+        this.updateGeneralAreaCache(((ServerLevel)this.level).getChunkSource().chunkMap.playerGeneralAreaMap.getObjectsInRange(this.coordinateKey));
-+    }
-+
-+    public void removeGeneralAreaCache() {
-+        this.playerGeneralAreaCacheSet = false;
-+        this.playerGeneralAreaCache = null;
-+    }
-+
-+    public void updateGeneralAreaCache(com.destroystokyo.paper.util.misc.PooledLinkedHashSets.PooledObjectLinkedOpenHashSet<net.minecraft.server.level.ServerPlayer> value) {
-+        this.playerGeneralAreaCacheSet = true;
-+        this.playerGeneralAreaCache = value;
-+    }
-+
-+    public net.minecraft.server.level.ServerPlayer findNearestPlayer(double sourceX, double sourceY, double sourceZ,
-+                                                                     double maxRange, java.util.function.Predicate<Entity> predicate) {
-+        if (!this.playerGeneralAreaCacheSet) {
-+            this.updateGeneralAreaCache();
-+        }
-+
-+        com.destroystokyo.paper.util.misc.PooledLinkedHashSets.PooledObjectLinkedOpenHashSet<net.minecraft.server.level.ServerPlayer> nearby = this.playerGeneralAreaCache;
-+
-+        if (nearby == null) {
-+            return null;
-+        }
-+
-+        Object[] backingSet = nearby.getBackingSet();
-+        double closestDistance = maxRange < 0.0 ? Double.MAX_VALUE : maxRange * maxRange;
-+        net.minecraft.server.level.ServerPlayer closest = null;
-+        for (int i = 0, len = backingSet.length; i < len; ++i) {
-+            Object _player = backingSet[i];
-+            if (!(_player instanceof net.minecraft.server.level.ServerPlayer)) {
-+                continue;
-+            }
-+            net.minecraft.server.level.ServerPlayer player = (net.minecraft.server.level.ServerPlayer)_player;
-+
-+            double distance = player.distanceToSqr(sourceX, sourceY, sourceZ);
-+            if (distance < closestDistance && predicate.test(player)) {
-+                closest = player;
-+                closestDistance = distance;
-+            }
-+        }
-+
-+        return closest;
-+    }
-+
-+    public void getNearestPlayers(double sourceX, double sourceY, double sourceZ, java.util.function.Predicate<Entity> predicate,
-+                                  double range, java.util.List<net.minecraft.server.level.ServerPlayer> ret) {
-+        if (!this.playerGeneralAreaCacheSet) {
-+            this.updateGeneralAreaCache();
-+        }
-+
-+        com.destroystokyo.paper.util.misc.PooledLinkedHashSets.PooledObjectLinkedOpenHashSet<net.minecraft.server.level.ServerPlayer> nearby = this.playerGeneralAreaCache;
-+
-+        if (nearby == null) {
-+            return;
-+        }
-+
-+        double rangeSquared = range * range;
-+
-+        Object[] backingSet = nearby.getBackingSet();
-+        for (int i = 0, len = backingSet.length; i < len; ++i) {
-+            Object _player = backingSet[i];
-+            if (!(_player instanceof net.minecraft.server.level.ServerPlayer)) {
-+                continue;
-+            }
-+            net.minecraft.server.level.ServerPlayer player = (net.minecraft.server.level.ServerPlayer)_player;
-+
-+            if (range >= 0.0) {
-+                double distanceSquared = player.distanceToSqr(sourceX, sourceY, sourceZ);
-+                if (distanceSquared > rangeSquared) {
-+                    continue;
-+                }
-+            }
-+
-+            if (predicate == null || predicate.test(player)) {
-+                ret.add(player);
-+            }
-+        }
-+    }
-+    // Paper end - optimise checkDespawn
- 
-     public LevelChunk(ServerLevel world, ProtoChunk protoChunk, @Nullable LevelChunk.PostLoadProcessor entityLoader) {
-         this(world, protoChunk.getPos(), protoChunk.getUpgradeData(), protoChunk.unpackBlockTicks(), protoChunk.unpackFluidTicks(), protoChunk.getInhabitedTime(), protoChunk.getSections(), entityLoader, protoChunk.getBlendingData());
diff --git a/patches/server/1032-Optimise-nearby-player-retrieval.patch b/patches/server/1032-Optimise-nearby-player-retrieval.patch
new file mode 100644
index 0000000000..40050b99af
--- /dev/null
+++ b/patches/server/1032-Optimise-nearby-player-retrieval.patch
@@ -0,0 +1,162 @@
+From 0000000000000000000000000000000000000000 Mon Sep 17 00:00:00 2001
+From: Spottedleaf <[email protected]>
+Date: Sat, 23 Sep 2023 23:15:52 -0700
+Subject: [PATCH] Optimise nearby player retrieval
+
+Instead of searching/testing every player online on the server,
+we can instead use the nearby player tracking system to reduce
+the number of tests per search.
+
+diff --git a/src/main/java/net/minecraft/server/level/ServerLevel.java b/src/main/java/net/minecraft/server/level/ServerLevel.java
+index 47e8a6b28960883da868061ed649152ea792c184..f502b01b564bd33c449cbe621966ef4076a38cca 100644
+--- a/src/main/java/net/minecraft/server/level/ServerLevel.java
++++ b/src/main/java/net/minecraft/server/level/ServerLevel.java
+@@ -575,6 +575,115 @@ public class ServerLevel extends Level implements WorldGenLevel {
+         this.lagCompensationTick = (System.nanoTime() - net.minecraft.server.MinecraftServer.SERVER_INIT) / (java.util.concurrent.TimeUnit.MILLISECONDS.toNanos(50L));
+     }
+     // Paper end - lag compensation
++    // Paper start - optimise nearby player retrieval
++    @Override
++    public java.util.List<net.minecraft.world.entity.player.Player> getNearbyPlayers(net.minecraft.world.entity.ai.targeting.TargetingConditions targetPredicate,
++                                                                                     net.minecraft.world.entity.LivingEntity entity,
++                                                                                     net.minecraft.world.phys.AABB box) {
++        return this.getNearbyEntities(Player.class, targetPredicate, entity, box);
++    }
++
++    @Override
++    public Player getNearestPlayer(double x, double y, double z, double maxDistance, @Nullable Predicate<Entity> targetPredicate) {
++        if (maxDistance > 0.0D) {
++            io.papermc.paper.util.player.NearbyPlayers players = this.chunkSource.chunkMap.getNearbyPlayers();
++
++            com.destroystokyo.paper.util.maplist.ReferenceList<ServerPlayer> nearby = players.getPlayersByBlock(
++                io.papermc.paper.util.CoordinateUtils.getBlockCoordinate(x),
++                io.papermc.paper.util.CoordinateUtils.getBlockCoordinate(z),
++                io.papermc.paper.util.player.NearbyPlayers.NearbyMapType.GENERAL
++            );
++
++            if (nearby == null) {
++                return null;
++            }
++
++            ServerPlayer nearest = null;
++            double nearestDist = maxDistance * maxDistance;
++            Object[] rawData = nearby.getRawData();
++            for (int i = 0, len = nearby.size(); i < len; ++i) {
++                ServerPlayer player = (ServerPlayer)rawData[i];
++                double dist = player.distanceToSqr(x, y, z);
++                if (dist >= nearestDist) {
++                    continue;
++                }
++
++                if (targetPredicate == null || targetPredicate.test(player)) {
++                    nearest = player;
++                    nearestDist = dist;
++                }
++            }
++
++            return nearest;
++        } else {
++            ServerPlayer nearest = null;
++            double nearestDist = Double.MAX_VALUE;
++
++            for (ServerPlayer player : this.players()) {
++                double dist = player.distanceToSqr(x, y, z);
++                if (dist >= nearestDist) {
++                    continue;
++                }
++
++                if (targetPredicate == null || targetPredicate.test(player)) {
++                    nearest = player;
++                    nearestDist = dist;
++                }
++            }
++
++            return nearest;
++        }
++    }
++
++    @Override
++    public Player getNearestPlayer(net.minecraft.world.entity.ai.targeting.TargetingConditions targetPredicate, LivingEntity entity) {
++        return this.getNearestPlayer(targetPredicate, entity, entity.getX(), entity.getY(), entity.getZ());
++    }
++
++    @Override
++    public Player getNearestPlayer(net.minecraft.world.entity.ai.targeting.TargetingConditions targetPredicate, LivingEntity entity,
++                                   double x, double y, double z) {
++        double range = targetPredicate.range;
++        if (range > 0.0D) {
++            io.papermc.paper.util.player.NearbyPlayers players = this.chunkSource.chunkMap.getNearbyPlayers();
++
++            com.destroystokyo.paper.util.maplist.ReferenceList<ServerPlayer> nearby = players.getPlayersByBlock(
++                io.papermc.paper.util.CoordinateUtils.getBlockCoordinate(x),
++                io.papermc.paper.util.CoordinateUtils.getBlockCoordinate(z),
++                io.papermc.paper.util.player.NearbyPlayers.NearbyMapType.GENERAL
++            );
++
++            if (nearby == null) {
++                return null;
++            }
++
++            ServerPlayer nearest = null;
++            double nearestDist = Double.MAX_VALUE;
++            Object[] rawData = nearby.getRawData();
++            for (int i = 0, len = nearby.size(); i < len; ++i) {
++                ServerPlayer player = (ServerPlayer)rawData[i];
++                double dist = player.distanceToSqr(x, y, z);
++                if (dist >= nearestDist) {
++                    continue;
++                }
++
++                if (targetPredicate.test(entity, player)) {
++                    nearest = player;
++                    nearestDist = dist;
++                }
++            }
++
++            return nearest;
++        } else {
++            return this.getNearestEntity(this.players(), targetPredicate, entity, x, y, z);
++        }
++    }
++
++    @Nullable
++    public Player getNearestPlayer(net.minecraft.world.entity.ai.targeting.TargetingConditions targetPredicate, double x, double y, double z) {
++        return this.getNearestPlayer(targetPredicate, null, x, y, z);
++    }
++    // Paper end - optimise nearby player retrieval
+ 
+     // Add env and gen to constructor, IWorldDataServer -> WorldDataServer
+     public ServerLevel(MinecraftServer minecraftserver, Executor executor, LevelStorageSource.LevelStorageAccess convertable_conversionsession, PrimaryLevelData iworlddataserver, ResourceKey<Level> resourcekey, LevelStem worlddimension, ChunkProgressListener worldloadlistener, boolean flag, long i, List<CustomSpawner> list, boolean flag1, @Nullable RandomSequences randomsequences, org.bukkit.World.Environment env, org.bukkit.generator.ChunkGenerator gen, org.bukkit.generator.BiomeProvider biomeProvider) {
+diff --git a/src/main/java/net/minecraft/world/entity/ai/targeting/TargetingConditions.java b/src/main/java/net/minecraft/world/entity/ai/targeting/TargetingConditions.java
+index 58422f00c7d64dbd1cf6d7211c9838875cbe7778..c157309ac78e7af084d3acb6e8b2bcd469a39d5e 100644
+--- a/src/main/java/net/minecraft/world/entity/ai/targeting/TargetingConditions.java
++++ b/src/main/java/net/minecraft/world/entity/ai/targeting/TargetingConditions.java
+@@ -10,7 +10,7 @@ public class TargetingConditions {
+     public static final TargetingConditions DEFAULT = forCombat();
+     private static final double MIN_VISIBILITY_DISTANCE_FOR_INVISIBLE_TARGET = 2.0D;
+     private final boolean isCombat;
+-    private double range = -1.0D;
++    public double range = -1.0D; // Paper - public
+     private boolean checkLineOfSight = true;
+     private boolean testInvisible = true;
+     @Nullable
+diff --git a/src/main/java/net/minecraft/world/level/EntityGetter.java b/src/main/java/net/minecraft/world/level/EntityGetter.java
+index b3293a722fb5c5262a777402140c764c03367800..aaa07fcd4b32fe0de88142ab30378327a01f1729 100644
+--- a/src/main/java/net/minecraft/world/level/EntityGetter.java
++++ b/src/main/java/net/minecraft/world/level/EntityGetter.java
+@@ -230,9 +230,13 @@ public interface EntityGetter {
+         T livingEntity = null;
+ 
+         for(T livingEntity2 : entityList) {
++            // Paper start - move up
++            // don't check entities outside closest range
++            double e = livingEntity2.distanceToSqr(x, y, z);
++            if (d == -1.0D || e < d) {
++            // Paper end - move up
+             if (targetPredicate.test(entity, livingEntity2)) {
+-                double e = livingEntity2.distanceToSqr(x, y, z);
+-                if (d == -1.0D || e < d) {
++                // Paper - move up
+                     d = e;
+                     livingEntity = livingEntity2;
+                 }