Effiziente 2D-Java-Sichtlinie für viele Entitäten?

Mein Problem heute ist folgendes:

Ich habe viele Zivilisten, sie sind Klassen, die von einem Arraylisten gespeichert werden.

Die Idee ist, wenn sie eine weitere zivile Panik sehen, werden sie in Panik geraten und sie wird sich ausbreiten.

Zuerst rufe ich jede Klassenfunktion auf Step(), indem ich einen Iterator durchlaufe. Dann Step()durchläuft es in der Funktion einen anderen Civillian-Iterator. Während es durchläuft, versucht es zu erkennen, ob es den anderen Civillian im Iterator sehen kann. Hier geht die Leistungszeit von 0 auf 50 Millisekunden für 100 Civillians.

Dies ist das Problem, das ich beheben muss. Ich habe versucht, auf einfache Weise festzustellen, ob sich Objekte im Weg von Punkt a bis Punkt b befinden.

Hier ist der Code für die Sichtlinie:

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

Wenn Sie Kopfschmerzen haben, sind die Grundlagen:

Es ermittelt 10 Punkte dazwischen und erkennt mithilfe von 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;
   }
}

Meine Frage ist: Gibt es eine einfachere Möglichkeit, diese Sichtlinie zu erkennen, die meine Leistung in großer Zahl nicht stark beeinträchtigt? Irgendeine Anregung?

Ein Gedanke wäre, nicht panische und panische Personen in getrennten Listen N und P zu halten und dann Ihre LOS-Prüfungen auf <n, p> ∈ N × P zu beschränken. Auf diese Weise überprüfen Sie niemals Personen mit demselben Status, was die Dinge beschleunigt oben.

Eine andere Sache (die Sie möglicherweise bereits tun - nicht sicher) wäre, sicherzustellen, dass Sie, sobald Sie feststellen, dass ein Nicht-Panicker zu einem Panicker geworden ist, die verbleibenden Überprüfungen für diesen ehemaligen Nicht-Panicker sofort einstellen. Dies hilft Ihrem Algorithmus, mit zunehmender Populationsgröße für eine feste Karte zu skalieren. Wenn die Bevölkerung sehr groß wird, sollten Sie ziemlich schnell zu einer 100% igen Panik konvergieren, was bedeutet, dass keine weiteren Überprüfungen erforderlich sind, wie in den Kommentaren unten angegeben.

Aus Ihrer Beschreibung geht hervor, dass Ihr Code jede mögliche Paarung zweier Zivilisten durchläuft. Die Zeichnung legt nahe, dass dies nicht erforderlich ist. Sie können eine Art geometrische Indizierung verwenden, um die Zivilbevölkerung in der Nähe zu verfolgen. Dann testen Sie sie zuerst. Wenn sie in der LOS sind, dann Panik. Ansonsten testen Sie weiter entfernte Zivilisten.

Sie haben mehrere Möglichkeiten:

A) Nehmen Sie an, dass Menschen in Panik geraten können, wenn sie auch andere Menschen schreien hören, sodass der Code für die Sichtlinie nicht so wichtig ist. XD.

B) Falls A keine Option ist, müssen Sie dies für jeden Zivilisten tun:

1. Berechnen Sie, ob das Segment zwischen zwei Zivilisten eine Länge hat, die kleiner oder gleich einem konstanten Wert ist.
2. Berechnen Sie, ob sich dieses Segment mit einem Poligon schneidet (in Ihrem Fall mit einem Rechteck).

Sie müssen 1 vor 2 ausführen, da dies den Arbeitsaufwand erheblich reduziert, da 2 die teuerste Berechnung ist. Außerdem müssen Sie eine Art "Speicher" für die Berechnungen berücksichtigen, die Sie bereits durchgeführt haben, z. B.: Wenn Sie gerade das C1-C2-Segment verarbeitet haben, führen Sie C2-C1 nicht erneut aus.

Darüber hinaus müssen Sie 2 optimieren. Das Testen, ob sich ein Segment mit einem Rechteck schneidet, entspricht dem Testen, ob sich ein bestimmtes Segment mit 4 Segmenten schneidet. Wenn Sie sich mit einem von ihnen überschnitten haben, sehen sich die Zivilisten sicher nicht. Daher ist es nicht sinnvoll, die verbleibenden Segmente im Rechteck zu verarbeiten.

Da dies ein typisches geometrisches Problem ist, das als Liniensegmentschnittpunktproblem bekannt ist , finden Sie im Internet reichlich Open Source-Code. Die meisten Leute verwenden einen Sweep-Line-Algorithmus zusammen mit einer Datenstruktur.

Wenn Sie Räume als Zonen behandeln, die durch Portale verbunden sind , müssen Sie nur Sichtbarkeitsscans in jedem Raum und in den Teilen benachbarter Räume durchführen, die durch die festgelegten Portale sichtbar sind.

Ihre Sichtlinie berücksichtigt wahrscheinlich nicht die Richtung, in die der Zivilist blickt? In einem solchen Fall, wenn Sie Räume, die Hindernisse wie Säulen enthalten oder um Ecken gehen, in separate konvexe Zonen unterteilen und davon ausgehen, dass alle Zivilisten in derselben Zone für einander sichtbar sind. Sie können dies weiter verfolgen, indem Sie überlappende konkave Zonen haben und Zivilisten erlauben, sich gleichzeitig in mehr als einer Zone zu befinden, um so viele wie möglich in derselben Zone wie der andere Zivilist zu finden, um alle anderen Sichtbarkeitsprüfungen zu vermeiden.

Wenn Ihr Gelände uneben ist und Sie eine große Anzahl von Agenten haben, könnte Sie dieser O (n) -Feger interessieren (wobei N die Granularität eines Gitters ist, in das Sie das Gelände unterteilt haben):