Войти
ПроектыФорумОцените

Niko Saves World [RELEASED][Конкурс: «Я слышу тебя!»] (6 стр)

Страницы: 15 6 7 8 9 Следующая »
#75
17:52, 13 июля 2021

Запустить видео по клику - Как делать игрыЗапустить видео по клику - Как делать игры

Сделал спавн NPC и AI для них.
AI основан на стейт машине с приоритетами. Аналогично, как описано тут .
Стейт-машина состоит из стека Jobs с приоритетами. А каждый джоб содержит список Task.
Джоб выполняет глобальные задачи. Например джоб по умолчанию - это гулять туда сюда по улице периодически останавливаясь и отдыхая. А Task - это локальная задача, типа идти в точку или ждать в точке.
При этом, джоб прогулки при активации находит целевую точку на крате, ищут туда путь и создает два таска - первый это идти к точке, второй - стоять в точке в состоянии Idle. Когда оба таска выполнены, джоб счтается тоже выполненым и удалется из стека.
Если в процессе работы джоба появляются другие задачи - например НПСа сбила машина - то создается новый джоб (реакции на сбитие) с более высоким приоритетом. Пердыдущий джоб останаваливает свою работу, и передает управление более приоритетному джобу.
Когда он заканчивается - управление обратно передается джобу прогулки. Поскольку после возобновления джоба условия поменялись (например НПС уже может стоять в другом месте, и предыдущий путь уже не актуален), то список тасков для джоба удаляется и создается заново. При этом целевая точка прогулки остается прежней, но путь к ней и таски для движения по пути - перестраиваются.
В целом стейт-машина с приоритетом мне кажется подходящей для этой игры. Хотя некторые вопросы мне остаются не очень понятны.
Например, непонятно как в такой стейт машине реализовать выполнение нескольких тасков/джобов одновременно. Например, в процессе прогулки, НПС может что-то пробормотать или поговорить по телефону. Но у меня в один момент может выполняться только один таск - движение по маршруту. Как же запускать параллельное таски? Не очень понятно.
Другая непонятная пока для меня проблема - это кто должен реагировать на собятия? Отвественность ли это джоба? Или таска?
Например НРС столкнулся с другим НПС-ом в процессе движения. Кто должен на это реагировать? Таск? Джоб? Или контроллер НПСа?
Во всех случаях есть непонятки. Вроде как реагировать должен контроллер. Однако я старался сделать его максимально независимым от джобов. То есть он работает по принципу - вот я создал базовый джоб - отдал в стейт машину и забыл про него. А дальше стейт машина работает сама по себе. С точки зрения абстракции это правильно. Но в таком случае реагировать на события должны сами джобы, что как то не совсем логично и сложновато в реализации.
В общем, я пока не придумал хорошей архитектуры в этом моменте.

Сама же стейт машина выглядит примерно так:

+ Базовый_класс_для_джобов

Наследникам BaseJob нужно переопределить метод CreateTaskList, который создает список тасков. Остальную работу по вызову тасков берет на себя базовый класс.

+ Базовый_класс_для_тасков

#76
(Правка: 17:56) 17:55, 13 июля 2021

Наслденикам же BaseTask нужно переопределить метод Execute:

protected abstract IEnumerator Execute();
Он возвращает IEnumerator и вызывается аналогично корутине. Это позволяет сделать работу таска в асинхронном стиле и при этом разместив весь код таска в одном методе.
Например, таск движения по маршруту выглядит так:
+ MovingTask

Оба класса BaseJob и BaseTask поддерживают остановку после определенного таймаута. Это позволяет останавливать работу джоба, который вполняется слишком долго (и скорее всего не выполнится вообще). В таком случае джоб автоматически останавливается, переходит в состояние Fail и удалется из стека джобов.

#77
(Правка: 11:31) 10:21, 16 июля 2021

Smeler
> Пока выглядит так, что
> вы отказались от развития непрямоугольного варианта из-за сложности реализации.
> Это не плохо - данное решение выглядит верным для бизнеса "меньше усилий -
> больше эффекта", но я могу видеть, из первых постов этой темы, что вы как раз и
> желали достигнуть более интересной организации. Я думаю, что ваши неоспоримые
> многочисленные улучшения генерации можно применить к произвольной системе, но
> придётся использовать больше математики.

Возвращаюсь к вопросу о предыдущей "непрямоугольной" версии, и почему я от нее отказался.

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

+ Показать

Далее, я получаю набор многоугольников. Ихние ребра - это будущие дороги. Далее я применяю к многоугольником такую операцию как Shrink (сжатие). Эта операция сдвигает ребра многоугольника к центру. При этом после shrink я получаю новый многоугольник строго внутри исходного (это гарантируется тем, что у меня полигоны всегда выпуклые).

Изображение

Кроме shrink, есть еще две операции - Lift (поднятие вершин по оси Y) и RoundCorners (сглаживание углов полигона, на выходе получаем тот же полигон, но с бОльшим числом вершин и скругленными углами).

Комбинируя эти операции, получаем набор многоугольников примерно следующего вида:
Изображение

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

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

Но уже тут возникают концептуальные проблемы.
Вот они:

1. Несмотря на то, что полигоны изначально обозначают дороги, но создание графа дорог (который нужен для множества вещей, например для движения машин) - проблематично.
Во-первых потому, что не все грани полигонов есть дороги, некторые из них - технические, просто для сшивания. Например это края начального шестиугольника, грани которого не есть дороги.
Во-вторых, возникает проблема того, что считать дорогой, и как разбить эту дорогу на сегменты для смежных полигонов. Что было понятно, рассмотрим такой случай:
Изображение
Здесь начальный полигон черного цвета разбивается на три полигона. Далее, посмотрим на точку A. Она очевидно нужна, потому что это вершина для полигонов b и c. И логично считать, что это есть перекресток. Но вот для полигона a эта точка ничего не означает, она ему не нужна, она не является для него вершиной, и его часть дороги проскакивает сквозь точку A.
Получается для полигона a либо нужно вводить фейковую вершину A, либо же его часть дороги будет кардинально отличаться от той же дороги но с другой стороны. Но эта точка A ему не нужна, это нарушает его внутреннюю структуру. Если изначально все полигоны внутридомовой территории - четырехугольниые (что облегчает дальнейшие манипуляции), то эта точка превращает его в пятиугольник, что плохо.
В общем, здесь возникает проблема и для меша, и для графа дорог.

2. Еще одна проблема в том, что нельзя сделать перепады высот для дорог. Хотя казалось бы, полигоны идеально для этого подходят - достаточно просто добавить к координате Y вершин случайный шум (перлина например) и мы получим дороги на холмистой местности.
Но нет. Проблема опять же в точках, аналогичных точке A как на картинке выше. Если на картинке выше сдвинуть все вершины на случайные высоты, то между полигонами a и (b, c) возникает зазор по высоте. потому что точка A сдвинулась, а ребро полигона a - осталось прямым.

3. Еще одна принципиальная проблема - в системе полигонов нельзя или крайне затруднительно сделать мосты, тоннели, подземные переходы. И вообще любые развязки отличные от простого перекрестка. Почему? Ну я вообще не могу себе представить как это сделать полигонами. Отчасти потому что они начинают пересекаться, отчасти потому что мосты требуют криволинейной поверхности по Y и непонятно как в таком случае строить внутридомовую территорию. Даже сделать просто подвал дома в такой системе очень сложно, потому что внутридомовая территория уже строится ровным непрерывным мешем, без дырок.

4. Ну и есть еще много проблем связанных со сложностью вычислений. Например, если есть произвольная точка на местности, и я хочу узнать находится ли она на дороге и если да, то на какой? То ответить на этот вопрос - сложно. Для этого нужно много рассчетов. И все это вычислительная геометрия и все это довольно сложно и не тривиально.

#78
(Правка: 11:39) 10:24, 16 июля 2021

Идем дальше. После того, как граф дорог, меш дорог, тротуаров и пола - построены - нужно строить дома.

Изначально у нас есть полигон внутридомовой территории. По построению он всегда - четырехугольник, так гарантирует предыдущий этап рассчетов.
Этот факт позволяет использовать подход, который у меня называется FlexiGrid.
Суть в том, что внутри произвольного четырехугольника строится сетка, как на картинке:

Изображение

Ее линии - не параллельнные и не ортогональные, то есть это искаженная сетка. НО со стороны кода она выглядит просто как двумерный массив ячеек. И для внутренних алгоритмов с ней можно работать просто как с обычным двумерным массивом ячеек. На ней множно рисовать дома "попиксельно", как на карте. А вот на этапе экструдинга меша, узловые точки искривляются и принимают свои истинные координаты в пространстве.
Это позволяет довольно легко строить дома, дорожки и внутридомовую территорию:

Карта на FlexiGrid:
Изображение
И экструдированный меш:
Изображение

Но тут возникают вторая волна проблем, которая и вынудила меня отказаться это это затеи:

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

В результате, дома, построенные про неравномерной сетке выглядят неестественно.
То шаг окон/дверей разный, то углы острые, то дорожки разной ширины. К сожалению, не сохранились скрины, но можно представить как это выглядит, если с одной стороны дома шаг окон - один, а с другой все окна, двери, дорожки в два раза уже.
Плюс острые углы - меня окончательно расстроили.
Я долго думал, как красиво избавиться от этих острых углов, и добиться того, что бы сетка была более регулярной, но не нашел хорошего решения.

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

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

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

3. Есть еще более мелкие, но тоже проблемы. Они технического характера.
Например, в текущей версии я создаю меш из мелких quads (то есть прямоугольников), которые затем автоматически объединяются в quad'ы больших размеров. Это нужно для сокращения числа вершин и полигонов в меше.
При этом, два прямоугольника с общими вершинами при объединении всегда дают тоже прямоугольник. Это позволяет проводить процесс итерационно, заменяя огромные площади одним полигоном. Но в неравномерных сетках получается так, что у нас не прямоугольники, а четырехугольники. А объединение произвольных четырехугольников дает фигуру сложной формы, не quad. Поэтому сделать простую и эффективную систему триангуляции поверхности из мелки четырехугольников - уже не полчится.

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

Изображение

Но и в этом варианте остаются все те же проблемы, только чуть менее выраженные. Тоже острые углы, тоже неравномерные сетки.

И тогда я подумал - а что мне собственно дает уж такого хорошего неравномерная сетка? Если уж я делаю четырехугольный город, то может я просто сделаю его ортогональным, где все углы будут под 90 градусов - и решу все проблемы одновременно?

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

Резюмируя, вариант основанный на полигонах имеет недостатки:
1. Сложен математически, сложно строить граф дорог.
2. Не поддерживает перепады по высоте, не поддерживает многослойных поверхностей (мосты, переходы, подземелья и т.д.)
3. Неравномерная сетка приводит к домам неестественной формы и размеров.
4. Нельзя сделать глобальную карту местности.
5. Сложности с оптимизацией меша.

Все эти проблемы были решены во втором варианте, в котором я отказался от полигонов. Цена - дороги только ортогональные.

#79
21:42, 16 июля 2021

Zeus44
Благодарю за развёрнутый ответ, интересно было прочесть.

#80
11:34, 18 июля 2021

Zeus44
Все проблемы из-за того, что городскую застройку ты представляешь как связанную сетку кварталов. На самом деле квартал это просто побочный продукт пересечения [3, inf) улиц. Город может состоять из нескольких улиц и не иметь кварталов вообще. Кольца, тупики и корты никак не могут быть созданы на квартальной сетке.
Строительным элементом городской застройки должна быть секция улицы - одна сторона улицы, отделённая перекрёстком, поворотом или длиной от соседних связанных секций. 3+ секций, связанных в кольцо формируют квартал. Пространство внутри квартала ничем не занято, это просто пустырь.

#81
(Правка: 13:17) 11:47, 18 июля 2021

pacos
> Строительным элементом городской застройки должна быть секция улицы - одна
> сторона улицы, отделённая перекрёстком, поворотом или длиной от соседних
> связанных секций. 3+ секций, связанных в кольцо формируют квартал.

Ну сейчас это так и есть. Только как это решает проблемы, описанные выше?
Как застраивать острый угол между дорогами? Как вообще застривать углы, если плясать от "стороны улицы" ?
Как делать глобальную карту местности, если все объекты распложены под произвольными углами, и нет единой сетки?
Как строить navMesh для всего это хозяйства на больших масштабах и в рантайм?
Оно-то абстрактно все хорошо, а вот практически реализовать это - немного сложнее.

#82
(Правка: 30 июля 2021, 15:24) 13:11, 18 июля 2021

Хочу сказать пару слов про генераторы случайных чисел для процедурной генерации.

Казалось бы, что проще - берешь Random и используешь.
Но не все так просто. По факту, Random в лоб использовать нельзя.

И вот почему. Дело в том, что если просто создать Random и затем использовать его во всех методах генерации, то получится такая ситуация, что любое изменение кода или настроек в одном месте, приводит к полному изменению генерации в других местах.
Это будет выглядеть так, что допустим, вы поменяете в настройках число фонарей в городе, а после этого изменится не только число фонарей но и вообще весь город изменится, потому что настройка изменила число выбранных из ГСЧ элементов, и алгоритмы, работающие после генератора фонарей - получили уже совсем другие случайные числа.

Такое поведение недопустимо. Каждая настройка будет полностью менять город, что приведет к невозможности как разработки, так и выпуска релиза - тем более. Ведь представим себе ситуацию, что мы выпустили игру. И после релиза неизбежно нужно выпускать патчи, фиксы, менять бюаланс и т.д. Но каждое такое изменение будет полностью перестраивать город, делая его неузнаваемым. Кроме того, будут ломаться сохранки игроков, расположение ключевых НПС и т.д.

ГСЧ должен обладать стабильностью. Изменения кода или настроек может влиять локально, но не должно приводить к полной перестройке города.

Как решить эту проблему? Первое, что приходит на ум - это создавать новый Random в каждом методе генерации. Тогда ГСЧ внутри каждого метода будет свой и не будет зависеть от других методов.
Но тут возникают проблемы. Главная - где брать seed для этого Random? Использовать что то типа DateTime.Now.Ticks - нельзя, потому что тогда генерация будет зависеть от текущего времени. А использовать константу вместо seed - тоже нельзя, потому что тогда генерация разных городов будет выглядеть одинаково - ведь seed для всех городов будут те же самые.

Для решения этой проблемы я не использую Random напрямую. Вместо него я сделал класс RandomGenerator. Внутри себя он содержит свой уникальный seed и может выдавать по требованию Random, инициированный данным seed.
При этом, создать RandomGenerator непосредственно - нельзя, он не имеет публичных конструкторов.
Зато, он имеет метод Create который создает новый RandomGenerator но на базе текущего.

Это выглядит так (псевдокодом):

class RandomGenerator
{
 int mySeed;

 private RandomGenerator(int seed)
 { 
  mySeed = seed;
 }

 public RandomGenerator Create(int seed)
 {
  return new RandomGenerator(mySeed ^ seed);
 }
}

Как видно, можно создать новый RandomGenerator с некоторым seed, но для этого нужно иметь родительский RandomGenerator, и при создании нового RandomGenerator, его seed микшируется с родительским seed.
Таким образом, seed в RandomGenerator будет всегда завистеть от seed всех своих родителей.

На практике это работает так. Создается рутовый RandomGenerator. В него передется GodSeed - это начальное зерно генератора мира. Оно задется в настройках и его изменение приводит к перестройке всего мира.
Далее, все методы генерации получают на вход родительский RandomGenerator и создают на его основе свой RandomGenerator. В качестве seed передается константа, уникальная для данного метода (это может быть например хеш код строки - имени метода или класса).
А объекты генерации (например острова) - создают свой RandomGenerator передавая в качестве seed свои координаты или другую уникальную информацию (например имя НПС).

И уже из этого созданного RandomGenerator берется Random и он уже используется внутри метода для построений.

Схематически, RandomGenerator-ы образуют дерево:

Изображение

То есть все методы и объекты формируют свои RandomGenerator, на основе родительского объекта, и только в самом конце создается Random на основании seed всех родителей.

Такая иерархическая схема позволяет менять алгоритмы и настройки в произвольных местах. И такие изменения будут влиять только на генерацию внутри данного метода. Но на остальные методы и на остальные объекты - изменения влиять не будут. Генерация становится стабильной.

#83
13:27, 18 июля 2021

Zeus44
Спасибо за рассказ, было интересно почитать!

#84
(Правка: 7:01) 6:57, 19 июля 2021

Zeus44
> Ну сейчас это так и есть. Только как это решает проблемы, описанные выше?
> Как застраивать острый угол между дорогами? Как вообще застривать углы, если
> плясать от "стороны улицы" ?

example | Niko Saves World [RELEASED][Конкурс: «Я слышу тебя!»]

Черные стрелки - рандомно-генерируемые участки улиц. В конце участка улица продолжается и/или ответвляется с вероятностью N. Угол продолжения/ответвления - 0/90 гр +/- вероятность рандома.
Параллельно участку улицы с каждой стороны проложена зона застройки.
Зона застройки - прямоугольная сетка заданной толщины. Зоны застройки, располагаемые на смежных участках улиц сшиты в точке перекрёстка/поворота улицы (красные кружки).
Сшитые зоны застройки тестируются на коллизию друг с другом. Залитые цветом ячейки зоны застройки свободны от коллизии и пригодны для размещения прямоугольного объекта на их площади.
Пересекающиеся ячейки зон сшиваются в отдельную угловую зону, которая состоит из:
- уличной стороны зоны 1
- уличной стороны зоны 2
- торцов пересекающихся ячеек зон 1 и 2
- грани, сшивающей торцы зон (показана красным цветом) или двух тыльных сторон зон, пересекающихся в точке (красный кружок). Выбор между сшивающей гранью или пересечением тыльных зон зависит от угла пересечения зон, стиля зоны. На рисунке слева показана остроугольная зона со сшивающей гранью, а справа тупоугольная с двумя вариантами соединения. Так как это находится с тыльной стороны, можно для простоты всегда использовать сшивающую грань.
Угловая зона застраивается, либо остаётся пустой, в зависимости от остроты угла.

> Как делать глобальную карту местности, если все объекты распложены под
> произвольными углами, и нет единой сетки?
> Как строить navMesh для всего это хозяйства на больших масштабах и в рантайм?

Я не знаю как это реализовано на юнити, поэтому даже не понимаю в чём у тебя проблема.

#85
(Правка: 11:36) 11:21, 19 июля 2021

pacos

Спасибо за разъяснения. То что вы показываете - понятно и тривиально. Но оно не годится на практике. Я такое уже проходил.

* это сложно, долго

  • нет общей карты, то есть нет прямоугольного массива в котором четко указано какой объект стоит в данной точке
  • нельзя построить большие объекты (стадион например)
  • улицы у вас - просто рандомные отрезки которые начнут персекаться, и для них нужно искать пересечения и внутренние полигоны - что уже вычислительно громоздкая задача
  • кроме того, вы так построите только один из типов городской застройки - т.н. натуральная застройка (произвольная, древовидная). А как же радиальная и квадратная? Натуральная застройка характерна только для небольших гродков и сел.
  • внутридомовая территория - совсем не пустырь, как вы почему то считаете
  • для постройки меша дороги, тротуара и определения внутриквартальных полигонов - нужны громоздкие расчеты
  • нет мостов, тоннелей и т.д.
  • дома у вас получатся скучно квадратные. В моем варианте я могу застраивать свой квадратик домами произвольной формы, но в вашем варианте они всегда будут вытянуто-прямоугольными
  • опять же, строить navMesh на такой карте - очень долго (вернее тут и карты то нет, это же просто набор отрезков)
  • Фактически, то что вы предлагаете - у меня решалось и в рамках flexiGrid, но я от этого всего отказался, это все сложно.
    Нужно найти какое-то более простое, элегантное, хорошо выглядящее и вычислительно эффективное решение.
    Я, к сожалению, кроме прямоугольного варианта, других решения пока не нашел.

    563
    > Спасибо за рассказ, было интересно почитать!

    Пожалуйста.

    #86
    23:11, 19 июля 2021

    Посмотрел видео. Если бы я играл, то в первую очередь гонял бы по улицам и разносил всё направо и налево. Сбивал бы всех и пытался вылететь "за борт". )))

    #87
    0:21, 20 июля 2021

    Mirrel

    Ну, в основном, геймплей сейчас так и выглядит :)
    Вылеты за борт, прыжки с мостов, закидывание НПС на крыши - присутствуют.

    #88
    0:22, 20 июля 2021

    Cool driver:

    Запустить видео по клику - Как делать игрыЗапустить видео по клику - Как делать игры

    #89
    22:59, 21 июля 2021

    Снижение нагрузки на видеокарту, путем уменьшения числа НПС:

    Запустить видео по клику - Как делать игрыЗапустить видео по клику - Как делать игры

    Страницы: 15 6 7 8 9 Следующая »
    ПроектыФорумОцените