Налаштування даних

Ніколи не замислювались, чи слід підходити до проблеми X зі структурою даних Y або Z? Ця стаття охоплює різноманітні теми, пов’язані з цими дилемами.

Примітка

Ця стаття містить посилання на операції "[щось] -час". Ця термінологія виходить з алгоритму аналізу Big O Notation.

Коротко кажучи, він описує найгірший сценарій тривалості роботи. Якщо говорити неспеціалістами:

"Зі збільшенням розміру проблемного домену тривалість виконання алгоритму ..."

• Постійний час, O(1): "... не збільшується."

• Логарифмічний час, O(log n): "... збільшується повільно."

• Лінійний час, O(n): "... збільшується з тією ж швидкістю."

• І так далі.

Уявіть, якби потрібно було обробити 3 мільйони точок даних за один кадр. Було б неможливо створити функцію за допомогою алгоритму лінійного часу, оскільки обсяг даних збільшив би час виконання значно більше, ніж відведено часу. Для порівняння, використання алгоритму з постійним часом може впоратися з операцією без проблем.

За великим рахунком, розробники хочуть якомога більше уникати участі в операціях з лінійним часом. Але якщо масштаб операції з лінійним часом зберігається невеликим, і якщо операції не потрібно часто виконувати, це може бути прийнятним. Балансування цих вимог та вибір правильної алгоритму/структури даних для роботи є частиною того, що робить навички програмістів цінними.

Масив, Словник та Об'єкт

Godot зберігає всі змінні в API скриптів у класі Variant. Варіанти можуть зберігати сумісні з варіантами структури даних, такі як Масив and Словник as well as Об'єкт.

Godot реалізує Масив як Vector<Variant>. Механізм зберігає вміст масиву у суміжній частині пам'яті, тобто вони знаходяться в ряду, що прилягають один до одного.

Примітка

Для тих, хто не знайомий з C++, Vector - це ім’я об’єкта масиву в традиційних бібліотеках C++. Це "шаблонний" тип, що означає, що його записи можуть містити лише певний тип (позначений кутовими дужками). Так, наприклад, PoolStringArray буде чимось типу Vector<String>.

Суміжні сховища пам’яті передбачають такі характерні операції:

• Ітерація: Найшвидша. Відмінно підходить для циклів.

  • Oп: Все, що вона робить, це збільшує лічильник, щоб перейти до наступного запису.

• Вставка, Стирання, Переміщення: Залежить від положення. Загалом повільна.

  • Oп: Додавання/видалення/переміщення вмісту включно з переміщенням сусідніх записів (щоб звільнити/заповнити місце).

  • Швидке додавання/видалення з кінця.

  • Повільне додавання/видалення з довільної позиції.

  • Найповільніше додавання/видалення спереду.

  • Якщо ви робите багато вставок/вилучень спереду, тоді ...

    1. інвертуйте масив.

    2. виконайте цикл, який виконує зміни масиву в кінці.

    3. повторно інвертуйте масив.

    Це дає лише 2 копії масиву (все ще постійний час, хоча й повільний) проти копіювання приблизно 1/2 масиву, в середньому N разів (лінійний час).

• Отримання, Встановлення: Найшвидше за позицією. Наприклад, може запитувати 0-й, 2-й, 10-й запис, тощо, але не може вказати, який запис ви хочете.

  • Oп: 1 операція додавання від початкової позиції масиву до бажаного індексу.

• Пошук: Найповільніша. Визначає індекс/позицію значення.

  • Oп: Мусить перебирати масив і порівнювати значення, поки не знайдеться збіг.

    • Ефективність також залежить від того, чи потрібен вичерпний пошук.

  • Якщо збережено впорядкування, користувацькі пошукові операції можуть привести його до логарифмічного часу (відносно швидко). Непрофесійним користувачам це буде неприємно. Виконується шляхом повторного сортування масиву після кожного редагування та написання впорядкованого алгоритму пошуку.

Godot реалізує Словник як OrderedHashMap<Variant, Variant>. Механізм зберігає невеликий масив (ініціалізований до 2^3 чи 8 записів) пар ключ-значення. Коли хтось намагається отримати доступ до значення, вони надають йому ключ. Потім він хешує ключ, тобто перетворює його в число. "Хеш" використовується для обчислення індексу в масиві. Як масив, OHM має швидкий пошук у "таблиці" ключів, зіставлених із значеннями. Коли HashMap стає занадто заповненим, він збільшується до наступної степені 2 (тобто 16 записів, потім 32 тощо) і відновлює структуру.

Хеші мають зменшити ймовірність зіткнення ключа. Якщо такий трапляється, таблиця повинна перерахувати інший індекс значення, яке враховує попередню позицію. Загалом, це призводить до постійного доступу до всіх записів за рахунок пам'яті та незначної операційної ефективності.

1. Хешування кожного ключа довільну кількість разів.

   • Операції хешування є постійними, тому, навіть якщо алгоритм повинен виконувати більше одної операції, до тих пір, поки кількість обчислень хешу не стане занадто залежною від щільності таблиці, все буде залишатися швидким. Що веде до ...

2. Зберігання постійно зростаючого розміру таблиці.

   • HashMaps підтримують прогалини невикористаної пам’яті, вбудовані в таблицю з метою зменшення колізійних зіткнень і підтримки швидкості доступу. Ось чому вона постійно збільшується в розмірі квадратично на ступінь 2.

Як можна було б зрозуміти, Словники спеціалізуються на завданнях, які Масиви не виконують. Для них характерні такі операції:

• Ітерація: Швидка.

  • Oп: Ітерація внутрішніх векторів карти хешів. Повертає кожен ключ. Потім користувачі використовують ключ, щоб перейти до потрібного значення та повернути його.

• Вставка, Видалення, Переміщення: Найшвидша.

  • Oп: Хешує заданий ключ. Виконує 1 операцію додавання, щоб знайти відповідне значення (початок масиву + зміщення). Переміщення включає дві операції (одна вставка, одна видалення). Карта мусить виконати певні дії, щоб зберегти свої можливості:

    • оновити впорядкований Список записів.

    • визначити, чи вимагає заповненість таблиці розширення ємності таблиці.

  • Словник пам’ятає, в якому порядку користувачі вставляли його ключі. Це дозволяє йому виконувати надійні ітерації.

• Отримання, встановлення: Найшвидша. Як і, що пошук за ключем.

  • Oп: Як і вставлення/видалення/переміщення.

• Пошук: Найповільніша. Ідентифікує ключ значення.

  • Oп: Потрібно перебрати записи та порівняти значення, поки не буде знайдено збіг.

  • Зауважте, що Godot не надає цю функцію out-of-the-box (з коробки) (оскільки вона не призначена для цього завдання).

Godot реалізує об’єкти як дурні, але динамічні контейнери вмісту даних. Об’єкти запитують джерела даних, коли ставлять запитання. Наприклад, щоб відповісти на запитання "чи є у вас властивість, що називається, 'position'?", він може запитати свій скрипт або ClassDB. Більше інформації про те, що таке об’єкти та як вони працюють, можна знайти в статті Застосування об’єктно-орієнтованого підходу у Godot.

Важливою деталлю тут є складність завдання Об’єкта. Кожного разу, коли він виконує один із цих запитів із декількома джерелами, він проходить через кілька циклів ітерацій та пошук HashMap. Більше того, запити - це операції лінійного часу, що залежать від розміру ієрархії успадкування Об’єкта. Якщо клас, який запитує Об'єкт (його поточний клас), нічого не знаходить, запит переходить до наступного базового класу і так аж до початкового класу Об'єкта. Хоча окремо кожна така операція швидка, той факт, що вона повинна зробити стільки перевірок, робить їх повільнішою, за обидві альтернативи пошуку даних.

Примітка

Коли розробники згадують, наскільки повільним є скриптове API, вони мають на увазі саме цей ланцюжок запитів. Порівняно зі скомпільованим кодом С++, де додаток точно знає, куди звернутися, щоб знайти що-небудь, неминуче операції скриптового API займуть набагато більше часу. Вони повинні знайти джерело будь-яких відповідних даних, перш ніж вони зможуть спробувати отримати до них доступ.

Причиною повільної роботи GDScript є те, що кожна операція, яку він виконує, проходить через цю систему.

C# може обробляти деякий вміст на вищих швидкостях за допомогою більш оптимізованого байт-коду. Але якщо скрипт C# викликає вміст класу движка, або якщо скрипт намагається отримати доступ до чогось зовнішнього для нього, він все-одно пройде цей конвеєр.

NativeScript C++ іде ще далі і зберігає все внутрішнє за замовчуванням. Виклики у зовнішні структури будуть проходити через скриптове API. У NativeScript C++ реєстрація методів, щоб піддати їх скриптовому API, є ручним завданням. Саме на цьому етапі зовнішні класи, що не належать C++, використовуватимуть API для їх пошуку.

Отже, якщо припустити, що Посилання можна розширити, щоб створити структуру даних, наприклад, Масив чи Словник, навіщо обирати Об’єкт коли є інші два варіанти?

1. Контроль: З об’єктами з’являється можливість створювати досконаліші структури. Можна накласти абстракції на дані, щоб переконатися, що зовнішній API не змінюється у відповідь на внутрішні зміни структури даних. Більше того, об’єкти можуть мати сигнали, що дозволяють реагувати на поведінку.

2. Чіткість: Об’єкти є надійним джерелом даних, коли йдеться про дані, які для них визначають скрипти та класи движка. Можливо, властивості не містять очікуваних значень, але не потрібно турбуватися про те, чи існує властивість взагалі.

3. Зручність: Якщо хтось вже має на увазі подібну структуру даних, то розширення з існуючого класу значно полегшує завдання побудови структури даних. Для порівняння, Масиви та Словники придатні не для всіх випадків, які можуть бути.

Об'єкти також дають користувачам можливість створювати ще більш спеціалізовані структури даних. За допомогою них можна створити власний Список, Двійкове Дерево Пошуку, Heap, Дерево Відтворення, Графік, Неперервний Набір та будь-який набір інших варіантів.

Може виникнути запитання: "Чому б не використовувати Вузли для структур дерева?". Ну, клас Вузол містить речі, які не будуть стосуватися власної структури даних. Таким чином, може бути корисно побудувати власний тип вузла при побудові структур дерева.

GDScriptC#

extends Object
class_name TreeNode

var _parent : TreeNode = null
var _children : = [] setget

func _notification(p_what):
    match p_what:
        NOTIFICATION_PREDELETE:
            # Destructor.
            for a_child in _children:
                a_child.free()

Звідси можна створити власні структури зі специфічними особливостями, обмеженими лише уявою.

Перерахунки: int та string

Більшість мов пропонує перерахунки. GDScript не відрізняється, але на відміну від більшості інших мов, він дозволяє використовувати цілі числа або текст для значень перерахування (останнє лише при використанні ключового слова export в GDScript). Тоді виникає запитання: "що використовувати?"

Коротка відповідь: "що тобі зручніше". Це особливість, специфічна для GDScript, а не скриптів Godot загалом; Мови надають перевагу зручності використання порівняно з продуктивністю.

На технічному рівні цілочисельні порівняння (постійний час) відбуватимуться швидше текстових порівнянь (лінійний час). Якщо хтось хоче дотримуватися конвенцій інших мов, тоді слід використовувати цілі числа.

Основна проблема з використанням цілих чисел виникає, коли хочеться надрукувати значення перерахунка. При використанні цілих чисел, спроба надрукувати MY_ENUM буде друкувати 5 або те, що є у вас, а не щось подібне "MyEnum". Щоб надрукувати ціле число, потрібно написати Словник, який відображає відповідне значення рядка для кожного перерахунку.

Якщо основною метою використання перерахунку є друк значень і хочеться згрупувати їх як пов'язані поняття, то є сенс використовувати для них текст. Таким чином, окрема структура даних для друку непотрібна.

AnimatedTexture,. AnimatedSprite, AnimationPlayer та AnimationTree

За яких обставин слід користуватися кожним із класів анімації Godot? Відповідь може бути не одразу зрозумілою для нових користувачів Godot.

AnimatedTexture це текстура, яку движок малює як анімований цикл, а не як статичне зображення. Користувачі можуть маніпулювати ...

1. швидкістю, з якою цикл відтворює кожну ділянку текстури (fps).

2. кількість областей, що містяться в текстурі (кадри).

Потім VisualServer Godot малює області послідовно із встановленою швидкістю. Хороша новина полягає в тому, що це не передбачає додаткової логіки з боку движка. Погана новина полягає в тому, що користувачі мають дуже слабкий контроль.

Також запримітьте, що AnimatedTexture - це Ресурс, на відміну від інших обговорених тут об'єктів Вузол. Можна створити вузол Спрайт, який використовує AnimatedTexture як свою текстуру. Або (те, що інші не можуть зробити), можна додати AnimatedTexture як плитки в TileSet та інтегрувати його з TileMap для багатьох фонів з автоматичною анімацією, які всі відображаються в одному пакетному виклику малювання.

Вузол AnimatedSprite у поєднанні з ресурсом SpriteFrames дозволяє створювати різноманітні послідовності анімації за допомогою таблиць спрайтів, перебирати між анімаціями та контролювати їх швидкість, регіональний зсув та орієнтацію. Це робить їх чудовими для управління 2D-анімацією на основі кадру.

Якщо потрібно викликати інші ефекти щодо змін анімації (наприклад, створити ефекти частинок, викликати функції або маніпулювати іншими периферійними елементами, крім анімації на основі кадру), тоді потрібно буде використовувати вузол AnimationPlayer спільно з AnimatedSprite.

AnimationPlayers - це також інструмент, який потрібно буде використовувати, якщо ви хочете розробляти складніші 2D-анімаційні системи, такі як ...

1. Вирізані анімації: редагування перетворень спрайтів під час відтворення.

2. Анімація 2D Меша: визначення області текстури спрайту та встановлення скелета до нього. Потім анімуюються кістки, які розтягують і згинають текстуру пропорційно відношенню кісток між собою.

3. Суміш вищезазначеного.

Хоча для розробки кожної з окремих послідовностей анімації для гри потрібен AnimationPlayer, також може бути корисним поєднання анімації для змішування, тобто забезпечення плавних переходів між цими анімаціями. Також може існувати ієрархічна структура між анімацією, яку планується для свого об’єкта. Це випадки для AnimationTree. Можна знайти поглиблене керівництво по використанню AnimationTree тут.