Добре всем. Уже всю голову сломал различными вариантами, и поэтому уже мало что соображаю, так что не обессудьте.
Пишу ИИ для игры, вернее пытаюсь писать. Сама система принятия решений в принципе есть, а вот системы ввода исходных данных в неё нет. Задача не сложна: рассказать объекту в мире, какие объекты находятся вокруг него, в определённом радиусе. С единственным условием, таких объектов, собирающих информацию обо всём вокруг в реалтайме, одновременно существует, до нескольких тысяч.
Может подскажите что-то дельное, перебирать каждым объектом каждый очевидно нельзя. Пробовал вешать коллайдеры тригерные, и записывать через он тригер энтер и удалять через ексит, проблема пришла откуда не ждали, при уничтожении объекта внутри тригера, ОнтриггерЭксит не вызывается. Пробовал стрелять рейкастами по сторонам, с системой разводки по времени, но это уже крик души.
Слышал про "решение белых людей распространённой проблемы" про дробление пространства на ячейки и хранение в них списка находящихся в ячейке объектов. И в реалтайме объект просто проверяет свою и соседние ячейки и формирует список объектов. Но всё это очень мельком, и даже не знаю как подобное решение называется. Что забивать в поисковик. Голова уже не варит, и ничего умнее чем прибежать на форум к завершению дня я уже видимо придумать не могу.
Хоть обучающую литературку по теме посоветуйте, крайне желательно на русском. Или на краяйняк скажите как эта "известная проблема" называется, и какой алгоритм искать и под юньку пытаться адаптировать.
Да, последнее, игра 2Д, и никаких препятствий видимости нет, препятствия большие, а радиус обзора относительно маленький, так что это можно не учитывать.
И да, устаёт, это вторая причина по которой отказался от колайдеров, про версия выдаёт 15 фпс уже на 7 тысячах. Но в принципе на первых парах думаю 5 000 мне более чем хватит) А там посмотрим, либо обработку всех невидимых объектов за движок вынесу, либо буду искать как можно это ограничение обойти ибо ресурсов вычислительных предполагается много, на крайняк переступлю себя, и забью на полностью живой, независимый от игрока(ов) мир), но это последнее решение.
Иии, пока никаким образом не делаю, вот это и спрашиваю, как его можно эргономично делать, слышал про описанный метод, вроде всё логично, но много вопросов по занесению и изменению данных в ячейке, туманно представляю себе мастер-класс, который будет этим заниматься, и к которому в конечном итоге будут принадлежать все поведенчесские классы игры, но поподробнее бы про решение почитать, а я даже не знаю как оно называется, как проблематику обозвать, по моим запросам ничего не находит.
Ну под такие задачи юнити не подходит мне каж. Нужно искать другой движок. Хотя можно и "закостылить". Делать инстациацию объектов по мере приближения игрока, удаление по мере его удаления (от слова дальность, даль ). Управление объектами вынести отдельно. Возможно придется это делать в плюсовой ДЛЛ, чтобы не связываться с виртуальными машинами, но может и удастся обойтись и стандартным шарпом.
Читал про игру сталкер. В игре реализован динамический мир. Причем детализация жизни мира была разделена на 3 зоны по дальности к игроку. то есть если в самой ближней зоне при схватке мутанта с военным отрабатывались выстрелы, координаты, попадания, урон; в самой дальней зоне просто "бросался кубик кто выжил".
Думаю можно попробовать выделить менеджер объектов, который 1. обслуживать рожание/удаление объектов на сцене. 2. руками дергать поведенческие методы удаленных объектов. для них необязательно обновление раз в кадр. можно самостоятельно настроить частоту вызываемых методов.
Но в этом подходе есть проблема: если планируется большой открытый мир, его необходимо будет тайлить, т.е. далекие объекты будут за пределами террейна и считать их положение, пресечения и физику придется руками.
в поисковик можно вбить: реализация алгоритма восприятия окружения оптимизация..
самый быстрый способ без коллайдеров, имхо, будет повесить на всех объектах микроскрипт с функцией определения расстояния до ГГ (можно задать частоту проверки в зависимости от предыдущей - если удаление большое, проверить позже, иначе - чаще) и оповещения ГГ о попадании в диапозон. в ГГ добавлять всех сообщивших в список и очищать список после обработки.. ну эт уже детали.. но тут ВОТ В ЧЕМ ВОПРОС: - неужели все 10 000 объектов мира являются значимыми для восприятия ГГ?! т.е. задача ИИ тут в чем? поиск иголок в стоге сена? обычно значимыми являются 5-25% всех объектов в игре.. и их можно сделать коллайдерами запросто.. (т.е. из 10 000 - 2500, вполне перевариваемо) Мыслю - значит программирую... Конструктивная критика - умных ведет к совершенству... Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
Сообщение отредактировал KamiRonin - Четверг, 18 Декабря 2014, 11:46
Делать инстациацию объектов по мере приближения игрока, удаление по мере его удаления (от слова дальность, даль ).
Этого делать не стоит. Если постоянно удалять и создавать 5 к объектов, то будет еще хуже. Чтобы оперировать с большим кол-вом одинаковых объектов, лучше использовать object pool (ССЫКА, ССЫЛКА)
romeo98, можно сделать и пулом, но насколько понял, речь не идет о мгновенном появлении 5000 объектов в зоне игрока и городить огород неоправданно. + объекты могут быть разные. придется пулы создавать под разные типы объектов. размер пулов придется менять по ситауции. зачем такой гемор?? в пулы хорошо снаряды укладывать - они однотипны. На заметку: 1гигогерцовый андроед спокойно тащит 10 рождений в сек.
Сообщение отредактировал Ranger - Четверг, 18 Декабря 2014, 12:03
пул можно делать типа GameObject, а потом при обработке - смотреть на тэг и добывать из объекта нужный компонент в зависимости от тэга. не, тут сложностей особых нет. но сам пул не ускорит работу на большой показатель - т.к. для выявления близлежащих объектов его придется каждый такт перебирать ЦЕЛИКОМ! тест на удаленность в апдэйте 5000 объектов будет в несколько раз быстрее т.к. там решаются сразу обе задачи - и проверка попадания в диапазон восприятия и передача ссылки ГГ для обработки... при внесении в обработчик гибкости в виде регулирования частоты проверки (можно так же иметь отключение этой проверки для значимых предметов в сундуках например) решение будет достаточно эффективным.. Мыслю - значит программирую... Конструктивная критика - умных ведет к совершенству... Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
Уххх, сходил, называется, на работу... Итак, по порядку: To Ranger: Несколько тысяч объектов не в видимости игрока, а в мире, и да, весь мир, это одна сцена (в идеале, хотя скорее всего без разбиения не обойтись, но посмотрим). И да они все существуют вне зависимости видит их игрок или нет, кстати игра мультиплеерная, и с живым функционирующим миром и "экосистемой" которая может функционировать и без иргоков, ради чего собственно и весь гемор.
Да, отчасти как в Сталкере, и собственно в чём проблема, отрисовывать их всех в одном кадре конечно не буду, даже создание разведено по времени, и плавно наращивает количество управляемых ИИ персонажей и прочих объектов до заданного и поддерживаемого значения, с нижних уровней, и поднимаясь плавно выше. И я не собираюсь обрабатывать физику взаимодействия между ними, но согласись, что бы хотя бы бросить кубики, нужно определить кто с кем сравнивается, а значит кто-то на кого-то должен напасть, а значит, этот кто-то должен знать что рядом находится кто-то другой. И для решения этого вопроса я и ищу, как тут подсказывают "Алгоритм восприятия окружения", или иную систему дающую подобный функционал. И я, в принципе, не понимаю, почему эта задача такая редкая, любой не заскриптованный на игроке ИИ должен её ставить вопрос её решения, а я ни чего в интернетах найти не могу(
Кстати безмерно благодарен KamiRonin, обязательно поищу.
А вариантов её решения как всегда, несколько, первый: дискретное пространство, это я даже вроде придумал как реализовать, здравствуй наследование классов, и класс родитель который содержит всё взаимодействие с табличей пространства, и от которого наследуют логику все поведенческие скрипты игры. Но опять же не без боя, внезапно осознал что в каждой ячейки массива находится список всех находящихся внутри объектов, куда можно быстро записать и выписать любой объект, и безразмерный лист для этой цели крайне медлителен, а размерный массив имеет сложности, сейчас думаю над одной переменной типа стринг с ключевыми символами после которых идёт ID объекта.
Второй внешний менеджер который знает о местоположении всех объектов ииии, видимо ежесекундно просчитывает расстояние между ними всеми, или делит пространство на определённые зоны, и смотрит кто в этой зоне находится и они все взаимодействуют, не знаю, этот вариант не продумывал.
Третий, он же сейчас, "План Б": Так как игра мульплеерная, и весь мир будет считаться на сервере, сделать его не на юньке, а на С++, обойдя все ограничения всех движков, и упершись лишь в вычислительные мощности серверной машины, которые планируются весьма выдающимися и уже заложены в бюджет...
P.S. OpenGOO От юньки отказаться не могу, ибо это 16 платформ, и да, в идеалистических планах, кроссплатформенный мультиплеер на 10-14 платформ и всё это на одном сервере и в огромном мире, который единая сцена, как на сервере так и у всех игроков) Но это уже, как говорится, на правах грёз и рекламы)
Вот еще полезная информацияSpatial Partition Мои проекты: - Свободный и открытый клон World Of Goo - TrueEngine2D (2D игровой фреймворк основанный на FreeBASIC)
Безмерно благодарен, вот чего мне для счастья не хватало, тем более что я готов реабилитироваться как пользователь гугла, и нашёл перевод этой книги на русском: Шаблоны игрового программирования.
Там рассматриваются весьма обобщённые случаи, на С++, и как я понимаю заточенные под UDK, и для юньки это нужно сильно адаптировать, но в принципе этого уже более чем достаточно, при наличии большого желания) Безмерно благодарен)
"о едином мире на сервере" кстати - отдельная крайне интересная тема... сейчас ММО в подавляющем большинстве реализована либо узкими локациями за раз (хочешь идти дальше - идет выгрузка прежней локации, загрузка новой). либо многогигабайтным КЛИЕНТСКИМ приложением - главной функцией сервера является пересылка сведений о действии и местоположении каждого клиента другим клиентам и все (служебные функции это не важно сейчас). много гигабайт потому что в клиентскую часть игры загружаются все объекты уровня, т.е. имеем ТЫСЯЧУ КЛОНОВ одного и того же контента.. и это мировая практика. так что "на одном сервере и в огромном мире, который единая сцена, как на сервере так и у всех игроков" - это либо тысячаклонник, либо НОВОЕ СЛОВО в игрострое! (думаю об этом уже полгода в связи со своим проектом gcuptown! тоже есть острая необходимость выйти из порочного круга) Мыслю - значит программирую... Конструктивная критика - умных ведет к совершенству... Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
Сообщение отредактировал KamiRonin - Пятница, 19 Декабря 2014, 15:20
KamiRonin: Тут много специфики самой игры. Очень простой мир, грубо говоря это просто пространство с фоном, в котором существует множество динамичных объектов со своей логикой поведения. Не знаю, может это и есть то самое новое слово?) А вообще, и тут есть выход. То от чего я отказался, генерация мира по ключу) На сервере стоит генератор, и в каждом клиенте стоит генератор, дублируется только он, при подключении к серверу, он посылает клиенту ключ генерации имеющегося мира, и клиент у себя в памяти строит идентичную копию, и раскидывает в неё все статические объекты. А динамические объекты передаются клиенту по видимости.
Если не нужно что бы мир менялся, не надо менять ключ, и пусть каждый раз на клиентах строится одна и та же копия мира. Из минусов, нужно основательно подойти к вопросу генератора и сделать его достаточно качественным что бы результат удовлетворял всем критерии.
Вряд ли открыл Америку, но надеюсь дал пищу для размышлений)
клиент у себя в памяти строит идентичную копию, и раскидывает в неё все статические объекты
чтобы клиент генерировал - ему нужны "кирпичики" - модели, меши, текстуры и тп. это и есть многигибайтконтента в клиентской части.. генерация мира по ключу - это долго, разработчики создают системы описаний, специальные схемы для генерации мира.. если нужно чтобы он был отличным от предыдущего.. но смысл тогда в нем - если он не известен заранее?!
ЦитатаBlackX ()
динамические объекты передаются клиенту по видимости
по видимости - это как? там все равно передаются модели, текстуры, меши и тп.. - все те же гигабайты.. говорю же - тут порочный круг... Мыслю - значит программирую... Конструктивная критика - умных ведет к совершенству... Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
KamiRonin, не скажи, клиент содержащий набор кирпичиков несоизмеримо меньше клиента содержащий огромный список готовых объектов и уровней. Здесь нет необходимости хранить каждый кирпичик множество раз в каждом объекте, достаточно одного экземпляра каждого вида.
А на счёт скорости, ну так это взаимосвязь, либо скорость, либо объём. Либо хранишь, либо генерируешь.
P.S. Если у тебя кирпичиков на несколько гегибайт, до у тебя проблема с кирпичиками...
клиент содержащий набор кирпичиков несоизмеримо меньше клиента содержащий огромный список готовых объектов и уровней. Здесь нет необходимости хранить каждый кирпичик множество раз в каждом объекте, достаточно одного экземпляра каждого вида.
не скажи, все уровни построены из тех же кирпичиков, обрати внимание хотя бы на CoD WM3 - там есть уровень в котором одна и та же машина выставлена больше 20 раз в разных местах, под разным углом.. и это небольшой уровень. генерировать на лету намного накладнее чем создать заранее и просто загрузить готовый уровень! тем более что есть технологии, которые помогают хранить одну модель на все однотипные готовые объекты. и повторюсь - это мировая практика! даже огромный мир скайрима создан заранее и подгружается только по мере перемещения. и скайрим одна из самых многогигабайтных игрушек при этом. хотя там большинство моделей - повторяются.
в общем попробуй создавать меши на лету, рисовать текстуры по описанию (а не хранить их готовыми), добавлять созданным моделям генерацией скелеты и анимации и тп и тд.. я посмотрю на объем работы по ТАКОЙ генерации! думаешь из 20 кирпичиков можно построить с.т.а.л.к.е.р.? ах да.. я и забыл - может ты о майнкрафте все это????? Мыслю - значит программирую... Конструктивная критика - умных ведет к совершенству... Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
Конечно, о нём родимом) В конце концов сколько стоит Скайрим и Сталкер, 100 миллионов? 500? Миллиард? А Майнкрафт 2,5 миллиарда в американской валюте)
А генерация штука всё равно крайне полезная, хоть и специфическая. Я твёрдо уверен, что за генерацией (не обязательно рандомной) будущее. Просто не научились ещё пользоваться ей полноценно, да мощностей вычислительных не хватало, но щас эта проблема уходит. И кстати самое яркое подтверждение моих слов "No Man's Sky" игра построенная на сгенерированном контенте, и что бы просмотреть весь уникальный контент, говорят необходимо несколько десятков лет реального времени (преувеличивают конечно как всегда, и считают все, даже самые минимальные отличия, но надеюсь смысл понятен). Она содержит несколько миллионов планет и каждая со своим ландшафтом, атмосферой, фауной и прочими спецификами.
А тот же MW3, если там одна машина 20 раз в сцене используется, то вероятно она не часть меша сцены, иначе бы их сделали бы поуникальней, и эти 20 копий создаются из эталона непосредственно при запуске сцены, а это и называется генерация Только не по какому-то алгоритму, а вероятно, по списку заданных точек, мол, при старте сцены, там, там, и вон там, создай вот эту машину. А можно было бы, например, сделать 3-4 вида колёс, и по тому же принципу раскидать по этим копиям машин, сделав их более разными, или например текстуры на них разные натянуть (хотя подозреваю это как раз делается, и машина эта, там встречается сильно больше раз, чем 20 ), причём натягивать текстуры именно на лету, что бы не хранить в билде несколько моделей машины отличающихся только цветом.
Просто нужно определять что делать заготовками, а что генерировать из кубиков, и размер этих самых кубиков, и чем они меньше, тем меньше весит билд и больше уникальных вещей можно из них построить, но дольше это будет загружаться сцена. И разумная комбинация этих двух подходов даёт сейчас самые лучшие результаты, и это сейчас мировая практика.
Но конечно, я знаю и о противоположных примерах, где генерация в мире вообще не используется, яркий представитель "RAGE", где все не интерактивные объекты, это часть одного огромного заготовленного разработчиками меша сцены, с натянутой на него всего, огромной, несколькогигобайтовой текстурой. Так что тоже имеет право на жизнь такой подход, по крайней мере пока
Но что-то меня опять понесло, и мы совсем отдалились от темы. И если есть желание буду рад перенести нашу дискуссию в личные сообщения. А тем временем решение найдено, называлось необходимое мне безобразие "паттерн пространственного разбиения" ссылку на английское описание которого здесь уже скинул OpenGOO, за что ему ещё раз спасибо. Русская версия этой же статьи. Там всё достаточно подробно описано с простыми примерами на С++ и ссылками на более развитые решения.
эпично "No Man's Sky" - воксели, собственный движок и собственная среда разработки, ЗА ГОД.. Не хватает только эволюционно генетического алгоритма создания существ на разных планетах и Матрица готова!
воксели - тот же майнкрафт только в наноразмере. а так ребятам реально - респект!! (скоро видать все игры будут по типу майнкрафта - кубичный мир, и единственное что греет душу - 2.5 млрд в американской валюте за игровую СТУДИЮ Mojang, а не игру, кстати) Небольшая статистика по доходам от игр с заранее "сгенерированным" миром за 2013: майнкрафт - 314 млн. за 2013...и его нет ни в одном из 5 списков лучших игр всех времен, которые нашлись в гугле за 5 минут.. не знаю даже.. ну на троечку с минусом расклад по ходу. хотя нельзя ей отказать в шикарности такого достижения!
ЦитатаBlackX ()
И разумная комбинация этих двух подходов даёт сейчас самые лучшие результаты, и это сейчас мировая практика.
можешь рассказать хотя бы о ПАРЕ мирового уровня проектов (типа CoD, майнкрафт, варкрафт и тп) с ТАКОЙ практикой? а то не успеваю читать билборды с новостями об мировых тенденциях в игровых структурах..
Мыслю - значит программирую... Конструктивная критика - умных ведет к совершенству... Великие умы обсуждают идеи, средние - обсуждают поступки, а малые - людей.
). 
