Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / [Решено]Navigation mesh (5 стр)

[Решено]Navigation mesh (5 стр)

Поделиться
Advanced: Тема повышенной сложности или важная.

Страницы: 1 2 3 4 5

AntonioModerПостоялецwww11 авг. 201617:51#60
А че вы тут делаете ? :D

Правка: 11 авг. 2016 18:11

SaiteiПостоялецwww16 окт. 201723:26#61
MrShoor
> Dictionary<edge, List<int> >; //ключ - ребро треугольника, значение - список
> индексов треугольников в вышеописанном списке, и имеющих данное ребро
>
Простите за некропостинг, но как определить что ребра А и Б - одинаковые?

Ребро - это две вершины a и b, если поменять b и a местами, то смысл не изменится. То есть в операторе сравнения нужно делать что-то вроде такого?:

bool Edge::operator ==(const Edge& e)
{
  bool x1 = ((a ==  e.a) && (b == e.b));
  bool x2 = ((a == e.b) && (b == e.a));
  return x1 || x2;
}

MrShoorУчастникwww16 окт. 201723:47#62
Saitei
> То есть в операторе сравнения нужно делать что-то вроде такого?
Можно типа такого, только с вычислением хеша нужно быть осторожным, и делать в хеше только коммутативные операции по вершинам.
А еще можно просто посортировать вершины в ребре сначала по x, и если x совпадает - то сортиравать по y, и если уж и y совпадает, то сортировать по z.
SaiteiПостоялецwww17 окт. 20170:11#63
MrShoor
> только с вычислением хеша нужно быть осторожным, и делать в хеше только
> коммутативные операции по вершинам.
Простите, честно говоря не понял вас. Вот как бы вы поступили? У меня есть вектор треугольников, необходимо составить граф
MrShoorУчастникwww17 окт. 20170:17#64
Saitei
Если граф не ориентированный, то завел бы структуру edge, в конструкторе которой сортировал бы вершины, и сложил бы это все в Dictionary<edge, List<int> >;
Все, граф готов.
Говори конкретно что именно тебе не понятно.

Правка: 17 окт. 2017 0:17

SaiteiПостоялецwww17 окт. 20173:38#65
MrShoor
Мне не совсем понятно что вы сортировкой делаете и насколько это эффективно. Ну и хотелось бы узнать что именно вы имели ввиду под "аккуратнее с хешами"
SaiteiПостоялецwww17 окт. 20174:43#66
MrShoor
а ещё у меня есть другой вопрос, больше теоретический.

Я как понимаю поиск пути происходит в два этапа:
1. А* по графу, где каждый узел - треугольник
2. Путь из треугольников превращается в список порталов, потом путь строится на основе точек (я буду использовать Simple Stupid Funnel Algorithm)

В игре будут юниты разных размеров и форм. Как правильно отмечать треугольники как "занятые"? И самое главное - когда это делать? Юнит теоретически может занять несколько треугольников сразу. Пока ничего путевого не придумал, искать треугольники в BVH и потом проецировать AABB объекта мне кажется плохой идеей

MrShoorУчастникwww17 окт. 20174:45#67
> Мне не совсем понятно что вы сортировкой делаете и насколько это эффективно.
В конструкторе меняю вершины местами, для двух векторов Vec3 это примерно так:
public struct Edge
{
    public Vec3 p1, p2;

    public Edge(Vec3 pt1, Vec3 pt2)
    {
        if (pt1.x < pt2.x) {
            p1 = pt1;
            p2 = pt2;
        } else if (pt1.x > pt2.x){
            p1 = pt2;
            p2 = pt1;
        } else if (pt1.y < pt2.y) {
            p1 = pt1;
            p2 = pt2;
        } else if (pt1.y > pt2.y){
            p1 = pt2;
            p2 = pt1;
        } else if (pt1.z < pt2.z) {
            p1 = pt1;
            p2 = pt2;
        } else {
            p1 = pt2;
            p2 = pt1;
        }
    }
}
теперь инвариант сохраняется вне зависимости от того, в каком порядке вершины попадут в конструктор. Это эффективно, потому что 99% вершин отсеятся после первых двух if-ов.

> Ну и хотелось бы узнать что именно вы имели ввиду под "аккуратнее с хешами"
Все Edge, которые равны друг другу - должны выдавать одинаковый HashCode. Иначе любой код, работающий с хешами будет работать не правильно (например тот же самый Dictionary). Поскольку ты перегрузил Equal, то нужно быть уверенным, что если A == B, то и A.GetHashCode() == B.GetHashCode().
Вот на примере вектора:

struct X {
    public double a;
    public double b;
}
Если ты в коде напишешь:
X x;
x.a = 1;
x.b = 5;
X y;
y.a = 5;
y.b = 1;
WriteLn(x.GetHashCode() == y.GetHashCode());
То дожно быть всегда True. Я не знаю какой механизм используется в C# по умолчанию, но хеш код должен быть коммутативен по полям так же, как операция Equal. Можно перегрузить GetHashCode и внутри сделать:
GetHashCode() {
    return (a.GetHashCode()^b.GetHashCode());
}
Вот операция ^ - коммутативна, а значит a.GetHashCode()^b.GetHashCode() == b.GetHashCode()^a.GetHashCode(), а значит, что x.GetHashCode() == y.GetHashCode() всегда вернет true

Но можно конечно не парится с Equal и GetHashCode а тупо посортировать вершины.

Правка: 17 окт. 2017 4:49

MrShoorУчастникwww17 окт. 20174:50#68
Saitei
> Я как понимаю поиск пути происходит в два этапа:
> 1. А* по графу, где каждый узел - треугольник
> 2. Путь из треугольников превращается в список порталов, потом путь строится на
> основе точек (я буду использовать Simple Stupid Funnel Algorithm)
Нет, поиск пути происходит в один этап. Это либо A*, либо Simple Stupid Funnel Algorithm
MrShoorУчастникwww17 окт. 20174:53#69
Saitei
> В игре будут юниты разных размеров и форм. Как правильно отмечать треугольники
> как "занятые"? И самое главное - когда это делать? Юнит теоретически может
> занять несколько треугольников сразу.
Проблемы уходят в сторону абстрактных. А что если другой юнит перекроет проход, и там уже ходить нельзя? А что если... бла бла бла. Предлагаю тебе сначала сделать что-то, а там посмотреть на реальные проблемы, и придумывать к ним реальные решения. Серебряной пули не бывает.
SaiteiПостоялецwww17 окт. 20174:57#70
MrShoor
> Нет, поиск пути происходит в один этап. Это либо A*, либо Simple Stupid Funnel
> Algorithm
Тогда я, честно говоря, полностью запутался. Все статьи, которые я читал, рассматривают порталы от стартовой точки до конечной, там даже нет критериев "отброса ненужных узлов"
http://ahamnett.blogspot.ru/2012/10/funnel-algorithm.html
http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html
https://habrahabr.ru/post/278151/

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

Правка: 17 окт. 2017 5:04

SaiteiПостоялецwww17 окт. 20175:01#71
Saitei
> ты
Уф, неловко получилось. Вы же не против, если я перейду на "ты"?
SaiteiПостоялецwww17 окт. 20175:17#72
http://jceipek.com/Olin-Coding-Tutorials/pathing.html#navigation-meshes
Mapping Paths to Space
Now what? We have some optimal path in an abstract graph. How does that help our characters move? The answer to that question depends a lot on the specifics of the game you're making. In some games, you can probably get away with mapping the graph directly to physical space. In most cases, though, you need to smooth the resulting path somehow. In Left 4 Dead, characters move between portal midpoints and smooth their path by moving towards a visible node that is part of the optimal A* path but is several steps ahead.

We can do better, though. If we are using a grid or navigation mesh, we can implement a smoothing technique known as the Simple Stupid Funnel Algorithm, a practical path smoothing technique developed by the lead AI programmer from the original Crysis, based on a PHD thesis on pathfinding.

The algorithm proceeds as follows:

1. Create a list of the portals along the A* path. Make sure that the points of each portal are stored the same way relative to the character. You will need to know if a point is to the left or right of the character.
2. Create a "funnel" with three points: the characters starting location (the apex), the right side of the portal, and the left side of the portal.
3. Alternate updating the left and right sides of the "funnel," making it narrower each time
4. When the sides of the funnel cross, make the point you didn't update the apex of the new funnel, and store it as part of the smoothed path.

Правка: 17 окт. 2017 5:19

MrShoorУчастникwww17 окт. 20178:20#73
Saitei
> Вы же не против, если я перейду на "ты"?
Не против. Я же с тобой на ты.

> smoothing technique known as the Simple Stupid Funnel Algorithm
А, ну походу они его используют для сглаживания. Я просто со Simple Stupid Funnel Algorithm никогда не работал. Загуглил, это вроде поиск пути с помощью порталов. Но видимо его можно еще и для сглаживания пути использовать. Я путь сглаживал собственным наколенным методом.

Страницы: 1 2 3 4 5

/ Форум / Программирование игр / Игровая логика и ИИ

2001—2017 © GameDev.ru — Разработка игр