Помогите! деже не знаю где спросить :: Беседка :: Форум

Как делают учет юнитов в поисках путей в стратегиях? Алгоритмы поиска пути дают путь по клеткам, но в клетках могут быть и юниты размером в полклетки и меньше. Их тоже ведь надо как то обходить.
Отталкивание вроде не катит - если в сторону друг друга 2 юнита направить, они не смогут обойти друг друга, также юнит не сможет обойти шеренгу юнитов.

Инженер‑космогоник

Опубликовано 15.02.2016 19:21 (9 лет назад) #

Традиционный способ - делать мелкую сетку(размером с пехотинца) и делать такой хак - вокруг всех препятствий при создании карты генерируется бордюр в одну клетку (в каждой соседней для препятствия проходимой клетке ставится маркер "не проходима для техники"). Таким образом пехота ищет путь по всем клеткам кроме препятствий, а техника - по всем клеткам кроме препятствий и бордюров. Пехота в этом случае тоже помечается как препятствие и создает бордюры(это можно сделать шустро, если пересчитывать только движущуюся пехоту). Ну или техника ее давит.
Тем же методом можно делать на карте леса - это сразу территории, помеченные "проходима только пехотой".
При этом методе обхват юнитов будет соответственно 1, 3, 5 и т.д клеток.
Возможно есть и другие методы, например, которые находят кратчайший путь, а затем проверяют его ширину на всем протяжении.

Опубликовано 15.02.2016 19:48 (9 лет назад) #

Способов много - и мелкая сетка с недискретным, а плавным занятием юнитом своей зоны клеток (на краю зоны занятость клетки для некоторых расчётов игнорируется), также и пасфайнд по клеткам, но с некоторым радиусом в клетках вокруг основного пути для "протискивания". Для сталкивающихся юнитов есть вариант алгоритма обмена друг с другом, если не нужна логичность и визуальная строгость, обход шеренги либо по зоне с частичным игнором, либо с небольшим расталкиванием (шеренга всё равно обычно с небольшими промежутками стоит, которые как раз тоже могут описываться зонами с частичным игнором на персечение и алгоритмом потенциального/отталкивающего поля всех пододвигать). Есть варианты с недискретным, а точным поиском пути (не в клетках, а во флоат координатах, с учётом размеров) - там просто будете регулировать настройки промежутков в шеренгах и размеров юнитов. Есть алгоритмы стайного поведения которые могут помочь в случаях массового движения своих, чтобы друг за друга не запинались, а как бы работали сообща.
Есть очень крутая либа для подобных вещей https://sourceforge.net/projects/opensteer/ стоит взглянуть, ещё видел неплохой недискретный поисковик пути на дельфи http://dtf.ru/articles/read.php?id=46788

Сам когда думаю о таких вопросах (тоже падок на продумки алгоритмов в стратегиях) - вспоминаю этот ролик

редакция от phomm, 15.02.2016 19:57

Опубликовано 16.02.2016 18:01 (9 лет назад) #

Спасибо, буду думать) Сейчас склоняюсь к мысли, что обход юнитов мне нужен собственно только для обхода юнитов, на путь глобально как то юниты не должны, то есть ситуаций, что в узком проходе столпилась куча техники и надо искать обходной путь быть не должно. Поэтому, наверное, поиск пути сделаю просто по клеткам, а обход попробую как то эвристически что ли сделать. типа если на пути вижу юнита то возьму правее.
P.S. японцы отожгли. В предлагаемых в конце роликах еще и тайскую армию глянул, вот уж действительно кому делать нечего было ^^

Опубликовано 18.02.2016 06:18 (9 лет назад) #

Сперва находишь путь по треугольникам поверхности любым алгоритмом на графе (каждый треугольник знает ссылки на примыкающие к рёбрам). Затем для аппроксимации траектории заданной набором треугольников обычно используют funnel алгоритм, принцип его очень простой. А для обхода динамических препятствий дополнительно приходится учитывать направления и скорости, в итоге выбирать пути в зоны меньшего веса (веса задаются масками обычно). Либо же просто рассталкивать всех :)
Вот статья и пример работы: http://digestingduck.blogspot.hk/2010/07/my-paris-game-ai-conference.html

редакция от XProger, 18.02.2016 06:19

Опубликовано 20.02.2016 17:35 (9 лет назад) #

XProger, спасибо, почитаю)

Опубликовано 16.03.2016 13:43 (9 лет назад) #

Хочется сделать свой пакер ресурсов, дабы хранить кучу текстур\звуков и прочих ресурсов в одном сжатом файле. Формат файла представляю себе так: заголовок в котором хранится массив инфы о каждом ресурсе(имя, степень сжатия, оффсет в файле и прочее) и далее массив сжатых ресурсов(каждый ресурс сжат отдельно от других).
Непонятно как это организовать чтоб на лету архив редактировать, например, если добавляем ресурс, то надо добавить еще одну запись в заголовок и сам ресурс в конец файла. Если зарезервировать место в заголовке, то получим ограничение на количество ресурсов. Если не резервировать, то большую часть файла придется переписывать\сдвигать в конец. Ограничение на количество ресурсов терпимо, но нежелательно.
Еще проблема получается при удалении. Если удалить ресурс из середины файла получается фрагментация. Работал с одним пакером, который при удалении ресурса полностью копировал весь архив в новый за исключением удаленного ресурса, а старый удалял. Мне кажется это нехороший подход.
Пока склоняюсь к такому решению: пока идет активная работа с архивом резервируем большой заголовок, при удалении ресурсов из архива ничего дополнительно типа дефрагментации\сдвига не делаем. При необходимости перепаковываем архив, убирая ненужный резерв заголовка и склеивая данные в нужном порядке уменьшая размер файла.
Какие будут мысли?

Древний организм

Опубликовано 16.03.2016 13:52 (9 лет назад) #

Ну вообще тут всё немного не так радужно как тебе кажется.
1 - если ты пакуешь ресурсы, игра или прога, не важно, будет расжимать их дважды. Сначала твой архиватор будет их распаковывать, потом еще джипег\пнг\огг.
2 - сжатие уже сжатых ресурсов не даст какого-то комфортного уменьшения зажираемого программой места.
3 - если очень хочется не держать ресурсы открытыми, их можно просто объединить в один файл-пак без сжатия. Скорости не потеряешь на загрузке.

Опубликовано 16.03.2016 13:55 (9 лет назад) #

Посмотри в сторону "Compound File Binary File Format", он умеет в динамическое добавление и удаление файлов. Фрагментация да, беда, но можно посмотреть там пару идей.

Опубликовано 16.03.2016 14:10 (9 лет назад) #

2Darthman,
Вот именно из этих соображений я и задумал хранить ресурсы в пакере. Зачем пользоваться jpg, tga, ogg, когда можно грузить всё из сжатого пакером bmp\wav? Тем более, что пакер даст примерно такое же сжатие. В случае с jpg и ogg еще понятно, что сжатие у них больше из за какой то потери качества. Но выигрыш по размеру не так уж и велик, да и не думаю, что стоит экономить на качестве.
Да, про альфу в bmp я знаю:D

2pelmenka,
это походу целый монстр:D миниатюрная файловая система в одном файле) Идея прикольная, надо поразбираться, может что из идей и наковыряю.

Опубликовано 16.03.2016 14:16 (9 лет назад) #

Она там не одна :D

Древний организм

Опубликовано 16.03.2016 14:20 (9 лет назад) #

В таком случае тебе и WAV с BMP не нужны, сразу храни RAWdata в паке, чего уж там.
Но это изобретение велосипеда. Геморрой для всех. Надо заменить картинку - переупаковывай весь архив. Чего ради? Кто выигрывает в итоге?

Опубликовано 16.03.2016 19:02 (9 лет назад) #

Чем тебе мой вариант не нравится? По названию легко гуглится спецификация, формат простой, можно за вечер на коленке работу с ним написать.

Древний организм

Опубликовано 16.03.2016 19:04 (9 лет назад) #

Вопрос о том какие мысли, а не какой алгоритм сжатия выбрать был.

Опубликовано 17.03.2016 01:34 (9 лет назад) #

Опять басня — «monobogdan и colorkey»... Интересно, может он еще скажет, что bmp не умеет в альфу?..

Опубликовано 17.03.2016 10:56 (9 лет назад) #

2pelmenka,
твой вариант не нравится сложностью) сектора всякие, минисектора, цепочки секторов, это слишком сложный путь для этой задачи. Её я хочу решить с минимальными затратами, т.к. на крайняк я могу и просто в отдельных файлах ресурсы хранить. Или как уже описал - с резервированным заголовком да отсутствием автоматической дефрагментации. Это намного проще.

2Darthman,
Ну в общем то Raw я хранить и собираюсь, шоб сразу готовые к загрузке данные. Не знаю чем плохо изобретение велосипеда в данном случае. Если нужно добавить текстуру, то берешь tga, jpeg, или что нибудь еще, кормишь его пакеру, указываешь какой формат текстуры нужен, альфа, колор, серый цвет, количество и размер кадров если надо, пакер все это сам конвертит в нужный для загрузки формат, сжимает и сохраняет.

Древний организм

Опубликовано 17.03.2016 12:17 (9 лет назад) #

Тогда вопрос в чем? Решил так, значит так и делай.

Инженер‑космогоник

Опубликовано 17.03.2016 12:30 (9 лет назад) #

MysticCoder
Виртуальные файловые системы в контейнерах придуманы не от хорошей жизни, а как раз потому, что в файлах медленно, а в raw - не удобно. Суть не только в том, что данные готовы к загрузке из Raw, все быстро и т.д, но и в принципе разработки.
Очень неудобно перед использованием пересобирать архив данных, поэтому делают так:
Ты пользуешься одной и той же базой методов Resource.Load("textures/head.bmp"), и оно одинаково работает и для файлов в папке и для упакованного data.raw
Причем при разработке ты пользуешься обычной файловой системой, ибо удобно, а при релизе собираешь свою папку data в raw файл и все работает точно так же.

Опубликовано 17.03.2016 12:56 (9 лет назад) #

2Darthman,
Вопрос стоял как поудобнее и меньшей кровью это все организовать. Чтобы и ресурсы на ходу удобно и быстро было заменять и не тратить на это много сил. Впрочем, сейчас вопрос закрыт, сделал пока хранение заголовка в отдельном файле и данных в другом. Проблема фрагментации - перепаковка при отдельном запросе.

2Mefistofel,
Это здравая мысль. Но вот, допустим, 2d анимацию хранить в каком нибудь отдельном png неприкольно, т.к. в нем не сохраняются данные о раскадровке, хардкодом эти данные хранить тоже нехорошо. В таком случае нужен отдельный инструмент конвертации png в "png с данными раскадровки" и его то можно как раз совместить с пакером.

Инженер‑космогоник

Опубликовано 17.03.2016 13:41 (9 лет назад) #

Ну тут скорее должен быть файл "данные раскадровки", в котором ты сохраняешь данные о раскадровке, который лежит в виде xml(для систем контроля версий) в папке данных, а при упаковке попадает в сборку в виде бинарного файла для скорости.
Например, во флеше или конструкторах, ты не работаешь напрямую с ресурсами, ты работаешь с их представлениями, а флеш непрозрачно для тебя хранит их в файле проекта или собирает в финальный exe/swf. Аналогия та же самая.
У Unity тоже забавный подход - ресурсы хранятся в 3-х местах. Ты закидываешь файл в проект, Unity обрабатывает его(создает копию в папке Assets в нечитаемом виде) и создает к нему meta файл.
Ресурс лежит в папке в исходном виде, в meta файле хранятся его настройки(например то, что из картинки 2048*2048 нужно сделать 1024*1024 упакованную).
При запуске в редакторе берется файл из Assets, упакованный и готовый к работе. При сборке проекта берется оригинал, режется/зажимается по настройкам и поставляется в архив.
При этом для тебя эти 3 представления выглядят как один метод - Resource.Load("filename")
Забавно и то, что все настройки, meta файлы, анимации и прочее, могут лежать в проекте в бинарном виде или в виде yaml. Но при сборке в ресурсы попадает компактная и быстрая бинарная версия.

Страница 7 из 8

Перейти на форум:

Конкурсы

Открытые конкурсы:

Активных нет

Недавние конкурсы:

Случайная игра

Мини-чат

Вам необходимо залогиниться.

Архив чата