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

 текст = здоровье.ToString();

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

 текст = $"{value}/{maxValue}";

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

если здоровье = 0..100, то можно занести массив и взять стоимость:

 текст = arr[здоровье];

или

 текст = arr[maxValue][значение];

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

Читать далее  

Можно представить такую сортировку, которая отработает за 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 (тоже наркота какая-то) или от старшего разряда к младшему.


Читать далее  

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

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

Еще есть алгоритм Форчуна, результат которого идентичен, но принцип работы немного иной.

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

Читать далее  

Довольно часто мне нужно упаковать 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; 
} 
Читать далее  

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, которое и решает этот сценарий.

Читать далее  

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

Читать далее  

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

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

Читать далее  

Чтобы понять как они работают, нужно понять как работает Enumerator. Если коротко, то это некий объект, у которого есть метод MoveNext(), если его вызвать, то произойдет переключение на следующий шаг:

// step
yield return null;
// step 2

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

IEnumerator MyMethod() {
    // step 1
    yield return null;
    // step 2 
}

list.Add(MyMethod()); 

А теперь в update мы просто переключаем шаги:

for (int i = 0; i < list.Count; ++i) {
     if (item.MoveNext() == false) {
         item.Current // тут мы можем проверить возвращаемое значение, например, если там внутренняя корутина, то ее тоже хорошо бы выполнить 🙂
         list.RemoveAt(i);
         --i;
     }
}  

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

Корутины в юнити работают примерно таким образом. Еще я бы добавил, что при вызове StartCoroutine сразу выполняется первый шаг, т.е. вызывается MoveNext(), если он возрващает true, то значит дальше что-то есть и нужно добавлять корутину в список выполнения.

Т.е. нужно понять главное: корутины - это не какая-то особенная штуковина, которая работает только в юнити, это стандартный синтаксис и коллекции C#.

Читать далее  

На самом деле вариантов всего три:

1. Вы делаете дополнительную ортографическую камеру, которая снимает сверху весь ваш мир (или нужный кусок), которая может исключать определенные слои или, напротив, включать определенные слои, которые не видит основная камера.

2. Вы для каждого объекта считаете позицию в мире и проецируете ее на UI, т.е. если позиция объекта в мире находится в точке 10;20 и размер мира 100x100, то на миникарте эта позиция будет 10/100;20/100 в процентах, а значит умножив полученные проценты на размер миникарты - получим точку в UI миникарты.

3. Гибридный вариант. Когда мы можем снимать некоторые объекты "как есть", а потом накладывать поверх уже вариант 2 для pixel-perfect варианта.

Еще я бы сюда добавил такой интересный момент: для 1-го варианта можно использовать лоды, чтобы сократить количество треугольников + сократить количество draw call.

Я предпочитаю использовать только второй вариант + подкладывать (или вообще не использовать) фон.

Читать далее  

in - это сахар от ref. Любой in в итоге становится ref. Соотвественно относиться к нему следует таким же образом. Но все же стоит понимать разницу. in - это доступ только на чтение, ref - чтение и запись, out - только запись.

Пример:

void Method(in Vector3 vector) {
  vector.x = 123f; // будет ошибка доступа
  vector.Method(); // будет сделана копия vector, если метод не readonly
}

А вот тот же пример с ref:

void Method(ref Vector3 vector) {
  vector.x = 123f; // ошибки не будет, значение будет изменено&nbsp;
  vector.Method(); // копии не будет
}

Теперь рассмотрим вариант с возвращаемым значением по ссылке:

Vector3[] arr;
public ref Vector3 Method(int index) {
  return ref arr[index];
}

Во-первых, возвращаемое значение не может быть из стэка, т.е. нельзя сделать вот так:

void Method() {
  ref var a = 123;
}

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

ref var data = ref Method(index);
System.Array.Resize(ref arr, ...); // Меняем данные, на которые держим ссылку
data.x = 123f; // Изменит данные в предыдущем массиве, а не в новом, т.е. фактически изменений не будет

В-третьих, можно вернуть данные только для чтения:

public ref readonly Vector3 Method() {...}

только не путать с этим:

public readonly ref Vector3 Method() {...}

В первом варианте мы возвращаем данные, доступные для чтения, а во втором мы делаем метод, который не меняет объект, в котором объявлен.

Особенно прекрасно выглядит это:

public readonly ref readonly Vector3 Method() {...}

Лично я считаю, что это накосячили разрабы языка, т.к. readonly ref readonly - это дичь, почему было не использовать слово const?

Ну и последнее - нужно понимать, что in и ref - это ссылки, а значит void Method(in LargeStruct s) имеет смысл, чтобы избежать копирования, а вот void Method(in int val) не имеет, т.к. такой int будет передаваться по ссылке ref, но запрещать изменения, при этом ссылка будет занимать 8 байт.

Читать далее  

Cross Product (векторное произведение) - по сути это способ нахождения нормали. Если у нас есть 2 вектора, то эти два вектора так или иначе образуют плоскость. Так вот Cross дает нам нормаль этой плоскости. Направление этой нормали (она же может смотреть как вверх, так и вниз) зависит от порядка этих векторов, т.е. если Cross(a, b), то нормаль смотрит вверх (как на картинке). Если же Cross(b, a), то нормаль будет смотреть вниз. Можно запомнить по так называемому правилу "правой руки":

Есть еще несколько свойств, которые мы получаем, подробнее можно почитать, например, в википедии или https://en.wikipedia.org/wiki/Cross_product.

Dot Product (скалярное произведение) - по сути способ определить угол между векторами. Формула довольно простая: x1*x2 + y1*y2 + z1*z2. То есть мы складываем произведения по каждой из осей. Окей, что нам это дает? Можно запомнить, что по сути это дает нам косинус угла между векторами, если они нормализованы (т.е. длина вектора единица), т.е. acos(dot(a, b)) дает нам угол.
Подробнее тут или https://en.wikipedia.org/wiki/Dot_product.

Да, это далеко не полный перечень того, что можно получить, но я же пытаюсь объяснить "простыми словами" :)

Читать далее  

Как мы рисуем стрелку приказов.

У нас прошло несколько этапов рисования стрелки: в Mushroom Wars 1 это был большой спрайт, в Mushroom Wars 2 мы основательно подошли к этому вопросу и начали сами генерировать меш для стрелки, а вот в новых проектах мы не используем ни первый, ни второй вариант. .

Мы используем LineRenderer. Да, просто линия. Мы контролировали каждый участок, чтобы придать стрелке нужную форму. Т.е. в коде нужно найти нужные точки (а их будет всего 4) и задать им неправильную точку.

Читать далее