数据偏好

在面对问题 X 的时候，你有没有对应该使用数据结构 Y 还是 Z 产生过困惑？本文会涉及到与这些困境有关的各种主题。

备注

本文会提及“[某某]时间”的操作。这个术语来自于算法分析中的大 O 表示法。

简而言之，它描述了最坏情况下的运行时长。用外行的话来说：

“随着问题域的大小增加，算法的运行时长……”

  • 常量时间，O(1)：“……不会增加。”

  • 对数时间，O(log n)：“……会以较慢的速度增长。”

  • 线性时间，O(n)：“……会以相同的速度增长。”

  • 等等。

想象一下, 如果必须在一帧内处理300万个数据点. 不可能使用线性时间算法来设计这个特性, 因为数据的绝对大小, 将使运行时间大大超出分配的时间. 相比之下, 使用常量时间算法可以毫无问题地处理该操作.

总的来说, 开发人员希望尽可能避免进行线性时间操作. 但是, 如果保持线性时间运算的规模很小, 并且如果不需要经常执行操作, 则这是能够接受的. 平衡这些需求, 并为工作选择正确的算法/数据结构, 是使程序员的技能有价值的一部分.

数组、字典、对象

Godot 把脚本 API 中的所有变量都存储在 Variant 中。Variant 可以存储兼容数据结构，例如 Array （数组）、 Dictionary （字典）、 Object （对象）。

Godot 使用 Vector<Variant> 实现数组。引擎会将数组内容存储在一段连续的内存之中，也就是说，元素与元素之间是相邻的。

备注

这里的 Vector 是传统 C++ STL 库中数组对象的名称，是个“模板”类型，即它只能存储特定类型的数据（用尖括号表示）。例如，PackedStringArray 其实就类似于 Vector<String>。

因为是在内存中连续存储，所以执行各种操作的性能如下：

  • 迭代：最快，非常适合循环。

    • 操作：把计数器加一即可获取下一个元素。

  • 插入、删除、移动：与位置相关，一般较慢。

    • 操作：元素的添加、删除、移动需要移动与之相邻的元素（腾出地方或者填充空缺）。

    • 在末尾添加、删除很快。

    • 在任意位置添加、删除较慢。

    • 在开头添加、删除最慢。

    • 如果需要在开头执行多次插入、删除操作，那么……

      1. 反转数组。

      2. 通过循环在末尾执行数组更改。

      3. 再把数组反转回来。

      这样就只复制了两次数组（虽然比较慢，但还是常数时间），否则就得把平均大概一半的数组复制 N 遍（线性时间）。

  • 取值、设值：因为是按位置存取的，所以最快。例如你可以请求第 0 个、第 2 个、第 10 个等等的元素，但不能按照元素的值来请求。

    • 操作：把起始位置做一次加法，得到所需的索引。

  • 查找：最慢。根据值获取索引，也就是位置。

    • 操作：必须遍历数组，一个个元素做比较，直到找到匹配的为止。

      • 性能同时也取决于是否需要查遍整个数组才能找到目标。

    • 如果保持有序, 自定义搜索操作, 可以使其达到对数时间(相对较快). 不过, 外行用户对此会感到不舒服. 通过在每次编辑之后, 重新排序数组, 并编写一个感知顺序的搜索算法来完成.

Godot 使用 OrderedHashMap<Variant, Variant> 实现 Dictionary。引擎存储一个键值对的小数组（初始化为 2^3 即 8 条记录）。当试图访问一个值时，它提供一个键。然后，对键进行哈希处理，即转换成一个数字。“哈希”值用来计算进入数组的索引。作为一个数组，OHM 就可以在键映射到值的“表”中快速查找。当 HashMap 变得过满时，它会增加到2的下一个幂值（即 16 条记录，然后是 32 条，以此类推），并重新构建结构。

散列是为了减少键碰撞的机会. 如果发生了, 列表必须为考虑前一个位置的值, 重新计算另一个索引. 总之, 这导致以牺牲内存和一些较小的操作效率为代价, 对所有记录的常量时间访问.

  1. 散列每个键任意次数.

    • 散列操作是常量时间的, 因此即使一个算法必须执行多于一个, 只要散列计算的数量不太依赖于列表的密度, 一切都会保持快速. 这导致了……

  2. 保持不断增长的表规模.

    • HashMaps maintain gaps of unused memory interspersed in the table on purpose to reduce hash collisions and maintain the speed of accesses. This is why it constantly increases in size exponentially by powers of 2.

如大家所知，字典擅长的任务是数组所不擅长的。其操作细节概述如下：

  • 迭代 : 快速.

    • 操作: 遍历映射的内部散列向量. 返回每个键. 之后, 用户使用该键跳转到并返回所需的值.

  • 插入, 删除, 移动 : 最快.

    • 操作: 散列给定的键. 执行1个加法操作来查找适当的值(数组开始+偏移量). 移动其中的两个(一个插入, 一个擦除). 映射必须进行一些维护, 以保留其功能:

      • 更新记录的有序列表.

      • 确定列表密度, 是否需要扩展列表容量.

    • 字典会记住用户插入键的顺序. 这使它能够执行可靠的迭代.

  • 取值, 设值 : 最快. 和 根据键 查找相同.

    • 操作: 和插入/删除/移动类似.

  • 查找 : 最慢. 标识值的键.

    • 操作: 必须遍历记录并比较该值, 直到找到匹配的为止.

    • 请注意,Godot并未开箱即用地提供此功能(因为它们并非用于此任务).

Godot用愚蠢, 但动态的方式容纳数据容器实现对象. 提出问题时, 对象将查询数据源. 例如, 要回答”你是否有一个名为 position 的属性？”的问题, 它可能会询问其 script 或 ClassDB. 你可以在 在 Godot 中应用面向对象原则 文章中, 找到有关什么是对象以及它们如何工作的更多信息.

这里重要的细节是对象任务的复杂性. 每次执行这些多源查询时, 它运行 几个 迭代循环和哈希表查找. 此外, 查询是线性时间操作, 依赖于对象的继承层次结构大小. 如果 Object 查询的类(当前类)什么都没有找到, 则该请求将一直推迟到下一个基类, 一直到原始 Object 类为止. 虽然这些都是单独的快速操作, 但它必须进行如此多的检查, 于是这一事实使得它们比查找数据的两种方法都要慢.

备注

当开发人员提到脚本API有多慢时, 所引用的正是这一系列查询. 与编译后的, 应用程序知道在哪里可以找到任何东西的,C++代码相比, 不可避免的是, 脚本API操作将花费更长的时间. 他们必须定位任何相关数据的来源, 然后才能尝试访问它.

GDScript 很慢的原因是, 它执行的每个操作都要经过这个系统.

C#可以通过更优化的字节码, 以更快的速度处理一些内容. 但是, 如果C#脚本调用引擎类的内容, 或者脚本试图访问它的外部内容, 它会通过这个管道.

NativeScript C++甚至更进一步, 默认将所有内容都保持在内部. 对外部结构的调用将通过脚本API进行. 在NativeScript C++中, 注册方法以将其公开给脚本API是一项手动任务. 至此, 外部非C++类将使用API来查找它们.

因此, 假设从引用扩展到创建数据结构, 比如一个 Array 或 Dictionary, 为什么选择一个 Object 而不是其他两个选项？

  1. 控件 : 对象能够创建更复杂的结构. 可以在数据上分层抽象, 以确保外部API不会响应内部数据结构的更改. 更重要的是, 对象可以有信号, 允许响应式行为. 对象带来了创建更复杂结构的能力.

  2. 清晰 : 当涉及到脚本和引擎类为对象定义的数据时, 对象是一个可靠的数据源. 属性可能不包含期望的值, 但是无需担心这个属性是否首先存在.

  3. 便利 : 如果已经有了类似的数据结构, 之后从现有类扩展, 可以使构建数据结构的任务变得容易得多. 相比之下, 数组和字典不能满足所有的用例.

对象还让用户有机会创建更专门化的数据结构。有了它，一个人可以设计自己的列表、二叉搜索树、堆、散列树、图、不相交集，以及其他选择。

“为什么不在树结构中使用节点？” 有人可能会问. 节点类包含与自定义数据结构无关的内容. 因此在构建树结构时, 构造自己的节点类型是很有帮助的.

GDScriptC#

  1. extends Object
  2. class_name TreeNode
  4. var _parent: TreeNode = null
  5. var _children := []
  7. func _notification(p_what):
  8.     match p_what:
  9.         NOTIFICATION_PREDELETE:
  10.             # Destructor.
  11.             for a_child in _children:
  12.                 a_child.free()
  1. using Godot;
  2. using System.Collections.Generic;
  4. // Can decide whether to expose getters/setters for properties later
  5. public partial class TreeNode : GodotObject
  6. {
  7.     private TreeNode _parent = null;
  9.     private List<TreeNode> _children = new();
  11.     public override void _Notification(int what)
  12.     {
  13.         switch (what)
  14.         {
  15.             case NotificationPredelete:
  16.                 foreach (TreeNode child in _children)
  17.                 {
  18.                     node.Free();
  19.                 }
  20.                 break;
  21.         }
  22.     }
  23. }

从这里开始, 然后就可以创建具有特定功能的结构, 只会受到他们想象力的限制.

枚举：整数 VS 字符串

Most languages offer an enumeration type option. GDScript is no different, but unlike most other languages, it allows one to use either integers or strings for the enum values (the latter only when using the @export_enum annotation in GDScript). The question then arises, “which should one use?”

简单回答一下就是：“你觉得哪个更舒服就选哪个。” 这是 GDScript 特有的特性，并非（C++、C#等）一般的 Godot 脚本所特有的特性；该语言将可用性置于性能之上。

在技术层面上，整数比较（常量时间）比字符串比较（线性时间）更快，若想保持其他语言中使用枚举的习惯，则应使用整数来表示枚举值。

当你想要 打印 枚举值时，使用整数的主要问题就出现了：尝试直接打印以 int 型保存的枚举 MY_ENUM 会打印 5 之类的东西，而不是像 MyEnum 这样的字符。若要打印以 int 型保存的枚举。必须编写一个字典来映射每个枚举所对应的字符串值。

如果开发者使用枚举的主要目的是打印值，并希望将它们作为相关概念组合在一起，那么将枚举作为字符串使用是有意义的。这样一来，也就不需要在打印上执行单独的数据结构了。

AnimatedTexture vs. AnimatedSprite2D vs. AnimationPlayer vs. AnimationTree

在什么情况下应该使用Godot的各种动画类？对于Godot的新用户来说, 可能不是马上清楚答案.

AnimatedTexture 是引擎绘制一个动画循环, 而不是一个静态图像的纹理. 用户可以进行如下操作…

  1. 它在纹理的每个部分移动的速率（FPS）。

  2. 纹理中包含的区域数(帧).

Godot 的 RenderingServer 会按照规定的速度依次绘制区块。好处是不涉及引擎部分额外的逻辑。坏处是用户几乎没有控制权。

另外请注意，AnimatedTexture 是一种 Resource，与此处讨论的其他 Node 对象不同。可以创建 Sprite2D 节点，使用 AnimatedTexture 作为其纹理。或者（仅在其他方法无法满足要求时）可以将 AnimatedTexture 作为图块添加到 TileSet 中并将其与 TileMap 集成到一起，从而获得自动动画化的背景。使用此方法时所有的渲染将在单个批处理内绘制调用。

AnimatedSprite 节点可以与 SpriteFrames 资源结合使用，使用户可以通过精灵表创建各种动画序列、在动画之间切换并控制它们的速度、区域偏移量和方向。这使得它们非常适合控制基于二维的帧动画。

触发与动画更改相关的其他效果，例如创建粒子效果、调用函数或操作除基于帧的动画外的其他外围元素需要将一个 AnimationPlayer 节点与 AnimatedSprite 关联。

如果你想设计更复杂的二维动画系统，AnimationPlayer 也是你的必备工具，例如……

  1. 剪纸动画：在运行时编辑精灵的变换。

  2. 二维网格动画：为精灵的纹理划分一个区域，并将骨架绑定在上面。然后动画化其中的骨骼，使骨骼按照彼此之间的关系，成比例地拉伸和弯曲纹理。

  3. 综上所述.

虽然我们需要一个 AnimationPlayer, 来为游戏设计每个独立的动画序列, 它也可以用来混合复合动画, 也就是说, 在这些动画之间实现平滑的转换. 在为对象规划的动画之间, 也可能存在一个层次结构. 在这些情况下使用 AnimationTree 效果很出色. 可以在 这里 找到关于使用 AnimationTree 的深入指南.