Данная статья является переводом другой статьи. С оригиналом вы можете ознакомиться по ссылке. В оригинальную статью в процессе перевода были внесены некоторые правки, а материал расширен для лучшего раскрытия темы.
В процессе разработки игр мы постоянно работаем с большими объёмами данных — будь то инвентарь игрока, ИИ врагов или состояние игрового мира. Эффективная организация и доступ к этим данным крайне важны для оптимизации производительности и создания захватывающего игрового процесса. И именно здесь нам на помощь приходят структуры данных/
Структуры данных предоставляют мощные инструменты для хранения, организации и обработки данных. Используя их в Unity, вы сможете раскрыть целый мир возможностей, делая игры быстрее, более масштабируемыми и простыми в поддержке. Ниже приведены примеры того, как структуры данных могут принести пользу при разработке игр на Unity.
Array (массив)
Массивы — одна из базовых структур данных. Они позволяют хранить коллекцию элементов одинакового типа фиксированного размера. Обеспечивают быстрый доступ к элементам по индексу, но после инициализации размер массива изменить нельзя. В Unity массивы часто используют для хранения игровых объектов, данных игрока или других связанных данных.
// Пример: Хранение позиций контрольных точек на пути патрулирования
Vector3[] waypoints = new Vector3[3] { new Vector3(1, 0, 0), new Vector3(0, 0, 1), new Vector3(2, 0, 2) };
void Patrol()
{
foreach (Vector3 waypoint in waypoints)
{
// Перемещаем объект к следующей точке
transform.position = waypoint;
// Выполняем другие действия патрулирования
// ...
}
}
List (список)
Списки — динамические коллекции элементов, размер которых может увеличиваться или уменьшаться. Они часто применяются, когда заранее неизвестно количество элементов или оно может меняться во время выполнения. Списки предлагают большую гибкость по сравнению с массивами и имеют встроенные методы для добавления, удаления и доступа к элементам. В Unity списки обычно используют для управления такими сущностями, как враги, снаряды, предметы и т.д.
// Пример: Хранение списка собранных предметов в системе инвентаря
List<string> collectedItems = new List<string>();
void CollectItem(string item)
{
collectedItems.Add(item);
}
void DisplayInventory()
{
foreach (string item in collectedItems)
{
Debug.Log(item);
}
}
Реализованы списки в C# с помощью класса List<T>. Список по сути реализован как динамический массив, то есть под капотом хранится обычный массив типа T (где Т – любой тип данных, который вы хотите использовать), но с механизмом автоматического увеличения его размера. У каждого списка есть свойство Capacity, которое определяет, сколько элементов он может вместить, не выполняя перераспределения памяти. При добавлении элементов, если текущая вместимость исчерпана, создаётся новый внутренний массив большего размера, и все данные копируются в него.
Давайте рассмотрим список с точки зрения алгоритмической сложности. Добавление элемента в конец списка (Add) при условии, что ещё есть свободное место, происходит за константное время O(1). Если же массива внутри уже не хватает, он пересоздаётся с увеличенным размером, и операция в этот момент становится O(n). Но в среднем такая операция всё равно считается O(1), так как пересоздание происходит относительно редко. Поскольку список хранит данные в непрерывном участке памяти, доступ к элементу по индексу (например, myList[i]) работает за константное время O(1). Вставка же элемента в произвольное место или удаление какого-то конкретного элемента (кроме последнего) имеет сложность O(n), так как в этих операциях используется сдвиг элементов справа.
Dictionary (словарь)
Словари хранят данные в виде пар «ключ-значение». Они обеспечивают быстрый поиск по ключу, что полезно в ситуациях, когда нужно получить доступ к данным по определённому идентификатору. В Unity словари часто используют для сопоставления игровых сущностей с их данными.
using System.Collections.Generic;
// Пример: Создание и использование словаря с очками игроков
Dictionary<string, int> playerScores = new Dictionary<string, int>();
playerScores["Player1"] = 100;
playerScores["Player2"] = 200;
playerScores["Player3"] = 150;
// Доступ к значениям словаря
int score = playerScores["Player2"]; // Получение значения, связанного с ключом "Player2" (200)
// Перебор элементов словаря
foreach (KeyValuePair<string, int> entry in playerScores)
{
Debug.Log(entry.Key + ": " + entry.Value);
}
// Пример: Управление достижениями в игре и статусом их выполнения
Dictionary<string, bool> achievements = new Dictionary<string, bool>();
void UnlockAchievement(string achievementName)
{
achievements[achievementName] = true;
}
bool IsAchievementUnlocked(string achievementName)
{
if (achievements.ContainsKey(achievementName))
{
return achievements[achievementName];
}
return false;
}
Словарь позволяет быстро находить значение по уникальному ключу. В роли ключа может выступать практически любой тип, для которого корректно определены методы GetHashCode() и Equals(). Под капотом Dictionary — это хеш-таблица, в которой каждый элемент распределяется по «корзинам» в зависимости от хеш-кода ключа. Разумеется, внутри есть механизмы разрешения коллизий (случаев, когда разные ключи дают одинаковый хеш).
Как и в List, у Dictionary есть «внутренняя емкость», определяющая, сколько элементов он может хранить, не выполняя пересоздания. При превышении этого лимита создаётся новый, более «просторный» массив корзин, а все существующие элементы перераспределяются заново.
Словарь в среднем обеспечивает сложность O(1) на добавление новых пар «ключ—значение», удаление и поиск по ключу. Это достигается за счет того, что при добавлении элемент помещается в корзину, определяемую хеш-кодом ключа, а при поиске нужная корзина выбирается по тому же хеш-коду.
Queue (очередь)
Очереди реализуют принцип «первым зашел — первым вышел» (FIFO, First In – First Out). Элементы добавляются (Enqueue) в конец очереди и извлекаются (Dequeue) с её начала. Очереди часто применяются для реализации очередей заданий, систем событий или управления поведением ИИ — в общем, там, где важно обрабатывать события в определённом порядке (например, действия в пошаговой игре).
Очередь в C# (класс Queue) чаще всего реализуется как круговой буфер поверх массива. При добавлении элемента, если в текущем массиве ещё есть место, операция происходит за O(1). Если массив переполняется, он автоматически пересоздаётся с увеличенным размером, и добавление в этот момент становится O(n), но в среднем всё равно считается O(1) из-за амортизированного анализа. Извлечение элемента также выполняется за O(1) в обычных условиях, поскольку достаточно сдвинуть указатель на голову очереди.
using System.Collections.Generic;
// Пример: Создание и использование очереди игровых событий
Queue<string> eventQueue = new Queue<string>();
eventQueue.Enqueue("Event1");
eventQueue.Enqueue("Event2");
eventQueue.Enqueue("Event3");
// Извлечение элемента
string currentEvent = eventQueue.Dequeue(); // Получает и удаляет первый элемент очереди
// Просмотр следующего элемента без его удаления
string nextEvent = eventQueue.Peek();
// Перебор элементов очереди
foreach (string item in eventQueue)
{
Debug.Log(item);
}
Stack (стек)
Стек работает по принципу «последним зашел — первым вышел» (LIFO, Last In – First Out). Элементы добавляются (Push) и извлекаются (Pop) с одного конца (вершины стека). Стеки часто используются для управления состояниями игры, реализации функций «отмена/повтор» или отслеживания вложенных операций. Добавление элемента (Push) в стек происходит сверху и занимает O(1), пока не потребуется расширение массива. При достижении предела ёмкости массив пересоздаётся, что в этот момент даёт O(n), но остаётся O(1) в среднем. Извлечение также занимает O(1).
using System.Collections.Generic;
// Пример: Создание и использование стека игровых объектов
Stack<GameObject> objectStack = new Stack<GameObject>();
objectStack.Push(object1);
objectStack.Push(object2);
objectStack.Push(object3);
// Извлечение элемента из стека
GameObject currentObject = objectStack.Pop(); // Получает и удаляет верхний элемент
// Просмотр верхнего элемента без удаления
GameObject topObject = objectStack.Peek();
// Перебор элементов стека
foreach (GameObject item in objectStack)
{
Debug.Log(item.name);
}
HashSet (хэш-набор)
Хэш-наборы (HashSet) — неупорядоченные коллекции, которые хранят только уникальные элементы. Они полезны, когда нужно управлять множеством объектов без повторов.
// Пример: Управление набором активных усилений (power-ups)
HashSet<string> activePowerUps = new HashSet<string>();
void ActivatePowerUp(string powerUpName)
{
activePowerUps.Add(powerUpName);
}
void DeactivatePowerUp(string powerUpName)
{
activePowerUps.Remove(powerUpName);
}
bool IsPowerUpActive(string powerUpName)
{
return activePowerUps.Contains(powerUpName);
}
HashSet работает по тому же принципу хеш-таблицы, что и Dictionary, но она хранит только ключи без сопутствующих значений. Как и в словаре, каждая операция добавления, удаления или проверки элемента (Contains) в среднем выполняется за O(1), и точно так же при превышении внутренней ёмкости происходит расширение и перераспределение элементов, влекущее за собой более дорогую операцию O(n) — но это случается редко.
HashSet оптимизирован именно под операции, связанные с наличием элемента, объединением, пересечением и разностью множеств.
Собственные структуры данных
C# также позволяет создавать собственные структуры данных, полностью соответствующие логике вашей игры. Вы можете спроектировать необходимые структуры — например, сетки для управления уровнем или любую другую специализированную модель организации информации.
Главное — выбирать подходящую структуру данных исходя из специфики вашей игры и типов данных, с которыми вы работаете. При принятии решения учитывайте факторы, связанные с производительностью, объёмом памяти и теми операциями, которые вы планируете проводить над данными.
Объединив возможности различных структур данных с гибкостью и мощью Unity и C#, вы сможете вывести разработку игр на новый уровень и открыть новые горизонты для своих проектов. От оптимизации производительности до реализации сложных игровых систем — грамотное использование структур данных позволит эффективно и элегантно решать возникающие задачи.
Поэтому, будь вы опытным разработчиком игр или только начинаете свой путь, обязательно изучайте увлекательный мир структур данных. Экспериментируйте с разными способами хранения и обработки данных, и вы сами увидите, как это отразится на производительности, масштабируемости и общем дизайне ваших проектов!
Как перестать писать спагетти-код: интенсив по алгоритмам и структурам данных
Если вы хотите развиваться в программировании и готовитесь к собеседованиям в IT-компании, курс по алгоритмам и структурам данных может стать отличным дополнением к вашим знаниям, обеспечивая практический опыт и теоретическую базу.
Что вас ждет на курсе:
- Интенсивная программа: 47 видеолекций и 150 практических заданий для закрепления материала.
- Поддержка преподавателей: Комментарии и советы по заданиям на протяжении всего обучения.
- Гибкий формат: Курс в записи на платформе CoreApp, доступен в любое время.
- Длительность: 6 месяцев обучения с возможностью вернуться к материалам в любое время.
Для кого подходит курс:
- Junior-разработчики: Если вы хотите стать разработчиком или устроиться на эту должность.
- Middle-разработчики: Освежите знания и научитесь решать сложные задачи.
- Все, кто хочет улучшить навыки: Знание алгоритмов расширяет инструментарий разработчика и помогает в решении практических задач.
Почему важно изучать алгоритмы:
- Подготовка к собеседованиям: Знание алгоритмов необходимо для успешного прохождения технических собеседований в IT-компаниях.
- Практический опыт: Вы получите навыки, которые сможете применять в реальных проектах.
- Квалифицированный сертификат: По окончании курса вы получите сертификат, подтверждающий ваши знания.
Комментарии