[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 3
  • 1
  • 2
  • 3
  • »
Модератор форума: Jery  
Форум » Knights and Merchants: Remake » Редактирование игры » Возвращаясь к перестроению юнитов (ищем алгоритм)
Возвращаясь к перестроению юнитов
mihail_mskДата: Понедельник, 19.09.2011, 23:02 | Сообщение # 1
Ополченец
Группа: Проверенные
Сообщений: 32
Награды: 0
Репутация: 2
Статус: Offline
Возвращаясь к перестроению юнитов. Я тут пока шел с работы придумал свой алгоритмик. Я полный профан в этих вопросах и если есть специалисты или уже известные хорошие алгоритмы такого рода - просьба меня ногами не пинать smile

Алгоритм сводится к последовательному сканированию всего пространства, которое занимают юниты с четырех углов и их группировку относительно этих же четырех углов. Группировка просиходит условным движением юнитов от клеток
с меньшим весом к клеткам с большим весом с ограниченным набором направлений движения.
Его наглядное пояснение - в приложено как картинка.
Если вдруг ничего лучше не придумаете, то могу пояснить поподробнее, что на этих картинках имеется в виду.
Прикрепления: 0574755.gif(24.6 Kb)


Сообщение отредактировал mihail_msk - Среда, 21.09.2011, 15:00
 
KromДата: Вторник, 20.09.2011, 12:37 | Сообщение # 2
Воитель
Группа: Супер Модераторы
Сообщений: 2526
Награды: 25
Репутация: 153
Статус: Offline
Я не совсем понял идею, но кажется в ней есть недостаток - в схеме юниты всегда находятся "под" углом, а что если они расположены иначе? Например хаотично стоят и отряд должен встать в центре.

Нашли баг в КаМ Ремейке? Отправьте отчет на contact@kamremake.com с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
 
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
Воитель
Группа: Супер Модераторы
Сообщений: 2526
Награды: 25
Репутация: 153
Статус: Offline
mihail_msk, Давай пока без диагональных построений, для простоты обсуждения.

- Вот есть куча из 20 юнитов на площади 10х10, как им встать отрядом 4х5 в произвольном месте?
- Есть отряд 4х5, как ему перегруппироваться в 5х4?
- Как встать отряду 4х5 на узком мосту шириной 3?
- Как встать отряду 4х5 если 3 произвольных места в его расположении заняты непроходимыми камнями?
- Учеть, что в поле могут быть и другие неподвластные нам объекты/юниты, т.е. нельзя предсказать, что один юнит придет на свое место раньше другого при меньшем расстоянии ходьбы.

Исходные данные - список юнитов и их положений. Результат - приказы кому куда идти.


Нашли баг в КаМ Ремейке? Отправьте отчет на contact@kamremake.com с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
 
mihail_mskДата: Среда, 21.09.2011, 13:02 | Сообщение # 5
Ополченец
Группа: Проверенные
Сообщений: 32
Награды: 0
Репутация: 2
Статус: Offline
С одиночными редкими камнями и другими юнитами неразрешимых проблем в теории быть не должно - просто при группировке к углам эти помехи расставляются там. Если же они не одиночные, а по два или три в ряд - алгоритм хорошо работать не будет sad
Но может быть не нужно такой сложный случай сразу рассматривать....

Что касается построения 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
Воитель
Группа: Супер Модераторы
Сообщений: 2526
Награды: 25
Репутация: 153
Статус: Offline
Алгоритм должен работать для всех случаев, без особых вариантов. На таких особых вариантах у нас сейчас взаимодействие юнитов написано - это жесть.

Я так и не понимаю как сканирование углов решает проблему в общем случае, это алгоритм расстановки весов или..? Ты мог бы написать тестовую программку, например на GDI ? Можно проще - взять канву и на ней двигать квадраты. Достаточно 2х состояний для начала - исходное и стрелки кто куда пойдет.

Использование простых методов для перестроения - плохая идея. Опять же толкотня и оптимальное решение в таком случае - боковые должны разойтись, а задние зайти внутрь. Причем это зависит от численности войск, писать под это особые методы - значит погрязнуть в деталях.


Нашли баг в КаМ Ремейке? Отправьте отчет на contact@kamremake.com с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
 
mihail_mskДата: Среда, 21.09.2011, 17:48 | Сообщение # 7
Ополченец
Группа: Проверенные
Сообщений: 32
Награды: 0
Репутация: 2
Статус: Offline
Ладно, если будет немного времени, в течении двух недель попробую закодировать алгоритм. Тогда искать другие, не "бредовые" как мой, а реально профессиональные алгоритмы придется кому-нибудь еще.

Вот такой стенд я имел в виду - пока что он без наполнения.
Прикрепления: KAM_reorder.exe(447.0 Kb)


Сообщение отредактировал mihail_msk - Среда, 21.09.2011, 17:49
 
KromДата: Среда, 21.09.2011, 19:55 | Сообщение # 8
Воитель
Группа: Супер Модераторы
Сообщений: 2526
Награды: 25
Репутация: 153
Статус: Offline
Как нам посоветовал человек с геймдева - надо посчитать все пути и использовать алгоритм подбора пар: http://en.wikipedia.org/wiki/Hungarian_algorithm Там внизу есть примеры на разных языках, самый подходящий нам, кажется, C#.

Нашли баг в КаМ Ремейке? Отправьте отчет на contact@kamremake.com с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
 
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
Воитель
Группа: Супер Модераторы
Сообщений: 2526
Награды: 25
Репутация: 153
Статус: Offline
Скопирую сюда мой ответ на gamedev, чтобы все были в курсе:

Значит нам нужен алгоритм, который не только выбирает пары с минимальным суммарным расстоянием, но и с наиболее равномерным их распределением. В таком случае можно попробовать этот алгоритм: http://en.wikipedia.org/wiki/Transportation_problem - тут есть абзац про затраты времени на перемещение книг. К сожалению в русском переводе его нет, но думаю смысл примерно понятен - штрафуются варианты с неравномерными весами (1+1+1 предпочтительнее 0+0+3).

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

Кстати, выделяется параллельная задача - с учетом проходимости местности, выбрать места где встанут юниты не попавшие в строй.

Армия из 100 это нонсенс, можем принять это как максимальное значение, если при нём будет работать, то нам подойдёт.


Нашли баг в КаМ Ремейке? Отправьте отчет на contact@kamremake.com с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
 
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
Воитель
Группа: Супер Модераторы
Сообщений: 2526
Награды: 25
Репутация: 153
Статус: Offline
Заниматься оптимизациями до того как будет готов протестирован и отлажен основной алгоритм - зло. Только время потратится и сложность возрастет, чтобы потом узнать, что узкое место в чем-то другом.

Я - за венгерский алгоритм с квадратами расстояний (лучше даже вынести степень в регулируемые параметры, для интереса). Просто и доступно.

Можно попросить тебя реализовать его в Делфи?


Нашли баг в КаМ Ремейке? Отправьте отчет на contact@kamremake.com с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
 
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
Воитель
Группа: Супер Модераторы
Сообщений: 2526
Награды: 25
Репутация: 153
Статус: Offline
mihail_msk, основное время венгерского алгоритма занимает вычисление расстояний между всеми юнитами и всеми позициями. Твоему алгоритму это не нужно?

Можно обрисовать примерные рамки того что надо сделать:
Требования непосредственно к алгоритму - это должна быть 1 функция, которая принимает 2 массива TPoint и выдает массив TPoint (в котором указаны пару - кому куда идти). Тебе будет удобно использовать такое объявление для своего алгоритма? Дело в том что надо учитывать непроходимые тайлы, которые могут быть в зоне построения отряда (банальны пример - построить отряд 4х5 на узком мосту). Я предполагаю, что сначала будет алгоритм поиска мест (он уже по сути есть и достаточно простой). Если тебе удобнее, то тогда вместо массива доступных мест - будет отправляться наоборот - массив недоступных мест в области нахождения отряда.

Тогда, можно будет выполнить каждую функцию по 100000 раз на случайных данных и определить - какая быстрее )


Нашли баг в КаМ Ремейке? Отправьте отчет на contact@kamremake.com с пометками, желательно на английском, в какой версии, что и когда случилось, приложите реплей или сохраненную игру в которой этот баг воспроизводится.
 
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
 
Форум » Knights and Merchants: Remake » Редактирование игры » Возвращаясь к перестроению юнитов (ищем алгоритм)
  • Страница 1 из 3
  • 1
  • 2
  • 3
  • »
Поиск: