Najszybszy sposób na grupowanie jednostek, które się widzą?

W grze 2D, z którą pracuję, silnik gry jest w stanie podać dla każdej jednostki listę innych jednostek znajdujących się w jej zasięgu widzenia.

Chciałbym wiedzieć, czy istnieje ustalony algorytm sortowania jednostek w grupach , gdzie każda grupa byłaby zdefiniowana przez wszystkie te jednostki, które są „połączone” ze sobą (nawet przez inne).

Przykład może pomóc lepiej zrozumieć pytanie (E = wróg, O = własna jednostka). Najpierw dane, które otrzymam z silnika gry:

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

Następnie powinienem obliczyć grupy w następujący sposób:

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

Można bezpiecznie założyć, że istnieje pole przemienne pola widzenia: [jeśli A widzi B, to B widzi A].

Żeby wyjaśnić: napisałem już naiwną implementację, która zapętla się w każdym rzędzie informacji o silniku gry, ale z wyglądu wydaje się, że problem jest na tyle ogólny, że można go dogłębnie zbadać i zastosować różne ustalone algorytmy (być może przez jakąś drzewiastą strukturę?). Mój problem polega na tym, że nie mogłem znaleźć sposobu na opisanie mojego problemu, który zwrócił użyteczne trafienia w Google.

Z góry dziękuję za Twoją pomoc!

Jeśli twoja relacja „widzi” jest symetryczna, więc „A widzi B” oznacza, że ​​„B widzi A”, to grupy, które chcesz obliczyć, są połączonymi składnikami wykresu zdefiniowanymi przez relację „widzi”. Jak zauważyli inni, istnieją proste algorytmy ich obliczania, takie jak:

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

(Zamiast stosu spowyżej można zastosować kolejkę lub inną kolekcję, która skutecznie realizuje operacje „dodaj nowy element” i „usuń i zwróć jakiś element” ).

Jeśli twoja relacja „widzi” nie jest symetryczna, musisz zdecydować, czy chcesz, aby twoje grupy były silnie, czy słabo połączonymi komponentami. W przypadku słabo połączonych komponentów powyższy algorytm będzie działał tak, jak jest, z wyjątkiem tego, że wiersz for each unit w that v can seenależy zastąpić for each unit w that can see v, or that v can see. W przypadku silnie połączonych komponentów można użyć jednego z algorytmów ( Kosaraju , Tarjan lub Gabow ) wymienionych na powiązanej stronie Wikipedii.

W przypadku relacji niesymetrycznych możesz również obliczyć przechodnie zamknięcie relacji lub jej silnie połączonych komponentów. W tym celu możesz użyć algorytmu Floyda – Warshalla ; zobacz tę odpowiedź na SO, aby uzyskać (trochę) więcej informacji.

Ps. Ponieważ artykuł w Wikipedii, do którego nawiązałem powyższe uwagi, może być bardziej wydajne dynamiczne aktualizowanie grup wraz ze zmianą relacji widoczności. Nie jestem zaznajomiony z zaawansowanymi (?) Algorytmami wymienionymi na Wikipedii, ale nie powinno być trudno połączyć coś, co przynajmniej przewyższa przeliczanie grup za każdym razem.

Połowa z tego jest łatwa: jeśli dwie jednostki w różnych grupach uzyskają między nimi linię wzroku, połącz grupy. Radzenie sobie z jednostkami tracącymi się z oczu jest nieco trudniejsze; jednym prostym, ale być może nieoptymalnym rozwiązaniem jest ponowne uruchomienie algorytmu grupowania dla jednostek w grupie, której to dotyczy, ilekroć to się stanie. Istnieją pewne optymalizacje, które można wprowadzić, jeśli zmiany widoczności występują po jednej parze jednostek na raz:

• Jeśli jednostka może zobaczyć tylko jedną inną jednostkę i straci ją z pola widzenia, po prostu usuń ją z poprzedniej grupy i przypisz do nowej grupy.
• W przeciwnym razie możesz zacząć od jednej z jednostek, których dotyczy problem, i przeprowadzić wyszukiwanie A * na wykresie widoczności (używając np. Odległości linii prostej jako heurystyki) dla drugiej jednostki. Jeśli go znajdziesz, grupa się nie rozpadła; jeśli nie, zestaw jednostek, które odwiedził wyszukiwarka, tworzy nową grupę.
• Możesz spróbować zgadnąć, która z dwóch jednostek jest bardziej skłonna do przynależności do mniejszej połowy grupy, jeśli się podzieli, i rozpocznij wyszukiwanie od tej jednostki. Jedną z możliwości byłoby zawsze zacząć od jednostki, która bezpośrednio widzi mniej innych jednostek.

To, co masz, to wykres łączności. Ogólnie rzecz biorąc, najlepszym sposobem grupowania połączonych węzłów (tj. Znaków) jest użycie algorytmu wyszukiwania grafów. Najpierw głębokość, najpierw szerokość, cokolwiek. Wszystko, co robisz, to budowanie listy dostępnych węzłów ze wszystkich innych. Dopóki twój wykres nie jest przekierowany (jeśli A jest widoczny dla B, to B jest widoczny dla A), działa to dobrze.

W niektórych przypadkach mogą istnieć pewne algorytmy poprawiające to. Na przykład, jeśli czasem postacie się nie poruszają (a teren też się nie porusza, więc nieruchome postacie pozostają widoczne), możesz zrezygnować z ich ponownego testowania, aby zaktualizować wykresy połączeń.

Ale ogólnie rzecz biorąc, będziesz musiał ponownie sprawdzić widoczność każdej klatki. Szanse są, to będzie wolniejsze niż przejście wykresu, aby znaleźć grupy widoczności.

Wydaje się, że jest to standardowy problem z łącznością z wykresem. Może być do tego jakiś algorytm, który może wyglądać następująco:

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

Oczekuję, że można to zaimplementować za pomocą drzewa, takiego jak hierarchiczne grupowanie, ale wątpię, by działało to szybciej - drzewa zwykle mają postać O (log N), podczas gdy większość kontroli, które podałem powyżej, można zaimplementować jako O (1) .

Zgadzam się ze wszystkimi innymi, którzy odpowiedzieli, że jest to problem z połączeniem grafu, jednak pozwól mi zaznaczyć, że potrzebujesz tutaj wykresu triangulacji Delaunaya wygenerowanego ze wszystkich odpowiednich jednostek. Powoduje to, że na generowanym przez Ciebie wykresie zostaną połączone tylko jednostki znajdujące się najbliżej siebie. Bardzo trudno będzie to zrobić w inny sposób, ponieważ przecięcia wykresów (nieplanarność) spowodują, że jednostki znajdujące się zbyt daleko od siebie będą niepoprawnie połączone w obrębie wykresu.

Powyższe ma zastosowanie tylko wtedy, gdy używasz ciągłego spacji (jak w większości FPS swobodnie poruszających się); Jeśli jednak masz już siatkę bazową (wykres płaski), na której poruszają się twoje jednostki, możesz po prostu użyć jej do oceny łączności.