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

[bwolf88]

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

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

1. Если бот может передвигаться во время расчета следущего цикла, тогда путь станет совсем не короткий, потому что он расчитает путь на 50 точек, упрется в стену, потом еще на 50 - упрется в другую стену и может к 3 или 4 разу он наконец то выйдет.



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

Таже петрушка будет с автоматами.

[Syberex]

Искать путь частями это бред. Проще ехать куда глаза глядят и объезжать препятствия

[bwolf88]

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

Я вчера поправил расчеты. Зигзагами ходили, потому что при определение стоимости пути от соседней клетки до конечной изначально было привязано к масштабу (на первых этапах). Причем при масштабах <=1 он строил зигзагами, а при больших только прямыми по горизонтали и вертикали . Сейчас уже все нормально. И еще добавил поддержку прямоугольных карт (хотя обычно карты квадратные, но мало ли).

Искать путь частями это бред. Проще ехать куда глаза глядят и объезжать препятствия

.
Это я уже делал еще в самом начале своего пути в Unity в "конструкторе" .

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

[lawson]

непроходимую зону можно определить перебрав их все

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

[bwolf88]

непроходимую зону можно определить перебрав их все

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

А если это не прямоугольник и сложная фигура, Чет мне кажется, что я снова пришел к пока недоступному для моего понимания алгоритму GreedyMesh. По сути это тот же алгоримт объединения слодных кубических строений в более простой. Могу скинуть ссылку или в Гугле можете набрать GreedyMesh Микола Лысенко. Очень интересная штука, хоть там и на примере кубических чанков (аля майнкрафт), но суть таже.

[lawson]

А если это не прямоугольник и сложная фигура,

Вы хотите все и сразу. Делить на части.
удалять ячейки областями: ставим объект - получаем координаты, в этих координатах примерно выбираем несколько ячеек(к примеру 5) - удаляем, можно брать углы объекта - xMin, yMin, xMax, yMax. А иначе если очень сложный и большой ОБЪЕКТ(не группа объектов), то тогда не знаю, да и что это может быть за объект!?

[Salamandr]

вот, что советуют начинающим по поводу коллизий? Правильно, юзать простые коллайдеры. Аналогично, можно использовать упрощенную фигуру 4 точки (не квадрат, скорее полигон) на любую 4х угловую секцию и т.д. по аналогии.

[bwolf88]

Изменил схему поиска соседей в списках. При обычной схеме поиска на карте размером 120х120 с таким расположением препятствий, нарисованный маршрут (один из самых сложных для расчетов А* вариантов, поскольку приходится перебирать практически все клетки) уходило от 6 до 8 секунд !!



Видео сравнения:

Скрытый текст: показать

Теперь всего 0.04-0.06 с, то есть ускорил в 150 раз, что считаю весьма хорошим результатом и большой победой над производительностью.
В принципе теперь можно пробовать и закраской областей взяться.

[bwolf88]

1. Запилил динамику, правда пока без обхода ботов, но сейчас мне это не нужно. Теперь бот пересчитывает путь находясь у препятствия, если какая то точка на пути стала недоступной. Также запилил возможность ботом изменять карту проходимости.

2. Сделал раздельный выбор ботов с подсветкой.

3. Наконец то додумался как убрать обработку скрипта с кучей сериализованных данных в OnInspectorGUI - это больше всего бесило. Теперь в редакторе большие карты не тормозят. .

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


Но столкнулся с переполнением стака, странно пишет про Vertices, Indices, хотя в списке у меня Int. Видать любые списки больше 65к объектов не поддерживают, плюс все таки получаю провисончик в пол секунды при переборе всех точек большой карты (если пытаюсь построить путь в закрытую зону).Сделал ограничение на поиск в 3000 точек закрытого списка. В большинстве случаев на более менее открытой карте этого больше чем достаточно.

А вот если сложный лабиринт и боту нужно добраться до выхода (цели) все таки нужно смотреть в сторону поиска пути по частям (аля Автоматы как писал Salamandr). Но нужно еще прикинуть необходимость этого.

[bwolf88]

Несколько дней решал головоломку с динамичным поиском источника энергии по упрощенному A*.
Сегодня наконецто допилил базу. Уточню, сверху над первой сеткой еще одна, по которой и строится энергомеш. Потом квадратики на что нибудь другое поменяю.
Особенности:
"Постройки" не привязаны к маштабу сетки. То есть сетка может быть и с шагом от 1 ед и меньше кратное 2 (0.5, 0.25 и т.д.) Закраска клеток под зданиями атоматически подстраивается под маштаб.
Источник энергии можно переносить в рантайме.
Энергопуть можно прокладывать в рантайме.
Потребители автоматически перепрокладывают путь если проводящая клетка стала неактивной (только те, которые проходят через эту клетку) или перенесен источник энергии.

Вот что получилось (честно говоря я залип и игрался минут 10, из них пару минут записал ).


Теперь буду биться над оптимизацией при удалении клетки-проводника. Сейчас там жестокие циклы переборов.
А вообще я с неделю как засел за своей РПГ- стратежкой и это будущая ее часть.

[bwolf88]

Сегодня провел небольшой тест на выживаемость.
200 агентов следуют за целью в динамике просчитывая путь. Препятствия устанавливаются/удаляются на ходу. Тест показал, что на более менее открытой карте просчет пути не занимает больше 0.002 секунды (самое большее проскакивало 0.0025 секунды).
Как видно 200 агентов вполне себе нормально следуют за целью при этом на ФПС это никак не отражается. Считаю - неплохо. Пробовал запустить с 400 агентами, начинало лагать из за физики, при отключенной физике проблем нет. В принципе по производительности получается также как при простом следовании без поиска пути, а по функциональности гораздо прикольнее.



Я уже пару дней пытаюсь прикрутить А* к планетоиду. Сшивать точки это конечно жестоко . Даже не знаю, стоит ли оно того.

[lwe]

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

[bwolf88]

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

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

[Salamandr]

классное видео. Каким путём пошел, как разпараллелил? Да и динамически вроде путь считается или как?

[bwolf88]

В алгоритме нет ни одного параллельного процесса. Я вообще не понимаю где в Юньке потоки юзать, любые расчеты в какой то мере затрагивают Unity- объекты. Пробовал как то на мешчанках запускать параллельные расчеты их построения, так он мне набор полигонов выдавал вместо коробки. Да и раньше игры делали с поиском пути для 1600 юнитов (старкрафт 1) и играли нормально на 300МГц полупроцах (у меня Селерон был), это сейчас уже зажрались, что в однокнопочных играх лаги на многоядерниках похлеще чем в Крузисе .

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