Войти
UnityФорумОбщее

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

Страницы: 1 2 Следующая »
#0
11:56, 15 июня 2021

Думал будет несколько проще в реализации... но чет не получилось. Точнее получилось, если не брать в расчет координату Y, а вот в ней собственно и вопрос.

Начал делать поиск пути по карте, пока для конкретного небольшого участка, для одного моба.
- Взял квадрат вокруг моба заданного размера, моб не может выйти за пределы этого квадрата.
- Этот квадрат поделил на сетку из квадратов изменяемого размера (сегмент).
- Каждый сегмент поделил на 2 треугольника.
- Нашел, так скажем, центры треугольников.
- Спроецировал препятствия на всю эту полученную сетку.
- Исключил занятые треугольники.

Получился массив из центральных точек треугольников (так же есть массив всех углов этих треугольников), на которые моб может идти, далее просчет пути это уже детали, но вот собственно вопрос, а как быть с координатой Y?

Сейчас это двумерный массив, построенный таким образом, что бы зная координаты моба, можно было за одно действие обратиться к ячейке отвечающей за эти координаты. Это все работает для уровня Terrain. Моб движется обходит препятствия типа все ок...

Начал усложнять и полностью завис:

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

Правильный ли будет подход если использовать 3х мерный массив с такой же сеткой как и двумерный. (вот неделю изврящаюсь с 3х мерным, пока не получилось, вроде сделать можно, но тормозня капец)

Как правильно хранить навигационную карту, и как правильно к ней делать доступ?

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

То есть вопрос в хранении данных навигационной карты, как это вообще организовано?
Есть что-то почитать?

(Сам поиск пути меня не интересует, с этим вроде нет проблем пока, (вроде))
(можно конечно не ставить объекты так, что бы можно было и проходить под ними и ходить над ними, но все же...)


#1
12:31, 15 июня 2021

FourGen
> Правильный ли будет подход если использовать 3х мерный массив с такой же сеткой
> как и двумерный
  А потом 4-х мерный и 5-ти мерный массив понадобится по мере того как ты будешь наращивать свойства карты.

#2
15:17, 15 июня 2021

Наверное нужно слоями.

#3
15:41, 15 июня 2021

nerengd, да в этом то и вопрос.
gamedevfor, но непонятно как слои связать сделав понятно, что тут переход.

#4
17:04, 15 июня 2021

FourGen
> gamedevfor, но непонятно как слои связать сделав понятно, что тут переход.

слой переходов?

#5
(Правка: 23:04) 23:03, 15 июня 2021

>gamedevfor

слой переходов?

Для начала надо понять, что значит слой. В моем понимании это тот же двумерный массив, но с данными смещенными по высоте (координате Y), и в итоге получается тот же 3х мерный, так как без разницы как оно записано в одном 3х мерном или в 10 двумерных? а с трехмерным проще работать, то есть это получается что-то типа создаем меш всей карты, но не отображаем его на экране, а просто храним в памяти, или подгружаем по мере необходимости?

Под тем, что вы имеете в виду слой, я правильно понимаю? (Просто мне почему-то кажется, что вы имеете в виду что-то другое)


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

#6
(Правка: 23:35) 23:34, 15 июня 2021

FourGen
> Под тем, что вы имеете в виду слой, я правильно понимаю?

Неправильно.
Слой это набор/коллекция объектов, а не 2D массив.
Но в принципе 2D массив можно виртуализировать/эмулировать используя данные слоя.
Просто массивы это дикий оверхед, можно конечно сделать разреженный массив что частично может решить проблему но всё же лучше делать эмуляцию.

#7
(Правка: 23:49) 23:47, 15 июня 2021

>gamedevfor

Слой это набор/коллекция объектов

Коллекция объектов? Не очень понял.

Первый слой получается , когда я на Terrain проецирую объекты на карте, которые находятся над Terrain на заданной высоте, ну для примера не выше 0.5f над Terrain. Получается этакий двумерный массив, который можно подкорректировать увеличив треугольники, где нет объектов и уменьшив количество точек и возможных путей. Вот это я уже сделал, это работает. Такие препятствия обходятся +-, надо пооптимизировать, но это пока не суть.

Далее получается я проецирую все объекты на второй слой, которые не попали в первый и до следующего шага? типа от 0.5f до 1.0f?

Сорри в прошлом сообщении, я сам сказал сгенерировать меш... а почему называется NavMesh? не в виде ли меша данные хранятся? (Вероятно это пойдет, там можно треугольники порезать как угодно, в пустых зонах... до огромных, минимизировав количество точек меша... и работать с ним вроде не оч сложно будет, надо попробовать)

(я NavMesh не использую, просто так к слову)

#8
(Правка: 0:16) 0:00, 16 июня 2021

FourGen
Что то типа такого:

class Layer
{
private:
   quad_tree<Object*> collection; 

public:
   Object* get_object(long x, long y)
   {
      return collection.find(x, y);
   };
};

class Layers
{
private:
      //zorder; layer;
   hash_map<long, Layer*> layers; 

public:
  Object* operator[](const Index& index)
  { 
      return layers[index.get_z()]->get_object(index.get_x(), index.get_y());
  }
};
#9
(Правка: 0:49) 0:43, 16 июня 2021

Это мне к сожалению ни о чем не говорит. Я даже не понимаю, что тут происходит.

collection

Этого я еще не видел, понятия не имею, что это.
hash_map

Примерно представляю, что это но не использую, так как надо разбираться.
Данный код для меня сложен. Да и указатели со ссылками пока не понадобились.

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

И зачем все же позиция объекта, если у меня есть все точки, где нет объектов?

#10
1:00, 16 июня 2021

FourGen
> Я даже не понимаю, что тут происходит.

Тогда задача тебе явно не по зубам, учись сначала делать более простые игры.

#11
7:05, 16 июня 2021

FourGen
> я NavMesh не использую, просто так к слову
А почему?

#12
8:58, 16 июня 2021

Звучит так, как будто ты идёшь к тому, чтобы изобрести навмеш
FourGen
> А как правильно организовать хранение данных карты, если добавить координату Y.
> У моба есть высота, на карте далеко не все объекты стоят на земле, есть
> нависающие элементы, под которыми можно пройти, и так же может быть в этой
> точке площадка на которой можно стоять.
У навмеша это решается на этапе генерации сетки - ты указываешь радиус и высоту агента, максимальный уклон, по которому можно ходить. В результате генерится меш, по которому можно гарантировано таскать центр агента с заданными характеристиками. Этот меш не равномерный (внутри огромного треугольника всегда можно дойти из одной до другой точки по прямой, не зачем их дробить и как-то упорядочивать в пространстве). Хранится он в виде графа смежных треугольников и поиск происходит по этому графу. На этом этапе поиска тебе в целом пофиг, где какой треугольник находится в пространстве, достаточно хранить какие-нибудь эвристики расстояний для переходов между треугольниками. Поэтому никакие 2д/3д массивы тебе не нужны, максимум - какая-нибудь ускоряющая структура, чтобы быстрее находить ближайший треугольник к произвольной точке

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

#13
(Правка: 10:25) 10:23, 16 июня 2021

>gamedevfor

Тогда задача тебе явно не по зубам

Ну не совсем. Глобальных проблем с нахождением пути нет, у меня на Terrain все работает уже, проблема с удобным хранением этих данных при использовании простейшей логики и прилеплением 3ей координаты  )).

>meekobold

На этом этапе поиска тебе в целом пофиг, где какой треугольник находится в пространстве, достаточно хранить какие-нибудь эвристики расстояний для переходов между треугольниками.

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

эвристики расстояний для переходов между треугольниками

Сорри не знаю, что такое "эвристики расстояний" (почитаю) (как ранее писал, знаю математику в пределах 10 на пальцах) но у меня хранятся хранятся центральные точки треугольников.

Ааааа кажется понял, там объема-то никакого не надо???
Ведь получается пофиг куда эта плоскость наклонена, закручена и тд?
Да кажется понял, буду пробовать.

Хранится он в виде графа

Сейчас буду разбираться, что это значит, кажется это то что нужно.
Стандартный NavMesh

Я так понял, оно работает только с RigitBody, которого у меня так же нет. Кроме того, мне не нужно двигать персонажа автоматически, мне просто нужно получить список навигационных точек. Далее я сам разбираюсь с движением, а NavMesh, вроде как, этого не позволяет. Так же у него не достаточная для меня точность обхода препятствий.

Спасибо, надо поэксперементировать.

#14
11:26, 16 июня 2021

FourGen
> Я так понял, оно работает только с RigitBody, которого у меня так же нет. Кроме
> того, мне не нужно двигать персонажа автоматически, мне просто нужно получить
> список навигационных точек.
NavMesh можно использовать просто чтобы получать путь и делать с ним что хочешь:
https://docs.unity3d.com/ScriptReference/AI.NavMesh.CalculatePath.html

NavMeshAgent - это уже отдельная система, которая использует путь от NavMesh и "толкает" по нему свой объект. С учётом других таких агентов - это называется avoidance, немного отдельная штука от поиска пути

Страницы: 1 2 Следующая »
UnityФорумОбщее