¿Eficaz línea de visión Java 2D para muchas entidades?

Mi problema hoy es este:

Tengo muchos civiles dando vueltas, son clases almacenadas por un arraylist.

La idea es que cuando vean otro pánico civil, comenzarán a entrar en pánico y se extenderá.

Primero llamo a cada Step()función de clases haciendo un bucle a través de un iterador. Luego, en la Step()función, pasa por otro iterador civillian. A medida que avanza, intenta detectar si puede ver al otro civillian en el iterador, aquí es donde el tiempo de rendimiento va de 0 a 50 milisegundos por tener 100 Civillians.

Este es el problema que necesito solucionar, traté de hacer una manera fácil de detectar si algún objeto está en el camino del punto a al punto b.

Aquí está el código para la línea de visión:

public static Object LOS(int x, int y, int x2, int y2, String Scan, Object Me, Object You) {
   DirectionX = (x-x2)/Quality;
   DirectionY = (y-y2)/Quality;
   CurrentX = x;
   CurrentY = y;
   String[] ScanArray = Scan.split(":");
   for(int I=0;I<=Quality;I++) {
      for(String Type: ScanArray) {
         if(Type.equals("Boxs")) {
            Iterator it=Level.Boxs.iterator();
            while(it.hasNext()) {
               Box Box = (Box)it.next();
               if(Me!=Box&&You!=Box) {
                  //Collision = Tools.Collision((int)(CurrentX-(Width/2)), (int)(CurrentY-(Width/2)), Width, Width, Box.GetX(), Box.GetY(), Box.GetWidth(), Box.GetHeight(), 1);
                  boolean Col = Tools.BasicCollision((int)(CurrentX-(Width/2)), (int)(CurrentY-(Width/2)), Width, Width, Box.GetX(), Box.GetY(), Box.GetWidth(), Box.GetHeight());
               }
            }
         }
      }

      CurrentX-=DirectionX;
      CurrentY-=DirectionY;
   }
   return null;
}

Si le duele la cabeza, los fundamentos son:

Calcula 10 puntos intermedios y detecta si está dentro, usando BasicCollision:

public static boolean BasicCollision(int x, int y, int width, int height, int x2, int y2, int width2, int height2) {
   if(x<x2+width&&x+width>x2&&y<y2+height&&y+height>y2) {
      return true;
   } else {
      return false;
   }
}

Mi pregunta es: ¿hay una manera más fácil de detectar esta línea de visión que no afecte gravemente mi rendimiento en grandes cantidades? ¿Cualquier retroalimentación?

Una idea sería mantener a las personas sin pánico y sin pánico en listas separadas N y P, y luego limitar sus cheques LOS a <n, p> ∈ N × P. De esa manera nunca verificará a personas del mismo estado, lo que acelerará las cosas arriba.

Otra cosa (que ya puede estar haciendo, no está seguro) sería asegurarse de que una vez que determine que un no paricker se ha convertido en un panicker, detenga inmediatamente los cheques restantes para ese antiguo no parcheador. Esto ayudará a su algoritmo a escalar con el aumento del tamaño de la población para un mapa fijo. Cuando la población se vuelve muy grande, entonces debes converger hacia el 100% en pánico con bastante rapidez, lo que significa que no se necesitan más controles como se señala en los comentarios a continuación.

Según su descripción, parece que su código está iterando sobre cada posible emparejamiento de dos civiles. El dibujo sugiere que esto es innecesario. Puede usar algún tipo de indexación geométrica para realizar un seguimiento de los civiles cercanos. Entonces pruébelos primero. Si están en el LOS, entonces entra en pánico. De lo contrario, pruebe a civiles más alejados.

Tienes varias opciones:

A) Suponga que las personas pueden entrar en pánico y escuchar a otras personas gritar, por lo que el código de la línea de visión no es tan importante XD.

B) En caso de que A no sea una opción, debe hacer esto para cada civil:

1. Calcule si el segmento entre dos civiles tiene una longitud menor o igual a algún valor constante.
2. Calcule si este segmento se cruza con un polígono (rectángulo, en su caso).

Debe realizar 1 antes que 2 porque reduce en gran medida la cantidad de trabajo, dado que 2 es el cálculo más costoso. También debe considerar algún tipo de "memoria" sobre los cálculos que ya ha realizado, por ejemplo: si acaba de procesar el segmento C1-C2, no vuelva a hacer C2-C1.

Además de eso, debe optimizar 2. Probar si un segmento se cruza con un rectángulo es equivalente a probar si un segmento dado se cruza con 4 segmentos. Cuando se ha cruzado con uno de ellos, estamos seguros de que los civiles no se ven, por lo que no tiene sentido procesar los segmentos restantes en el rectángulo.

Dado que este es un problema geométrico típico, conocido como el problema de intersección del segmento de línea , puede encontrar un montón de código abierto en Internet. La mayoría de las personas usa un algoritmo de línea de barrido junto con alguna estructura de datos.

Si trata las habitaciones como zonas, unidas por portales , solo tiene que hacer escaneos de visibilidad dentro de cada habitación y aquellas partes de las habitaciones contiguas que son visibles a través de los portales predeterminados.

¿Es probable que su línea de visión no tenga en cuenta la dirección a la que se enfrenta el civil? En tal caso, si divide las habitaciones que contienen obstáculos como pilares o da vuelta a las esquinas en zonas convexas separadas y suponiendo que todos los civiles en la misma zona son visibles entre sí. Puede ir más allá al tener zonas cóncavas superpuestas y permitir que los civiles se encuentren en más de una zona a la vez para encontrar la mayor cantidad posible en la misma zona que el otro civil para evitar todas las demás comprobaciones de visibilidad.

Si su terreno es desigual y tiene una gran cantidad de agentes, entonces puede estar interesado en este barrido O (n) (donde N es la granularidad de una cuadrícula en la que ha dividido el terreno):