Пилю A*, 2D и 3D Tile Map Editor

[bwolf88]

У меня тайлы по три в ряд идут в атласе, поэтому тоже удобно считать . А вообще я список сделал на каждый тип тайла, один раз в скрипте прописал номера и они рандомно из списков выбираются.

[bwolf88]

Запарился немного с установкой элементов на карту
Изменения:
1. Поиск пути учитывает стоимость "Земли". Сейчас пилю дороги .
2. Теперь редактирование земли не изменяет проходимость клеток, а только их стоимость и тип.
Добавлено:
1. Возможность устанавливать контент различных размеров с произвольным количеством непроходимых клеток и клеток взаимодействия. То есть в библиотеке объектов задаются (могут в произвольном порядке) какие из клеток всего элемента будут считаться непроходимыми, какие клетками взаимодействия.
2. Правильное перекрытие друг другом элементов окружения только слоями, ось Z больше не используется.
3. При установке учитывается пересечение устаналиваемых непроходимых клеток с клетками взаимодействия и клетками непроходимого для этого вида контента. При этом непроходимые клетки разных объектов могут объединяться, что позволит создавать более различное окружение за счет совмещениея нескольких элементов. (Больше всего парился). Из окружения в качестве тестового только это страшненькое дерево . Остальное рисуется потихоньку.
4. Поигрался с анимацией в передвижении . Пока 4-направленное движение для тестового персонажа (8 направленного кастомизатора персонажа не нашел), но, это легкая часть.
5. Добавил несколько плюшек: типа отображения проходимости, запрет на редактирование земли/объектов в зависимости от менюшки.

Скрипты уже выросли до неприличных размеров, так что процесс немного замедляется. Плюс по ходу дела многое приходится доделывать или переделывать.

Все больше приближаюсь к редактору HOMM3. Сижу его целыми днями изучаю, все таки насколько он продуманный и непростой.

[bwolf88]

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

[bwolf88]

Добавлено: полноценная загрузка/сохранение карты, пока без контента, сохранение контента добавлю когда будет что сохранять.
Начал плиить логику боевки, плюс потихоньку пишу диздок, чтобы самому не запутаться.
Рисую контент, начал с деревьев - 10 шт за 7 часов , учитывая время которое учился, дальше быстрее пойдет.
Тайлы земли и дорог явно требуют перерисовки, но уже кое какой вид появляется.

[lwe]

Pixel Art

[bwolf88]

Я ориентируюсь на героев 3 или JaggedAliance 2, первые фаллоуты по графике, мне она больше всего нравится - и не пластиковая как в 4 героях и дисайплес 2, и не явно квадратно пиксельная аля FinalFantasy 2,3 или первые герои.
С каждым днем рисовать получается все лучше .

[bwolf88]

Пробная версия волнового алгоритма с определенным радиусом, зависящим от количества MovePoints. Просчет происходит один раз (в данном случае при клике мышкой по коллайдеру, точка пересечения - стартовая клетка, в будущем будет в начале хода персонажа). В среднем один просчет в радиусе 16 клеток (1000+ клеток) занимает 0.001-0.003 сек, что для тактической пошаговой игрушки вполне сносно (зато бот сможет получить всю информацию в радиусе действия). При этом на просчет самого пути процессорного времени не затрачивается.

Поиск работает в 3Д, есть 2 вида проходимости полётный и пеший вариант, поскольку еще нет деталей окружения, чтобы показать обход использую 1 уровень, где каждая клетка % 5 ==0 непроходима. на самом деле можно было сделать несколько уровней, но без окружения даже вблизи сложно разобрать . Алгоритм даже проще чем А*, и на большие дистанции убийственный. Так же к нему будет прикручиваться 3D Map Editor по типу тайлинга, который уже пару дней как делаю .

на видео просчет в радиусе 10-11 клеток.

[bwolf88]

Вернулся к своему редактору карт. Сделал первоначально взаимодействие устанавливаемых объектов с сеткой. Большие "кубики" можно ставить только на клетку с полом. Пол не может быть поставлен если уже на клетке есть пол. Большие "кубики" могут быть полом для вышестоящего уровня.

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

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

[bwolf88]

Сделал 3 режима поиска пути: пеший, прыжковый и полетный. Прыжковый и полетный по алгоритму поиска практически идентичны, разгица лишь в наличии точек за которые можно зацепиться. Также в пешем варианте добавил обход диагональных подъемов (45*) типа лестница. В редакторе диагональные подъемы изменяют позицию нода. Так же есть учет высоты объекта, (персонаи гуманоидных размеров не смогут проходить если между клетками высота 1 единица, мелкие персонажи смогут) буду доделывать учет полных размеров, что скорей всего еще больше снизит ФПС.

На небольшой сценке тестирую скорость просчетов каждый кадр на 6 клеток (для 10 клеток еще -50% к скорости). Первичная обработка волновой алгоритм, конечная А*. Для пешего варианта (0) весьма неплохо, прыжковый и полетный (1 и 2) довольно сильно грузят, поскольку обрабатывается в несколько раз больше доступных клеток. Учитывая что пилю для пошаговой игрушки, впринципе не критично, поскольку просчет пути будет производиться единожды в начале хода персонажа и обработка конечного поиска по A* не жрет ресурсов вообще .

Не могу догнать как раньше на древних машинах обрабатывался поиск пути такого типа. Взять тот Incubation, я в него играл еще на 1 пентиуме, и там так же присутствуют мобы огромных размеров и поиск пути осуществляется по похожему алгоритму (я так думаю).

[Tolking]

Инкубатор не реалтайм...

[bwolf88]

Инкубатор не реалтайм...

Я в курсе, несколько раз проходил, вот только обработка поиска там по похожей схеме. И если судить по скорости обработки, и перенести мою реализацию в нее да на первый пенек, думаю на каждом ходе игра безбожно подвисала бы .

[bwolf88]

Почти допилил 3Д вариант А*.

Игровое поле 128х128х16, среднее время поиска 0.004 с. Поиск идет от 0 точки (0,0,0) до указателя мыши. Меш поднят на самый верхний 16 уровень для максимальной сложности. Тип поиска: полет/прыжок - как самый непроизводительный. Пеший поиск быстрее работает, поскольку проверяется меньше клеток.

Задолбался искать свои баги .

[bwolf88]

Попробовал начать пилить ИИ ботов.
На видео первоначальный вариант тупого ИИ.

Красный бот - ИИ. Синие - под моим управлением .
1. Умеет выбирать ближайшую цель по А* стоимости пути.
2. Учитывает занятость клетки целью и выбирает ближайшую к нему по стоимости соседнюю клетку. (В пошаговом режиме это сделать проще)
3. Если цель находится в соседней с ИИ клетке, то сбрасывает очки хода, имитируя другое действие.

Если очков хода у бота нет или слишком мало для действия - ход передается следующему персонажу.

Имеет свойство тупть на диагональных подъемах, пока так и не понял почему .

[bwolf88]

Кстати я забыл тогда выложить видео 2Д редактора.
Снова перерисовал атлас земли, подогнав цветую гамму и лучшую отрисовку. Трава теперь похожа на траву, земля на землю, а снег на снег. И добавил деревьв, камней, горы ,цветочки, в общем начальный контент. Уже выглядит красивее, мне аж самому понравилось, но сейчас я его забросил, и делаю 3Д редактор .

[bwolf88]

Сегодня осилен очередной алгоритм .
На этот раз это Алгоритм двухпроходной, четырехсвязной авторазметки и заливки карты. Оказался не сложным, но замороченным. Буду прикручивать его к 2Д A*, чтобы не тратить время на просчет всей карты. Правда для больших карт не подойдет, оптимален для 128х128 клеток, максимум для 256х256 клеток. Пересчет карты 512х512 - занимает по времени 0.03-0.1 секунды (30-100 млс), в зависимости от количества зон, что считаю недопустимым, даже в отдельном потоке, при наличии остальной логики. Но для небольших карт подойдет.

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