GAMEDEV
Добавлен Devion
Вот знаю я простой способ запекания - чтобы каждая клетка в поиске пути запоминала информацию, в какую из соседних клеток нужно пройти, чтобы достичь определенной точки.
Но в этом способе есть минус. Количество хранимых данных экспоненциально растет, то есть равно N^N ячеек.
То есть в поле 100х100 мы запоминаем 10000 значений.
Но в этом способе есть минус. Количество хранимых данных экспоненциально растет, то есть равно N^N ячеек.
То есть в поле 100х100 мы запоминаем 10000 значений.
В принципе есть еще модификация этого способа - не запоминать инверсию. В этом случае мы получим треугольное число, то есть количество хранимых данных равно N*(N+1)/2
То есть в поле 100х100 мы запоминаем 4950 значений.
То есть в поле 100х100 мы запоминаем 4950 значений.
Довольно часто экспоненцию можно сильно упростить. И вот скажите, есть ли какой-нибудь способ позволяющий достичь более хорошего результата, скажем чтобы было N*Log(N) хранимых данных?
Мне почему то кажется, что такое решение есть, или хотя бы какая-нибудь другая подобная хитрость.
Интересуют именно способы упростить запекание, а не эвристика.
Интересуют именно способы упростить запекание, а не эвристика.
Принятый ответ
У меня есть проект RTS с большим количеством юнитов (выпотрошенный старкрафт). Так вот, я решал вопрос оптимизации поска путей так: делишь карту на большие квадраты. Расчитываешь возможность проходимости из квадрата в квадрат, стоишь по этим данным граф связей квадратов. Далее заранее рассчитываешь кратчайшие пути от смежных вершин графа (от центра квадрата к центру другого). Во время поиска пути пачками юнитов по-честному ищешь путь от юнита до центра ближайшего к нему квадрата и от цели к центру её квадрата - остальное собираешь из путей между квадратами: честный поиск пути на графе квадратов (он простой) и сбор пути из заранее рассчитанных фрагментов. Дальше полученный путь немного сглаживаешь, чтобы лишние углы были не такими явными и подаёшь на стол.
На картинке граф проходимости между центрами квадратов, для каждого ребра этого графа заранее рассчитывается оптимальный путь.
Загруженные файлы
`
ОЖИДАНИЕ РЕКЛАМЫ...
Чтобы оставить комментарий, пожалуйста, войдите на сайт.
Ред. Kozinaka
Ред. Devion
Но у меня тут немного другая история. Я пробовал генерировать навмеш под свои нужды, но он выходит весьма накладным в плане производительности.
Затем я думал заюзать эвристический алгоритм. Но как ты можешь увидеть на скрине ниже - у меня многоуровневый ланд, потому хорошего способа юзать эвристику не нашел.
Потому и надумал - запекать всю карту неразрывно.
Большую карту опять же сделать не могу - в этом случае препятствия, существующие диагонально будут иметь очень кривую проходимость. А мне нужно не мир подстроить под алгоритм, а наоборот, алгоритм под мир.
Ред. Kozinaka
Ред. Devion
В общем то приценился на дальнейшими действия. Сейчас попробуем-с, по надобности обновим сабж. Решил-таки попробовать еще раз в эвристику.
А в целом наверное так и выходит, что запекание в глубину как раз даст то самое "(N*Log(N)) количество данных" или близкое к этому, на этом пока что и закончим