Solved Getting block amount between 2 coordinates (any version)

Discussion in 'Spigot Plugin Development' started by MiMiMiEnot, Jul 3, 2021.

  1. I have 2 coordinates, which say, a corners of Parallelepiped. I need to get amount of blocks between that corners.

    I know:
    x1, x2, y1, y2, z1, z2 coordinates of corners.
    I need:
    amount of blocks between them

    The simple way is to get a length of sides and multiply them (absolute values). That method works, but are some slow. Work code is:
    Code (Java):
    public static int getBlocksBetween(Corner corner1, Corner corner2) {
            return (int) (abs(corner1.getX() - corner2.getX()) * abs(corner1.getY() - corner2.getY()) * abs(corner1.getZ() - corner2.getZ()));
        }
    But, if i know the coordinates of corners I can to get vectors and work with them. To do that I need to get determinant of matrix, where first line - first vector coordinates, second - second, third - third. I do that, and that work... but not at any case.

    I create two methods for that

    Code (Java):
    //  vector1(corner2.x - corner1.x, corner1.y, corner1.z)
            //  vector2(corner1.x, corner2.y - corner1.y, corner1.z)
            //  vector3(corner1.x, corner1.y, corner2.z - corner1.z)
            //      | vector1.x vector1.y vector1.z |
            //  x = | vector2.x vector2.y vector2.z | =
            //      | vector3.x vector3.y vector3.z |
            //  = vector1.x * ((vector2.y * vector3.z) - (vector2.z * vector3.y)) -
            //  - vector1.y * ((vector2.x * vector3.z) - (vector2.z * vector3.x)) +
            //  + vector1.z * ((vector2.x * vector3.y) - (vector2.y * vector3.x))
            //  _______________________________________________________________
            //  x = (vector1.x * vector2.y * vector3.z) + (vector2.x * vector3.x * vector1.z) + (vector1.y * vector2.z * vector3.x)
            //      - (vector1.z * vector2.y * vector3.x) - (vector1.y * vector2.x * vector3.z) - (vector3.y * vector2.z * vector1.x)
            int[][] v = {
                    {
                            corner2.getX() - corner1.getX(),
                            corner1.getY(),
                            corner1.getZ()
                    },
                    {
                            corner1.getX(),
                            corner2.getY() - corner1.getY(),
                            corner1.getZ()
                    },
                    {
                            corner1.getX(),
                            corner1.getY(),
                            corner2.getZ() - corner1.getZ()
                    }
            };
            return v[0][0] * ((v[1][1] * v[2][2]) - (v[1][2] * v[2][1]))
                    - (v[0][1] * ((v[1][0] * v[2][2]) - (v[1][2] * v[2][0]))
                    + (v[0][2] * ((v[1][0] * v[2][1]) - (v[1][1] * v[2][0]))));
    Code (Text):
    //  vector1(corner2.x - corner1.x, corner1.y, corner1.z)
            //  vector2(corner1.x, corner2.y - corner1.y, corner1.z)
            //  vector3(corner1.x, corner1.y, corner2.z - corner1.z)
            //      | vector1.x vector1.y vector1.z |
            //  x = | vector2.x vector2.y vector2.z | =
            //      | vector3.x vector3.y vector3.z |
            //  = (vector1.x * vector2.y * vector3.z) + (vector2.x * vector3.y * vector1.z) + (vector1.y * vector2.z * vector3.x)
            //    - (vector1.z * vector2.y * vector3.x) - (vector1.y * vector2.x * vector3.z) - (vector3.y * vector2.z * vector1.x)
            int[][] v = {
                    {
                            corner1.getX() - corner2.getX(),
                            corner1.getY(),
                            corner1.getZ()
                    },
                    {
                            corner1.getX(),
                            corner1.getY() - corner2.getY(),
                            corner1.getZ()
                    },
                  {
                            corner1.getX(),
                            corner1.getY(),
                            corner1.getZ() - corner2.getZ()
                    }
            };
            return (v[0][0] * v[1][1] * v[2][2]) + (v[1][0] * v[2][1] * v[0][2]) + (v[0][1] * v[1][2] * v[2][0]) -
                    (v[0][2] * v[1][1] * v[2][0]) - (v[0][1] * v[1][0] * v[2][2]) - (v[2][1] * v[1][2] * v[0][0]);
    Difference of methods are only at method of find of determinant, different methods of 3x3 matrix determinant.

    That methods are quickly, but not at every case there give correct answer. Some tests:
    If corner1(x = 0, y = 0, z = 0), corner2(x = 10, y = 10, z = 10) - all methods give write answer (1000 volume), but if corner1(x = 3, y = 3, z = 3), corner2(x = 4, y = 4, z = 4) - only first method give write answer (1).

    Testing results (at "()" are difference at nanos before calling an method and after, please do not pay attention about negative, that`s easy to fix):
    1000(560700)
    1000(3900)
    -1000(2000)

    1(495900)
    -8(3200)
    80(2100)
    (test methods are at the same order as I write their code, first line - first method what works at any case)

    Problem at method of finding a determinant? Help, or give where I can reed about that.
     
  2. My Function
    Code (Java):

    int getBlocks(Location loc1, Location loc2, boolean includeAir){
            int startX = (loc1.getBlockX() < loc2.getBlockX())?loc1.getBlockX() : loc2.getBlockX();
            int startY = (loc1.getBlockY() < loc2.getBlockY())?loc1.getBlockY() : loc2.getBlockY();
            int startZ = (loc1.getBlockZ() < loc2.getBlockZ())?loc1.getBlockZ() : loc2.getBlockZ();
            int endX = (loc1.getBlockX() < loc2.getBlockX())?loc2.getBlockX() : loc1.getBlockX();
            int endY = (loc1.getBlockY() < loc2.getBlockY())?loc2.getBlockY() : loc1.getBlockY();
            int endZ = (loc1.getBlockZ() < loc2.getBlockZ())?loc2.getBlockZ() : loc1.getBlockZ();

            int count = 0;
            for(int x = startX; x <= endX; x++) {
                for(int y = startY; y <= endY; y++) {
                    for(int z = startZ; z <= endZ; z++) {
                        boolean isAir = loc1.getWorld().getBlockAt(x, y, z).getType().equals(Material.AIR);
                            if(!isAir)
                                count++;
                            else
                                if(includeAir)
                                    count++;
                    }
                }
            }
            return count;
        }
    }
     
  3. Math.max. isAir = getBlock().getType()isAir(). if (!isAir || includeAir)
     
  4. Are you sure tihs is slow? As far as I know, math is always the fastest solution
     
  5. Calculate every x, y and z like: x = x1 - x2, if result is negative, then multiply it with -1, then, multiply x with y and z and you have the volume, the number of blocks between corners :D
     
  6. I test by difference between nanoseconds before call function and after. I understood, that difference is so small to see by human, but when we need to do that a lot of times - I need best performance what I can.


    You interate all blocks, that are a lot of iterations, I don`t need that. I need to calculate volume of parallelepiped to get amount of blocks, and math has methods for that, I only don`t understand problem with calculations.


    When I get 3dimension coordinates ('vectors') I can`t change their coordinates (for find a volume I need to get vectors of 3 sides). If I get corners first(-10; 10; -10) and second (10; -10; 10) I cant reverse their Y coordinates (second coordinate), because that change their coordinates (position at world), and if at that example that not change something - at some case that will produce not right calculations. Of course we can change Basis to get some change at coordinates, but I think, that will be slowest, if I would transform every time basis (another calculations, and hardest material of math)

    Maybe, I need to play with Max and Min values, but we have matrix way to get volume of cubic figure, so that shoud work, formula for that are only one, I try to search, but I can`t find additional requirements for some cases, so formula must work at any case, at real numbers at all.
     
    #6 MiMiMiEnot, Jul 13, 2021
    Last edited: Jul 13, 2021
  7. About my ecuation, I was wrong, first you need to check if x, y or z are < 0, if true, multiply with -1 to be positive, then add x with x, y with y and z with z, then multiply x with y and z

    EDIT: it's just a volume of a cuboid shape, nothing so complicated

    EDIT 2: I'm dumb, I was right at first, you need to reduce not to add, so if you have -10 and 10 is -10 -10 which is -20, multiply with -1 and will be 20
     
  8. Well, if you really care about performance, you can use this to get the absolute value of an integer
    Code (Java):
    static int abs(int x) {
        return (x & 0x80000000) == 0 ? x : ~x + 1;
    }
    This will check if the two's complement of x has the signum bit set to 0: if it's true then the number is non-negative and the same value is returned, otherwhise the two's complement of x is returned. The equal check is done with 0 because in some architectures comparing with 0 is faster than with a variable.
    Note that, if you already know all the corners, to help the branch predictor it would be useful to sort the corners array in case you need to call this method many times (caching the volume's result somewhere, obviously).
    You can then remove the method call overhead by allocating the variable holding the side length and repeating the code each time (a variable allocation is cheaper than method call).
    Anyway, this will give you some nanoseconds in the best scenarios, so unless you want to bring minecraft servers to the moon I'm not sure you'll ever need it
     
    #8 TheSniper99, Jul 13, 2021
    Last edited: Jul 13, 2021
    • Informative Informative x 1
  9. Thanks for your reply and your help!

    I absolutely forgot, about geometry sense of integral. I try to get triple integral (because cuboid constructed at lines and have only 90* angle we don`t need to care about that, at minecraft for sure). That`s look to simple, but that`s work.. and works faster that any other method I try, because of coordinates are constants - simple multiplying of their difference are a solution. I try to test like other methods simple code
    Code (Java):
    (corner2.getZ() - corner1.getZ()) * (corner2.getY() - corner1.getY()) * (corner2.getX() - corner1.getX())
    and that`s work exactly how I want, difference between nanos before and after calling a method are only 1100 (I can`t be sure that that numbers meen what I want, but their difference talk about something). All what I need - get absolute value and all. I so thanks @TheSniper99 for telling about method of absolute value.

    Thank`s you all! I hope that such long deliberations with such simple solutions will help someone not to look for the simplest problems, but to achieve better results. Thanks again!
     
    • Friendly Friendly x 1