Linha de visão 2d Java eficiente para muitas entidades?

Meu problema hoje é este:

Eu tenho muitos civis por aí, são classes armazenadas por um arraylist.

A idéia é que, quando virem outro pânico civil, começarão a entrar em pânico e isso se espalhará.

Primeiro, chamo a Step()função de cada classe fazendo um loop através de um iterador. Então, na Step()função, ele passa por outro iterador civil Enquanto ele tenta, tenta detectar se ele pode ver o outro civil no iterador, é aqui que o tempo de desempenho varia de 0 a 50 milissegundos por ter 100 civilianos.

Esse é o problema que eu preciso resolver, tentei facilitar o modo de detectar se algum objeto está no caminho do ponto a ao ponto b.

Aqui está o código para a linha de visão:

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;
}

Se você está com dor de cabeça, os fundamentos são:

Ele mostra 10 pontos no meio e detecta se 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;
   }
}

Minha pergunta é: Existe uma maneira mais fácil de detectar essa linha de visão que não afeta severamente meu desempenho em grandes números? Algum feedback?

Um pensamento seria manter as pessoas que não estavam em pânico e em pânico em listas separadas N e P e, em seguida, limitar suas verificações de LOS a <n, p> ∈ N × P. Dessa forma, você nunca verifica pessoas do mesmo estado, o que acelerará as coisas acima.

Outra coisa (o que você já deve estar fazendo - não tenho certeza) seria garantir que, depois de determinar que um não violador tenha se tornado um violador, pare imediatamente as verificações restantes do ex-violador. Isso ajudará seu algoritmo a escalar com o aumento do tamanho da população para um mapa fixo. Quando a população fica muito grande, você deve convergir rapidamente para o pânico a 100%, o que significa que não são necessárias mais verificações, conforme observado nos comentários abaixo.

Pela sua descrição, parece que seu código está repetindo todos os pares possíveis de dois civis. O desenho sugere que isso é desnecessário. Você pode usar algum tipo de indexação geométrica para rastrear civis próximos. Em seguida, teste-os primeiro. Se eles estiverem no LOS, entre em pânico. Caso contrário, teste os civis mais distantes.

Você tem várias opções:

A) Suponha que as pessoas possam entrar em pânico também ouvindo outras pessoas gritando, então o código da linha de visão não é tão importante para o XD.

B) Caso A não seja uma opção, você deve fazer isso para cada civil:

1. Calcule se o segmento entre dois civis tem um comprimento menor ou igual a algum valor constante.
2. Calcule se esse segmento cruza com um polígono (retângulo, no seu caso).

Você precisa executar 1 antes de 2 porque isso reduz bastante a quantidade de trabalho, já que 2 é o cálculo mais caro. Além disso, você deve considerar algum tipo de "memória" sobre os cálculos que já fez, por exemplo: Se você acabou de processar o segmento C1-C2, não faça novamente C2-C1.

Além disso, você precisa otimizar 2. Testar se um segmento se cruza com um retângulo é equivalente a testar se um determinado segmento se cruza com 4 segmentos. Quando você cruza com um deles, temos certeza de que os civis não se vêem, então não faz sentido processar os segmentos restantes no retângulo.

Como esse é um problema geométrico típico, conhecido como problema de interseção do segmento de linha , você pode encontrar bastante código-fonte aberto na Internet. A maioria das pessoas usa um algoritmo de linha de varredura junto com alguma estrutura de dados.

Se você tratar as salas como zonas, unidas por portais , você só precisará fazer verificações de visibilidade em cada sala e nas partes das salas adjacentes que são visíveis através dos portais pré-determinados.

Sua linha de visão provavelmente não é responsável pela direção que o civil está enfrentando? Nesse caso, se você dividir quartos que contenham obstáculos, como pilares, ou contornem esquinas em zonas convexas separadas, e supondo que todos os civis na mesma zona sejam todos visíveis um ao outro. Você pode levar isso adiante ao ter zonas côncavas sobrepostas e permitir que os civis estejam em mais de uma zona ao mesmo tempo, a fim de encontrar o maior número possível na mesma zona que o outro civil, para evitar todas as outras verificações de visibilidade.

Se o seu terreno for irregular e você tiver um grande número de agentes, poderá estar interessado nessa varredura de O (n) (onde N é a granularidade de uma grade na qual você dividiu o terreno):