Как устроен GOAP (или Goal-Oriented Action Planning)?
Все мы знаем деревья поведений или FSM. FSM дает возможность приходить к конкретной цели, основываясь на параметрах, приобретенных при выполнении конкретных состояний, но при этом вы можете находиться в конкретном одном состоянии в определенный момент времени.
В деревьях поведений же мы не ограничены одним состоянием в определенный момент, но сейчас не о них.
Есть еще Utility based AI, но о нем нужно рассказывать отдельно.

GOAP не имеет связей. Это важно. Совсем.
Простыми словами GOAP представляет собой массив простых событий, которые выполняются, если обеспечены их входные параметры, а на выходе дают необходимые эффекты. А имея такие вводные, можно без труда построить граф для достижения необходимого действия.

Как видно из названия, Goal-Oriented или ориентрир - это цель, мы ориентируемся на достижения цели. То есть мы говорим персонажу "будь сыт", а он сам добудет еду и поест. Ну или "построй дом", а он сам добудет необходимые материалы и построит дом.
Пожалуй, на этом примере можно и остановиться.
Допустим, у вас есть 3 простых действия:
1. Собирать камень
2. Рубить дерево
3. Строить дом

Строить дом - это действие, которое как результат выдает "дом построен", но на вход ему необходимо 2 камня и 4 дерева. Для того чтобы добыть 2 камня нужно иметь кирку, а чтобы добыть 4 дерева - нужен топор. Допустим, что топор и кирка у нас уже есть. Мы идем рубить дерево и добывать камень. И повторяем эти действия столько раз, пока не наберется необходимое количество.
Таким образом GOAP - это граф, который строится динамически, когда мы просим дать нам какой-то результат. Он всегда строится исходя из кратчайшего пути, т.е. если 4 дерева будет лежать на складе, то персонаж пойдет именно туда, т.к. рубить ничего не нужно.

А что вы используете в своих проектах?

#algorithms

Как работает HashSet?

Вы наверняка использовали эту структуру данных для хранения уникальных данных, но скорее всего вы слышали, что поиск в этой структуре занимает 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 будет возвращать нам всегда одно и то же число, например.

#datastructures #algorithms

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

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

Для добавления объектов в QuadTree необходимо сперва знать, какой ячейке они принадлежат. Каждый объект добавляется в самую мелкую ячейку, которая полностью охватывает его. Если ячейка становится слишком заполненной, то она разбивается на более мелкие. Проще говоря, нужно делать rect.Contains() несколько раз, чтобы понять куда отнести элемент.

Поиск объектов в QuadTree осуществляется путем перебора узлов дерева. Начиная с корня, мы проверяем, находится ли ячейка, в которой мы ищем объект, в пределах текущей ячейки узла. Если да, то мы переходим к следующему уровню дерева и продолжаем поиск в ячейках потомков. Если нет, то мы переходим к следующему соседнему узлу.

Преимущества QuadTree заключаются в том, что он позволяет быстро находить объекты в двумерном пространстве, а также быстро выполнять операции вставки и удаления объектов. Недостатком может быть то, что при неправильном выборе размера ячеек и глубины дерева, может возникнуть слишком большая структура, что негативно скажется на производительности.

На практике мы такое используем для поиска целей для атаки.

Существует еще и Octree для 3D, алгоритм работы по сути ничем не отличается.

#datastructures #algorithms

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

https://telegra.ph/Unity-Poisk-puti-05-28

#pathfinding #algorithms

Немного про оценку сложности алгоритмов.

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

int Method(int n) {
    var sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += i;
    }
    return sum;
}

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

for (int i = 0; i < 10; ++i) {
    sum += i;
}

то казалось бы, что сложность должна увеличиться на 10 (O(n + 10), но в О-нотации это будет константное время, а значит мы не будем учитывать это в сложности, т.е. сложность все еще останется O(n).

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

Вот для сравнения методы со сложностью O(n) и O(1).

Метод O(n):

int Method(int n) {
    var sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += i;
    }
    return sum;
}

Метод O(1):

int Method() {
    var sum = 0;
    for (int i = 0; i < 100_000; ++i) {
        sum += i;
    }
    return sum;
}

Как видно из примера, любой вызов первого метода с n < 100_000 будет отрабатывать быстрее, чем второй метод с константным временем выполнения. Так что когда вам говорят, что какая-то коллекция работает за константное время на добавление элементов, например, то это совсем не означает что она делает это максимально эффективно.

#algorithms #notations #basics

Диаграмма Вороного

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

#algorithms #voronoi

Radix Sort

Можно представить такую сортировку, которая отработает за O(n), если у нас на вход идут положительные числа, например, 0..100. Нам нужно всего лишь считать количество входных чисел:
++arr[number];
Где number - это наше число, а arr - хранилище для подсчета.
Таким образом на выходе мы получаем массив отсортированных чисел:

arr[0] = 1; // число 0 встречается 1 раз
arr[1] = 0; // число 1 встречается 0 раз
arr[2] = 5; // число 2 встречается 5 раз
...

Таким образом мы получаем результат такой сортировки:

022222...

Это сортировка подсчетом.

А теперь представим, что у нас числа 0..10000. Массив мы уже не заведем на 10к элементов, мы можем завести разряды, т.е. массив на 10 элементов:

arr = new int[10];

А принцип будет примерно таким же, как и выше, но теперь мы раскладываем числа по разрядам.
Допустим, у нас такие числа:

456 542 123 89 543

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

Ну и сам процесс сортировки:
1. Берем первый разряд и по нему раскладываем числа:

arr[2] = 542
arr[3] = 123 543
arr[6] = 456
arr[9] = 89

2. Теперь у получившихся чисел (542 123 543 456 89) мы берем следующий разряд:

arr[2] = 123
arr[4] = 542 543
arr[5] = 456
arr[8] = 89

3. И последний разряд (123 542 543 456 89) - у 89 мы дописываем 0:

arr[0] = 089
arr[1] = 123
arr[4] = 456
arr[5] = 542 543

Это довольно интересный алгоритм, сложность которого O(n), на практике, наверное, один из самых быстрых, если речь идет о сортировке положительных чисел.

Стоит заметить, что я рассмотрел только LSD (от младшего разряда к старшему) вариант сортировки, существует еще MSD (тоже наркота какая-то) или от старшего разряда к младшему.

#sorting #algorithms

Рандом

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

var rnd = new Random();
var value = rnd.NextValue();

То есть есть некий класс рандома, который что-то делает и на выходе выдает "случайное" число. Как это работает?

На самом деле все довольно прозаично. Для того, чтобы выдать "случайное число", нужно знать некое другое число (или seed). Обычно дефолтное значение этого самого seed берется из тиков, времени, да чего угодно положительного.
Т.е. мы фактически в каждый момент времени уже имеем случайное число - это время.

А теперь каким образом работает этот самый rnd.NextValue()?
Random внутри себя хранит seed + в зависимости от реализации рандома может хранить другие параметры. Мне нравится больше всего самая простая реализация только с seed:

struct Random {
  uint seed;
  uint NextValue() {
     var next = this.seed;
     this.seed += 123;
     return next;
  }
}

Т.е. сейчас мы при каждом обращении к NextValue к seed прибавляем некое число, изменяя этот самый seed таким образом, чтобы при следующем обращении нам выдали уже другое число.
На этом месте можно рассмотреть вариант Unity.Mathematics:
uint next = seed;
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
return next;

По сути мы сдвигаем значение seed, получая "рандомное" число. Отсюда, кстати, и ограничение, что seed не может быть 0, т.к. чего бы мы там не двигали 0 всегда останется нулем.

Это я все к тому, что такой рандом можно передавать по сети и "откатывать", т.к. оно всегда будет выдавать некую последовательность чисел, основанную на этом самом seed. Т.е. взяв на одном клиенте 5 чисел, начиная с seed = 5:
5, 15, 60, 70, 1
то на другом клиенте мы точно так же получим эти же числа в этой же последовательности. Т.е. чтобы "откатиться" на какое-то состояние рандома назад, нужно всего лишь знать его seed в тот момент времени.

Ремарка: Алгоритмов рандома множество, некоторые легко предугадать, другие - сложнее, но качество функций рандома сводится к тому, чтобы выдавать равномерное распределение чисел, и чем больше оно равномерно, тем лучше считается функция рандома.

#random #code #algorithms

Бинарный поиск

Допустим, что у нас есть отсортированный массив чисел:
1 2 6 8 56 234 745 998 1010

Как нам определить, что в этом массиве есть какое-то число?
Самый простой вариант - пройти линейно от первого элемента до последнего. Таким образом мы получаем O(n) (Если кто не видел пост https://t.iss.one/unsafecsharp/97).

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

На самом деле существует небольшой лайфхак: если вы видите что-нибудь отсортированное (массив это или матрица - не важно) и задача - поиск, то сложность всегда будет log(n). В теории можно придумать алгоритм, который будет еще умнее, но сложность от этого не изменится.

Итак, для начала нам нужно взять центральный индекс, то есть length / 2. После чего у нас массив разделится на два подмассива, при этом слева элементы будут всегда меньше искомого, а справа - больше.
Т.е. если центральный элемент не тот, который мы ищем, то мы сразу отсеиваем половину элементов массива и берем индекс снова центральный от подмассива.
Ищем 2:
[1 2 6 8 56 234 745 998 1010]
[1 2 6 8 56]
[1 2 6]

Т.е. мы за 3 итерации нашли число. Вот это отбрасывание половины и есть log(n).

#search #binary #code #algorithms

Рекурсивный метод можно представить в виде цикла.

Допустим, у нас есть простой метод для перебора чего-либо:


class Node {
public int value;
public Node[] children;
}

Node FindRecursively(Node root, int value) {
if (root.value == value) return root;
for (int i = 0; i < root.children.Length; ++i) {
var node = FindRecursively(root.children[i], value);
if (node != null) return node;
}
return null;
}


Мы видим, что если на вход передать ноду графа и значение, то мы в итоге найдем нужную ноду, либо вернем null.

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

Что же делать?
Давайте избавимся от рекурсивного вызова метода. Самый простой вариант это сделать - использовать Stack или Queue:


Node Find(Node root, int value) {
var queue = new Queue<Node>();
queue.Enqueue(root);
while (queue.Count > 0) {
var node = queue.Dequeue();
if (node.value == value) return node;
for (int i = 0; i < node.children.Length; ++i) {
queue.Enqueue(node.children[i]);
}
}
return null;
}


Из минусов - придется объявить коллекцию, куда мы будем складывать элементы. из плюсов - можно обойти граф любой глубины.

#recursion #code #algorithms

Floodfill

Алгоритм заливки. На самом деле ничего нового в нем нет, мы выбираем элемент массива, читаем из него данные и рекурсивно (https://t.iss.one/unsafecsharp/115) обращаемся к элементу сверху, снизу, справа и слева. Таким образом мы обойдем все элементы, но нам нужно обойти лишь те, которые имеют те же данные, что и наш начальный элемент.

Пример:
77777
77555
75557
75577
77775

Если мы возьмем центральную 5, то результат заливки числом 6 будет таким:

77777
77666
76667
76677
77775

Алгоритм используется в различных областях. Например, в графах поиска пути (https://t.iss.one/unsafecsharp/69) заливка используется для формирования «закрытых областей», чтобы можно было рано выйти при построении пути, если дойти до точки невозможно (области начальной точки не совпадают с конечной).

#floodfill #algorithms

Немного про сжатие данных.

https://telegra.ph/Kak-rabotaet-szhatie-06-21

#compress #algorithms

Быстрый указатель в алгоритмах.

Допустим, что вам нужно найти середину связного списка, как это быстрее всего сделать? Завести 2 указателя, один будет шагать через один элемент, а второй - по каждому элементу. Таким образом когда первый указатель доберется до конца такого списка - второй будет указывать на середину. Так вот первый указатель называют "быстрым".

Недавно встретил такую задачку и хотел бы с вами поделиться:
На вход нашему методу передается некий граф, который содержит ноды вида

Node {
  int value;
  Node next;
}

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

1 -> 2 -> 3 -> 4 -> 2

Тут нода со значением 2 начинает цикл.
Если же ноды нет, то метод должен вернуть null.
Решение этой задачи довольно простое, если бы не одно условие: нужно найти решение без использования дополнительной памяти.
Насколько я помню, я встретил ее по теме "какие задачи не нужно задавать на собесах", т.к. если решения ты не знаешь - решить ее практически невозможно, но все равно - подумайте, ну а вдруг 🙂
p.s: задача была задана на собесе в компанию Apple.

#algorithms #interview

Как перемещать персонажа по точкам правильно

Многие из вас делали перемещение персонажа по нодам. Например, когда поиск пути вернул массив точек, а нам нужно персонажем пройти по ним.
Обычно такой код выглядит примерно так:

var nextPoint = points[index];
if ((nextPoint - position).sqrMagnitude <= MIN_DISTANCE_SQR) {
  ++index;
  if (index >= points.Length) {
    // Мы дошли до конца пути
    return;
  }
}

position = Vector3.MoveTowards(position, nextPoint, dt * speed);

Логика понятная: дошли до точки - берем следующую и идем к ней, и так пока не дойдем до конца.

Но в таком подходе кроется одна проблема: если персонаж проходит за кадр 1 метр, а расстояние до точки 0.5 метра, то персонаж будет проходить на самом деле меньшее расстояние, чем должен был:

-[]--[]--[]--[]--[]
---------------[]  // Этот персонаж дойдет до конца быстрее, чем первый

Что делать?

На самом деле нужно использовать примерно такую логику:

var distance = speed * dt;
while (distance > 0f) {
    var nextNodePos = points[index];
    var distanceToNextNode = (nextNodePos - currentPos).magnitude;
    if (distance >= distanceToNextNode) {
        distance -= distanceToNextNode;
        currentPos = nextNodePos;
        ++index;
        if (index >= points.Length) break;
        continue;
    }
    var direction = (nextNodePos - currentPos).normalized;
    currentPos = direction * distance;
    break;
}

Метод HasReached должен проверять "перешли ли мы точку или еще нет". Таким образом, мы "перебрасываем" часть длины, которую мы прошли на новую точку, а если перешли и ее, то еще раз и так пока либо не закончится этот хвост, либо мы не дойдем до конца.
Грубо говоря, если персонаж будет двигаться со скоростью 1000 метров в секунду, а контрольных точек на пути будет много (например, каждый метр), то за секунду он пройдет ровно 1000 метров, а в первом варианте намного меньше.

#unity #algorithms #movement

Довольно интересная задачка попалась на собеседовании в гугле:
Есть матрица (массив массивов) вида
[
[1, 0, 0, 0, 0, 1],
[0, 1, 0, 1, 1, 1],
[0, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 1, 0],
[1, 0, 1, 1, 0, 0],
[1, 0, 0, 0, 0, 1]
]

Нужно реализовать метод, который найдет все острова. Островом считаются 1, которые не примыкают к границам. Диагонали не считаются за соединения.
То есть на выходе должна быть матрица такого вида:
[
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0]
]

Как вы бы решали такую задачу?
Доп вопросы:
- Возможно ли решить задачу без аллоцирования памяти? (Стэк константного размера не считается)
- Какая минимально возможная сложность по времени (О-нотация)?

#interview #task #algorithms