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

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

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

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

https://www.tgoop.com/unsafecsharp/92

#event

https://unsafecsharp.timepad.ru/event/2464311/

В следующую субботу проведу лекцию на тему мультиплеера в играх. Обсудим какой вариант лучше выбрать, какие варианты синхронизации существуют.
Регайтесь 🙂

#event

Кто такой Лисков?

Обычно такой вопрос был у нас на собесах N лет назад. И правильный ответ на него должен быть один: он - Барбара.

#interview

Тесты.

Хотел тут написать пост про юнит-тесты, а потом понял, что есть 3 типа разрабов:
1. Те, кто уже пишет юнит-тесты, понимают зачем, и имеют профит с этого;
2. Те, кто ни разу не писал тестов, и не понимают зачем они;
3. Те, кто понимает зачем тесты, но «у нас проект вчера надо сдать, а еще багов миллион фиксить надо, а если мы бы тесты писали, то вообще ничего бы не сделали».

Вот пост скорее для последних. Ребят, если бы вы потратили время на тесты - не было бы у вас столько багов :)

#unittest

Как работает FixedUpdate.

Unity предоставляет нам 3 варианта update: Update, LateUpdate и FixedUpdate.
Update - этот метод вызывается настолько часто, насколько это возможно, проще говоря while (true) { Update(); }. Если включен vsync или установлен target fps, то будет задержка между вызовами, чтобы удовлетворить условиям. По сути можно считать. что Update - это логика кадра.
LateUpdate - вторая итерация Update, вызывается столько же раз, сколько и Update, но всегда после.
А вот FixedUpdate имеет совершенно иную логику вызова. Он может вызываться 10 раз за кадр, а может не вызваться ни разу. FixedUpdate гарантирует, что вызовется фиксированное количество раз за секунду, а вот сколько именно вызовов будет - зависит от вашего fps. Поэтому, например, Unity предлагают использовать FixedUpdate для расчета физики, а, например, для перемещения камеры или получения инпута его лучше не использовать. Но получается, что если с прошлого вызова прошло 10 секунд, а шаг у нас, например, 33мс, то вызовется FixedUpdate в текущем кадре аж 300 раз.
А теперь самое интересное, что логика одного вызова может быть больше, чем 33мс. Если такое произойдет, то будет бесконечный вызов FixedUpdate. И вот чтобы приложение продолжало работать - есть ограничение в max allowed timestep, которое и решает этот сценарий.

#unityloop

Довольно часто мне нужно упаковать 2 инта в лонг, или из лога получить 2 инта, ну или в шортов сделать инт и т.д.
Это применяется в основном в каких-нибудь Dictionary (или подобных кейсах) в виде ключей, чтобы не городить структуру, да и работать оно будет быстрее.

void ToInts(long a, out int a1, out int a2) {
    a1 = (int)(a & uint.MaxValue);
    a2 = (int)(a >> 32);
}

long ToLong(int a1, int a2) {
    long b = a2;
    b = b << 32;
    b = b | (uint)a1;
    return b;
}

#bits #pack #basics

FMOD

В Unity довольно неплохо сделана настройка звука, тут есть и микшеры, и 3д-звук, и различные фейды.
Но для средних и больших проектов я бы рекомендовал использовать https://fmod.com. Расскажу почему:
1. Человек, который занимается звуком у вас в проекте - никак не будет связан с юнити, при этом настраивать звуки он сможет уже в готовом билде;
2. В самом проекте юнити пропадают файлы со звуками и музыкой, а сама связь происходит по событиям. Т.е. физически вам не нужен файл звука, чтобы сказать игре "я вот в этом месте хочу проиграть такой-то звук";
3. Все фейды, точки перехода между дорожками (например, для смены настроения в игре) будут не кашей, а конкретными точками перехода, которые приятно будет слушать;
4. Автоматические бандлы и плагин для юнити. У fmod.com есть unity-плагин, который предоставляет возможность нормально расставить события, контролировать это все из кода при необходимости. А при сборке оно сделает отдельные бандлы под нужные платформы.

Посмотрите, если еще не используете.

#sounddesign #sound #fmod #unityloop

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

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

#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

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

text = health.ToString();

А ведь есть еще и всякие

text = $"{value}/{maxValue}";

На самом деле есть довольно простой способ избежать аллокаций в данном кейсе, когда мы знаем конечное значение для вывода:
если health = 0..100, то можно завести массив и брать значение оттуда:

text = arr[health];

или

text = arr[maxValue][value];

Да, мы сделаем некое подобие https://www.tgoop.com/unsafecsharp/11, но мы не используем объединение строк, т.к. у нас они уже созданы.

#lifehack #strings #gc

Любой n-мерный массив можно представить в виде одномерного:

arr[x, y] = arr[x * width + y]

И да, это будет быстрее, чем двумерный массив.

#arrays #basics

Destroy и DestroyImmediate

Destroy - это маркер, который говорит, что мы хотели бы удалить объект, но это не произойдет моментально. Юнити отложит удаление до конца кадра и он будет удален позже.

Object.Destroy(gameObject);
if (gameObject != null) {
// gameObject is alive
}


DestroyImmediate - это фактическое удаление, т.е. когда нужно удалить объект прямо здесь и сейчас.

Object.DestroyImmediate(gameObject);
gameObject // тут он уже помер


Дело в том, что DestroyImmediate ломает юнити флоу, т.к. с точки зрения всех юнити-колбэков они выполнятся моментально, а не в нужном порядке, например, при использовании DefaultExecutionOrder.
При этом DestroyImmediate имеет дополнительный флаг, который позволяет убить ассет из проекта, про что стоит не забывать :)

И ремарка: Object.Destroy/Object.DestroyImmediate могут убить то, что вы туда передаете, т.е. передали компонент - убивается компонент, передали go - убивается go, текстуру - текстура и т.д. Иногда встречаю код вида Object.Destroy(component), при этом явно хотели убивать не компонент, а go.

#basics #destroy

Рандом

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

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://www.tgoop.com/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

Напоминаю, что сегодня мы обсуждаем мультиплеер;)

https://www.tgoop.com/unsafecsharp/99

#event

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

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


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

Когда мы начинали делать проект, в юнити не было возможности отключить Garbage Collector. А нам было нужно)
У нас геймплей был динамичный и любые "провисания" из-за gc плохо влияли на ощущения от игры. Поэтому мы решили его отключить. Раньше для этого нужно было делать хаки, а сейчас уже есть возможность это сделать нормально: https://docs.unity3d.com/Manual/performance-disabling-garbage-collection.html

В нашем кейсе в геймплее мы очень бережно относились (да и относимся) к аллокациям, всё на пулах, поэтому перед началом боя мы выключаем GC, а после боя - включаем и собираем мусор.
Такое решение на самом деле в последствии нам помогло на различных платформах в свое время: на ps4 и switch GC.Collect мог занимать до пары секунд. Надеюсь, что сейчас уже нет таких проблем, но 10 лет назад - были 🙂

#unity #gc