Способы определения группы единиц в РТС

Question

В поисках алгоритма, который можно использовать для определения групп юнитов, которые движутся вместе в отряде в стратегической игре в реальном времени, такой как StarCraft. Направление, на которое я сейчас обращаю внимание, - это алгоритм кластеризации, но ему сложно найти, какой из них будет работать лучше, поскольку юниты движутся как группа, а не просто стоят на месте. Любая помощь будет великолепна.

Answer 1

K-означает не лучший выбор, так как он требует от вас указать количество кластеров, которые вы ожидаете найти. Некоторые из них могут содержать отдельные объекты.

Я рекомендую адаптировать DBSCAN. В частности, обобщенная версия GDBSCAN.

Для этого вам необходимо определить, что составляет окрестность отряда, скажем, любого другого отряда в диапазоне 2, принадлежащего тому же игроку и движущегося примерно в одном направлении (до определенной дельты порог в x и y скорости).

Далее, вам нужно указать, когда вы рассматриваете юниты, чтобы начать формировать начальный кластер, называемый «базовой точкой». Скажите, что это минимум 3 единиц.

Тогда использование DBSCAN является довольно простым и должно дать вам хорошие результаты. Вам нужно немного настроить параметры. Такие вещи, как этот минимальный размер, явно являются входным параметром и зависят от вашего варианта использования. Как и определение окрестности: вы ищете группы, которые движутся в одном направлении, эту информацию нужно как-то включить в алгоритм. С GDBSCAN это тривиально, корректируя определение окрестности.

Answer 2

Возможно, вы захотите взглянуть на ряд алгоритмов классификации, например k-Nearest Neighbor или Машины опорных векторов

Answer 3

Kmeans Алгоритм довольно простой и стандартный подход.Вы можете проверить, работает ли он: