Devion
Game Dev

Запекание ячеек в поиске пути

Добавлен
Вот знаю я простой способ запекания - чтобы каждая клетка в поиске пути запоминала информацию, в какую из соседних клеток нужно пройти, чтобы достичь определенной точки.
Но в этом способе есть минус. Количество хранимых данных экспоненциально растет, то есть равно N^N ячеек.
То есть в поле 100х100 мы запоминаем 10000 значений.
В принципе есть еще модификация этого способа - не запоминать инверсию. В этом случае мы получим треугольное число, то есть количество хранимых данных равно N*(N+1)/2
То есть в поле 100х100 мы запоминаем 4950 значений.
Довольно часто экспоненцию можно сильно упростить. И вот скажите, есть ли какой-нибудь способ позволяющий достичь более хорошего результата, скажем чтобы было N*Log(N) хранимых данных?
Мне почему то кажется, что такое решение есть, или хотя бы какая-нибудь другая подобная хитрость.
Интересуют именно способы упростить запекание, а не эвристика.

У меня есть проект RTS с большим количеством юнитов (выпотрошенный старкрафт). Так вот, я решал вопрос оптимизации поска путей так: делишь карту на большие квадраты. Расчитываешь возможность проходимости из квадрата в квадрат, стоишь по этим данным граф связей квадратов. Далее заранее рассчитываешь кратчайшие пути от смежных вершин графа (от центра квадрата к центру другого). Во время поиска пути пачками юнитов по-честному ищешь путь от юнита до центра ближайшего к нему квадрата и от цели к центру её квадрата - остальное собираешь из путей между квадратами: честный поиск пути на графе квадратов (он простой) и сбор пути из заранее рассчитанных фрагментов. Дальше полученный путь немного сглаживаешь, чтобы лишние углы были не такими явными и подаёшь на стол.
На картинке граф проходимости между центрами квадратов, для каждого ребра этого графа заранее рассчитывается оптимальный путь.
Загруженные файлы
25 дек 2014
4 895
`
ОЖИДАНИЕ РЕКЛАМЫ...
2
Показать
14
2
Показать
В голову проходит, разве что, вариант с разбитием на зоны, но всё зависит от характера поля.
0
Показать
20
0
Показать
А обязательно ли вообще хранить эти данные? Поиск пути по карте можно реализовать через рекурсию. Нужно только знать проходима ячейка или нет, дальше поиск автоматом. Но не знаю, подойдет ли это по быстродействию для твоей задачи.
0
Показать
27
0
Показать
PhysCraft, принято запекать чтобы не обсчитывать пути постоянно на локациях с большим количеством юнитов и высокой частотой расчетов. Таким образом скорость нахождения пути равна О(1), а не О(N)
0
Показать
29
0
Показать
Extravert:
с большим количеством юнитов
Можно запекать не все пути, а лишь часть по частотности использования, что то типа кеша, что используется в процессорах. Так же можно уменьшать кол-во ячеек и потом для каждой ячеек решать частную задачу
0
Показать
20
0
Показать
В Unreal Tournament пути для ботов заданы просто расположением на карте Path Node объектов, как некоторые контрольные точки. Может, это поможет, если на карте много прямолинейных участков.
0
Показать
27
0
Показать
alexprey, конкретно моя задача - статичное запекание, которое делается не в игре, а еще в редакторе. То есть где позволительно тратить неприлично большие силы на просчет чего-либо.
Вопрос лишь в том, чтобы хранить меньше данных при хотя бы чуток схожем КПД (О(1))
0
Показать
29
0
Показать
Extravert, ну запекать можно и большие куски. Я в одной игре заметил, что боты на открытых участках концентрируются в точках, равно удаленных между собой. Разбивай на разные уровни масштаба и запекай разный масштаб. Да и вообще 100х100 это вообще не проблема даже для самого простого алгоритма, который пишется с коленки. Для A* так это вообще как нефиг делать.
0
Показать
27
0
Показать
alexprey, я гипотетически привел в пример поле 100 на 100, чтобы показать масштабы, в которых происходит запекание. Вот будет поле скажем 1000 х 1000 - 1000000 ячеек сохранено. А я тут даже ошибся чутка. Ведь сама экспоненция уже будет 1000000*1000000 - чисто ради запекания. Это несоизмеримо много. Ну не ок же. Потому и спрашиваю, мб есть какие-то фишки/трюки, чтобы сделать как бы почти тоже самое, но хранить меньше данных.
0
Показать
29
0
Показать
Extravert, я же говорю уменьшай масштаб, дели свои 100к ячеек на меньшее, делай размер яччек поверх до 1к и так далее. И для каждого масштаба можно решать эту задачу. На каких то этапах можно и вовсе уже будет обойтись без запекания, чтобы сохранить динамику проходимости
0
Показать
24
0
Показать
Можно запекать не в виде ячеек, а пересчитывать в регионы с однородной проходимостью или в меш, но тогда и алгоритмы поиска пути немного менять надо.
4
Показать
14
4
Показать
У меня есть проект RTS с большим количеством юнитов (выпотрошенный старкрафт). Так вот, я решал вопрос оптимизации поска путей так: делишь карту на большие квадраты. Расчитываешь возможность проходимости из квадрата в квадрат, стоишь по этим данным граф связей квадратов. Далее заранее рассчитываешь кратчайшие пути от смежных вершин графа (от центра квадрата к центру другого). Во время поиска пути пачками юнитов по-честному ищешь путь от юнита до центра ближайшего к нему квадрата и от цели к центру её квадрата - остальное собираешь из путей между квадратами: честный поиск пути на графе квадратов (он простой) и сбор пути из заранее рассчитанных фрагментов. Дальше полученный путь немного сглаживаешь, чтобы лишние углы были не такими явными и подаёшь на стол.
На картинке граф проходимости между центрами квадратов, для каждого ребра этого графа заранее рассчитывается оптимальный путь.
Загруженные файлы
Принятый ответ
0
Показать
27
0
Показать
Kozinaka, ты построил навмеш в плоскости, грубо говоря. Основное правило навмеша - обеспечение 100% проходимости в рамках определенной области. Ну и области на пересечениях "стыкуются". Хотя тут у тебя есть хитрость, получается несколько уровней под просчет путей.
Но у меня тут немного другая история. Я пробовал генерировать навмеш под свои нужды, но он выходит весьма накладным в плане производительности.
Затем я думал заюзать эвристический алгоритм. Но как ты можешь увидеть на скрине ниже - у меня многоуровневый ланд, потому хорошего способа юзать эвристику не нашел.
Вот и подумал что не лучше бы в запекание. Места "стыков" у поверхностей часто не однозначны (особенно там, где стыки поверхностей выражены несколькими точками).
Потому и надумал - запекать всю карту неразрывно.
Большую карту опять же сделать не могу - в этом случае препятствия, существующие диагонально будут иметь очень кривую проходимость. А мне нужно не мир подстроить под алгоритм, а наоборот, алгоритм под мир.
Или я неправильно понял, что ты имел ввиду
В общем и не знаю что и делать. В идеале хотел конечно поиск по рукавам юзнуть, и будь что будет. Но есть много разных вариантов, которые я не смог проработать на многоуровневом поиске, в частности как детектить правильные препятствия и как быстро находить переход на другой этаж.
Загруженные файлы
0
Показать
14
0
Показать
Extravert, у тебя есть двери или что-то такое, что меняет проходимость на лету? Многоуровневость особо ничем не усложняет работу с э... навмешем - мост и проход под постом просто две несмежных ветки графа будут каждая со своей ценой прохода. Просто немного сложнее строить при предобработке.
0
Показать
27
0
Показать
Kozinaka, да есть + сами юниты динамичные, меняют проходимость.
В общем то приценился на дальнейшими действия. Сейчас попробуем-с, по надобности обновим сабж. Решил-таки попробовать еще раз в эвристику.
А в целом наверное так и выходит, что запекание в глубину как раз даст то самое "(N*Log(N)) количество данных" или близкое к этому, на этом пока что и закончим
2
Показать
29
2
Показать
Запекают как раз навмеш.
0
Показать
27
0
Показать
Doc, никто не отрицал необходимость запекания навмеша.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.