数据偏好

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

注解

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

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

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

  • 常量时间,O(1):“…不会增加。”
  • 对数时间,O(log n):“…以缓慢的速度增长。”
  • 线性时间,O(n):“…以同样的速度增长。”
  • 等等。

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

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

数组VS字典VS对象

Godot将所有变量存储在 Variant 类的脚本API中。Variant 可以存储与 Variant 兼容的数据结构,例如 ArrayDictionary 以及 Object

Godot将数组实现为 Vector<Variant>。引擎将数组内容存储在一个连续的内存段中,也就是说,它们是连续相邻的。

注解

对于不熟悉C++的人来说,Vector 是传统C++库中数组对象的名称。它是一个“模板化”类型,这意味着它的记录只能包含特定的类型(用尖括号表示)。举个例子,一个 PoolStringArray 类似于一个 Vector<String>

连续的内存存储意味着以下操作性能:

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

    • 运行:它所做的就是增加一个计数器,以得到下一个记录。
  • 插入、删除、移动:依赖于位置。一般慢。

    • 运行:添加/删除/移动内容,涉及移动相邻的记录(腾出房间/填补空间)。

    • 快速的 从末尾 添加/删除。

    • 慢速的 从任意位置 添加/删除。

    • 最慢的 从前面 添加/删除。

    • 如果执行多次 从前面 插入/删除,那么…

      1. 反转数组。
      2. 执行一个循环,该循环 在末尾 执行数组更改。
      3. 重新反转数组。

      这只是复制了数组的两个副本(仍然是常数时间,但是速度很慢),大约复制了数组的1/2,平均N次(线性时间)。

  • 取值,设值按位置 最快。例如:可以请求第0、第2、第10条记录,诸如此类,但不能指定想要哪个记录。

    • 操作:从数组起始位置到所需索引的1个加法运算。
  • 查找:最慢。识别一个数值的索引/位置。

    • 操作:必须遍历数组并比较值,直到找到匹配的为止。

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

Godot implements Dictionary as an OrderedHashMap<Variant, Variant>. The engine stores a small array (initialized to 2^3 or 8 records) of key-value pairs. When one attempts to access a value, they provide it a key. It then hashes the key, i.e. converts it into a number. The "hash" is used to calculate the index into the array. As an array, the OHM then has a quick lookup within the "table" of keys mapped to values. When the HashMap becomes too full, it increases to the next power of 2 (so, 16 records, then 32, etc.) and rebuilds the structure.

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

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

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

    • 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 quadratically by powers of 2.

As one might be able to tell, Dictionaries specialize in tasks that Arrays do not. An overview of their operational details is as follows:

  • 迭代:快速。

    • 操作:遍历映射的内部散列向量。返回每个键。之后,用户使用该键跳转到并返回所需的值。
  • 插入,删除,移动:最快。

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

      • 更新记录的有序列表。
      • 确定列表密度,是否需要扩展列表容量。
    • 字典会记住用户插入键的顺序。这使它能够执行可靠的迭代。

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

    • 操作:和插入/删除/移动类似。
  • 查找:最慢。标识值的键。

    • 操作:必须遍历记录并比较该值,直到找到匹配的为止。
    • 请注意,Godot并未开箱即用地提供此功能(因为它们并非用于此任务)。

Godot用愚蠢、但动态的方式容纳数据容器实现对象。提出问题时,对象将查询数据源。例如,要回答“您是否有一个名为 position 的属性?”的问题,它可能会询问其 scriptClassDB。您可以在 Applying object-oriented principles in Godot 文章中,找到有关什么是对象以及它们如何工作的更多信息。

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

注解

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

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

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

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

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

  1. 控件:对象能够创建更复杂的结构。可以在数据上分层抽象,以确保外部API不会响应内部数据结构的更改。更重要的是,对象可以有信号,允许响应式行为。对象带来了创建更复杂结构的能力。
  2. 清晰:当涉及到脚本和引擎类为对象定义的数据时,对象是一个可靠的数据源。属性可能不包含期望的值,但是无需担心这个属性是否首先存在。
  3. 便利:如果已经有了类似的数据结构,之后从现有类扩展,可以使构建数据结构的任务变得容易得多。相比之下,数组和字典不能满足所有的用例。

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

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

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)
    {
        if (what == NotificationPredelete)
        {
            foreach (object child in _children)
            {
                TreeNode node = child as TreeNode;
                if (node != null)
                    node.Free();
            }
        }
    }
}

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

枚举:整数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 keyword in GDScript). The question then arises, "which should one use?"

简而言之,“你觉得哪个更舒服就选哪个。”这是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 的深入指南。