Util Using rays to quickly and accurately detect hitbox collisions

Discussion in 'Resources' started by JRL1004, Jan 14, 2017.

?

Was this useful to you and/or a good idea?

  1. Useful; Not a good idea

  2. Not useful; Not a good idea

  3. Useful; Good idea

  4. Not useful; Not a good idea

  5. Not Useful; Good idea (Because I messed up on the poll the first time)

Results are only viewable after voting.
Thread Status:
Not open for further replies.
  1. Offline

    JRL1004

    Hello, Bukkit community! Just as a short bit of backstory, I was making a magic-based plugin and ran into an issue involving the inaccuracy of using a for loop and distance checks for a raycast. This utility is my solution to the problem, as it ensures that a bounding box collision was present and does so quickly. In addition to this, the length of the ray is the maximum collision distance (something that was not always true when using the Location#distance() method).

    As a forenote, I am building this off of CraftBukkit 1.8.8 without reflection, however it does work on higher versions (I have not checked < 1.8.8) so long as you fix your imports.

    If you just want the code (as this is a Util post), please expand the complete class spoiler, otherwise expand the tutorial box
    Complete class (open)

    Code:java
    1. public class Ray {
    2.  
    3. public double startX, startY, startZ;
    4. public double endX, endY, endZ;
    5. public Set<Entity> entitySet;
    6.  
    7. public Ray(double startX, double startY, double startZ, double endX, double endY, double endZ) {
    8. this.startX = startX;
    9. this.startY = startY;
    10. this.startZ = startZ;
    11. this.endX = endX;
    12. this.endY = endY;
    13. this.endZ = endZ;
    14. entitySet = new HashSet<Entity>();
    15. }
    16.  
    17. public void removeNonCollidingAlongXZPlane() {
    18. Iterator<Entity> entityIterator = entitySet.iterator();
    19. while (entityIterator.hasNext()) {
    20. AxisAlignedBB aabb = ((CraftEntity) entityIterator.next()).getHandle().getBoundingBox();
    21.  
    22. double rectX = aabb.a, rectXLength = aabb.d - rectX;
    23. double rectZ = aabb.c, rectZLength = aabb.f - rectZ;
    24. Rectangle2D.Double entityRectangle = new Rectangle2D.Double(rectX, rectZ, rectXLength, rectZLength);
    25.  
    26. boolean collided = entityRectangle.intersectsLine(startX, startZ, endX, endZ);
    27.  
    28. if (!collided) entityIterator.remove();
    29. }
    30. }
    31.  
    32. public void removeNonCollidingAlongXYPlane() {
    33. Iterator<Entity> entityIterator = entitySet.iterator();
    34. while (entityIterator.hasNext()) {
    35. AxisAlignedBB aabb = ((CraftEntity) entityIterator.next()).getHandle().getBoundingBox();
    36.  
    37. double rectX = aabb.a, rectXLength = aabb.d - rectX;
    38. double rectY = aabb.b, rectYLength = aabb.e - rectY;
    39. Rectangle2D.Double entityRectangle = new Rectangle2D.Double(rectX, rectY, rectXLength, rectYLength);
    40.  
    41. boolean collided = entityRectangle.intersectsLine(startX, startY, endX, endY);
    42.  
    43. if (!collided) entityIterator.remove();
    44. }
    45. }
    46.  
    47. public void removeNonCollidingAlongZYPlane() {
    48. Iterator<Entity> entityIterator = entitySet.iterator();
    49. while (entityIterator.hasNext()) {
    50. AxisAlignedBB aabb = ((CraftEntity) entityIterator.next()).getHandle().getBoundingBox();
    51.  
    52. double rectZ = aabb.c, rectZLength = aabb.f - rectZ;
    53. double rectY = aabb.b, rectYLength = aabb.e - rectY;
    54. Rectangle2D.Double entityRectangle = new Rectangle2D.Double(rectZ, rectY, rectZLength, rectYLength);
    55.  
    56. boolean collided = entityRectangle.intersectsLine(startZ, startY, endZ, endY);
    57.  
    58. if (!collided) entityIterator.remove();
    59. }
    60. }
    61.  
    62. public void removeAllNonColliding() {
    63. removeNonCollidingAlongXZPlane();
    64. removeNonCollidingAlongXYPlane();
    65. removeNonCollidingAlongZYPlane();
    66. }
    67. }


    Tutorial/How it works (open)

    Let's get started with the Tutorial/how it works! In order for this method to be used, we are going to need to construct a new class: the Ray class. This class is going to handle storing the ray, the entities that we are going to check of collisions, and will also be responsible for the minimal amount of computations that we are going to use.
    Code:java
    1. public class Ray {
    2. // Create some fields for storing the start and end points of the Ray
    3. public double startX, startY, startZ;
    4. public double endX, endY, endZ;
    5. // We could use Vectors, but I find that all of the methods and such that
    6. // come with the Vector class are unnecessary for calculations
    7.  
    8. // We are also going to need a collection containing the entities that we are checking
    9. // Be sure to clear this after the calculations are completed!
    10. public Set<Entity> entitySet;
    11.  
    12. // Create a constructor in a way that works for you, just make sure that you have your ray's
    13. // starting and ending point available for reference
    14. public Ray(double startX, double startY, double startZ, double endX, double endY, double endZ) {
    15. this.startX = startX;
    16. this.startY = startY;
    17. this.startZ = startZ;
    18. this.endX = endX;
    19. this.endY = endY;
    20. this.endZ = endZ;
    21. entitySet = new HashSet<Entity>();
    22. }
    23. }

    Now that we have the ray class itself, let's make a few methods to reduce down the number of entities in the set to only those that had their bounding box intersected by the Ray. Due to how minecraft functions, it is more likely for entities to be separated along the XZ (ground) plane than it is for them to be separated by the XY or ZY planes. We can use this reasoning to quickly remove all of the entities from the set that do not touch the Ray's XZ path. We can do this by treating the 3-dimensional bounding box as a set of interconnected 2-Dimensional bounding boxes (is it still a box if it's in 2D? Maybe bounding squares), as well as treating the Ray as if it only existed on the XZ plane (did not have a Y value). What we are effectively doing is looking at all of the entities and the ray from the top-down view to reduce workload.
    Code:java
    1. public void removeNonCollidingAlongXZPlane() {
    2. // I use an Iterator as it allows for the use of the remove() call when
    3. // when we find an entity that does not collide with the ray
    4. Iterator<Entity> entityIterator = entitySet.iterator();
    5. while (entityIterator.hasNext()) {
    6. // You can store the entity if you would like to, but I only need to know it's bounding box for the sake of collision detection
    7. AxisAlignedBB aabb = ((CraftEntity) entityIterator.next()).getHandle().getBoundingBox();
    8.  
    9. // What we can do is use Java's geometry package to see if our ray will intersect the bounding box
    10. // Rectangle2D objects are defined by a 2D point, a length, and a width
    11. double rectX = aabb.a, rectXLength = aabb.d - rectX;
    12. double rectZ = aabb.c, rectZLength = aabb.f - rectZ;
    13. Rectangle2D.Double entityRectangle = new Rectangle2D.Double(rectX, rectZ, rectXLength, rectZLength);
    14.  
    15. // We can can now use the Rectangle2D object to check for an XZ collisions
    16. boolean collided = entityRectangle.intersectsLine(startX, startZ, endX, endZ);
    17.  
    18. // If we didn't get a collision, we can use the Iterator to simply remove the entity from the set
    19. if (!collided) entityIterator.remove();
    20. }
    21. }

    Using this same reasoning as from the other step, we can adapt our code to check along a plane that uses the Y axis. We reason that we use a plane is so that slope can be taken into account and allow for ray to pass barely, diagonally over a target and still not intersect. As we have already checked the XZ plane for collisions, we can now check the XY and ZY planes. The ordering here does not matter.
    Code:java
    1. public void removeNonCollidingAlongXYPlane() {
    2. Iterator<Entity> entityIterator = entitySet.iterator();
    3. while (entityIterator.hasNext()) {
    4. AxisAlignedBB aabb = ((CraftEntity) entityIterator.next()).getHandle().getBoundingBox();
    5.  
    6. // Be sure that you are only using data from the plane that you are using
    7. // I have changed the Z information out for Y as I am now using the XY plane instead of XZ
    8. double rectX = aabb.a, rectXLength = aabb.d - rectX;
    9. double rectY = aabb.b, rectYLength = aabb.e - rectY;
    10. Rectangle2D.Double entityRectangle = new Rectangle2D.Double(rectX, rectY, rectXLength, rectYLength);
    11.  
    12. boolean collided = entityRectangle.intersectsLine(startX, startY, endX, endY);
    13.  
    14. if (!collided) entityIterator.remove();
    15. }
    16. }
    17.  
    18. public void removeNonCollidingAlongZYPlane() {
    19. Iterator<Entity> entityIterator = entitySet.iterator();
    20. while (entityIterator.hasNext()) {
    21. AxisAlignedBB aabb = ((CraftEntity) entityIterator.next()).getHandle().getBoundingBox();
    22.  
    23. double rectZ = aabb.c, rectZLength = aabb.f - rectZ;
    24. double rectY = aabb.b, rectYLength = aabb.e - rectY;
    25. Rectangle2D.Double entityRectangle = new Rectangle2D.Double(rectZ, rectY, rectZLength, rectYLength);
    26.  
    27. boolean collided = entityRectangle.intersectsLine(startZ, startY, endZ, endY);
    28.  
    29. if (!collided) entityIterator.remove();
    30. }
    31. }

    Now that we have coded what is required for correct checks along every plane, we can apply them all at once to make sure that our Set contains only entities hit by the Ray!
    Code:java
    1. public void removeAllNonColliding() {
    2. removeNonCollidingAlongXZPlane();
    3. removeNonCollidingAlongXYPlane();
    4. removeNonCollidingAlongZYPlane();
    5. }

    This is my first time making a tutorial or anything like that so, if we parts are confusing or badly worded, please let me know and I will correct them! Thank you

    To set which entities to check, use [rayObject].entitySet.add()
    Once you have added all of the entities to the set, use [rayOject].removeAllNonColliding()
    and finally, to access the remaining entities, just access [rayObject].entitySet

    I purposely avoided getters and setters in this for the sake of making it as simple as possible. I do recommend adding them in.

    EDIT: finished instructions (I hope)
     
    Last edited: Apr 15, 2017
  2. Offline

    Zombie_Striker

    @JRL1004
    Nice util. I may use this in another one of my plugins.

    I noticed you said you did this without reflection. Since I know how to add it, here is the updated code:
    Code:
    import java.awt.geom.Rectangle2D;
    import java.util.*;
    
    import org.bukkit.Bukkit;
    import org.bukkit.entity.Entity;
    
    public class Ray {
    
        public double startX, startY, startZ, endX, endY, endZ;
        private Set<Entity> entitySet;
        private Class<?> CRAFT_ENTITY;
        private final String SERVER_VERSION;
    
        public Ray(double startX, double startY, double startZ, double endX,
                double endY, double endZ, List<Entity> entities) {
            String name = Bukkit.getServer().getClass().getName();
            SERVER_VERSION = name.substring(
                    name.indexOf("craftbukkit.") + "craftbukkit.".length())
                    .substring(0, name.indexOf("."));
            try {
                CRAFT_ENTITY = Class.forName("org.bukkit.craftbukkit."
                        + SERVER_VERSION + ".entity.CraftEntity");
            } catch (Exception e) {
            }
            this.startX = startX;
            this.startY = startY;
            this.startZ = startZ;
            this.endX = endX;
            this.endY = endY;
            this.endZ = endZ;
            entitySet = new HashSet<Entity>(entities);
        }
    
        public void removeNonColliding(PlaneType type) {
            Iterator<Entity> entityIterator = entitySet.iterator();
            while (entityIterator.hasNext()) {
                try {
                    Object handle = (CRAFT_ENTITY.cast(entityIterator.next()))
                            .getClass().getMethod("getHandle")
                            .invoke((CRAFT_ENTITY.cast(entityIterator.next())));
                    Object aabb = handle.getClass().getMethod("getBoundingBox")
                            .invoke(handle);
    
                    double rectX, rectXLength, rectZ, rectZLength;
                    if (type == PlaneType.XZ || type == PlaneType.XY) {
                        rectX = aabb.getClass().getField("a").getDouble(aabb);
                        rectXLength = aabb.getClass().getField("d").getDouble(aabb)
                                - rectX;
                    } else {
                        rectX = aabb.getClass().getField("c").getDouble(aabb);
                        rectXLength = aabb.getClass().getField("f").getDouble(aabb)
                                - rectX;
                    }
                    if (type == PlaneType.XY || type == PlaneType.YZ) {
                        rectZ = aabb.getClass().getField("b").getDouble(aabb);
                        rectZLength = aabb.getClass().getField("e").getDouble(aabb)
                                - rectZ;
                    } else {
                        rectZ = aabb.getClass().getField("c").getDouble(aabb);
                        rectZLength = aabb.getClass().getField("f").getDouble(aabb)
                                - rectZ;
                    }
                    boolean collided = new Rectangle2D.Double(rectX, rectZ,
                            rectXLength, rectZLength).intersectsLine(startX,
                            startZ, endX, endZ);
                    if (!collided)
                        entityIterator.remove();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }
    
        public void removeAllNonColliding() {
            for (PlaneType p : PlaneType.values())
                removeNonColliding(p);
        }
    
        public Set<Entity> getEntities() {
            return entitySet;
        }
    }
    
    enum PlaneType {
        XY, XZ, YZ;
    }
    Also, I added the imports, removed a lot of repeated lines, and merged all three methods into one. It is only 19 lines longer than the original (including the imports).
     
  3. Offline

    JRL1004

    @Zombie_Striker Sweet! Thank you! I'll go ahead and update this in my personal projects. I am going to be leaving the main method in it's current format, however, as I want to have the tutorial section in place.

    Edit 1: Just as a recommendation, I would say to make the XZ plane the first in your PlaneType enum as it is the plane that is most likely to make the ray miss. By doing so, you can loop through the enum (in the remove all plane's method) and get through the calculations faster (Less entities in consecutive loops)

    Edit 2: Just so you are aware, your reflection method also fails because you never changed the plane of the Ray that was being checked. If you add that into your if statements as well, it will function properly.
     
    Last edited: Jan 14, 2017
  4. Offline

    pretocki3

    @JRL1004 How this even work? Looks like entitySet is empty. Maybe put all entity in entrySet?
     
  5. Offline

    JRL1004

    @pretocki3 Sorry for having such a late reply. For some reason, this forum never lets me sign in. I forgot one step in this resource so I am going to edit it in now.
     
Thread Status:
Not open for further replies.

Share This Page