Рандом

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

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

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

У вас есть односвязный список и указатель на один из его элементов (не последний), как удалить этот элемент из списка, оставив список целостным? Возможно ли решение за О(1)?

#interview

Как мы строим пути для юнитов в Mushroom Wars 2.

https://telegra.ph/Kak-my-stroim-puti-dlya-yunitov-06-23

#mushroomwars #pathfinding

Напоминаю, что сегодня встреча, на которой поговорим про джобы. Кто еще не зарегался - велкам)
https://news.1rj.ru/str/unsafecsharp/119

#event

Довольно долго эта картинка висела у нас в офисе на стене. И да, в целом так оно и было;)

#meme

У Vector2/Vector3/Vector4 переопределен оператор ==.
Он сравнивает не точное значение, а приблизительное, с учетом погрешности:

var v = new Vector3(0f, 0f, 0f);
var v2 = Vector3.one - Vector3.one;

v == v2

#basics #floats

Запись с последнего урока по Unity Jobs:

https://www.youtube.com/watch?v=Abp_9x8pX-E

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

#event #record