算法动画设计模式：反向播放和概念解耦

理论计算机科学电子笔记224（2009）67-76www.elsevier.com/locate/entcs算法动画的第一组设计模式GuidoRüoßling1达姆施塔特工业大学德国达姆施塔特摘要设计模式在防止程序员“重新发明轮子”方面非常有帮助。 然而，算法动画区域似乎还没有任何设计模式，尽管在许多系统中有几个设计问题需要解决。我们提出了两个设计模式，解决了两个中心点，在可伸缩的算法动画系统：反向播放和概念解耦，以方便扩展。关键词：设计模式，算法动画，双向导航，解耦1引言计算机科学背景下的设计模式可以追溯到[4]的书，该书将架构师ChristopherAlexander的原始概念映射到软件开发中。这本书提供了解决问题的方法，这些问题可能会出现在几个不同的应用程序中，通过遵循相同的基本对于算法可视化（以下简称为AV），我们无法找到对正在使用的设计模式的“真实”描述，尽管许多系统面临的问题也是类似的。例如，用户通常会发现能够通过可视化后退是很有趣甚至很重要的[2]，而没有（对他们来说）任意限制，例如有限的撤销堆栈。此外，后退的过程应该相当快。由于没有一个AV系统可能是真正“完整”的，因此需要提供引入扩展或重新配置的方法。感兴趣的开发人员应该发现，包含一个新的原语或数据结构、提供一个新的1电子邮件：roessling@acm.org1571-0661/© 2008 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2008.12.05068G. Rößling/Electronic Notes in Theoretical Computer Science 224（2009）67动画效果或状态转换，或者两者都做。但是，这应该是可能的，而不需要强迫开发人员同时处理所有事情。此外，开发人员可能没有--或者甚至不想有--对底层系统的更深入的理解。因此，不应强迫他或她修改现有的组成部分，因为这会降低“只提供一个小改动”的动机在本文中，我们定义了两个初始AV模式，希望它们能服务于作为第二节简要总结了设计模式的主要内容。第3节介绍了一种在两个方向上都可以轻松导航的模式， 撤消堆栈。第4节介绍了一种模式，用于在不触及其他部分的情况下扩展AV系统的不同方面。第五部分总结了本文中的模式，并概述了未来AV相关模式的研究方向。2设计模式简介设计模式描述了在我们环境的不同部分多次出现的问题。通过描述问题解决方案的核心，可以使用相同的基本方法来解决问题，尽管实际代码每次都很可能不同[4，p.2]。 一个设计模式，正如在基础书中所描述的，[4]它有五个基本要素：模式名称用于引用模式。它提供了对所指内容的共同理解，假设所有读者都熟悉给定的模式。intent在一个句子中描述了模式的意图问题是对模式所处理的情况的描述解决方案描述了可用于解决问题的组件。它并不描述具体的实现，而是描述用于实现具体实现的元素，以便更容易地重用和调整。结果描述了应用模式的结果和权衡。虽然模式的使用可能会增加软件的可扩展性，但它也可能会影响运行时或所需的内存量[4]的书中提到了模式的许多其他方面可以讨论，例如动机和示例代码。 但是，我们不会严格遵守 为了清楚和简洁起见，我们将使用模式名称作为部分的名称。其他元素将显示为子部分。3通过Fast Forward实现3.1意图通过快进反向支持灵活的无限双向导航。G. Rößling/Electronic Notes in Theoretical Computer Science 224（2009）67693.2问题在算法的可视化期间，用户可能在某个阶段变得困惑。此外，用户编写的算法的可视化可能会显示需要跟踪到其起源的错误。这两种情况都受益于轻松返回到前一步或前几步的能力。在这里，一个步骤被认为是一个封闭的操作集，这些操作发生在相同的基本时间，并代表完整的操作。因此，物体沿着直线的一次移动将总是恰好是一步的一部分，即使它是使用一组中间动画帧来呈现的。但是，下一步可能包含同一对象的另一个移动支持后退的标准方法是保留先前可视化状态的撤消堆栈。在某些系统中，这可能是静态图像的堆栈，而其他系统需要存储完整的对象表示。这两种情况通常都受到为堆栈保留的内存量的限制，并且可能进一步受到所显示内容的大小的限制。例如，覆盖200个动画步骤的动画可能需要存储199个先前步骤状态以用于撤消。如果要存储中间动画帧，则数量会非常迅速地上升。如果撤消堆栈试图通过动画镜像用户的移动，并且因此可能必须在用户通过动画后退时多次存储相同的中间状态，则情况也是如此研究论文[8，7]中也讨论了能够导航回显示器中易于理解的步骤的重要性。 然而，要找到一个快速和任意导航的一个很好的解决方案，正如“有效倒带是AV中最开放的问题之一”的声明所示3.3溶液我们使用一种称为“快进反向”的技术，这是作者和Amruth Kumar几年前在SIGCSE会议休息期间讨论时创造的一个术语。经典的撤销堆栈的主要限制已经在上面描述过了：它可能会很快达到固定的内存限制，消耗大量内存，并且可能会在不同的位置冗余地存储同一组对象。我们的建议可能看起来违反直觉：我们通过从AV内容中定义明确的位置快速向前移动来向后导航。类似的方法也用于反向调试和检查点[3]。要使这一方法发挥作用，必须满足以下条件• 内容必须具有一定的结构，例如单独的步骤，以便对“当前”和“上一步”以及“开始”进行有意义的定义。的内容。• 对象和转换必须以允许多次执行的方式进行编码，并始终产生相同的结果。在实践中，即使在操作执行之后，也可以存储操作的副本70G. Rößling/Electronic Notes in Theoretical Computer Science 224（2009）67approach.• 必须存储两组对象：在动画中最初定义的原始对象，以及这些对象的一组克隆对象。因此，该方法需要两倍于普通方法所需的内存来存储对象。• 图形对象的变换可以由系统可视化，但也可以在不执行任何可视化代码的情况下“快速”执行系统将执行以下步骤，而不是对原始对象执行给定的操作或动画步骤(i) 确定用户想要到达的动画步骤(ii) 确保所选步骤实际存在。 在手动步骤输入的情况下， 用户可以提供不存在的步骤号，或者可以向前导航超过动画的结束或向后导航超过动画的开始。 如果所选步骤不存在，请在此阶段停止(iii) 克隆所有原始图形对象并将其放置在适当的数据结构中，例如哈希表或列表。(iv) 对于初始状态和目标步骤之间的所有步骤，在克隆的图形对象上快速执行所有转换，而不可视化效果。(v) 一旦达到目标阶跃，恢复正常操作。在大多数情况下，在对象上执行实际转换而不创建任何可视化内容或更新显示，视觉化ANUMEROUS系统的实际经验[6]表明，按下“后退”或“前进”按钮和显示更新之间的间隙为了提高显示的性能，还可以存储来自先前动画步骤的克隆。如果用户请求显示下一步，则可以跳过项目列表的前四个步骤，直接继续执行。此外，在某些时间间隔的步骤的快照（例如，每十步）也可以以支持更快的导航。然而，这也将增加所需的内存量，并且如果用户主动编辑动画，可能会严重损害动画速度，迫使系统不断更新“快照”-在其他应用领域中不会发生的情况[3]。如果动画效果被适当地编码，则任意动画步骤也可以在相反方向上动态地执行这是用于自动驾驶AV系统[6]，以允许完全灵活的双向导航，即使在步骤内，让由于该模式只需要存储原始对象和克隆对象，没有给出UML图3.4后果快进反转模式有一系列后果：G. Rößling/Electronic Notes in Theoretical Computer Science 224（2009）6771• 用户可以随时跳转到动画中的任意点。 它们不限于下一个或上一个步骤，预定义的点（如开始，结束）或有限数量的步骤被逆转。• 即使是对象销毁操作（如缩放0或乘以0）也可以• 应用程序使用的内存量增加，因为每个图形对象必须存储两次。 由于克隆必须在每个步骤中制备（参见3.在上面的列表中），这还可能导致增加的内存碎片和垃圾收集，这可能会影响运行时。4请求处理器4.1意图请求控件从图形对象中提取动画效果，使两者更灵活，更易于扩展。4.2问题在AV和常规图形系统中，用户通常具有（至少）两个不同的抽象：图形对象和动画或编辑效果。图形对象可以是基本的，如文本或正方形，也可以是复杂的，如数组或者一棵树它们还可以为某些操作封装特殊的语义，或提供特定于对象的行为。例如，将表示透射光的圆的填充颜色更改为红色与仅为“正常”圆着色不同;交换元素需要适当的视觉再现，以便最终用户可以轻松看到。通常，图形对象负责存储它们的当前状态，并且可以被请求绘制它们自己。 动画效果负责更改图形对象，还可以选择使用定时指定，例如在效果开始之前等待的时间或其总持续时间。感兴趣的开发人员应该能够实现一个新的图形对象与触摸现有的动画效果。它们还应该能够添加新的动画对象，而不必修改现有的图形对象，并且应该能够避免在这些实体之间提供硬链接。最后，仅在小方面不同的现有动画效果应该是可修改的，而不必触及动画效果。 例如，如果存在用于改变颜色的动画效果，则不需要实现一个标准的方法是结合一个设计，如MVC（模型，视图，控制器），其中模型是图形对象，控制器的角色是由动画效果，视图是对象的图形再现。然而，这并不提供上述必要的解耦。所描述的模式的意图也类似于[ 5 ]所描述的然而，他们的方法（和其他相关方法）需要72G. Rößling/Electronic Notes in Theoretical Computer Science 224（2009）67Java中没有的特殊mixin特性。 相关的其他方法，在[9]中，需要Java泛型，因此需要在单独的类中显式实现4.3溶液使用请求转换模式拦截图形对象和转换对象之间的直接交互，如图1所示。在这里，ActualModel实体表示图形对象。它知道自己的当前状态，因此可以回答相关代理的请求。Fig. 1. 请求队列架构图1中的Modifier是动画效果。它需要知道可以在所选图形对象上执行的操作。比如说，一般的最后，该对象充当两个实体之间的中间对象。它可以通过HandlerExtension的子类进一步细化。该公司只列出了四种方法：addExtensionMethodsFor查找在一个（可能是多个）HandlerExtension对象中实现的现有扩展方法，并将它们添加到getMethods返回的Vector中。getMethods返回ActualModel和传入参数调用insertHandlerExtension以添加新的HandlerExtension。当到达新的动画阶段时，modifier会调用propertyChange请注意，在SQL接口中的四个方法中，只有两个实际上与请求处理有关，而其他两个则不支持扩展。现在，协商给定属性的更改的工作方式如下。 为了为了清楚起见，我们假设用户想要改变一个圆对象的填充颜色，并且ActualModel圆和Modifier颜色改变器都已经存在。请参见图2，以了解该过程的说明(i) Modifier调用getMethods（myCircle，x），其中x是描述要更改的属性在我们的例子中，这可以是任意的G. Rößling/Electronic Notes in Theoretical Computer Science 224（2009）6773java.awt.Color实例。(ii) 由于Color参数传入，所以该函数(iii) 查询器查询ActualModel的当前状态。通过这种方式，处理程序请求可以检测圆是否被填充，并因此可以更改其轮廓和填充颜色，或者是否只能调整轮廓颜色(iv) 该函数将一个包含适当操作名称的Vector返回给Modifier，允许用户选择一个。在我们的示例中，Vector可能包含操作名称图二、谈判可能的转换方法在稍后的某个时间，调用实际的效果。图3中说明了此过程，并在接下来的两段中进行了描述首先，Modifier根据初始状态（原始填充颜色）、目标状态（目标填充颜色）和当前时间（已通过的效果百分比）确定当前状态，并对结果进行插值使用propertyChange方法将此更改后的值与ActualModel实例一起传递给EJB在我们的示例中，根据当前已达到的颜色变化效果的百分比，将值转换为沿原始颜色和所然后，转换器从传入的PropertyChangeEvent中提取目标状态和转换信息，PropertyChangeEvent 对 要 更 改 的 “ 属 性 ” 的 名 称 然 后 ， 它 将 此 更 改 映 射 到ActualModel上的一组（通常几乎是微不足道的）操作。例如，如果方法名为请求代理模式在概念上类似于适配器[4，第139页]和中介器[4，第139页]。273]设计模式，但在一组关键点的差异74G. Rößling/Electronic Notes in Theoretical Computer Science 224（2009）67图3.第三章。执行具体转换4.4后果请求验证模式具有以下后果：• ActualModel类与Modifier类解耦。在我们的例子中，这意味着图形对象不需要知道动画，一种内部状态的动态变化。它们只是响应改变其内部状态的请求（例如，通过改变填充颜色），并在提示时重新绘制自己。动画效果也不知道它们修改的实际对象，并且不需要处理特定对象类型的代码• 中心方法getMethods和propertyChange通常很容易实现。第一个需要根据转换类型，找出对于给定的具体ActualModel可能的操作集这通常很容易实现。后一个方法接收getMethods中生成的转换名称、要处理的ActualModel以及当前值和目标值。 将其映射到ActualModel上的适当操作通常也非常简单。对于• 由于ActualModel引用总是在需要的地方传递，因此对于每个图形对象类，可以将其实现为Singleton[4这是在AV系统中完成的。• 使用HandlerExtension，开发人员可以轻松地添加新的转换对象名称，而无需修改原始对象本身的代码• 可以将addExtensionMethodsFor和insertHandlerExtension方法的实现委托给实际EJB实例的超类，从而将每个EJB要实现的方法数量减少到两• 如果已经实现了新的图形对象，开发人员只需添加G. Rößling/Electronic Notes in Theoretical Computer Science 224（2009）6775用于此对象类型的对象。所有转换方法都可以直接用于新的图形对象，而不需要修改任何转换对象的代码。• 如果已经实现了新的转换效果，开发人员只需修改那些支持新效果的处理程序。然后，该结果可以直接用于图形对象，而无需修改它们的代码。• 如果给定图形对象的新转换子类型应得到支持，则开发人员只需向getMethods和proper- tyChange方法添加适当的代码。不需要改变转换对象或图形对象类。开发人员还可以将更改放入一个新的扩展中并注册它-在这种情况下，根本不会触及现有代码• 必须为每个图形对象添加一个额外的类（类）5总结与未来研究在本文中，我们提出了两种设计模式的AV相关的系统。通过快进的反向可用于支持AV材料中的高效双向导航。它非常容易实施，也适用于符合第3节要求的其他材料。根据我们的经验，即使在旧硬件上运行请求转换模式将图形对象及其上的转换为对象。它允许开发人员实现新的图形对象，而无需修改现有的转换，或者提供新的转换而无需修改图形对象的实现。 在熟悉了底层概念之后，请求管理器已被证明是非常有用的。这两种模式已在主动AV系统中使用多年。虽然掌握他们通常是困难的，首先为我们的学生实施新的他们在系统的实施阶段看到了好处在未来，我们希望其他的AV研究人员能够以设计模式的形式收集他们的这将最终帮助其他系统开发人员采用经过验证的技术，从长远来看，甚至可以使AV系统之间的数据交换更容易。引用[1] Akingbade，A.，T. Finley，D. Jackson，P. Patel and S. H. Rodger，JAWAA：基于Web的简易动画从CS 0到高级CS课程，见：第34届ACM SIGCSE计算机科学教育技术研讨会论文集（SIGCSE 2003），内华达州里诺市（2003），162比166[2] J. M.安德森和T. L. Naps，算法可视化系统作为教学工具的评估背景，第一届国际程序可视化研讨会，芬兰波尔沃。约恩苏大学出版社（2001），pp. 121-130[3] 布斯，B.，Eachcient algorithms for bidirectional debugging，in：PLDI299-310.76G. Rößling/Electronic Notes in Theoretical Computer Science 224（2009）67[4] 伽马，E.，R.赫尔姆河Johnson和J.Vlissides，“设计模式。可重用面向对象软件的元素，”Addison-Wesley，1995年。[5] Odersky，M.和M. Zenger，Independently extensible solutionstothe expression problem，in：Proc.FOOL12，2005，http://homepages.inf.ed.ac.uk/wadler/fool。[6] R？oßling，G.，“Anumber-Farm：AnExtensibleFrameWorkforAlgorithmVisualization，”VDMVerlagDr.Müller，2008.[7] R ？ oßling ， G.和 T. L. Naps ， ATest bedforP edagogiccalR equi rementsinAlgorithmVisualization s，Proceedings of the7thAnnual ACM SIGCSE / SIGCUE Conference on Innovation and TechnologyinComputerScienceEducation（ITiCSE2002），Denmark，Spain，Hus，Denmark（2002），pp. 96比100[8] R？oßling，G. 和T. L. 张文，《算法可视化中的个人支持》，第二届国际程序可视化研讨会，北京，中国（2002年），第100页。125-130[9] Torgersen，M.，重新讨论表达式问题，在：欧洲面向对象编程会议（ECOOP）会议记录，奥斯陆，挪威，2004年，pp. 123-143