游戏设计模式 #8 优化型设计模式与其他资料

作者:浅墨
2017-03-10
5 2 1

本系列可在专题游戏设计模式查看。

优化型模式 Optimization Patterns

这一部分,描述了几个优化和加速游戏的中间层模式:

  • 数据局部性介绍了计算机的存储层次以及如何使用其以获得优势。
  • 脏标识帮我们避开不必要的计算。
  • 对象池帮我们避开不必要的分配。
  • 空间分区加速了虚拟世界和其中内容的空间布局。

数据局部性模式 Data Locality

合理组织数据,充分使用CPU的缓存来加速内存读取。

要点
  • 现代的CPU有缓存来加速内存读取,其可以更快地读取最近访问过的内存毗邻的内存。基于这一点,我们通过保证处理的数据排列在连续内存上,以提高内存局部性,从而提高性能。
  • 为了保证数据局部性,就要避免的缓存不命中。也许你需要牺牲一些宝贵的抽象。你越围绕数据局部性设计程序,就越放弃继承、接口和它们带来的好处。没有银弹,只有权衡。
使用场合
  • 使用数据局部性的第一准则是在遇到性能问题时使用。不要将其应用在代码库不经常使用的角落上。 优化代码后其结果往往更加复杂,更加缺乏灵活性。
  • 就本模式而言,还得确认你的性能问题确实由缓存不命中而引发的。如果代码是因为其他原因而缓慢,这个模式自然就不会有帮助。
  • 简单的性能评估方法是手动添加指令,用计时器检查代码中两点间消耗的时间。而为了找到糟糕的缓存使用情况,知道缓存不命中有多少发生,又是在哪里发生的,则需要使用更加复杂的工具 —— profilers。
  • 组件模式是为缓存优化的最常见例子。而任何需要接触很多数据的关键代码,考虑数据局部性都是很重要的。
引申与参考
  • Tony Albrecht的《Pitfalls of Object-OrientedProgramming》是传播广泛的内存友好设计游戏指南。PDF下载
  • Noel Llopis一篇博客,也分析了内存友好的游戏设计。
  • 本节内容相关的英文原文
  • 本节内容相关的中文翻译

脏标识模式 Dirty Flag

将工作延期至需要其结果时才去执行,以避免不必要的工作。

要点
  • 脏标记,就是用来表示被标记的内容是否有被修改过的一个标志位。
  • 脏标识模式:考虑情况,当前有一组原始数据随着时间变化而改变。由这些原始数据计算出目标数据需要耗费一定的计算量。这个时候,可以用一个脏标识,来追踪目前的原始数据是否与之前的原始数据保持一致,而此脏标识会在被标记的原始数据改变时改变。那么,若这个标记没被改变,就可以使用之前缓存的目标数据,不用再重复计算。反之,若此标记已经改变,则需用新的原始数据计算目标数据。
使用场合
  • 就像其他优化模式一样,此模式会增加代码复杂度。只在有足够大的性能问题时,再考虑使用这一模式。
  • 脏标记在这两种情况下适用:
    • 当前任务有昂贵的计算开销
    • 当前任务有昂贵的同步开销。

若满足这两者之一,也就是两者从原始数据转换到目标数据会消耗很多时间,都可以考虑使用脏标记模式来节省开销。

  • 若原始数据的变化速度远高于目标数据的使用速度,此时数据会因为随后的修改而失效,此时就不适合使用脏标记模式。
引申与参考
  • 脏标记模式在游戏外的领域也是常见的,比如像Angular这种browser-side web框架,其利用赃标记来跟踪浏览器中变动的数据以及需要提交到服务端的数据。
  • 本节内容相关的英文原文
  • 本节内容相关的中文翻译

对象池模式 Object Pool

放弃单独地分配和释放对象,从固定的池中重用对象,以提高性能和内存使用率。

要点
  • 对象池模式:定义一个包含了一组可重用对象的对象池。其中每个可重用对象都支持查询“使用中”状态,说明它是不是“正在使用”。 对象池被初始化时,就创建了整个对象集合(通常使用一次连续的分配),然后初始化所有对象到“不在使用中”状态。
  • 当我们需要新对象时,就从对象池中获取。从对象池取到一个可用对象,初始化为“使用中”然后返回给我们。当不再需要某对象时,将其设置回“不在使用中”状态。 通过这种方式,便可以轻易地创建和销毁对象,而不必每次都分配内存或其他资源。
使用场合
  • 这个模式广泛使用在可见事物上,比如游戏物体和特效。但是它也可在不那么视觉化的数据结构上使用,比如正在播放的声音。
  • 满足以下情况可以使用对象池:
    • 需要频繁创建和销毁对象。
    • 对象大小相仿。
    • 在堆上分配对象缓慢或者会导致内存碎片。
    • 每个对象都封装了像数据库或者网络连接这样很昂贵又可以重用的资源。
引申与参考
  • 对象池模式与GOF设计模式中享元模式类似。 两者都控制了一系列可重用的对象。不同在于重用的含义。
    • 享元对象分享实例间同时拥有的相同部分。享元模式在不同上下文中使用相同对象避免了重复内存使用。
    • 对象池中的对象也被重用了,但是是在不同的时间点上被重用的。重用在对象池中意味着对象在原先的对象用完之后再分配内存。对象池的对象不会在它的生命周期中与其他对象共享数据。
  • 将内存中同样类型的对象进行整合,能确保在遍历对象时CPU缓存是满载的。这便是数据局部性模式中介绍的内容。
  • 本节内容相关的英文原文
  • 本节内容相关的中文翻译

空间分区模式 Spatial Partition

将对象存储在基于位置组织的数据结构中,来有效的定位对象。

要点
  • 对于一系列对象,每个对象都有空间上的位置。将它们存储在根据位置组织对象的空间数据结构中,让我们有效查询在某处或者附近的对象。 当对象的位置改变时,更新空间数据结构,这样它可以继续找到对象。
  • 最简单的空间分区:固定网格。想象某即时战略类游戏,一改在单独的数组中存储我们的游戏对象的常规思维,我们将它们存到网格的格子中。每个格子存储一组单位,它们的位置在格子的边界内部。当我们处理战斗时,一般只需考虑在同一格子或相邻格子中的单位,而不是将每个游戏中的单位与其他所有单位比较,这样就大大节约了计算量。
使用场合
  • 空间分区模式在需要大量存储活跃、移动的游戏物体,和静态的美术模型的游戏中比较常用。因为复杂的游戏中不同的内容有不同的空间划分。
  • 这个模式的基本适用场景是你有一系列有位置的对象,当做了大量通过位置寻找对象的查询而导致性能下降的时候。
  • 空间分区的存在是为了将O(n)或者O(n²) 的操作降到更加可控的数量级。 你拥有的对象越多,此模式就越好用。相反的,如果n足够小,也许就不需要使用此模式。
引申与参考
  • 了解了空间分区模式,下一步应该是学习一下常见的结构,比如:
  • Bounding volume hierarchy 每种空间划分数据结构基本上都是将一维数据结构扩展成更高维度的数据结构。而了解它的直系子孙,有助于分辨其对当前问题的解答是不是有帮助:
  • 本节内容相关的英文原文
  • 本节内容相关的中文翻译

更多参考与学习资源