Алгоритм поиска пути в больших подземельях.

Темы, связанные с проектированием и программированием roguelike-игр

Модераторы: Sanja, Максим Кич

altmax
Сообщения: 94
Зарегистрирован: 15 сен 2012, 11:59

Re: Алгоритм поиска пути в больших подземельях.

Сообщение altmax » 21 июл 2017, 10:36

Я писал всё к тому, что вот этот кусок

Код: Выделить всё

                                ProcessNeighbor(ob, area, currentNode, x + 1, y);
				ProcessNeighbor(ob, area, currentNode, x - 1, y);
				ProcessNeighbor(ob, area, currentNode, x, y + 1);
				ProcessNeighbor(ob, area, currentNode, x, y - 1);
				ProcessNeighbor(ob, area, currentNode, x + 1, y + 1);
				ProcessNeighbor(ob, area, currentNode, x + 1, y - 1);
				ProcessNeighbor(ob, area, currentNode, x - 1, y - 1);
				ProcessNeighbor(ob, area, currentNode, x - 1, y + 1);

все координаты соседей можно посчитать заранее один раз и записать их в ноды, а тут 12 арифметических действий. И у меня карта представляет собой одномерный массив, а класс Level просто преобразует декартовы координаты в нужный номер ячейки, а там в алгоритме есть и деление, и умножение. А можно писать не декартовы координаты ноды, а конкретный номер ячейки в одномерном массиве. В общем масса возможностей для оптимизации. Хотя поиск пути используется не очень часто, а если и используется - то на крайне небольшие расстояния в пределах прямой видимости, а там всё происходит практически мгновенно.
Ну а если нужно пути искать через весь уровень, то уровень обычно состоит из отдельных комнат, между которыми можно просчитать пути и записать их, ну и использовать по мере надобности.

Аватара пользователя
Anfeir
Сообщения: 651
Зарегистрирован: 14 дек 2007, 09:29
Контактная информация:

Re: Алгоритм поиска пути в больших подземельях.

Сообщение Anfeir » 21 июл 2017, 14:37

Ну у меня тоже одномерный массив, если внимательно посмотреть. Если уж так смущают арифметические действия, то можно заменить на чтонибудь типа ProcessNeighbor(ob, area, currentNode, index + OFFSET), да и что-то подозрение имеется, что не будет это весомой оптимизацией. Вот если карта активно меняется - открываются двери, разрушаются стены, растекается вода, то заранее что-то составить сложно. Кстати, у меня соседние ноды тоже же априрои есть. Просто обращение по индексу + одно сложение, ерундовая по нагрузке операция.
Оптимизировать конечно можно, причем почти бесконечно, если нужно.

P.S. если сохранить всех соседей, то при итерации цикла for int i = 1 to numNeighbors тоже каждый раз будет арифметическая операция - увеличение на 1 .) а ещё сравнение с конечным числом, а ещё переход в машинных инструкциях jmp ;)
Хотя я уже детали алгорима туманно помню в целом, работает - и ладно.

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 7 гостей