Поиск пути на больших картах (Dwarf Fortress)

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

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

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

Поиск пути на больших картах (Dwarf Fortress)

Сообщение altmax » 04 янв 2020, 09:18

Заинтересовала реализация поиска пути на очень больших картах. Конкретно - игра Dwarf Fortress. Если бы там поиск пути был реализован стандартным способом, то при населении крепости 100+ дварфов и атаке такого же количества гоблинов - никакого процессора не хватило бы для обсчёта пути для всех юнитов.
В данной же игре имеем конечно некоторое снижение FPS при увеличении численности крепости, но не столь критичное - т.е. поиск пути реализован как-то по другому, возможно в поиске используются не отдельные клетки, а комнаты в целом - только что в этом случае считать комнатой? Плюс скорее всего какие-то стандартные маршруты просчитываются один раз и сохраняются, и стоит дварфу дойти до такого маршрута - он уже идет по нему, а не ищет путь после каждого шага (или нескольких шагов).
Какие мысли у кого будут - как всё это оптимизировано в данной игре?

Аватара пользователя
thefish
Сообщения: 29
Зарегистрирован: 18 июн 2012, 22:37

Re: Поиск пути на больших картах (Dwarf Fortress)

Сообщение thefish » 05 янв 2020, 17:00

емнип, автор говорил что в DF использован A* с оптимизацией (jump point search или чем-то подобным).

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

Re: Поиск пути на больших картах (Dwarf Fortress)

Сообщение altmax » 08 янв 2020, 09:03

thefish писал(а):
05 янв 2020, 17:00
емнип, автор говорил что в DF использован A* с оптимизацией (jump point search или чем-то подобным).
Это-то как раз понятно. А что делают дальше с результатами? Там не ищут путь каждый ход для каждого юнита, иначе процессора просто не хватило бы - просадки начинаются когда становится 150+ юнитов, а до этого спокойно обсчитывается.
Весь вопрос состоит в том, как просчитать пути, сохранить результаты и потом пользоваться уже готовыми результатами - скорее всего так там и сделано.
Надо видимо каким-то образом делить уровень на комнаты, сохранять пути уже между комнатами, а не между отдельными клетками. Если уровень перестроили или двери открыли/закрыли - пересчитывать только его. Если его не трогали, то и пути для этого уровня не пересчитывать. Т.к. всю крепость глобально редко перестраивают, то будут сохранённые маршруты, которыми и пользоваться.

Аватара пользователя
thefish
Сообщения: 29
Зарегистрирован: 18 июн 2012, 22:37

Re: Поиск пути на больших картах (Dwarf Fortress)

Сообщение thefish » 09 янв 2020, 06:40

Ну логично что для каждого персонажа есть список координат, по которым он будет двигаться в дальнейшем. Этот путь пересчитывается только при когда невозможно по нему пройти дальше, при смене поведения, получении дамага - т.е. далеко не каждый ход.

Но у вас как я понял мысль об оптимизации идет дальше, тема интересная.

Для перемещений по более или менее статическому ландшафту (читай- крепости) я бы сделал так
- определил бы "комнаты" (непростая задачка, кстати)
- Нашел бы их центры
- нашел бы кратчайшие пути между центрами (триангуляцией Делоне например)
- в получившемся графе пробежался бы по ребрам между вершинами тем самым A*, получив массив готовых "шоссе" для персонажей.
- хранил бы этот массив отдельно в памяти, и если персонажу нужно пройти со "складов" в "забой шахты" - брал бы готовый маршрут "склад -> шахты" из массива и штатным поиском пути находил бы ближайший к персонажу узел в этом маршруте. Результат - "путь до шоссе" + "путь по шоссе" + "путь от шоссе до точки назначения" - складывал бы в список координат для дальнейшего движения.

Сразу видна беда этого метода - на "шоссе" будет постоянно толпа мешающихся друг другу персонажей, нужно придумывать "лёгкий" алгоритм обхода препятствий.

В общем есть тут место для полета фантазии, и для тестирования - действительно ли такая "шоссейная" оптимизация улучшит производительность.

PS В случае с DF я бы кстати грешил не на pathfinding, а на "медицинский" и "физический" движок. Для каждого живого тела DF обчитывает состояние организма, от костей до пищеварения. Для каждого юнита воды считается давление, направление движения итд. Мне кажется, что причина торможения DF скорее закопана тут.

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

Re: Поиск пути на больших картах (Dwarf Fortress)

Сообщение altmax » 12 янв 2020, 14:58

Именно оптимизации и интересует - ведь этот алгоритм вполне применим и в рогаликах - при генерации уровня сразу и все возможные пути прописываем, а потом уже используем эти маршруты в игре, тем более что уровни по большей части статичные. Хотя в рогаликах глобальный поиск пути используется крайне редко, обычно он ограничивается радиусом в 10-15 клеток.
Ну и в игре типа DF - создать огромный мир из 100 уровней, и чтобы 200+ гномов постоянно бегали из конца в конец почти не нагружая процессор )))) Вообще, учитывая развитие многоядерных процессоров в настоящее время, этот просчёт и запись маршрутов можно выделить в отдельный поток, тем более что данный поток не надо будет синхронизировать с основным, он может обсчитываться асинхронно и просто писать маршруты в базу данных.

Ответить

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

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