Der schnellste Weg, um Einheiten zu gruppieren, die sich gegenseitig sehen können?

In dem 2D-Spiel, mit dem ich arbeite, kann mir die Game Engine für jede Einheit die Liste der anderen Einheiten anzeigen, die sich in ihrem Sichtbereich befinden.

Ich würde gerne wissen, ob es einen etablierten Algorithmus gibt, um die Einheiten in Gruppen zu sortieren , wobei jede Gruppe durch alle Einheiten definiert wird, die miteinander "verbunden" sind (auch durch andere).

Ein Beispiel könnte helfen, die Frage besser zu verstehen (E = Feind, O = eigene Einheit). Zuerst die Daten, die ich von der Game Engine bekommen würde:

E1 can see E2, E3, O5
E2 can see E1
E3 can see E1
E4 can see O5
E5 can see O2
E6 can see E7, O9, O1
E7 can see E6
O1 can see E6
O2 can see O5, E5
O5 can see E1, E4, O2
O9 can see E6

Dann sollte ich die Gruppen wie folgt berechnen:

G1 = E1, E2, E3, E4, E5, O2, O5
G2 = O1, O9, E6, E7

Es kann mit Sicherheit angenommen werden, dass es eine kommutative Eigenschaft für das Sichtfeld gibt: [Wenn A B sieht, dann sieht B A].

Nur zur Verdeutlichung: Ich habe bereits eine naive Implementierung geschrieben, die sich in jeder Zeile der Game-Engine-Informationen wiederholt, aber es scheint ein allgemeines Problem zu sein, das eingehend untersucht wurde und über verschiedene etablierte Algorithmen verfügt (möglicherweise erfolgreich) durch eine baumartige Struktur?). Mein Problem ist, dass ich keinen Weg gefunden habe, mein Problem zu beschreiben, das nützliche Google-Treffer ergab.

Vielen Dank im Voraus für deine Hilfe!

Wenn Ihre Beziehung "Kann sehen" symmetrisch ist, so dass "A kann sehen, B" "B kann sehen, A" impliziert, sind die zu berechnenden Gruppen die verbundenen Komponenten des durch die "Kann sehen" -Relation definierten Diagramms. Wie andere angemerkt haben, gibt es einfache Algorithmen, um diese zu berechnen, wie zum Beispiel:

while ungrouped units remain:
    let u = arbitrary ungrouped unit
    let g = new group
    let s = temporary stack
    assign u to g
    push u onto s
    while s is not empty:
        let v = topmost unit in s
        remove v from s
        for each unit w that v can see:
            if w is ungrouped:
                assign w to g
                push w onto s
            end if
        end for
    end while
 end while

(Eine Warteschlange oder eine andere Sammlung, die die Operationen "Neues Element hinzufügen" und "Element entfernen und zurückgeben" effizient implementiert, kann anstelle des sobigen Stapels verwendet werden .)

Wenn Ihre "Kann sehen" -Relation nicht symmetrisch ist, müssen Sie entscheiden, ob Ihre Gruppen die stark oder die schwach verbundenen Komponenten sein sollen. Bei schwach verbundenen Komponenten funktioniert der obige Algorithmus so, wie er ist, mit der Ausnahme, dass die Zeile for each unit w that v can seedurch ersetzt werden sollte for each unit w that can see v, or that v can see. Für stark verbundene Komponenten können Sie einen der Algorithmen verwenden ( Kosarajus , Tarjans oder Gabow der ) auf der verlinkten Wikipedia - Seite erwähnt.

Bei nicht symmetrischen Beziehungen möchten Sie möglicherweise auch den transitiven Abschluss der Beziehung oder ihrer stark verbundenen Komponenten berechnen . Hierfür können Sie den Floyd-Warshall-Algorithmus verwenden . Siehe diese Antwort auf SO für (ein bisschen) mehr Informationen.

Ps.Da der Wikipedia-Artikel, den ich mit den obigen Anmerkungen verlinkt habe, möglicherweise effizienter ist, die Gruppen dynamisch zu aktualisieren, wenn sich die Sichtbarkeitsrelation ändert. Ich kenne die in Wikipedia erwähnten fortgeschrittenen (?) Algorithmen nicht, aber es sollte nicht schwer sein, etwas zusammenzubauen, das es zumindest übertrifft, die Gruppen jedes Mal von Grund auf neu zu berechnen.

Eine Hälfte davon ist einfach: Wenn zwei Einheiten in verschiedenen Gruppen eine Sichtlinie zwischen ihnen erhalten, führen Sie die Gruppen zusammen. Der Umgang mit Einheiten, die sich aus den Augen verlieren, ist etwas kniffliger. Eine einfache, aber möglicherweise nicht optimale Lösung besteht darin, den Gruppierungsalgorithmus für die Einheiten in der betroffenen Gruppe in jedem Fall erneut auszuführen. Es gibt einige Optimierungen, die Sie vornehmen können, wenn die Sichtbarkeitsänderungen paarweise auftreten:

• Wenn eine Einheit nur eine andere Einheit sehen konnte und diese aus den Augen verliert, entfernen Sie sie einfach aus ihrer vorherigen Gruppe und weisen Sie sie einer neuen Gruppe zu.
• Andernfalls könnten Sie an einer der betroffenen Einheiten starten und eine ausführen A * -Suche in der Sichtbarkeitsgrafik für die andere Einheit (z. B. anhand der geraden Entfernung als Heuristik). Wenn Sie es finden, hat sich die Gruppe nicht getrennt; Andernfalls bildet der von der Suche aufgerufene Einheitensatz die neue Gruppe.
• Sie könnten versuchen, zu erraten, welche der beiden Einheiten eher zur kleineren Hälfte der Gruppe gehört, wenn sie sich aufteilt, und die Suche von dieser Einheit aus starten. Eine Möglichkeit wäre, immer von der Einheit aus zu starten, die direkt weniger andere Einheiten sehen kann.

Was Sie haben, ist ein Konnektivitätsdiagramm. Und im Allgemeinen ist der beste Weg, die verbundenen Knoten (dh Zeichen) zu gruppieren, ein Graphensuchalgorithmus. Tiefe zuerst, Breite zuerst, was auch immer. Sie erstellen lediglich eine Liste der Knoten, die von allen anderen aus erreichbar sind. Solange Ihr Diagramm ungerichtet ist (wenn A für B sichtbar ist, ist B für A sichtbar), funktioniert dies einwandfrei.

Möglicherweise gibt es einige Algorithmen, um dies für bestimmte Fälle zu verbessern. Wenn sich Zeichen zum Beispiel manchmal nicht bewegen (und sich das Gelände auch nicht bewegt, sodass unbewegliche Zeichen sichtbar bleiben), können Sie festlegen, dass sie nicht erneut getestet werden, um ihre Konnektivitätsdiagramme zu aktualisieren.

Im Allgemeinen müssen Sie jedoch die Sichtbarkeit jedes Frames erneut testen. Wahrscheinlich ist dies langsamer als der Diagrammdurchlauf, um die Sichtbarkeitsgruppen zu finden.

Scheint wie ein Standard-Graph-Konnektivitätsproblem. Möglicherweise gibt es dafür einen Algorithmus, der wie folgt aussieht:

remaining units = all units
for each unit in remaining units:
    current group = create a new group
    add this unit to current group
    for each unit visible to this unit:
        if unit is in a group already:
            merge current group into that existing group
            set current group as that existing group
        else:
            remove that unit from remaining units
            add that unit to current group

Ich erwarte, dass es möglich ist, dies über einen Baum wie hierarchisches Clustering zu implementieren, aber ich bezweifle, dass dies schneller funktionieren würde - Bäume sind in der Regel O (log N), wohingegen die meisten der oben angegebenen Prüfungen als O (1) implementiert werden können. .

Ich stimme allen anderen zu, die daraufhin geantwortet haben, dass es sich um ein Graph-Konnektivitätsproblem handelt. Lassen Sie mich jedoch darauf hinweisen, dass Sie hier die Delaunay-Triangulation benötigen aus all Ihren relevanten Einheiten generiert wurde. Auf diese Weise wird sichergestellt, dass nur Einheiten in dem von Ihnen erstellten Diagramm verbunden werden, die einander am nächsten sind. Sie werden es sehr schwierig finden, dies auf andere Weise zu tun, da durch das Kreuzen von Graphen (Nicht-Planarität) Einheiten zu weit voneinander entfernt sind, um innerhalb des Graphen falsch verbunden zu werden.

Dies gilt nur, wenn Sie einen durchgehenden Bereich verwenden (wie bei den meisten FPS mit freier Bewegung). Wenn Sie jedoch bereits ein zugrunde liegendes Raster (ein planares Diagramm) haben, auf dem sich Ihre Einheiten bewegen, können Sie dieses nur verwenden, um stattdessen die Konnektivität zu bewerten.