Comments 29
Мы не хотим пересчитывать всю упрощённую карту при каждом добавлении или удалении сущности. В то же время, если упрощать карту заново каждый раз, когда нам нужно найти путь, то можно запросто потерять весь полученный выигрыш в производительности.
я трактую примерно как «Я не хочу программировать, хочу чтобы само».
А кто мешает построить упрощённую карту после редактирования? А зачем её пересчитывать каждый раз перед алгоритмом?
Предложенное решение по факту и является упрощением карты, только с какими-то своими ограничениями что, скорее всего, в конечном счёте выйдет боком.
Читайте эту фразу как "мы не хотим пересчитывать всю упрощенную карту десяток раз в секунду".
К подлагиваниям после выстрелов артиллерии игроки уже как-то привыкли, а вот лаги в процессе строительства каких-нибудь стен или разворачивания базы из чертежа с помощью дронов могут здорово испортить игру.
А кто мешает построить упрощённую карту после редактирования?
карта постоянно меняется, можно стену построить например
Не целиком же она меняется, а только тайл, где стена.
По большому счёту карта меняется редко, только засыпание водоёмов кардинально меняет карту, а любые постройки не меняют путь кусак. По крайней мере я ни разу не видел чтобы кусаки как-то хитро себя вели, бегут по кратчайшему пути от своей базы к максимально загрязнённым блокам не учитывая при выборе пути стены или другие постройки. Как только встречают что-то не природное, начинают грызть. Игрок для них более приоритетная цель и они бросают грызть и бегут к нему и, если он за стеной, а рядом можно оббежать, только тогда они могут оббежать стену.
Может вы не так поняли "не хотим пересчитывать всю упрощённую карту" ?
Они-то может в душе и хотят пересчитывать, но из-за этого пересчета у них смысл оптимизации потеряется.
Там же путь от одного стационарного объекта до другого стационарного объекта.
Фактически у нас есть группа гнезд кусак/плевак, которые можно объединить в большую сущность «база кусак» (БК). Можно взять сущность «база игрока» (БИ) — некоторая окрестность радом с чанками занятыми источниками загрязнения (например 2 чанка).
Соответственно можно заранее в фоне построить маршрут от вейпоинта рядом с КБ кусак до некого вейпоинта окрестности БИ.
Тогда придется только иногда (при постройке игроком чего-то там) уточнять позицию последней точки маршрута БК-БИ, а при поиске пути искать путьдо вейпоинта БК, добавлять к нему путь БК-БИ и потом достраивать путь от БИ до собственно того, что надо «покусать».
Опять же для артеллерийских вагонов — можно заранее почитать путь к нескольким окрестностям каждой ЖД сети (далее можно просто воспользоваться поиском пути от поездов)
Так ведь проблема-то не в источниках загрязнения, а в артиллерии. А она бывает и мобильной (арт. вагоны).
Во-первых, подобный способ перемещения кусак будет заметен невооруженным глазом. Во-вторых, рельсы могут быть построены игроком очень быстро, что при вашем алгоритме вызовет лаги. В-третьих, используя мод FARL можно вовсе отвязаться от рельс и получить полностью автономную мобильную арту, пусть и сложную в управлении.
А если, например, игрок отойдет от базы и поставит пушку «в чистом поле». Бежать кусакам к базе или к Ж\Д? Или растеряться и начать искать путь к внезапно появившемуся и шмальнувшему орудию? Так это ничем и не отличается от того что уже есть. А предложенная вами «оптимизация», выходит, неработоспособна, т.к. предполагает заранее общитывать гораздо больше маршрутов, чем требуется, и при этом совсем не учитывает ряд вполне возможных кейсов.
А вот агра от арты происходит внезапно, и реакция у кусак другая, они уже не собираются в отряд, а каждый из выживших сам по себе бежит на звук выстрела и путь честно считается для каждого, вот этот массовый рассчёт и вызывает снижение ups.
Теперь же как раз, примерно как вы и предлагаете, в фоне считается крупный путь по тайлам, а в момент агры и уже во время движения постоянно считается уже более точный используя посчитанный ранее упрощённый как эвристику.
biter-ов
Кусак. Они в русском переводе просто «кусаки». Spitters — «плеваки»
Меня всегда удивляло то, что байтеры находят артиллерию где попало на любом расстоянии. Исходя из бытового опыта, если не видишь атакующего, то надо переть в сторону откуда прилетело (а не делать pathfinding неограниченного размера).
dailytelefrag.ru/articles/print.php?id=3895
Новый алгоритм поиска пути в Factorio