Java Performace: Suche Algorithmus/Methode um ein Ziel zu ermittel (RTS Game Android)

[cooldiman1]

Performance: Suche Algorithmus/Methode um ein Ziel zu ermittel (RTS Game Android)

Hallo liebe CB-Experten,

ich arbeite an einem RTS Spiel für Android und im Moment benötige ich eine bessere Performance.

Infos:
- Ich nutze LIBGDX
- BOX2D
- Java
- Ich habe im Moment noch 3 Threads (Render, Box2D, Rest) (Zukünftig kommt sicherlich noch ein Pathfinder oder so dazu)

Mein Problem:
Ich habe testweise 10.000 Objekte. Diese können schießen, sich bewegen, etc. und sich ein Ziel suchen. Da die Logik für das Suchen eines Ziel sich in jedem Objekt befindet habe ich 10000*10000 Schleifendurchläufe und jedesmal werden alle Einheiten durchgegangen und deren Entfernung zueinander errechnet. Das ist sehr unperformant. Ganze 4-5 Durchläufe schafft mein Thread nur noch bei dieser Objektanzahl pro Sekunde.

Ich benötige eine Lösung. Best Practice.


Code Snippets (Beispielcode von meinen Versuchen):
Diese Funktion befindet sich in der Manager Class die alle units(Objekte) enthält.

public static ArrayList<Vector2> getUnitsPositions()
    {
        ArrayList<Vector2> p = new ArrayList<Vector2>();

        for(BaseObject o: units) // Diese Schleife kostet die gesamte Performance
        {
           
        }

        return p;
    }

Diese Funktion befindet sich in der Unit Class die bei jedem Update einer Unit aufgerufen wird.

private void searchTarget()
    {
        if(!this.hasRotationTarget)
        {
            ArrayList<Vector2> unitsPositions = Manager.getUnitsPositions();

            float nearest = this.shootRange;
            int count = 0;

            for (Vector2 o : units)
            {
                if(Utility.distance(this.getBodyPosition(), o) <= this.shootRange)
                {
                    float range = Utility.distance(this.getBodyPosition(), o);

                    if(range < nearest)
                    {
                        nearest = range;
                        baseObjectIndex = count;
                    }
                }

                count++;
            }
      }
}

Unwichtigen Code habe ich zur Übersicht entfernt.

Gedanken:
- Das Zielsuchen in einen seperaten Thread auslagern. Was aber nur minimal helfen würde, aber trotzdem sinnvoll denke ich.
- Postionen aller Units vor den einzelnen Units update() sortieren?
-

Danke schonmal für eure Hilfe

Gruß,
cooldi

 

[Rondrer]

Mit best practices kann ich dir nicht wirklich helfen, bin kein Game Entwickler und habe keine Ahnung wie sowas normalerweise gelöst wird.

Aber ich denke man kann an mindestens zwei Stellen ansetzen:
1. Ist es wirklich notwendig, dass sich jedes Objekt so oft ein neues Ziel sucht? Klingt ein bisschen übertrieben, wenn im extremfall ein Objekt 30mal (oder so) in der Sekunde ein anderes Ziel auswählt. Würde es nicht reichen, wenn einmal in der Sekunde (oder noch seltener) ein neus Ziel gesucht wird und bei den anderen Updates einfach nur das aktuelle Ziel weiter verfolgt wird?

2. Jedesmal die Distanz von jedem Punkt zu jedem anderen Punkt zu berechnen ist natürlich echt heftig, vorallem wenn es eigentlich nur darum geht den nähesten anderen Punkt zu finden. Hier kann es helfen das Spielfeld in Teile zu teilen, und dann nur die zu durchsuchen, die in der Nähe des Objektes sind. Gibt spezielle Datenstrukturen für sowas, z.B. Quadtrees, einfach mal danach Googeln.

 

[Lacritz]

Ich würde da mal etwas weniger mit dem Code überlegen und viel eher. Wo lassen sich die 10.000 Einheiten runter rechnen? Als Beispiel, bei Supreme Commander werden mehrere Einheiten als eine große berechnet. So wird 1x der Weg berechnet & alle deine Einheiten halten sich an diese eine Berechnung. Wo also gibt es bei dir die Möglichkeit die Berechnungen zusammen zu führen?

 

[Pawel23]

Drei Ideen, die ich spontan hatte:

• Bei jedem Durchgang wird für jedes Objekt die Distanz zwischen allen Objekten berechnet. Das führt dazu, dass die Distanz zwischen Objekt A und B berechnet wird und später die Distanz zwischen Objekt B und A. Beides sollte zu dem selben Ergebnis führen, unabhängig von der Richtung. Also sollte die Distanz zwischen A und B nur einmal berechnet werden und bei der Betrachtung von Objekt B wiederverwendet werden. (D.h. Ergebnisse Cachen)
• Es wird das Objekt B gesucht, was am nächsten zu Objekt A ist. Statt für jedes Objekt die Distanz zu berechnen, werden nur die Betrachtet, die in einem Quadrat um das Objekt A sind. Also nur die Distanz berechnen für Objekte, deren X und Y Koordinate innerhalb der Reichweite des Objekts A sind. In etwa B.x >= A.x - A.range && A.x + A.range <= B.x. Analog dazu die Y.Koordinate. Damit werden die teuren mathematischen Operationen für Quadrat und Wurzel gespart.
• Aufbau eines Netzes im Speicher, wo ein Objekt weiß, was seine Nachbarn sind.

 

[cooldiman1]

@Rondrer
Den Gedanken habe ich auch verfolgt und ich könnte es natürlich umsetzen das höchstens einmal pro Sekunden die searchTarget() Funktion aufgerufen wird.
Dadurch entsteht aber eine gewisse Ungenauigkeit sobald sich innerhalb der Pausesekunde ein Objekt sich in den Schussradius befindet/bewegt. Dann würde die Unit nicht schießen und wenn sich dann der Gegner auch noch schnell wieder herausbewegt hätte man nie geschossen. Worst Case.

@Lacritz
Gruppen habe ich auch aber jede Unit besitzt ja eine Reichweite und es soll das nächstgelgende Ziel angegriffen werden. Jetzt befinden sich Units einer Gruppe natürlich nicht an der exakt selben Position und dann könnte der ein oder andere Gegner näher an einer Unit dran sein.

Ergänzung vom 27.02.2016 22:36 Uhr:
Ich glaube ich komme nicht darum einen neuen Thread anzulegen der für die Zielsuche zuständig ist. Dann vielleicht 2mal die Sekunde maximal ausführen, bzw jede Unit bekommt nen Counter und darf maximal 2mal die Sekunde suchen. Als Beispiel. Dann Cachen welche sich schon gefunden haben um unnötige Berechnungen zu vermeiden.

Danke schonmal für die Tipps
Wenn ihr noch mehr Lösungsansätze habt oder Theorien dann teilt sie mir gerne mit

Ergänzung (28. Februar 2016)

Vorerst gelöst:
Ich habe das Problem vorerst anders gelöst. Die absolut schlechte Performance lag hauptsächlich daran weil in der Schleife eine ArrayList
durchgegangen wird und diese Vector2 Objekte von LIBGdx enthählt.


Das ist die Manager update Funktion (gekürzt)

Dort werden nun alle Positionen und die Id von der Unit in ein float Array gespeichert.

private static float[][] vPositions;

private static int unitsSize = 0;

    public static void update()
    {
        unitsSize = units.size();
        vPositions = new float[unitsSize][3];
        int i = 0;
        for (BaseObject u: units)
        {
            vPositions[i] = new float[] { u.getBodyPosition().x, u.getBodyPosition().y, (float)u.getId()};
            i++;
        }
    }

Dann haben wir alle Positionen gespeichert und können sie nun auswerten.

for (float[] o : units)
{
    // Berechnungen der Entfernung, etc.
}

Druch die float Array ist die Performance enorm hoch. Es kostet aber bei 10000 Objekten dennoch so viel Leistung das ich dennoch den seperaten Thread in Betracht ziehe und die Berechnungen pro Sekunde trotzdem begrenzen werde. Spart Akku und Hardwareleistung.

Danke nochmal

 

[NemesisFS]

Tipps:
- Berechne nicht die Distanz, sondern Distanz². Dadurch sparst du dir die Wurzel, die teuer ist. Das ganze funktioniert weil die Distanz² immernoch der Definition einer Distanzmetrik genügt.
- Such dir eine Bibliothek die effizient die pairwise-distance-matrix bestimmen kann. Da gibt es einige Optimierungen wenn man das richtig macht die das schneller machen. (Je nach Anwendungsfall kannst du auch diese Matrix behalten und aktualisieren wenn sich die Objekte bewegen. Ich bezweifel jedoch stark, dass das hier hilft.
- Benutz einen Quadtree als Datenstruktur anstatt einer Liste/Array. Auf der Datenstruktur kannst du queries wie den deinen effizient ausführen.

 

[cooldiman1]

@NemesisFS
Besten Dank auch an dich Das mit den QuadTree hört sich mega interessant an. Werde mich damit die Tage mal auseinander setzen, weil es genau das ist was ich in Zukunft brauche, denk ich

 

[kuddlmuddl]

Die Wurzel sparen ist schonmal super.
Quadtrees sehen auf den ersten Blick sehr nach einer guten Lösong aus. Ich stell mir aber den Aufwand einer fehlerfreien Implemtierung und Nutzung nicht ganz einfach vor.
Wenn dir der Quadtree Ansatz zu komplex ist könntest du vereinfacht auch erstmal mit Quadranten arbeiten, denn dein Ziel ist ja die Komplexität (10.000*10.000) zu reduzieren.
HIer könntest du dein Spielfeld in feste zB 100x100 Felder einteilen und jede Einheit trägt sich beim betreten oder verlassen in den dazugehörigen Quadraten ein. Prüfst du nun für eine Einheit, ob sie schießen kann musst du nur die Quadranten absuchen, in denen sich Einheiten befinden können, die dicht genug für die Angriffsreichweite sind. Da du wahrscheinlich auch nicht erlaubst dass alle Einheiten auf dem selben Punkt stehen, erreichst du so garangiert eine dramatische reduzierung der Komplexität. Außerdem durchsuchst du die in Frage kommenden 10.000 Ziele nicht 'unsortiert' sondern fängst mit den (wort wörtlich) naheliegendsten an, welche sich in dichten Quadranten aufhalten.
Außerdem macht es Sinn, dass eine Einheit den Angriff immer auf die selbe Einheit fortsetzt, wenn sie dieses Ziel einmal hat? Dh solange sie im 'schießen' modus ist, muss sie nicht alle 10.000 untersuchen sondern nur für die aktuell fokusierte Einheit prüfen, ob sie weiterhin in Reichweite ist.

 

[cooldiman1]

@kuddlmuddl

Danke dir Du hast meine Gedanken seit gestern Abend nochmal bestätigt
So wie ich das mit den Quadtrees auf Anhieb verstanden habe sind es ja Zonen.

Meine Überlegungen waren bisher die Units Positionen+UnitId grundsätzlich Zonen zuzuweisen und bei jedem Update, wenn eine Unit sich bewegt hat, zu überprüfen ob sie die Zone gewechselt hat oder sie direkt der passenden Zone zuzuweisen. Was davon schneller effektiver ist kann ich noch nicht sagen. Ich habe schon einen Filter eingebaut der überprüft ob eine Unit ein Ziel hat und wenn ja wird die searchTarget() Funktion nicht aufgerufen.