Pull to refresh

Comments 29

Было бы интересно посмотреть как алгоритм будет находить путь из случайного лабиринта.
Полагаю, никак. Потому как этому алгоритму требуется хорошая связность пространства поиска.
Точно так же. Принцип ведь простой, разбить карту на узлы, вычислить проходимость между соседними узлами, построить оптимальный маршрут. А тут это в два этапа делается, сначала маршрут по крупным «клеткам», потом внутри каждой клетки маршрут «по пикселям».
Я не знаком с игрой, но фраза
Мы не хотим пересчитывать всю упрощённую карту при каждом добавлении или удалении сущности. В то же время, если упрощать карту заново каждый раз, когда нам нужно найти путь, то можно запросто потерять весь полученный выигрыш в производительности.

я трактую примерно как «Я не хочу программировать, хочу чтобы само».
А кто мешает построить упрощённую карту после редактирования? А зачем её пересчитывать каждый раз перед алгоритмом?
Предложенное решение по факту и является упрощением карты, только с какими-то своими ограничениями что, скорее всего, в конечном счёте выйдет боком.

Читайте эту фразу как "мы не хотим пересчитывать всю упрощенную карту десяток раз в секунду".


К подлагиваниям после выстрелов артиллерии игроки уже как-то привыкли, а вот лаги в процессе строительства каких-нибудь стен или разворачивания базы из чертежа с помощью дронов могут здорово испортить игру.

А кто мешает построить упрощённую карту после редактирования?

карта постоянно меняется, можно стену построить например

Не целиком же она меняется, а только тайл, где стена.

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

А MipMapping ещё не изобрели? Кажется я забрался слишком далеко в прошлое..

При том, что объём пересчётов на каждом уровне незначителен, а пересчитать надо по одному не большому тайлу в каждом.

Если построить стену, то по моему опыту это не изменит глобальный путь кусак, они будут грызть стену, но не оббегать по карте её.

По большому счёту карта меняется редко, только засыпание водоёмов кардинально меняет карту, а любые постройки не меняют путь кусак. По крайней мере я ни разу не видел чтобы кусаки как-то хитро себя вели, бегут по кратчайшему пути от своей базы к максимально загрязнённым блокам не учитывая при выборе пути стены или другие постройки. Как только встречают что-то не природное, начинают грызть. Игрок для них более приоритетная цель и они бросают грызть и бегут к нему и, если он за стеной, а рядом можно оббежать, только тогда они могут оббежать стену.
Камни и деревья грызут точно также как и стенки, то что «мешает пройти»

Может вы не так поняли "не хотим пересчитывать всю упрощённую карту" ?


Они-то может в душе и хотят пересчитывать, но из-за этого пересчета у них смысл оптимизации потеряется.

Это переведенные Friday facts? Или пишет один из разработчиков?

Первое, о чём "намекает" плашка "Перевод" и ссылка на оригинал под заголовком.

Может не заметил, а может в мобильном приложении не видно было. Скорее первое.
А зачем считать весь путь непосредственно в момент «агры»?

Там же путь от одного стационарного объекта до другого стационарного объекта.

Фактически у нас есть группа гнезд кусак/плевак, которые можно объединить в большую сущность «база кусак» (БК). Можно взять сущность «база игрока» (БИ) — некоторая окрестность радом с чанками занятыми источниками загрязнения (например 2 чанка).

Соответственно можно заранее в фоне построить маршрут от вейпоинта рядом с КБ кусак до некого вейпоинта окрестности БИ.

Тогда придется только иногда (при постройке игроком чего-то там) уточнять позицию последней точки маршрута БК-БИ, а при поиске пути искать путьдо вейпоинта БК, добавлять к нему путь БК-БИ и потом достраивать путь от БИ до собственно того, что надо «покусать».

Опять же для артеллерийских вагонов — можно заранее почитать путь к нескольким окрестностям каждой ЖД сети (далее можно просто воспользоваться поиском пути от поездов)

Так ведь проблема-то не в источниках загрязнения, а в артиллерии. А она бывает и мобильной (арт. вагоны).

Вагоны ездят по рельсам. Рельсы стационарный объект. Можно заранее посчитать пути до нескольких точек на рельсах (например через каждые 5 чанков для каждой ЖД системы) а от этих точек тупо «вдоль рельс» идти (Используя алгоритм поиска пути от поездов)

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

А если баз несколько? Я вот по фану делаю несколько разнесенных фабрик специализирующихся на своем типе производства(химия, электроника, плавильня, военка и т д) и соединенных крупной ЖД сетью для обмена ресурсами. В таком случае куда бежать? Или каждому рою отдельно высчитывать маршруты к каждой из фабрик? Да и с ЖД, вы, я так понял, предлагаете рассчитывать путь к каждому из сегментов ЖД, чтобы кусаки понимали куда бежать?

А если, например, игрок отойдет от базы и поставит пушку «в чистом поле». Бежать кусакам к базе или к Ж\Д? Или растеряться и начать искать путь к внезапно появившемуся и шмальнувшему орудию? Так это ничем и не отличается от того что уже есть. А предложенная вами «оптимизация», выходит, неработоспособна, т.к. предполагает заранее общитывать гораздо больше маршрутов, чем требуется, и при этом совсем не учитывает ряд вполне возможных кейсов.

На сколько я помню они должны выбирать цель по загрязнению среды

Думаю кусаки собираются в строй именно для того чтобы не считать путь для каждого, а посчитать для отряда. И эта атака планируется заранее и в принципе в фоне и считается путь.
А вот агра от арты происходит внезапно, и реакция у кусак другая, они уже не собираются в отряд, а каждый из выживших сам по себе бежит на звук выстрела и путь честно считается для каждого, вот этот массовый рассчёт и вызывает снижение ups.
Теперь же как раз, примерно как вы и предлагаете, в фоне считается крупный путь по тайлам, а в момент агры и уже во время движения постоянно считается уже более точный используя посчитанный ранее упрощённый как эвристику.
biter-ов

Кусак. Они в русском переводе просто «кусаки». Spitters — «плеваки»

Меня всегда удивляло то, что байтеры находят артиллерию где попало на любом расстоянии. Исходя из бытового опыта, если не видишь атакующего, то надо переть в сторону откуда прилетело (а не делать pathfinding неограниченного размера).

Странно ведёт себя этот алгоритм в модах, если конечно там именно он используется, а не что-то своё. Пример при использовании «AAI Programmable Vehicle».
Sign up to leave a comment.

Articles