Devion
Game Dev

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

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

Принятый ответ

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