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

[bwolf88]

Что уже есть на 15.11.14г

1. Алгоритм A*:
Первоначальный вариант уже получившийся: на видео тест поиска пути 200 ботами. Поскольку активный оси X и Z то для 2Д эта реализация не годится, а для 3Д - сырая. Это скорее тестовый вариант, так же дальше по теме есть видео с передвижением ботов разных размеров. В дальнейшем не раз допиливался. Подробности дальше по теме.


Еще более улучшенная и ускоренная версия. Тестовое сравнение с Crystal Path Finding. Версия от 9.12.14


2. 2D редактор карты в стиле Heroes III. Не до конца доделан. Реализован автотайлинг земли (несколько видов), расстановка контента на карте с изменением проходимости клеток, дороги. Все рисовалось самостоятельно + на мой взгляд удобная Editor менюшка.
Передвижение ботов на переделанном чисто для 2Д режима и ускоренном алгоритме поиска пути А*. Так же уже присутствует пошаговый режим, учитывающий стоимость клеток (дорог) и количество очков передвижения и реалтайм передвижение. Подробности дальше по теме.



3. 3D редактор карты. Установка блоков различных размеров, изменяющий проходимость клеток карты.
2 Вида поиска пути для 3Д режима: волновой+A*3D (больше подходит для персонажа управляемого игроком) и чистый A*3D. Поиск пути учитывает стоимость подъемов, а также возможность забираться на небольшие уступы (для пешего варианта). Есть реалтайм и пошаговый режимы, а также режимы передвижения: пеший, прыжковый и полетный, для каждого из которых расчет пути немного различается.
3. Первоначальный ИИ бота, с поиском ближайшего по стоимости пути противника и передачей хода после завершения хода .
Подробности дальше по теме.



Кроме того, дополнительно изучены и позже будут внедряться в имеющиеся проекты:
QuadTree алгоритм для упрощения сетки поиска.
Добавил ссылку на ассет: https://drive.google.com/folderview?id= ... sp=sharing


Алгоритм двухпроходной четырехсвязной авторазметки и заливки карты, для изоляции непроходимых полностью огороженных зон карты. Правда для больших карт не подойдет. Пересчет оптимален по скорости для карт 128х128, максимум 256х256 клеток. Пересчет зон на карте 512х512 занимает 30-100 млс, что считаю очень долгим. Подробности дальше по теме.
Добавил ссылку на ассет: https://drive.google.com/folderview?id= ... sp=sharing

[lawson]

есть бесплатный А* с несколькими типам расчета пути + контроллеры идут сразу в ассете

[bwolf88]

есть бесплатный А* с несколькими типам расчета пути + контроллеры идут сразу в ассете

Есть много бесплатных и прикольных вещей, согласен и кому то они экономят массу времени.

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

Плюс - это опыт и карма .

[lawson]

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

[bwolf88]

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

Я маленько покапался в бесплатной версии, чего то не увидел распределение нагрузки по потокам. Да и расчеты там честно говоря странные.

[bwolf88]

Народ, разбираясь с логикой A* и столкнулся с интересной дилемой в алгоритмах которые есть в сети. Суть в том, что есть некий список нодов-точек, из которых состоит карта. Так же есть два списка - закрытый и открытый. У каждого нода есть родительский нод, от которого мы якобы строим путь дальше.

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

Дилему я конечно решу, но странно, что такую логику выкладывают в качестве обучающего материала - ведь подобные алгоритмы поиска используется для игр с несколькими персонажами, ботами (для одного проще сделать управление с клавиатуры). Хотя для одного персонажа - это рабочие варианты, но по мне бесполезные .

[Syberex]

Ты наверное что-то недопонял...
Хотя я не утверждаю, бесплатные не ковырял, тоже написал свой А* и Дейкстры

[bwolf88]

Сегодня наконец то вдохновение, а то на два дня забросил практически .

Вообщем немного подправил скрипт и потестил на 4-х ботах просчет поиска пути каждый кадр. Размер поля 100х100 (10 000 точек). Немного кривая функция движения (не совсем совместима с этим алгоритмом), взял из своего скрипта движения из "конструктора", поэтому бот крутится пока ищет путь. До этого стоял простой Translate по точкам, но шибко быстро перемещался - поэтому пусть будет пока этот.

ФПС при расчетах около 40-60 в зависимости от длины. При 200х200 - 15-40 в зависимости от длины. Считаю, пока неплохо.

Для сравнения тестил бесплатную версию А* из AssetStore. В нем изначально установлен поиск пути каждый кадр. Один бот при расчетах на такой же площади у меня выдает чуть лучшие показатели, чем четыре моих, но на площади 200х200 практически покадровая анимация.



P.S.На счет недопонял - возможно. Даже сейчас боты двигались по проложенным путям вполне адекватно, хотя по логике, при одновременных расчетах, последний должен был менять родителей на пересеченных точках из своего списка. Хотя если маршрут совпадает, то не так страшно. Но как мне кажется будет загвоздка, если два бота будут идти по одним точкам с противоположных концов. По логике опять же, если расчеты были параллельные, то первый бот собьется.

[lawson]

Я вижу вы перемещаете бота по каждой найденой точке?

[bwolf88]

Я вижу вы перемещаете бота по каждой найденой точке?

Пока да, потом оптимизирую, чтоб точек меньше было если на прямой. Это же только самое начало .

[Iq51]

Народ, разбираясь с логикой A* и столкнулся с интересной дилемой в алгоритмах которые есть в сети. Суть в том, что есть некий список нодов-точек, из которых состоит карта. Так же есть два списка - закрытый и открытый. У каждого нода есть родительский нод, от которого мы якобы строим путь дальше.

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

Дилему я конечно решу, но странно, что такую логику выкладывают в качестве обучающего материала - ведь подобные алгоритмы поиска используется для игр с несколькими персонажами, ботами (для одного проще сделать управление с клавиатуры). Хотя для одного персонажа - это рабочие варианты, но по мне бесполезные .

Родительские ссылки хранятся в нодах, которые в открытом\закрытом списках. Сама, общая карта местности - алгоритмом никак не меняется. Подробнее

[bwolf88]

Вообщето карта местности состоит из нодов, ссылки на которые хранятся в этих открытых/закрытых списках. И хранятся в единственном экземпляре. Вы предлагаете создавать новые ноды для каждого бота, а если их будет 200-300 и путь длиной в 100 точек, получим 20 000 - 30 000 точек просто чтобы добраться до цели ? А теперь представьте стратежку, где за миссию нужно 200-300 таких перемещений сделать - получите уже несколько миллионов точек. А как миллион точек с несколькими данными память сжирают я уже испытал, когда чанковые меши клепал.

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

Да и с этим и еще несколькими мануалами я ознакомился и руководствуюсь в процессе.

[bwolf88]

PS: Добавил видео текущего состояния в шапке.

Добрался до разделения карты на зоны проходимости и столкнулся с тем, что не могу додуматься как реализовать адекватное разделение карты в процессе игры. То есть допустим мост обрушился или построили здание/забор и какую то часть карты сделали непроходимой.
Простой перебор всех клеток на возможность пройти - полная . Даже 2000 клеток перебирать циклом поиска - просадка ФПС гарантирована.
Допустим строю здание оно перегораживает путь - делать опять же подобный перебор на разделение зон - снова такая же просадка правда однократная.

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



Как быть? .

[bwolf88]

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

[Salamandr]

На счет столкновений в путях видел как то интересный алгоритм. Суть в том что кроме точек в пути, записывалось и время. То есть, идя по пути во второй точке мы будем здесь проходить в такое то время, а другой персонаж в такое то. Всё что остается сверить - время, если оно примерно одинаковое, то меняем чей то путь в этой точке на обход. Но остальной путь мы не меняем.
А также можно поступить ещё проще, кто первый, тот и папа. То есть просчитав весь путь 1ый персонаж как бы забивает эту траекторию, а все остальные при расчетах учитывают проходы столкновений предыдущих.

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

На счет просадки... погоди, щас напишу (используй автоматное программирование)

Сейчас ты пытаешься просчитать за раз весь путь, так, будто твой персонаж, за секунду должно его пройти. Это ведь не так, ему незачем знать где он окажется через 300 миллисекунд и тем более через 30 секунд.
Проще говоря, начинаем работать с состоянием.
Дано:
персонаж имеет текущее положение и конечную точку в которую он должен придти
Всё что ему сейчас необходимо, это ближайший путь до следующего просчета и он вовсе не обязательно должен быть конечным.

Коль уж я заикнулся... Суть автоматного программирования заключается в построении "автоматов" - мини программ или совокупность триггеров. Где циклы, превращаются в одно действие с закосом в продолжение.

Синтаксис:

Синтаксис: [ Показать ]

Используется csharp

class Automat_1 {
  int progress = 0;
  public void goNext() {
  ...
    progress += 1;
  }
}

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

ЗЫ: надеюсь понятно объяснил )