Самый быстрый способ сгруппировать юниты, которые могут видеть друг друга?

В 2D игре, с которой я работаю, игровой движок может дать мне для каждого юнита список других юнитов, которые находятся в пределах его видимости.

Я хотел бы знать, если существует установленный алгоритм для сортировки единиц в группы , где каждая группа будет определяться всеми теми единицами, которые «связаны» друг с другом (даже через других).

Пример может помочь лучше понять вопрос (E = враг, O = собственный отряд). Сначала данные, которые я получу от игрового движка:

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

Затем я должен вычислить группы следующим образом:

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

Можно смело предположить, что для поля зрения существует коммутативное свойство: [если A видит B, то B видит A].

Просто для пояснения: я уже написал наивную реализацию, которая зацикливается на каждой строке информации о игровом движке, но, судя по всему, кажется, что проблема достаточно общая, чтобы ее можно было подробно изучить и иметь различные установленные алгоритмы (возможно, прохождение через какую-то древовидную структуру?). Моя проблема в том, что я не смог найти способ описать мою проблему, которая принесла полезные хиты Google.

Заранее спасибо за вашу помощь!

Если ваше отношение «вижу» симметрично, так что «А может видеть Б» подразумевает «Б может видеть А», то группы, которые вы хотите вычислить, являются связанными компонентами графа, определяемыми отношением «может видеть». Как уже отмечали другие, существуют простые алгоритмы для их вычисления, такие как:

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

(Вместо стека sвыше можно использовать очередь или любую другую коллекцию, которая эффективно реализует операции «добавить новый элемент» и «удалить и вернуть некоторый элемент» .)

Если ваше отношение «видеть» не является симметричным, вам нужно решить, хотите ли вы, чтобы ваши группы были сильно или слабо связанными компонентами. Для слабосвязанных компонентов приведенный выше алгоритм будет работать как есть, за исключением того, что строка for each unit w that v can seeдолжна быть заменена на for each unit w that can see v, or that v can see. Для сильно связанных компонентов вы можете использовать один из алгоритмов ( Косараю , Тарьяна или Габова ), упомянутых на связанной странице Википедии.

Для несимметричных отношений вы также можете рассчитать транзитивное замыкание отношения или его сильно связанных компонентов. Для этого вы можете использовать алгоритм Флойда – Варшалла ; см. этот ответ на SO для (немного) больше информации.

Ps. Как отмечается в статье Википедии, на которую я ссылался выше, может быть более эффективно динамически обновлять группы при изменении отношения видимости. Я не знаком с продвинутыми (?) Алгоритмами, упомянутыми в Википедии, но не должно быть сложно собрать воедино то, что по крайней мере превосходит пересчет групп с нуля каждый раз.

Половина этого проста: если две единицы в разных группах приобретают прямую видимость между ними, объединяют группы. Работать с единицами, упускающими из виду друг друга, немного сложнее; Одно простое, но, возможно, не оптимальное решение - это перезапускать алгоритм группировки для подразделений в затронутой группе всякий раз, когда это происходит. Есть некоторые оптимизации, которые вы можете сделать, если изменения видимости происходят по одной паре единиц за раз:

• Если юнит может видеть только один юнит и теряет его из виду, просто удалите его из предыдущей группы и назначьте его новой группе.
• В противном случае вы можете начать с одного из задействованных подразделений и выполнить поиск A * на графике видимости (используя, например, расстояние по прямой линии в качестве эвристики) для другого подразделения. Если вы найдете это, группа не распалась; если вы этого не сделаете, набор единиц, которые посетил поиск, образует новую группу.
• Вы можете попытаться угадать, какое из двух подразделений с большей вероятностью будет принадлежать к меньшей половине группы, если оно разделится, и начать поиск с этого подразделения. Одна из возможностей - всегда начинать с устройства, которое может непосредственно видеть меньше других устройств.

То, что у вас есть, это граф связности. И вообще, лучший способ сгруппировать связанные узлы (то есть: символы) вместе с алгоритмом поиска графа. Глубина первая, ширина первая, в зависимости от того, что Все, что вы делаете, это создаете список, какие узлы доступны из всех остальных. Пока ваш график не направлен (если A видим для B, то B видим для A), это работает нормально.

Там могут быть некоторые алгоритмы, чтобы улучшить это для конкретных случаев. Например, если иногда персонажи не двигаются (и местность не движется тоже, поэтому неподвижные персонажи остаются видимыми), вы можете не проверять их снова, чтобы обновить их графики связности.

Но в целом вам придется повторно тестировать видимость каждого кадра. Скорее всего, это будет медленнее, чем обход графа, чтобы найти группы видимости.

Похоже, проблема подключения стандартного графа. Для этого вполне может быть какой-то алгоритм, и он может выглядеть следующим образом:

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

Я ожидаю, что это можно реализовать с помощью дерева, например, иерархической кластеризации, но я сомневаюсь, что это сработает быстрее - деревья, как правило, имеют значение O (log N), тогда как большинство проверок, которые я даю выше, могут быть реализованы как O (1). ,

Я согласен со всеми, кто ответил, что это проблема с подключением графа, однако позвольте мне указать, что вам нужен график триангуляции Делоне, сгенерированный из всех ваших соответствующих единиц измерения. Это гарантирует, что на генерируемом вами графике будут подключены только самые близкие единицы. Вам будет очень сложно сделать это любым другим способом, потому что пересечения графа (непланарность) приведут к тому, что слишком далекие единицы будут неправильно соединены в графе.

Вышеуказанное применимо только в том случае, если вы используете непрерывный пробел (как в большинстве FPS со свободным движением); однако, если у вас уже есть базовая сетка (планарный график), по которой перемещаются ваши подразделения, вы можете просто использовать ее для оценки связности.