数据偏好

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

注解

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

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

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

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

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

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

  • 等等.

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

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

数组VS字典VS对象

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

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

注解

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

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

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

    • 运行:它所做的就是增加一个计数器,以得到下一个记录.

  • 插入、删除、移动:依赖于位置.一般慢.

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

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

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

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

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

      1. 反转数组.

      2. 执行一个循环,该循环 在末尾 执行数组更改.

      3. 重新反转数组.

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

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

    • 操作:从数组起始位置到所需索引的1个加法运算.

  • 查找:最慢.识别一个数值的索引/位置.

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

      • 性能也取决于是否需要一个详尽的搜索.

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

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#

  1. extends Object
  2. class_name TreeNode
  4. var _parent : TreeNode = null
  5. var _children : = [] setget
  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. // Can decide whether to expose getters/setters for properties later
  2. public class TreeNode : Object
  3. {
  4.     private TreeNode _parent = null;
  6.     private object[] _children = new object[0];
  8.     public override void Notification(int what)
  9.     {
  10.         if (what == NotificationPredelete)
  11.         {
  12.             foreach (object child in _children)
  13.             {
  14.                 TreeNode node = child as TreeNode;
  15.                 if (node != null)
  16.                     node.Free();
  17.             }
  18.         }
  19.     }
  20. }

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

枚举:整数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 的深入指南.