数据偏好

有没有想过应该用数据结构Y还是Z, 来处理问题X ？本文涵盖了与这些困境有关的各种主题.

注解

本文引用了 [something]-time 操作. 这个术语来自于算法分析的 大O 表示法.

长话短说, 它描述了运行时长度的最坏的情况. 用外行的话来说:

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

• 常量时间, O(1): “…不会增加.”

• 对数时间, O(log n): “…以缓慢的速度增长.”

• 线性时间, O(n): “…以同样的速度增长.”

• 等等.

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

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

数组、字典、对象

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

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

注解

如果你不熟悉 C++ 的话，这里的 Vector 是传统 C++ 库中熟组对象的名称，是个“模板”类型，也就是说它只能存储特定类型的数据（用尖括号表示）。所以举例来说，PoolStringArray 其实就类似于 Vector<String>。

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

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

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

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

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

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

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

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

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

    1. 反转数组。

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

    3. 再把数组反转回来。

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

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

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

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

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

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

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

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

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

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

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

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

   • HashMaps为了减少哈希冲突, 并保持访问速度, 在表中保留了未使用的内存的间隙. 这也是为什么它的大小不断地以2的幂次增加的原因.

如大家所知,Dictionaries [字典]擅长的任务是Arrays[数组]所不擅长的. 其操作细节概述如下:

• 迭代 : 快速.

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

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

  • 操作: 散列给定的键. 执行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. 便利 : 如果已经有了类似的数据结构, 之后从现有类扩展, 可以使构建数据结构的任务变得容易得多. 相比之下, 数组和字典不能满足所有的用例.

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

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

GDScript

C#

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()

// Can decide whether to expose getters/setters for properties later
public class TreeNode : Object
{
    private TreeNode _parent = null;
    private object[] _children = new object[0];
    public override void Notification(int what)
    {
        switch (what)
        {
            case NotificationPredelete:
                foreach (object child in _children)
                {
                    TreeNode node = child as TreeNode;
                    if (node != null)
                        node.Free();
                }
                break;
            default:
                break;
        }
    }
}

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

枚举: 整数VS字符串

大多数语言都提供了一个枚举类型选项.GDScript也不例外, 但与大多数其他语言不同的是, 它允许人们使用整数或字符串作为枚举值(只有在GDScript中使用 export 关键字时才可使用后者). 那么问题就来了,”应该使用哪一种？”

简而言之,”你觉得哪个更舒服就选哪个.” 这是GDScript特有的特性, 而并非一般的Godot脚本；该语言将可用性置于性能之上.

在技术层面上, 整数比较(常量时间)比字符串比较(线性时间)更快. 如果你想保持其他语言的习惯, 那么应该使用整数.

当您想要 打印 枚举值时, 使用整数的主要问题就出现了. 作为整数尝试打印 MY_ENUM, 将会打印 5 之类的东西, 而不是像 MyEnum 这样的词. 要打印整数枚举, 必须编写一个字典来映射每个枚举对应的字符串值.

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

AnimatedTexture vs. AnimatedSprite vs. AnimationPlayer vs. AnimationTree

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

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

1. 它在纹理的每个部分移动的速率(每秒帧数).

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

Godot的 VisualServer 按规定的速度依次绘制区块. 好消息是, 这并不涉及引擎部分额外的逻辑. 坏消息是, 用户几乎没有控制权.

另外请注意, AnimatedTexture 是一个 Resource, 与此处讨论的其他 Node 对象不同. 可以创建一个 Sprite 节点, 该节点使用 AnimatedTexture 作为其纹理. 或者(其他方法做不到的)可以将 AnimatedTexture 作为图块, 添加到一个 TileSet 中, 并将其与 TileMap 集成在一起, 以获得许多自动动画化的背景, 所有的渲染将在单个批处理内绘制调用.

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

如果需要触发与动画更改相关的其他效果(例如, 创建粒子效果, 调用函数, 或操作除基于帧的动画外的其他外围元素), 那么就需要使用一个 AnimationPlayer 节点与 AnimatedSprite 关联.

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

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

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

3. 综上所述.

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