OBB - это Oriented Bounding Box, это такой Rect с поворотом, но в 3D 🙂
Попробуйте ответить на этот вопрос до того, как посмотрите мое решение. Напишите в комменты свой вариант решения (просто описание алгоритма) хотя бы для 2D. Интересно было бы сравнить.
Мой вариант решения тут:
https://telegra.ph/Kak-poschitat-peresechenie-OBB-i-OBB-05-30
Написал немного про поиск пути, буду выкладывать ссылки на статьи в телеграф, если нужны картинки или хочу описать что-нибудь более подробно.
QuadTree - это структура данных, которая используется для разбиения двумерного пространства на более мелкие области. Каждый узел дерева представляет собой квадратную область (ячейку) внутри основной области. Если ячейка слишком большая, то она разбивается на четыре одинаковых подъячейки, каждая из которых может быть либо пустой, либо содержать объекты.
В QuadTree каждая нода может иметь до четырех потомков, которые представляют собой разделенную ячейку.
Для добавления объектов в QuadTree необходимо сперва знать, какой ячейке они принадлежат. Каждый объект добавляется в самую мелкую ячейку, которая полностью охватывает его. Если ячейка становится слишком заполненной, то она разбивается на более мелкие. Проще говоря, нужно делать rect.Contains() несколько раз, чтобы понять куда отнести элемент.
Поиск объектов в QuadTree осуществляется путем перебора узлов дерева. Начиная с корня, мы проверяем, находится ли ячейка, в которой мы ищем объект, в пределах текущей ячейки узла. Если да, то мы переходим к следующему уровню дерева и продолжаем поиск в ячейках потомков. Если нет, то мы переходим к следующему соседнему узлу.
Преимущества QuadTree заключаются в том, что он позволяет быстро находить объекты в двумерном пространстве, а также быстро выполнять операции вставки и удаления объектов. Недостатком может быть то, что при неправильном выборе размера ячеек и глубины дерева, может возникнуть слишком большая структура, что негативно скажется на производительности.
На практике мы такое используем для поиска целей для атаки. Существует еще и Octree для 3D, алгоритм работы по сути ничем не отличается.
Вы наверняка использовали эту структуру данных для хранения уникальных данных, но скорее всего вы слышали, что поиск в этой структуре занимает O(1), поэтому вы ее и используете.
Давайте разебермся откуда берется этот загадочный O(1) и каким образом он вообще получается.
Реализаций HashSet может быть много, но смысл остается примерно таким: У вас есть значение, которое вы хотите положить в коллекцию, допустим оно равно 12. Чтобы получить поиск элемента за O(1), самое простое - это завести массив bool, где индекс будет равен этому числу, а значение true или false.
Таким образом мы получаем супер-быстрое добавление элементов и супер-быструю проверку на существование.
Но что если значение будет 1_000_000 или вообще отрицательным?
Получается, что использовать массив таким образом мы уже не можем. Для этого давайте вызовем метод GetHashCode(), который нам вернет hash от элемента (т.к. далеко не факт, что мы будет добавлять в коллекцию только числа, там же могут быть и структуры и классы).
Таким образом получим некое число в любом случае. Но снова число может быть любым.
Для того, чтобы решить эту задачу, давайте заведем массив "вёдер" или проще говоря "массив списков" (это для простоты понимания). Мы будем хранить элемент в одном из этих ведер (или buckets). Количество ведер изначально зададим, например, 10. Таким образом, чтобы засунуть число 12 в одно из этих бакетов, нам нужно найти остаток от деления 12 % 10 = 2. Вот и наше ведёрко найдено.
А дальше мы выполняем операцию buckets[index].Add(value), т.е. добавляем наш элемент в список. Получается, что добавление элемента будет действительно O(1).
Но что же с поиском элемента? Нетрудно догадаться, что если мы таким образом добавили элемент в ведро, то и найти его нужно таким же образом. Ищем остаток от деления, находим ведро, а потом ...ой. А потом нам нужно перебрать все элементы в ведре, чтобы найти нужный 🙂
И получается, что никаким O(1) тут и не пахнет. Но мы же знаем, мы же слышали. Мозг скорее всего уловил O(1), но не уловил слова типа "среднее" или "условное", что подразумевает, что в лучшем случае O(1), а в худшем O(n), что понятно, если мы будем добавлять разные истансы одного объекта в HashSet, но при этом метод GetHashCode будет возвращать нам всегда одно и то же число, например.
Как устроен GOAP (или Goal-Oriented Action Planning)?
Все мы знаем деревья поведений или FSM. FSM дает возможность приходить к конкретной цели, основываясь на параметрах, приобретенных при выполнении конкретных состояний, но при этом вы можете находиться в конкретном одном состоянии в определенный момент времени.
В деревьях поведений же мы не ограничены одним состоянием в определенный момент, но сейчас не о них. Есть еще Utility based AI, но о нем нужно рассказывать отдельно.
GOAP не имеет связей. Это важно. Совсем. Простыми словами GOAP представляет собой массив простых событий, которые выполняются, если обеспечены их входные параметры, а на выходе дают необходимые эффекты.
А имея такие вводные, можно без труда построить граф для достижения необходимого действия. Как видно из названия, Goal-Oriented или ориентрир - это цель, мы ориентируемся на достижения цели. То есть мы говорим персонажу "будь сыт", а он сам добудет еду и поест. Ну или "построй дом", а он сам добудет необходимые материалы и построит дом. Пожалуй, на этом примере можно и остановиться.
Допустим, у вас есть 3 простых действия:
1. Собирать камень
2. Рубить дерево
3. Строить дом
Строить дом - это действие, которое как результат выдает "дом построен", но на вход ему необходимо 2 камня и 4 дерева. Для того чтобы добыть 2 камня нужно иметь кирку, а чтобы добыть 4 дерева - нужен топор. Допустим, что топор и кирка у нас уже есть. Мы идем рубить дерево и добывать камень. И повторяем эти действия столько раз, пока не наберется необходимое количество.
Таким образом GOAP - это граф, который строится динамически, когда мы просим дать нам какой-то результат. Он всегда строится исходя из кратчайшего пути, т.е. если 4 дерева будет лежать на складе, то персонаж пойдет именно туда, т.к. рубить ничего не нужно.