数据首选项

有没有想过用数据结构y或z来处理问题x？本文涵盖了与这些困境相关的各种主题。

注解

这篇文章提到 [某物] -时间”操作。这个术语来自算法分析。 Big O Notation .

长话短说，它描述了运行时长度的最坏情况。用外行的术语来说：

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

  • 恒定时间， O(1) ：“…不增加。”

  • 对数时间， O(log n) ：“…缓慢增长。”

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

  • 等。

想象一下，如果必须在一个帧内处理300万个数据点。用线性时间算法来处理这个特性是不可能的，因为数据的绝对大小会使运行时间大大超过分配的时间。相比之下，使用恒定时间算法可以处理操作而不产生问题。

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

数组与字典与对象

godot将脚本API中的所有变量存储在 Variant 类。变量可以存储变量兼容的数据结构，例如 Array 和 Dictionary 以及 Object S.

Godot将数组实现为 Vector<Variant> . 引擎将数组内容存储在内存的连续部分中，即它们彼此相邻的一行中。

注解

对于那些不熟悉C++的人来说，向量是传统C++库中数组对象的名称。它是一个“模板化”类型，这意味着它的记录只能包含一个特定的类型（用尖括号表示）。例如，一个 PoolStringArray 会有点像 Vector<String> .

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

  • 迭代： 最快的。适合打圈。

    • OP：它所做的就是增加一个计数器以到达下一个记录。

  • 插入、擦除、移动： 位置相关。一般比较慢。

    • 操作：添加/删除/移动内容涉及移动相邻记录（以留出空间/填充空间）。

    • 快速添加/删除 从最后 .

    • 缓慢添加/删除 从任意位置 .

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

    • 如果进行多次插入/移除 从前面 ，然后…

      1. 反转数组。

      2. 执行数组更改的循环 最后 .

      3. 重新反转数组。

      这只复制了数组的两个副本（虽然时间不变，但速度较慢），而复制了大约1/2的数组，平均为n次（线性时间）。

  • 获取，设置： 最快的 按职位 . 例如，可以请求第0、第2、第10条记录等，但不能指定所需的记录。

    • 操作：1个从数组开始位置到所需索引的加法操作。

  • 查找： 最慢。标识值的索引/位置。

    • op：必须遍历数组并比较值，直到找到匹配项为止。

      • 性能还取决于是否需要彻底搜索。

    • 如果保持有序，自定义搜索操作可以使其达到对数时间（相对较快）。不过，外行用户对此并不满意。通过在每次编辑和编写顺序感知搜索算法后对数组重新排序来完成。

Godot把字典作为 OrderedHashMap<Variant, Variant> . 引擎存储一个巨大的键值对数组（初始化为1000条记录）。当一个人试图访问一个值时，他们会提供一个键。然后*散列* 键，即将其转换为数字。“hash”成为数组的索引，使ohm可以快速查找映射到值的键的概念“表”中的值。

散列是为了减少密钥冲突的可能性。如果发生这种情况，该表必须为考虑到上一个位置的值重新计算另一个索引。总的来说，这会导致对所有记录的持续时间访问，代价是内存和一些较小的操作效率。

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

    • 散列操作是一个固定的时间，所以即使一个算法必须执行不止一个，只要散列计算的数量不太依赖于表的密度，事情就会保持快速。这导致…

  2. 保持桌子的大尺寸。

    • 它从1000条记录开始，强制表中散布大量未使用的内存间隙的原因是为了最小化哈希冲突并保持访问速度。

可以看出，字典专门处理数组没有的任务。它们的操作细节概述如下：

  • 迭代： 快。

    • op：迭代映射的哈希内部向量。返回每个键。然后，用户使用键跳转到并返回所需的值。

  • 插入、擦除、移动： 最快的。

    • op：散列给定的键。执行1个加法操作以查找适当的值（数组开始+偏移）。移动是其中的两个（一个插入，一个擦除）。地图必须进行一些维护以保持其功能：

      • 更新记录的有序列表。

      • 确定表密度是否要求扩展表容量。

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

  • 获取，设置： 最快的。与查找相同 按密钥 .

    • 操作：与插入/擦除/移动相同。

  • 查找： 最慢。标识值的键。

    • op：必须遍历记录并比较值，直到找到匹配项为止。

    • 请注意，Godot不提供这种现成的功能（因为它们不是用于此任务的）。

Godot将对象实现为愚蠢但动态的数据内容容器。对象在提出问题时查询数据源。例如，要回答这个问题，“您有一个名为‘position’的属性吗？”可能会问 script 或 ClassDB . 您可以找到关于对象是什么以及它们如何在 Godot场景和脚本是类 文章。

这里的重要细节是对象任务的复杂性。每次它执行这些多源查询之一时，都会通过 几个 迭代循环和哈希图查找。此外，查询是线性时间操作，取决于对象的继承层次结构大小。如果对象查询的类（其当前类）找不到任何内容，则请求将一直延迟到下一个基类，直到原始对象类为止。虽然这些都是孤立的快速操作，但事实上，它必须进行如此多的检查，这使得它们比查找数据的两个备选方案都慢。

注解

当开发人员提到脚本API的速度有多慢时，他们所指的就是这个查询链。与编译的C++代码相比，应用程序准确地知道去哪里查找任何东西，脚本编写操作不可避免地需要更长的时间。他们必须找到任何相关数据的来源，然后才能尝试访问它。

gdscript运行缓慢的原因是它执行的每一个操作都会通过这个系统。

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

NaseScript C++更进一步，默认情况下保持内部所有。对外部结构的调用将通过脚本API进行。在NATScript脚本C++中，注册方法将它们暴露给脚本API是一项手动任务。此时，外部的非C++类将使用API来定位它们。

所以，假设一个从引用扩展到创建数据结构，比如数组或字典，为什么选择一个对象而不是其他两个选项？

  1. 控制： 有了对象，就可以创建更复杂的结构。可以在数据上分层抽象，以确保外部API不会随着内部数据结构的变化而变化。而且，对象可以有信号，允许反应行为。

  2. 清晰： 当涉及到脚本和引擎类为其定义的数据时，对象是可靠的数据源。属性可能不包含人们期望的值，但首先不需要担心属性是否存在。

  3. 方便性： 如果一个人已经有了一个类似的数据结构，那么从一个现有的类进行扩展可以使构建数据结构的任务更加容易。相比之下，数组和字典并不能满足人们可能拥有的所有用例。

对象还让用户有机会创建更专业的数据结构。使用它，可以设计自己的列表、二进制搜索树、堆、展开树、图、不相交集以及其他任何选项。

“为什么不将节点用于树结构？”有人可能会问。好吧，node类包含与自定义数据结构无关的内容。因此，在构建树结构时，构建自己的节点类型是很有帮助的。

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

从这里开始，人们就可以用特定的特性来创建他们自己的结构，而这些特性只受他们想象力的限制。

枚举：int与string

大多数语言都提供枚举类型选项。gdscript没有什么不同，但与大多数其他语言不同，它允许使用整数或字符串作为枚举值。然后问题就出现了，“应该使用哪一种？”

简短的回答是，“你更喜欢哪个。”这是一个特定于gdscript的特性，而不是一般的godot脚本；语言将可用性优先于性能。

在技术层面上，整数比较（常量时间）将比字符串比较（线性时间）发生得更快。如果你想保持其他语言的约定，那么你应该使用整数。

使用整数的主要问题出现在人们想要 打印 枚举值。作为整数，尝试打印我的枚举将打印 5 或者你有什么，而不是像 "MyEnum" . 要打印整数枚举，必须编写一个字典，为每个枚举映射相应的字符串值。

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

动画纹理vs.动画精灵vs.动画播放器vs.动画树

在什么情况下应该使用Godot的动画课程？对于新的godot用户来说，答案可能不是很清楚。

AnimatedTexture 是引擎作为动画循环而不是静态图像绘制的纹理。用户可以操作…

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

  2. 纹理（帧）中包含的区域数。

Godot的 VisualServer 然后按指定的速率顺序绘制区域。好消息是，这不涉及引擎部分的额外逻辑。坏消息是用户几乎没有控制权。

还要注意动画纹理是 Resource 不同于另一个 Node 这里讨论的对象。可能会创建一个 Sprite 使用动画纹理作为其纹理的节点。或者（其他人做不到的）一个人可以在 TileSet 并将其与 TileMap 对于许多自动设置动画的背景，这些背景都在一次批处理的绘制调用中呈现。

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

如果需要触发与动画更改相关的其他效果（例如，创建粒子效果、调用函数或操纵基于帧的动画之外的其他外围元素），则需要使用 AnimationPlayer 与动画精灵一起使用的节点。

如果想设计更复杂的二维动画系统，比如……

  1. Cut-Out animations: 在运行时编辑精灵的转换。

  2. 二维网格动画： 为精灵的纹理定义一个区域，并为其装配骨架。然后一个动画骨骼拉伸和弯曲纹理的比例骨骼的相互关系。

  3. 上面的混合。

虽然一个人需要一个动画播放器来为一个游戏设计每一个单独的动画序列，但是将动画组合起来进行混合也很有用，即在这些动画之间实现平滑的过渡。在动画之间也可能有一个层次结构，为他们的对象规划。这些情况下 AnimationTree 闪耀。您可以找到有关使用动画树的深入指南。 here .