From 0000000000000000000000000000000000000000 Mon Sep 17 00:00:00 2001
From: Spottedleaf <Spottedleaf@users.noreply.github.com>
Date: Wed, 15 Apr 2020 18:08:53 -0700
Subject: [PATCH] Optimise entity hard collision checking

Very few entities actually hard collide, so store them in their own
entity slices and provide a special getEntites type call just for them.
This reduces entity collision checking impact (in my testing) by 25%
for crammed entities (shove 130 cows into an 8x6 area in one chunk).
Less crammed entities are likely to show significantly less benefit.
Effectively, this patch optimises crammed entity situations.

diff --git a/src/main/java/net/minecraft/server/Chunk.java b/src/main/java/net/minecraft/server/Chunk.java
index 3bcd63a754538ccfc5965207a8fc79faa31925c0..dface62144bb230c576e9eafad1016d19d211118 100644
--- a/src/main/java/net/minecraft/server/Chunk.java
+++ b/src/main/java/net/minecraft/server/Chunk.java
@@ -91,6 +91,56 @@ public class Chunk implements IChunkAccess {
     private final int[] inventoryEntityCounts = new int[16];
     // Paper end
 
+    // Tuinity start - optimise hard collision handling
+    final com.destroystokyo.paper.util.maplist.EntityList[] hardCollidingEntities = new com.destroystokyo.paper.util.maplist.EntityList[16];
+
+    {
+        for (int i = 0, len = this.hardCollidingEntities.length; i < len; ++i) {
+            this.hardCollidingEntities[i] = new com.destroystokyo.paper.util.maplist.EntityList();
+        }
+    }
+
+    public final void getHardCollidingEntities(@Nullable Entity entity, AxisAlignedBB axisalignedbb, List<Entity> into, Predicate<Entity> predicate) {
+        // copied from getEntities
+        int min = MathHelper.floor((axisalignedbb.minY - 2.0D) / 16.0D);
+        int max = MathHelper.floor((axisalignedbb.maxY + 2.0D) / 16.0D);
+
+        min = MathHelper.clamp(min, 0, this.hardCollidingEntities.length - 1);
+        max = MathHelper.clamp(max, 0, this.hardCollidingEntities.length - 1);
+
+        for (int k = min; k <= max; ++k) {
+            com.destroystokyo.paper.util.maplist.EntityList entityList = this.hardCollidingEntities[k];
+            Entity[] entities = entityList.getRawData();
+
+            for (int i = 0, len = entityList.size(); i < len; ++i) {
+                Entity entity1 = entities[i];
+                if (entity1.shouldBeRemoved) continue; // Paper
+
+                if (entity1 != entity && entity1.getBoundingBox().intersects(axisalignedbb)) {
+                    if (predicate == null || predicate.test(entity1)) {
+                        into.add(entity1);
+                    }
+
+                    if (!(entity1 instanceof EntityEnderDragon)) {
+                        continue;
+                    }
+
+                    EntityComplexPart[] aentitycomplexpart = ((EntityEnderDragon)entity1).children;
+                    int l = aentitycomplexpart.length;
+
+                    for (int i1 = 0; i1 < l; ++i1) {
+                        EntityComplexPart entitycomplexpart = aentitycomplexpart[i1];
+
+                        if (entitycomplexpart != entity && entitycomplexpart.getBoundingBox().intersects(axisalignedbb) && (predicate == null || predicate.test(entitycomplexpart))) {
+                            into.add(entitycomplexpart);
+                        }
+                    }
+                }
+            }
+        }
+    }
+    // Tuinity end - optimise hard collision handling
+
     public Chunk(World world, ChunkCoordIntPair chunkcoordintpair, BiomeStorage biomestorage, ChunkConverter chunkconverter, TickList<Block> ticklist, TickList<FluidType> ticklist1, long i, @Nullable ChunkSection[] achunksection, @Nullable Consumer<Chunk> consumer) {
         this.sections = new ChunkSection[16];
         this.e = Maps.newHashMap();
@@ -595,7 +645,7 @@ public class Chunk implements IChunkAccess {
         entity.chunkY = k;
         entity.chunkZ = this.loc.z;
         this.entities.add(entity); // Paper - per chunk entity list
-        this.entitySlices[k].add(entity);
+        this.entitySlices[k].add(entity); if (entity.hardCollides()) this.hardCollidingEntities[k].add(entity); // Tuinity - optimise hard colliding entities
         // Paper start
         if (entity instanceof EntityItem) {
             itemCounts[k]++;
@@ -633,7 +683,7 @@ public class Chunk implements IChunkAccess {
             entity.entitySlice = null;
             entity.inChunk = false;
         }
-        if (!this.entitySlices[i].remove(entity)) {
+        if (entity.hardCollides()) this.hardCollidingEntities[i].remove(entity); if (!this.entitySlices[i].remove(entity)) { // Tuinity - optimise hard colliding entities
             return;
         }
         if (entity instanceof EntityItem) {
diff --git a/src/main/java/net/minecraft/server/Entity.java b/src/main/java/net/minecraft/server/Entity.java
index 32dadb91a30b67202a463cf5c9abc998efecad80..4c67a767e65b8a76c5f5a267d0b4ddf28494bc55 100644
--- a/src/main/java/net/minecraft/server/Entity.java
+++ b/src/main/java/net/minecraft/server/Entity.java
@@ -230,6 +230,41 @@ public abstract class Entity implements INamableTileEntity, ICommandListener, Ke
     }
     // Paper end - optimise entity tracking
 
+    // Tuinity start
+    /**
+     * Overriding this field will cause memory leaks.
+     */
+    private final boolean hardCollides;
+
+    private static final java.util.Map<Class<? extends Entity>, Boolean> cachedOverrides = java.util.Collections.synchronizedMap(new java.util.WeakHashMap<>());
+    {
+        Boolean hardCollides = cachedOverrides.get(this.getClass());
+        if (hardCollides == null) {
+            try {
+                java.lang.reflect.Method getHardCollisionBoxEntityMethod = Entity.class.getMethod("j", Entity.class);
+                java.lang.reflect.Method hasHardCollisionBoxMethod = Entity.class.getMethod("aZ");
+                if (!this.getClass().getMethod(hasHardCollisionBoxMethod.getName(), hasHardCollisionBoxMethod.getParameterTypes()).equals(hasHardCollisionBoxMethod)
+                        || !this.getClass().getMethod(getHardCollisionBoxEntityMethod.getName(), getHardCollisionBoxEntityMethod.getParameterTypes()).equals(getHardCollisionBoxEntityMethod)) {
+                    hardCollides = Boolean.TRUE;
+                } else {
+                    hardCollides = Boolean.FALSE;
+                }
+                cachedOverrides.put(this.getClass(), hardCollides);
+            }
+            catch (ThreadDeath thr) { throw thr; }
+            catch (Throwable thr) {
+                // shouldn't happen, just explode
+                throw new RuntimeException(thr);
+            }
+        }
+        this.hardCollides = hardCollides.booleanValue();
+    }
+
+    public final boolean hardCollides() {
+        return this.hardCollides;
+    }
+    // Tuinity end
+
     public Entity(EntityTypes<?> entitytypes, World world) {
         this.id = Entity.entityCount.incrementAndGet();
         this.passengers = Lists.newArrayList();
@@ -2002,11 +2037,11 @@ public abstract class Entity implements INamableTileEntity, ICommandListener, Ke
         return EnumInteractionResult.PASS;
     }
 
-    public boolean j(Entity entity) {
+    public boolean j(Entity entity) { // Tuinity - diff on change, hard colliding entities override this
         return entity.aZ() && !this.isSameVehicle(entity);
     }
 
-    public boolean aZ() {
+    public boolean aZ() {// Tuinity - diff on change, hard colliding entities override this
         return false;
     }
 
diff --git a/src/main/java/net/minecraft/server/IEntityAccess.java b/src/main/java/net/minecraft/server/IEntityAccess.java
index 2639c17b7f6100533f33124f9e49990cd303d161..b053bb74f6df174a27dbfd7b1b3e3ccbb0b26659 100644
--- a/src/main/java/net/minecraft/server/IEntityAccess.java
+++ b/src/main/java/net/minecraft/server/IEntityAccess.java
@@ -55,16 +55,25 @@ public interface IEntityAccess {
         return this.b(oclass, axisalignedbb, IEntitySelector.g);
     }
 
+    // Tuinity start - optimise hard collision
+    /**
+     * Not guaranteed to only return hard colliding entities
+     */
+    default List<Entity> getHardCollidingEntities(@Nullable Entity entity, AxisAlignedBB axisalignedbb, Predicate<Entity> predicate) {
+        return this.getEntities(entity, axisalignedbb, predicate);
+    }
+    // Tuinity end - optimise hard collision
+
     default Stream<VoxelShape> c(@Nullable Entity entity, AxisAlignedBB axisalignedbb, Predicate<Entity> predicate) {
         if (axisalignedbb.a() < 1.0E-7D) {
             return Stream.empty();
         } else {
             AxisAlignedBB axisalignedbb1 = axisalignedbb.g(1.0E-7D);
 
-            return this.getEntities(entity, axisalignedbb1, predicate.and((entity1) -> {
+            predicate = predicate.and((entity1) -> { // Tuinity - optimise entity hard collisions
                 boolean flag;
 
-                if (entity1.getBoundingBox().c(axisalignedbb1)) {
+                if (true || entity1.getBoundingBox().c(axisalignedbb1)) { // Tuinity - always true, wtf did they think this.getEntities(entity, axisalignedbb1) does?
                     label25:
                     {
                         if (entity == null) {
@@ -82,7 +91,7 @@ public interface IEntityAccess {
 
                 flag = false;
                 return flag;
-            })).stream().map(Entity::getBoundingBox).map(VoxelShapes::a);
+            }); return ((entity != null && entity.hardCollides()) ? this.getEntities(entity, axisalignedbb1, predicate) : this.getHardCollidingEntities(entity, axisalignedbb1, predicate)).stream().map(Entity::getBoundingBox).map(VoxelShapes::a); // Tuinity - optimise entity hard collisions
         }
     }
 
diff --git a/src/main/java/net/minecraft/server/World.java b/src/main/java/net/minecraft/server/World.java
index 165b8e20ab090284b7c70b5cc9c0d58242400b54..15617d20883030b240014dbb258fd0086fef4235 100644
--- a/src/main/java/net/minecraft/server/World.java
+++ b/src/main/java/net/minecraft/server/World.java
@@ -1084,6 +1084,35 @@ public abstract class World implements GeneratorAccess, AutoCloseable {
         return this.getChunkAt(i, j, ChunkStatus.FULL, false);
     }
 
+    // Tuinity start - optimise hard collision handling
+    @Override
+    public List<Entity> getHardCollidingEntities(@Nullable Entity entity, AxisAlignedBB axisalignedbb, Predicate<Entity> predicate) {
+        return this.getHardCollidingEntities(entity, axisalignedbb, predicate, Lists.newArrayList());
+    }
+
+    public List<Entity> getHardCollidingEntities(@Nullable Entity entity, AxisAlignedBB axisalignedbb, Predicate<Entity> predicate, List<Entity> list) {
+        // copied from below
+        int i = MathHelper.floor((axisalignedbb.minX - 2.0D) / 16.0D);
+        int j = MathHelper.floor((axisalignedbb.maxX + 2.0D) / 16.0D);
+        int k = MathHelper.floor((axisalignedbb.minZ - 2.0D) / 16.0D);
+        int l = MathHelper.floor((axisalignedbb.maxZ + 2.0D) / 16.0D);
+
+        ChunkProviderServer chunkProvider = ((WorldServer)this).getChunkProvider();
+
+        for (int i1 = i; i1 <= j; ++i1) {
+            for (int j1 = k; j1 <= l; ++j1) {
+                Chunk chunk = chunkProvider.getChunkAtIfLoadedMainThread(i1, j1);
+
+                if (chunk != null) {
+                    chunk.getHardCollidingEntities(entity, axisalignedbb, list, predicate);
+                }
+            }
+        }
+
+        return list;
+    }
+    // Tuinity end - optimise hard collision handling
+
     @Override
     public List<Entity> getEntities(@Nullable Entity entity, AxisAlignedBB axisalignedbb, @Nullable Predicate<? super Entity> predicate) {
         this.getMethodProfiler().c("getEntities");
