[CHALLENGE!] Getting all LivingEntity in Player's field of view

Hi!
I think this is a really hard thing to do, but I need to start a thread about getting all LivingEntity in a Player's field of view. I had some ideas :
- Mathematic change of reference frame => Too heavy
- Trying to do something with yaw, vectors and angles ?

Thanks for your help

 

Are you wanting to check for line of sight as well?

 

This is what I found on the forums although it gets all players you can just change it to Entities

Code:

public class ConeEffect {
   
    /**
    *
    * @param players
    *  List of nearby players
    * @param StartLoc
    *  starting location
    * @param Radius
    *  distance cone travels
    * @param Degrees
    *  angle of cone
    * @param direction
    *  angle in degrees from north
    * @return All players inside the cone
    */
    public static List<Player> getDamagedPlayersInCone(List<Player> players, Location startLoc, int radius, int degrees, int direction) {
        List<Player> newPlayers = new ArrayList<Player>();
       
        int[] startPos = new int[] { (int)startLoc.getX(), (int)startLoc.getZ() };
       
        int[] endA = new int[] { (int)(radius * Math.cos(direction - (degrees/2))), (int)(radius * Math.sin(direction - (degrees/2))) };
        int[] endB = new int[] { (int)(radius * Math.cos(direction + (degrees/2))), (int)(radius * Math.sin(direction + (degrees/2))) };
       
        for(Player p :players) {
            Location l = p.getLocation();
            if (!isPointInCircle(startPos[0], startPos[1], radius, l.getBlockX(), l.getBlockZ())) {
                continue;
            }
            int [] playerVector = getVectorForPoints(startPos[0], startPos[1], l.getBlockX(), l.getBlockZ());
           
            double angle = getAngleBetweenVectors(endA, playerVector) + getAngleBetweenVectors(endB, playerVector);
            if (Math.abs(angle) * 10 - 2 < degrees) {
                newPlayers.add(p);
            }
        }
        return newPlayers;
    }
   
    private static int[] getVectorForPoints(int x1, int y1, int x2, int y2) {
        return new int[] { Math.abs(x2-x1), Math.abs(y2-y1) };
    }
 
    private static boolean isPointInCircle(int cx, int cy, int radius, int px, int py) {
        double dist = (px-cx)^2 + (py-cy)^2;
        return dist < (radius^2);
    }
   
    private static double getAngleBetweenVectors(int[] vector1, int[] vector2){
        return Math.atan2(vector2[1], vector2[0]) - Math.atan2(vector1[1], vector1[0]);
    }
}

 

The Line of Sight is the View Vector here. I want to get all entities in the cone. This is possible. But this is very hard.
My first try was to do a change of reference frame with some matrices, but this is hard and I think it's heavy.

Maybe getting all nearby entities and comparing the vector Player->Entity with the vector of the line of sight ? This could make an angle and we check if it is less than X... I don't know exactly

EDIT : thehutch I think this is exactly my second idea lol... Now I need some time to fully understand this code.

 

Being that a player can change their field of view without the server knowing , even in vanilla clients, would mean the best way I think would be to figure out the direction the player is facing the get all the nearby entities, get their locations and if they are within 90* in either direction of the players current line of sight, return them.

 

Ribesg
Also this is for the 2D plane for the player has to be at the same Y axis or I think at them in the same plane

 

Ok so after some work with 3D vectors, here is what I have for now. It works well, but I'm sure it could be really faster. What do you think of this ?

Code:java

public class Cone {
 
    /** @param entities
     *            List of nearby entities
     * @param startPos
     *            starting position
     * @param Radius
     *            distance cone travels
     * @param Degrees
     *            angle of cone
     * @param direction
     *            direction of the cone
     * @return All entities inside the cone */
    public static List<Entity> getEntitiesInCone(List<Entity> entities, Vector startPos, float radius, float degrees, Vector direction) {
 
        List<Entity> newEntities = new ArrayList<Entity>();        //    Returned list
        float squaredRadius = radius * radius;                     //    We don't want to use square root
 
        for (Entity e : entities) {
            Vector relativePosition = e.getLocation().toVector();                            //    Position of the entity relative to the cone origin
            relativePosition.subtract(startPos);
            if (relativePosition.lengthSquared() > squaredRadius) continue;                    //    First check : distance
            if (getAngleBetweenVectors(direction, relativePosition) > degrees) continue;    //    Second check : angle
            newEntities.add(e);                                                                //    The entity e is in the cone
        }
        return newEntities;
    }
 
    /** @param startPos
     *            starting position
     * @param radius
     *            distance cone travels
     * @param degrees
     *            angle of cone
     * @param direction
     *            direction of the cone
     * @return All block positions inside the cone */
    public static List<Vector> getPositionsInCone(Vector startPos, float radius, float degrees, Vector direction) {
 
        List<Vector> positions = new ArrayList<Vector>();        //    Returned list
        float squaredRadius = radius * radius;                     //    We don't want to use square root
 
        for (float x=startPos.getBlockX()-radius; x<startPos.getBlockX()+radius; x++)
            for (float y=startPos.getBlockY()-radius; y<startPos.getBlockY()+radius; y++)
                for (float z=startPos.getBlockZ()-radius; z<startPos.getBlockZ()+radius; z++) {
                    Vector relative = new Vector(x,y,z);
                    relative.subtract(startPos);
                    if (relative.lengthSquared() > squaredRadius) continue;            //    First check : distance
                    if (getAngleBetweenVectors(direction, relative) > degrees) continue;    //    Second check : angle
                    positions.add(new Vector(x,y,z));                                                //    The position v is in the cone
                }
        return positions;
    }
 
 
    public static float getAngleBetweenVectors(Vector v1, Vector v2) {
        return Math.abs((float)Math.toDegrees(v1.angle(v2)));
    }
}

 

stil code misses the players behind the player to check, because if you press double f5, then you could see mobs behind u

 

direction.multiply(-1);
Or
getAngleBetweenVectors(direction, relative) % 90

 

So anyone did it? any way to get entities in a cone? thanks!

 

you can look at the NoCheatPlus source code, and look at their direction check.

The Direction check will find out if a player tried to interact with something that's not in his field of view.

 

The direction check uses some heuristic thing, like comparing the difference from the distance vector to the looking direction vector scaled to the length of the distance vector.

But i think the efficiency question has to be put before even checking individual entities for if they are really inside of the field of view.

The pre-selection of entities/players is crucial, in terms of how it is done. This involves questions like asymptotic runtime, iterating over players (10 slot server.... 500 slot server?), what accuracy is needed, data structures to keep track of things in an efficient way, possibility of maintaining data structures that then only get updated by changes and some scheduling (checking entities not every tick for instance).

Have you thought about using a library for entity related functionality? BKCommonLib used to have some EntityMove event, but also that tux2lib might be a candidate (i have not checked if).

Depending on the task you might also consider using a protocol library (ProtocolLib, tux2lib, others?) to intercept entity related packets and then maintain the data structures from there on, manipulating the packets (prevent, add new ones for adding the entities once really visible). This would add overhead to the server for the packets, but reduce the complexity to find the entities near the player for pre-selection.

In fact the main point is what you really want to use this for...