| Возвращаясь к перестроению юнитов |
| mihail_msk | Дата: Понедельник, 19.09.2011, 23:02 | Сообщение # 1 |
|
Ополченец
Группа: Проверенные
Сообщений: 32
Награды: 0
Репутация: 2
Статус: Offline
| Возвращаясь к перестроению юнитов. Я тут пока шел с работы придумал свой алгоритмик. Я полный профан в этих вопросах и если есть специалисты или уже известные хорошие алгоритмы такого рода - просьба меня ногами не пинать 
Алгоритм сводится к последовательному сканированию всего пространства, которое занимают юниты с четырех углов и их группировку относительно этих же четырех углов. Группировка просиходит условным движением юнитов от клеток
с меньшим весом к клеткам с большим весом с ограниченным набором направлений движения.
Его наглядное пояснение - в приложено как картинка.
Если вдруг ничего лучше не придумаете, то могу пояснить поподробнее, что на этих картинках имеется в виду.
Сообщение отредактировал mihail_msk - Среда, 21.09.2011, 15:00 |
| |
| | |
| Krom | Дата: Вторник, 20.09.2011, 12:37 | Сообщение # 2 |
|
Воитель
Группа: Супер Модераторы
Сообщений: 2463
Награды: 25
Репутация: 153
Статус: Offline
| Я не совсем понял идею, но кажется в ней есть недостаток - в схеме юниты всегда находятся "под" углом, а что если они расположены иначе? Например хаотично стоят и отряд должен встать в центре.
Нашли баг в КаМ Ремейке? Отправьте отчет на с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
|
| |
| | |
| mihail_msk | Дата: Вторник, 20.09.2011, 15:23 | Сообщение # 3 |
|
Ополченец
Группа: Проверенные
Сообщений: 32
Награды: 0
Репутация: 2
Статус: Offline
| Krom, это универсальный алгоритм для построения из любого , даже хаотичного положения юнитов в прямоугольник. Если же отряду нужно встать по-диагонали, то можно придумать слегка модифицированный алгоритм - тогда и исходная зона сканирования и конечный вариант построения будут тоже повернуты по-диагонали.
На первой картинке приведен только порядок сканирования - там не показаны реальные юниты. Демонстрация группировки реальных юнитов - на последней картинке. Там они довольно хаотично стоят внутри квадрата. А сканирующий квадрат просто строится так, чтобы захватить всех юнитов.
Кстати, лучше сразу делать диагональное построения с учётом более плотного построения, которое я предложил. Я понимаю, многим удобно ставить один отряд внутрь другого при таком построении. Но это всё-таки не правильно, что при простом повороте фактически меняется формация - с плотной на разреженную. Если кому-то хочется иметь разреженные формации, логичнее сделать (как в age of empires 2 ) тоже два режима - плотный и разреженный, независимо от направления построения.
Но поскольку этот вопрос требует осмысления, то лучше для начала сделать перестроение только для построения в прямоугольник, не по-диагонали.
Сообщение отредактировал mihail_msk - Вторник, 20.09.2011, 15:26 |
| |
| | |
| Krom | Дата: Среда, 21.09.2011, 09:32 | Сообщение # 4 |
|
Воитель
Группа: Супер Модераторы
Сообщений: 2463
Награды: 25
Репутация: 153
Статус: Offline
| mihail_msk, Давай пока без диагональных построений, для простоты обсуждения.
- Вот есть куча из 20 юнитов на площади 10х10, как им встать отрядом 4х5 в произвольном месте?
- Есть отряд 4х5, как ему перегруппироваться в 5х4?
- Как встать отряду 4х5 на узком мосту шириной 3?
- Как встать отряду 4х5 если 3 произвольных места в его расположении заняты непроходимыми камнями?
- Учеть, что в поле могут быть и другие неподвластные нам объекты/юниты, т.е. нельзя предсказать, что один юнит придет на свое место раньше другого при меньшем расстоянии ходьбы.
Исходные данные - список юнитов и их положений. Результат - приказы кому куда идти.
Нашли баг в КаМ Ремейке? Отправьте отчет на с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
|
| |
| | |
| mihail_msk | Дата: Среда, 21.09.2011, 13:02 | Сообщение # 5 |
|
Ополченец
Группа: Проверенные
Сообщений: 32
Награды: 0
Репутация: 2
Статус: Offline
| С одиночными редкими камнями и другими юнитами неразрешимых проблем в теории быть не должно - просто при группировке к углам эти помехи расставляются там. Если же они не одиночные, а по два или три в ряд - алгоритм хорошо работать не будет 
Но может быть не нужно такой сложный случай сразу рассматривать....
Что касается построения 5x4 и прочих - то сканирование по углам вроде бы должно нормально работать для любого прямоугольника. Причем прямоугольник сканирующей области и прямоугольник финального построения могут быть совсем разными.
Если нужно выстроить в линию - особый случай, нужно модифицировать этот алгоритм или динамически менять на другой.
Но вообще хорошо бы сначала обратиться по e-mail к разным студиям разработки rts игр, написать вопросы на форумах - на том же gamedev.ru похожие вопросы часто поднимаются. Еще можно подробно погуглить на тему "rts unit formation". И только потом ("от безнадеги") браться за мой алгоритм.
По-хорошему нужно написать на delphi маленькую программку-стенд для отладки технологии перестроения. В программке будет 6 гридов (можно обычные штатные гриды взять). Первый грид - исходное хаотичное построение. 2-5 гриды - для демонстрации пошаговой группировки по 4 углам. Шестой грид - отображает финальное построение. Писать такую программку в ближайшие 2-3 недели у меня времени нет. Но если кто-нибудь возьмется - могу уже на этапе работающего алгоритма немного потестировать и поотлаживать.Добавлено (21.09.2011, 13:02)
---------------------------------------------
Я разместил этот вопрос на gamedev.ru
http://www.gamedev.ru/code/forum/?id=152639
Причем я подумал, что сложнее и актуальнее всего построение в формацию именно из хаотического положения. И мой алгоритм рассчитан именно на это.
А для перестроения можно использовать более простые методы.
Например, при перестроении из фаланги 3x5 в колонну 5x3 просто две последние шеренги разделяются пополам и становятся по бокам первых трех шеренг.
Сообщение отредактировал mihail_msk - Среда, 21.09.2011, 12:27 |
| |
| | |
| Krom | Дата: Среда, 21.09.2011, 14:14 | Сообщение # 6 |
|
Воитель
Группа: Супер Модераторы
Сообщений: 2463
Награды: 25
Репутация: 153
Статус: Offline
| Алгоритм должен работать для всех случаев, без особых вариантов. На таких особых вариантах у нас сейчас взаимодействие юнитов написано - это жесть.
Я так и не понимаю как сканирование углов решает проблему в общем случае, это алгоритм расстановки весов или..? Ты мог бы написать тестовую программку, например на GDI ? Можно проще - взять канву и на ней двигать квадраты. Достаточно 2х состояний для начала - исходное и стрелки кто куда пойдет.
Использование простых методов для перестроения - плохая идея. Опять же толкотня и оптимальное решение в таком случае - боковые должны разойтись, а задние зайти внутрь. Причем это зависит от численности войск, писать под это особые методы - значит погрязнуть в деталях.
Нашли баг в КаМ Ремейке? Отправьте отчет на с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
|
| |
| | |
| mihail_msk | Дата: Среда, 21.09.2011, 17:48 | Сообщение # 7 |
|
Ополченец
Группа: Проверенные
Сообщений: 32
Награды: 0
Репутация: 2
Статус: Offline
| Ладно, если будет немного времени, в течении двух недель попробую закодировать алгоритм. Тогда искать другие, не "бредовые" как мой, а реально профессиональные алгоритмы придется кому-нибудь еще.
Вот такой стенд я имел в виду - пока что он без наполнения.
Сообщение отредактировал mihail_msk - Среда, 21.09.2011, 17:49 |
| |
| | |
| Krom | Дата: Среда, 21.09.2011, 19:55 | Сообщение # 8 |
|
Воитель
Группа: Супер Модераторы
Сообщений: 2463
Награды: 25
Репутация: 153
Статус: Offline
| Как нам посоветовал человек с геймдева - надо посчитать все пути и использовать алгоритм подбора пар: http://en.wikipedia.org/wiki/Hungarian_algorithm Там внизу есть примеры на разных языках, самый подходящий нам, кажется, C#.
Нашли баг в КаМ Ремейке? Отправьте отчет на с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
|
| |
| | |
| mihail_msk | Дата: Четверг, 22.09.2011, 00:07 | Сообщение # 9 |
|
Ополченец
Группа: Проверенные
Сообщений: 32
Награды: 0
Репутация: 2
Статус: Offline
| Скопирую сюда мой ответ на gamedev, чтобы все были в курсе:
Я боюсь, что всё не так хорошо, как тебе кажется, Krom.
Венгерский алгоритм является, как я понял, упрощенной дискретной вариацией задачи о назначении.
Эту задачу я один раз реально прочитывал в MatLab-е для одной моей квалификационной работы. Так вот, там можно задать только веса расстояний от юнита до каждой из клеток. Но такая оптимальная по расстояниям расстановка вовсе не гарантирует от заторов ! Ведь алгоритму всё равно, пройдут два юнита расстояние по одной клетке, или один задний пройдет две клетки - ведь общее пройденное расстояние одинаково. А то, что задний в реале не сможет перепрыгнуть переднего этот алгоритм не интересует - он не для этого сделан.
Да и объем вычислений , как там написано - X^3 т.е. для отряда в 100 юнитов количество вычислений будет 100x100x100 что может быть слишком долго для rts игры.
Так что вопрос пока открыт.
|
| |
| | |
| Krom | Дата: Четверг, 22.09.2011, 10:50 | Сообщение # 10 |
|
Воитель
Группа: Супер Модераторы
Сообщений: 2463
Награды: 25
Репутация: 153
Статус: Offline
| Скопирую сюда мой ответ на gamedev, чтобы все были в курсе:
Значит нам нужен алгоритм, который не только выбирает пары с минимальным суммарным расстоянием, но и с наиболее равномерным их распределением. В таком случае можно попробовать этот алгоритм: http://en.wikipedia.org/wiki/Transportation_problem - тут есть абзац про затраты времени на перемещение книг. К сожалению в русском переводе его нет, но думаю смысл примерно понятен - штрафуются варианты с неравномерными весами (1+1+1 предпочтительнее 0+0+3).
Что-либо поделать с коллизиями мы не можем, т.к. заранее неизвестно какой путь будет признан оптимальным и сколько в нем будет пересечений между юнитами совпадающих по времени, учитывая внешние факторы и особенности местности.
Кстати, выделяется параллельная задача - с учетом проходимости местности, выбрать места где встанут юниты не попавшие в строй.
Армия из 100 это нонсенс, можем принять это как максимальное значение, если при нём будет работать, то нам подойдёт.
Нашли баг в КаМ Ремейке? Отправьте отчет на с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
|
| |
| | |
| mihail_msk | Дата: Четверг, 22.09.2011, 14:51 | Сообщение # 11 |
|
Ополченец
Группа: Проверенные
Сообщений: 32
Награды: 0
Репутация: 2
Статус: Offline
| KD tree - отличная идея ! Можно разбивать исходное множество юнитов по медиане сначала по вертикали на a1 и a2 . Потом a и b - по горизонтали на a1 , a2 b1 и b2. И уже эти четвертинки группировать по углам по моему методу. Или дальше разбивать по медиане до элементарных квадратов
2x2, 1x2 которые станут "кирпичиками" требуемого построения. Правда, проблема в том что равномерно разбить будет сложно - придется часть клеток ряда отсечения относить к одному подмножеству, а часть к другому. Но это вроде бы решаемо. Можно будет попробовать такую технологию вместо "сканирования по углам".
Что касается венгерского алгоритма с квадратичным весом расстояний от юнита до клетки - то он тоже выглядит весьма заманчиво и может сработать. Его тоже можно попробовать реализовать. Вот, есть хорошая иллюстрация венгерского алгоритма : http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/hungarian-2002
Сообщение отредактировал mihail_msk - Четверг, 22.09.2011, 15:10 |
| |
| | |
| Krom | Дата: Четверг, 22.09.2011, 15:34 | Сообщение # 12 |
|
Воитель
Группа: Супер Модераторы
Сообщений: 2463
Награды: 25
Репутация: 153
Статус: Offline
| Заниматься оптимизациями до того как будет готов протестирован и отлажен основной алгоритм - зло. Только время потратится и сложность возрастет, чтобы потом узнать, что узкое место в чем-то другом.
Я - за венгерский алгоритм с квадратами расстояний (лучше даже вынести степень в регулируемые параметры, для интереса). Просто и доступно.
Можно попросить тебя реализовать его в Делфи?
Нашли баг в КаМ Ремейке? Отправьте отчет на с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
|
| |
| | |
| mihail_msk | Дата: Понедельник, 26.09.2011, 02:35 | Сообщение # 13 |
|
Ополченец
Группа: Проверенные
Сообщений: 32
Награды: 0
Репутация: 2
Статус: Offline
| Я не уверен, что венгерский алгоритм будет так уж хорош. Особенно при построении отрядов больше 30 чел, всё-таки это "тяжелый" алгоритм полной оптимизации. Лучше попроси реализовать его товарища, который брался за это на ActionScript 3. Тем более его можно найти на С++ и довольно быстро переписать: http://code.google.com/p/hungarianassignment/
А я за 2-3 недели попробую найти время и реализовать на Delphi свой агроритм. Я сегодня придумал, как его улучшить. Нужно будет немного изменить порядок сканирования и использовать совсем другой принцип группировки по углам. Я называю его "последовательным подбитием с разных сторон".
И тогда мы сравним, какой алгоритм лучше и выберем его для интеграции в ремейк.
Сообщение отредактировал mihail_msk - Понедельник, 26.09.2011, 02:42 |
| |
| | |
| Krom | Дата: Понедельник, 26.09.2011, 09:10 | Сообщение # 14 |
|
Воитель
Группа: Супер Модераторы
Сообщений: 2463
Награды: 25
Репутация: 153
Статус: Offline
| mihail_msk, основное время венгерского алгоритма занимает вычисление расстояний между всеми юнитами и всеми позициями. Твоему алгоритму это не нужно?
Можно обрисовать примерные рамки того что надо сделать:
Требования непосредственно к алгоритму - это должна быть 1 функция, которая принимает 2 массива TPoint и выдает массив TPoint (в котором указаны пару - кому куда идти). Тебе будет удобно использовать такое объявление для своего алгоритма? Дело в том что надо учитывать непроходимые тайлы, которые могут быть в зоне построения отряда (банальны пример - построить отряд 4х5 на узком мосту). Я предполагаю, что сначала будет алгоритм поиска мест (он уже по сути есть и достаточно простой). Если тебе удобнее, то тогда вместо массива доступных мест - будет отправляться наоборот - массив недоступных мест в области нахождения отряда.
Тогда, можно будет выполнить каждую функцию по 100000 раз на случайных данных и определить - какая быстрее )
Нашли баг в КаМ Ремейке? Отправьте отчет на с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
|
| |
| | |
| mihail_msk | Дата: Понедельник, 26.09.2011, 12:03 | Сообщение # 15 |
|
Ополченец
Группа: Проверенные
Сообщений: 32
Награды: 0
Репутация: 2
Статус: Offline
| Quote (Krom) основное время венгерского алгоритма занимает вычисление расстояний между всеми юнитами и всеми позициями. Твоему алгоритму это не нужно?
Нет, не нужно :). К тому же, посмотрев визуализатор http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/hungarian-2002 я уверен, что первоначальное вычисление расстояний - это менее 10% всех вычислений по венгерскому алгоритму.
По поводу того, какой должна быть функция. На входе должны быть два двумерных массива. my_array =array(x,y) - где x и y - координаты ячейки.
Первый - требуемое расположение юнитов и препятствий внутри формации, второй - расположение юнитов сейчас. На выходе - двумерный массив такого же типа - какой юнит в какую клетку должен идти.
Можно, конечно, и одномерные массивы как ты предлагаешь использовать на входе и выходе а внутри их конвертировать в двумерные - но я не вижу в этом особого смысла.
В общем, сделаю пока как мне удобно, а потом переделаю формат входа и выхода, если будет нужно.
А вычислять требуемое расположение отряда с учетом крупных препятствий типа мостов и гор должен уже другой алгоритм. Причем он в ремейке уже есть, как я понимаю.
Сообщение отредактировал mihail_msk - Понедельник, 26.09.2011, 12:09 |
| |
| |
|
