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))
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.