Структуры данных GameMaker

Структуры данных GameMaker — это встроенные в среду разработки GameMaker (GameMaker Studio) программные объекты, предназначенные для хранения, организации и управления наборами данных в памяти компьютера. Они предоставляют разработчику инструменты, выходящие за рамки простых переменных и массивов, позволяя эффективно реализовывать сложные алгоритмы, такие как очереди, стеки, списки, карты и приоритетные очереди. Структуры данных GameMaker являются фундаментальной частью языка программирования GML (GameMaker Language) и используются для оптимизации производительности и упрощения кода в играх и приложениях.

История и назначение

Структуры данных были введены в GameMaker начиная с версии 6.0 (ранее известной как GameMaker 6) для расширения возможностей языка GML. До их появления разработчики были вынуждены использовать массивы и строки для имитации сложных структур, что было неудобно и ресурсоёмко. Внедрение нативных структур данных позволило стандартизировать и ускорить работу с коллекциями объектов, особенно в контексте игровой логики: управления врагами, обработки событий, хранения игровых состояний и реализации искусственного интеллекта.

В последующих версиях (GameMaker Studio 1.x, 2.x) функционал структур данных был расширен, добавлены новые типы и улучшена производительность. В настоящее время они остаются актуальным инструментом, хотя в GameMaker Studio 2 также появились более современные альтернативы, такие как встроенные структуры (structs) и массивы с динамическим изменением размера.

Типы структур данных

GameMaker поддерживает шесть основных типов структур данных, каждая из которых имеет свою область применения и методы работы.

Стек (Stack)

Стек — это структура данных, работающая по принципу LIFO (Last In, First Out — «последним пришёл — первым вышел»). Элементы добавляются и удаляются только с одного конца (вершины стека). В GameMaker стек реализуется с помощью функций ds_stack_create(), ds_stack_push(), ds_stack_pop(), ds_stack_top() и других.

Применение:

• Отмена и повтор действий (Undo/Redo).
• Обработка вложенных вызовов функций (например, в парсерах).
• Реализация алгоритмов обхода графов в глубину (DFS).

Очередь (Queue)

Очередь — структура данных, работающая по принципу FIFO (First In, First Out — «первым пришёл — первым вышел»). Элементы добавляются в конец очереди, а извлекаются из начала. Для работы с очередью используются функции ds_queue_create(), ds_queue_enqueue(), ds_queue_dequeue(), ds_queue_head().

Применение:

• Обработка событий в порядке их поступления (например, сообщения чата).
• Реализация алгоритмов обхода графов в ширину (BFS).
• Управление очередями анимаций или звуков.

Список (List)

Список — это упорядоченная коллекция элементов, доступ к которым осуществляется по индексу. В отличие от массивов, списки могут динамически изменять свой размер, а также поддерживают вставку и удаление элементов в произвольной позиции. Основные функции: ds_list_create(), ds_list_add(), ds_list_insert(), ds_list_delete(), ds_list_find_index().

Применение:

• Хранение динамических наборов объектов (например, список врагов на уровне).
• Сортировка данных (список поддерживает встроенные функции сортировки).
• Реализация алгоритмов, требующих частой вставки и удаления элементов.

Карта (Map)

Карта (или ассоциативный массив) — это структура данных, хранящая пары «ключ — значение». Ключи могут быть строками или числами, а значения — любыми типами данных GML. Карта обеспечивает быстрый доступ к значению по ключу. Функции: ds_map_create(), ds_map_add(), ds_map_find_value(), ds_map_exists(), ds_map_delete().

Применение:

• Хранение настроек и конфигураций (например, параметров персонажа).
• Реализация словарей и справочных таблиц.
• Создание кэшей для ускорения доступа к данным.

Приоритетная очередь (Priority Queue)

Приоритетная очередь — это структура данных, в которой каждый элемент имеет приоритет. Элементы извлекаются не в порядке добавления, а в порядке убывания (или возрастания) приоритета. Реализуется с помощью функций ds_priority_create(), ds_priority_add(), ds_priority_delete_min(), ds_priority_delete_max().

Применение:

• Реализация алгоритма Дейкстры для поиска кратчайших путей.
• Управление задачами с разными приоритетами (например, AI-процессы).
• Системы событий, где важные события должны обрабатываться раньше.

Сет (Grid)

Сет (или сетка) — это двумерная структура данных, представляющая собой прямоугольную таблицу фиксированного размера. Каждая ячейка сетки может хранить одно значение. Функции: ds_grid_create(), ds_grid_set(), ds_grid_get(), ds_grid_resize().

Применение:

• Реализация игровых полей (например, карта для пошаговой стратегии).
• Хранение данных тайловой карты.
• Реализация алгоритмов, работающих с двумерными пространствами (например, поиск пути A*).

Управление памятью и жизненный цикл

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

Для удаления структуры данных используется соответствующая функция ds_*_destroy(). Например, для списка — ds_list_destroy(id), для карты — ds_map_destroy(id). Если структура данных не будет удалена, это приведёт к утечке памяти, что может вызвать снижение производительности и, в конечном счёте, аварийное завершение игры.

Рекомендуется удалять структуры данных в событии очистки (Clean Up) объекта, который их создал, или в конце уровня. Также существуют глобальные функции для очистки всех структур данных, но их использование не рекомендуется из-за риска потери данных.

Особенности и ограничения

• Идентификаторы: Каждая структура данных при создании получает уникальный целочисленный идентификатор (ID), который используется для всех операций с ней.
• Вложенность: Структуры данных могут быть вложенными. Например, список может содержать идентификаторы карт, а карта — идентификаторы других списков. Это позволяет создавать сложные иерархические структуры.
• Производительность: Встроенные структуры данных оптимизированы для работы с большими объёмами данных, но при этом каждая операция (вставка, удаление, поиск) имеет свою временную сложность. Например, поиск по ключу в карте выполняется за O(1) в среднем, а вставка в середину списка — за O(n).
• Совместимость: Структуры данных могут быть переданы в функции и скрипты, а также сохранены в файлы с помощью функций ds__write() и ds__read().

Примеры использования

Пример 1: Очередь сообщений

```gml // Создание очереди message_queue = ds_queue_create();

// Добавление сообщений ds_queue_enqueue(message_queue, "Игрок вошёл в игру"); ds_queue_enqueue(message_queue, "Враг атакован");

// Обработка сообщений while (!ds_queue_empty(message_queue)) { var msg = ds_queue_dequeue(message_queue); show_debug_message(msg); }

// Удаление очереди ds_queue_destroy(message_queue); ```

Пример 2: Карта настроек

```gml // Создание карты settings = ds_map_create();

// Добавление настроек ds_map_add(settings, "volume", 0.8); ds_map_add(settings, "difficulty", "hard");

// Чтение настройки var vol = ds_map_find_value(settings, "volume");

// Удаление карты ds_map_destroy(settings); ```

Альтернативы и современные тенденции

Начиная с версии GameMaker Studio 2.3, в язык GML были добавлены нативные структуры (structs) и массивы с динамическим изменением размера. Эти конструкции автоматически управляют памятью и не требуют явного уничтожения, что делает их более безопасными и удобными для многих задач. Однако структуры данных (ds_list, ds_map и др.) по-прежнему остаются полезными для сценариев, требующих высокой производительности, специфических алгоритмов (например, приоритетные очереди) или совместимости со старым кодом.

Разработчикам рекомендуется выбирать между структурами данных и нативными структурами в зависимости от конкретной задачи: для простых коллекций и небольших проектов предпочтительнее использовать structs, а для сложных алгоритмов и больших объёмов данных — ds-структуры.

Источники

• Официальная документация GameMaker Studio 2: «Data Structures» (YoYo Games).
• Руководство по языку GML (GameMaker Language).
• Книга «GameMaker: Studio 100 Programming Challenges» (Ben Tyers).