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

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

#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://news.1rj.ru/str/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://news.1rj.ru/str/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://news.1rj.ru/str/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

Пишите non-alloc методы.

Мы часто пишем подобные методы:

List<int> GetItems() {
  var items = new List<int>();
  ...
  return items;
}

В этом методе мы просто собираем элементы и возвращаем.
При этом создаем список, создание которого мы не можем запретить извне. Для этого лучше писать таким образом:

void GetItems(List<int> items) {
  ...
}

Таким образом контроль над списком может быть таким:

var list = GetFromPool();
GetItems(list);
...
ReturnToPool(list);

#gc #code #allocations

Ссылка на запись последнего евента про мультиплеер:
https://youtu.be/nImCndj3F6U

Все, кто хотят меня поддержать, могут это сделать тут:
Евро: NL19 BUNQ 2070 8912 32
Доллары: GB45 TCCL 0414 0434 4305 90

#event #record

В субботу будет тема про джобы, будем разбираться как работают, что там внутри и всякое такое :) Приходите, будет интересно!

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

#event

Floodfill

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

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

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

77777
77666
76667
76677
77775

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

#floodfill #algorithms

Разбирая свой гитхаб, вспомнил что когда-то писал такую штуку:
https://github.com/chromealex/TapticEngine

#github

Ленивый if

Условие всегда ленивое и хочет побыстрее выйти.
Если v1 будет true, то что там дальше его не будет интересовать:

if (v1 == true || v2 == true) {...}

Таким образом, если у нас есть такой код:

var v1 = CalcV1();
var v2 = CalcV2();
if (v1 == true || v2 == true) {...}

Выглядит хоть и симпатично, но совершенно непроизводительно.
Лучше писать так:

if (CalcV1() == true || CalcV2() == true) {...}

Естественнно нужно понимать, что CalcV2 вызываться не будет, если CalcV1 вернет true, поэтому не нужно на это расчитывать. Но я надеюсь, что вы это знаете :)

#code #performance #basics

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

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

#compress #algorithms

💾 Хоткей дня
Ctrl/Cmd + Shift + P
Нажать на кнопку паузы. Довольно часто мышку использовать не получается (например, если нужно отловить состояние до потери фокуса).

#hotkey #editor

Catmull rom - это такая кривая, для построения которой нужно знать 4 точки. Особенность заключается в том, что кривая будет проходить через все 4 точки.

На практике мы такое часто используем, т.к. для построения, например, Безье требуются тангенты, расчет которых иногда затруднителен.

#splines #curve #math #catmullrom