Minecraft里的射线与方块碰撞检测算法

朱雀 2022-07-15 01:07 371阅读 0赞

觉得挺有用的就自己花时间研究了下，手动做了反混淆，顺便去掉了一些无用代码

这个函数在Minecraft中很多地方都用到了，比如判断鼠标正指向哪个方块哪个面，还有判断射出去的箭是否撞到了方块

这个函数返回从起始点到结束点这条射线碰撞到的第一个方块

// 参数：起始点，结束点，不忽略液体，忽略非固体方块
        public MovingObjectPosition rayTraceBlocks_do_do(Vec3 start, Vec3 end, boolean fluid, boolean noNonSolid)
        {
            if (!Double.isNaN(start.xCoord) && !Double.isNaN(start.yCoord) && !Double.isNaN(start.zCoord))
            {
                if (!Double.isNaN(end.xCoord) && !Double.isNaN(end.yCoord) && !Double.isNaN(end.zCoord))
                {
                    // 终点方块坐标
                    int intX2 = MathHelper.floor_double(end.xCoord);
                    int intY2 = MathHelper.floor_double(end.yCoord);
                    int intZ2 = MathHelper.floor_double(end.zCoord);
                    // 起点(当前)方块坐标
                    int intX1 = MathHelper.floor_double(start.xCoord);
                    int intY1 = MathHelper.floor_double(start.yCoord);
                    int intZ1 = MathHelper.floor_double(start.zCoord);
      
                    // 检测起点方块
                    int id = this.getBlockId(intX1, intY1, intZ1);
                    int data = this.getBlockMetadata(intX1, intY1, intZ1);
                    Block block = Block.blocksList[id];
      
                    if (block != null && (!noNonSolid || block == null || block.getCollisionBoundingBoxFromPool(this, intX1, intY1, intZ1) != null) && id > 0 && block.canCollideCheck(data, fluid))
                    {
                        MovingObjectPosition movingobjectposition = block.collisionRayTrace(this, intX1, intY1, intZ1, start, end);
      
                        if (movingobjectposition != null)
                        {
                            return movingobjectposition;
                        }
                    }
      
                    id = 200; // 最多检测201个方块
      
                    while (id-- >= 0)
                    {
                        if (Double.isNaN(start.xCoord) || Double.isNaN(start.yCoord) || Double.isNaN(start.zCoord))
                        {
                            return null;
                        }
                        // 检测了终点方块
                        if (intX1 == intX2 && intY1 == intY2 && intZ1 == intZ2)
                        {
                            return null;
                        }
      
                        // 起点(当前)方块和终点方块XYZ不同(向某方向选了候选方块)
                        boolean Xchanged = true;
                        boolean Ychanged = true;
                        boolean Zchanged = true;
                        // 各方向候选方块坐标
                        double newX;
                        double newY;
                        double newZ;
      
                        // 尝试向X方向选候选方块
                        if (intX2 > intX1)
                        {
                            newX = (double)intX1 + 1.0D;
                        }
                        else if (intX2 < intX1)
                        {
                            newX = (double)intX1;
                        }
                        else
                        {
                            Xchanged = false;
                        }
      
                        if (intY2 > intY1)
                        {
                            newY = (double)intY1 + 1.0D;
                        }
                        else if (intY2 < intY1)
                        {
                            newY = (double)intY1;
                        }
                        else
                        {
                            Ychanged = false;
                        }
      
                        if (intZ2 > intZ1)
                        {
                            newZ = (double)intZ1 + 1.0D;
                        }
                        else if (intZ2 < intZ1)
                        {
                            newZ = (double)intZ1;
                        }
                        else
                        {
                            Zchanged = false;
                        }
      
                        // 各方向候选方块离起点(当前)有多近，初始化为很大的数
                        double Xt = 999.0D;
                        double Yt = 999.0D;
                        double Zt = 999.0D;
                        double dX = end.xCoord - start.xCoord;
                        double dY = end.yCoord - start.yCoord;
                        double dZ = end.zCoord - start.zCoord;
      
                        // 向X方向选了候选方块
                        if (Xchanged)
                        {
                            Xt = (newX - start.xCoord) / dX;
                        }
      
                        if (Ychanged)
                        {
                            Yt = (newY - start.yCoord) / dY;
                        }
      
                        if (Zchanged)
                        {
                            Zt = (newZ - start.zCoord) / dZ;
                        }
      
                        // 最终选了哪个方向的候选方块
                        byte direction;
      
                        // 选出候选方块中离起点(当前)最近的，更新起点、要检测的方块坐标
                        if (Xt < Yt && Xt < Zt)
                        {
                            if (intX2 > intX1)
                            {
                                direction = 4;
                            }
                            else
                            {
                                direction = 5;
                            }
      
                            start.xCoord = newX;
                            start.yCoord += dY * Xt;
                            start.zCoord += dZ * Xt;
                        }
                        else if (Yt < Zt)
                        {
                            if (intY2 > intY1)
                            {
                                direction = 0;
                            }
                            else
                            {
                                direction = 1;
                            }
      
                            start.xCoord += dX * Yt;
                            start.yCoord = newY;
                            start.zCoord += dZ * Yt;
                        }
                        else
                        {
                            if (intZ2 > intZ1)
                            {
                                direction = 2;
                            }
                            else
                            {
                                direction = 3;
                            }
      
                            start.xCoord += dX * Zt;
                            start.yCoord += dY * Zt;
                            start.zCoord = newZ;
                        }
      
                        intX1 = MathHelper.floor_double(start.xCoord);
      
                        if (direction == 5) // X-方向
                        {
                            // MC以方块内各轴最小坐标为方块坐标，这里得到的是X上最大坐标所以要-1
                            --intX1;
                        }
      
                        intY1 = MathHelper.floor_double(start.yCoord);
      
                        if (direction == 1) // Y-方向
                        {
                            --intY1;
                        }
      
                        intZ1 = MathHelper.floor_double(start.zCoord);
      
                        if (direction == 3) // Z-方向
                        {
                            --intZ1;
                        }
      
                        // 检测新起点方块
                        int id2 = this.getBlockId(intX1, intY1, intZ1);
                        int data2 = this.getBlockMetadata(intX1, intY1, intZ1);
                        Block block2 = Block.blocksList[id2];
      
                        if ((!noNonSolid || block2 == null || block2.getCollisionBoundingBoxFromPool(this, intX1, intY1, intZ1) != null) && id2 > 0 && block2.canCollideCheck(data2, fluid))
                        {
                            MovingObjectPosition movingobjectposition1 = block2.collisionRayTrace(this, intX1, intY1, intZ1, start, end);
      
                            if (movingobjectposition1 != null)
                            {
                                return movingobjectposition1;
                            }
                        }
                    }
      
                    return null;
                }
                else
                {
                    return null;
                }
            }
            else
            {
                return null;
            }
        }

与一个方块的碰撞检测函数

// 一个从start到end的射线与一个方块碰撞检测，参数：世界，方块坐标，开始点，结束点
        /**
         * Ray traces through the blocks collision from start vector to end vector returning a ray trace hit. Args: world,
         * x, y, z, startVec, endVec
         */
        public MovingObjectPosition collisionRayTrace(World world, int X, int Y, int Z, Vec3 start, Vec3 end)
        {
            this.setBlockBoundsBasedOnState(world, X, Y, Z);
            // 以方块为原点
            start = start.addVector((double)(-X), (double)(-Y), (double)(-Z));
            end = end.addVector((double)(-X), (double)(-Y), (double)(-Z));
            // 计算start到end与方块各平面交点
            Vec3 YZ1 = start.getIntermediateWithXValue(end, this.minX);
            Vec3 YZ2 = start.getIntermediateWithXValue(end, this.maxX);
            Vec3 XZ1 = start.getIntermediateWithYValue(end, this.minY);
            Vec3 XZ2 = start.getIntermediateWithYValue(end, this.maxY);
            Vec3 XY1 = start.getIntermediateWithZValue(end, this.minZ);
            Vec3 XY2 = start.getIntermediateWithZValue(end, this.maxZ);
      
            // 交点不在碰撞盒内
            if (!this.isVecInsideYZBounds(YZ1))
            {
                YZ1 = null;
            }
      
            if (!this.isVecInsideYZBounds(YZ2))
            {
                YZ2 = null;
            }
      
            if (!this.isVecInsideXZBounds(XZ1))
            {
                XZ1 = null;
            }
      
            if (!this.isVecInsideXZBounds(XZ2))
            {
                XZ2 = null;
            }
      
            if (!this.isVecInsideXYBounds(XY1))
            {
                XY1 = null;
            }
      
            if (!this.isVecInsideXYBounds(XY2))
            {
                XY2 = null;
            }
      
            Vec3 hitPoint = null;
      
            // 选出最近的碰撞点
            if (YZ1 != null && (hitPoint == null || start.squareDistanceTo(YZ1) < start.squareDistanceTo(hitPoint)))
            {
                hitPoint = YZ1;
            }
      
            if (YZ2 != null && (hitPoint == null || start.squareDistanceTo(YZ2) < start.squareDistanceTo(hitPoint)))
            {
                hitPoint = YZ2;
            }
      
            if (XZ1 != null && (hitPoint == null || start.squareDistanceTo(XZ1) < start.squareDistanceTo(hitPoint)))
            {
                hitPoint = XZ1;
            }
      
            if (XZ2 != null && (hitPoint == null || start.squareDistanceTo(XZ2) < start.squareDistanceTo(hitPoint)))
            {
                hitPoint = XZ2;
            }
      
            if (XY1 != null && (hitPoint == null || start.squareDistanceTo(XY1) < start.squareDistanceTo(hitPoint)))
            {
                hitPoint = XY1;
            }
      
            if (XY2 != null && (hitPoint == null || start.squareDistanceTo(XY2) < start.squareDistanceTo(hitPoint)))
            {
                hitPoint = XY2;
            }
      
            // 不碰撞
            if (hitPoint == null)
            {
                return null;
            }
            else
            {
                // start到end都在碰撞盒内为-1
                byte direction = -1;
      
                // 与哪个面碰撞
                if (hitPoint == YZ1)
                {
                    direction = 4;
                }
      
                if (hitPoint == YZ2)
                {
                    direction = 5;
                }
      
                if (hitPoint == XZ1)
                {
                    direction = 0;
                }
      
                if (hitPoint == XZ2)
                {
                    direction = 1;
                }
      
                if (hitPoint == XY1)
                {
                    direction = 2;
                }
      
                if (hitPoint == XY2)
                {
                    direction = 3;
                }
      
                return new MovingObjectPosition(X, Y, Z, direction, hitPoint.addVector((double)X, (double)Y, (double)Z));
            }
        }

与一个面的碰撞检测函数

// 取该点到end点之间与某YZ平面交点
        /**
         * Returns a new vector with x value equal to the second parameter, along the line between this vector and the
         * passed in vector, or null if not possible.
         */
        public Vec3 getIntermediateWithXValue(Vec3 end, double X)
        {
            double dX = end.xCoord - this.xCoord;
            double dY = end.yCoord - this.yCoord;
            double dZ = end.zCoord - this.zCoord;
      
            // 与YZ平面平行
            if (dX * dX < 1.0000000116860974E-7D)
            {
                return null;
            }
            else
            {
                double scale = (X - this.xCoord) / dX;
                // 交点在该点和end点之间
                return scale >= 0.0D && scale <= 1.0D ? this.myVec3LocalPool.getVecFromPool(this.xCoord + dX * scale, this.yCoord + dY * scale, this.zCoord + dZ * scale) : null;
            }
        }

![20161027184909287][]

举个2D的例子，可以推广到3D

起始点是(0.5, 1.75)，结束点是(1.75, 0.75)

intXY2 = 1, 0(方块3)

intXY1 = 0, 1(方块1)

开始时检测起点方块(0, 1)(方块1)

\--循环---------------------

向X方向和Y方向选候选方块：

newX = 0 + 1 = 1(代表A点X坐标)

newY = 1(代表B点Y坐标)

dX = 1.75 - 0.5 = 1.25

dY = 0.75 - 1.75 = -1