写点什么

用 manim 写一个排序算法动画

作者:ooooooh灰灰
  • 2022 年 8 月 11 日
    浙江
  • 本文字数:3120 字

    阅读完需:约 10 分钟

用 manim 写一个排序算法动画

本文不介绍 manim 的安装教程,需要安装教程的请参考:https://docs.manim.org.cn/getting_started/installation.html

什么是 manim

Manim 是一个用于精确编程动画的引擎,专为创建解释性数学视频而设计。


注意,有两个主要版本的 manim。该存储库最初是 3Blue1Brown 的作者的个人项目,目的是为这些视频制作动画,此处提供了视频专用代码。2020 年,一群开发人员将其分叉成现在的社区版,目标是更稳定、更好地测试、更快地响应社区贡献,以及更友好地开始使用。


主要版本如下:


冒泡排序介绍

本文就使用 manim 来实现一个冒泡排序的动画,首先来了解下什么是冒泡排序


冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

算法步骤

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

  3. 针对所有的元素重复以上的步骤,除了最后一个。

  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

初始化元素

比如我们需要排序数组为: [4,2,3,1,5]


首先,需要在 manim 场景上初始化我们的需要排序的所有元素,这里用矩形来表示。


在 manim 中,可以用 Rectangle 来初始化矩形,然后我们通过设置元素不同的高度来表示不同的元素大小。


  • main.py


from manimlib import *
class Test(Scene): def construct(self): COLOR = [BLUE, GREEN, RED, PINK, ORANGE, MAROON_B, TEAL, PURPLE_B, GREY_BROWN] arr = [4,2,3,1,5] g = VGroup() for i in range(len(arr)): r1=Rectangle(width=1,height=arr[i],fill_color=COLOR[i%len(COLOR)],fill_opacity=1) t1=Text(str(arr[i])).scale(0.5) rec = VGroup(r1,t1) g.add(rec) g.arrange(RIGHT,aligned_edge=DOWN) self.add(g) self.wait()
复制代码


使用下面的命令运行上面的代码:


manimgl main.py BubbleSort
复制代码


ManimGL v1.6.1[11:27:18] INFO     Using the default configuration file, which you can modify in `/Users/zheng/anaconda3/envs/manim/lib/python3.10/site-packages/manimlib/default_config.yml`                                                                                         config.py:265           INFO     If you want to create a local configuration file, you can create a file named `custom_config.yml`, or run `manimgl --config`                                                                                                                       config.py:266[11:27:20] INFO     Tips: You are now in the interactive mode. Now you can use the keyboard and the mouse to interact with the scene. Just press `q` if you want to quit.
复制代码


运行后,就会出现一个窗口显示如下画面。


代码说明

上面代码中,通过继承父类 Scene 然后重新父类的 construct 来构建一个场景。


然后在场景中添加了矩形(Rectangle)和文本(Text),并且将这两个元素添加到了 VGroup 类中。


再用一个 VGroup 来包含所有的 VGroup,通过调用 arrange 方法来排列这些元素。第一个 RIGHT 参数表示所有元素向右依次排列,aligned_edge 表示对齐的边,这里我们传入 DOWN 将底边对齐。


最后使用 self.add() 方法把 VGroup 添加到场景中。


Rectangle 类定义了矩形的创建,更多图形可以查看 https://docs.manim.org.cn/documentation/mobject/geometry.html#tipablevmobject

元素交换动画

通过算法步骤的第一步:比较相邻的元素。如果第一个比第二个大,就交换他们两个。就涉及到了交换的动画。


一开始,我用 manim 提供的 CyclicReplace 方法来交换两个元素。效果如下:


self.play(CyclicReplace(g[0], g[1]))self.wait()
复制代码



交换是交换了,但是交换后对齐的边变成了顶部对齐了,不符合预期。于是继续查看文档,最终决定使用元素的 target 属性来进行交换动画的制作。


上面我们要交换 g(0)g(1) 两个元素,所以我们定义这两个交换元素的 target


g[0].generate_target()g[0].target.next_to(g[1],ORIGIN,aligned_edge=DOWN)
g[1].generate_target()g[1].target.next_to(g[0],ORIGIN,aligned_edge=DOWN)
复制代码


generate_target() 表示生成元素的 target, next_to() 表示将元素移动到指定的位置。


比如 g[0],我们先生成元素的 target,然后操作 target 将元素通过 next_to 方法移动到 g[1] 的位置。其中 ORIGIN 表示 g[1] 的所在位置。我们对 g[1] 的元素也做类似的操作。


然后使用 MoveToTarget 来将元素转换到定义的 target 上,通过调用 self.play() 方法来播放动画。


self.play(MoveToTarget(g[0]),MoveToTarget(g[1]))
复制代码



嗯~完美符合预期。

实现代码

根据上面的知识点,接下来就可以编写一个冒泡排序的动画了。


这里在初始化场景元素时,额外添加了一个数组来存放所有场景元素,因为在交换元素位置后,也要交换对应索引下的元素,如果直接用 VGroup 来交换时,会出现问题。


    self.g[j],self.g[j+1] = self.g[j+1],self.g[j]TypeError: 'VGroup' object does not support item assignment
复制代码


所以用额外的数组去接收。


还添加了一个 Indicate 方法,当涉及到对应交换的元素时,会做一个类似对焦的动作。


from manimlib import *
class BubbleSort(Scene): def construct(self): self.COLOR = [BLUE, GREEN, RED, PINK, ORANGE, MAROON_B, TEAL, PURPLE_B, GREY_BROWN] self.bubbleSort([4,2,3,1,5]) def init_vmobj(self,arr): ''' 初始化场景元素 ''' self.vmArr = [] g = VGroup() for i in range(len(arr)): r1=Rectangle(width=1,height=arr[i]/2,fill_color=self.COLOR[i%len(self.COLOR)],fill_opacity=1) t1=Text(str(arr[i])).scale(0.5) rec = VGroup(r1,t1) self.vmArr.append(rec) g.add(rec) g.arrange(RIGHT,aligned_edge=DOWN) self.add(g) self.wait() def bubbleSort(self,arr): ''' 冒泡排序 ''' self.init_vmobj(arr) for i in range(1, len(arr)): for j in range(0, len(arr)-i): self.play(Indicate(self.vmArr[j])) self.play(Indicate(self.vmArr[j+1],color=RED)) if arr[j] > arr[j+1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] self.cyc_move(self.vmArr[j],self.vmArr[j+1]) self.vmArr[j],self.vmArr[j+1] = self.vmArr[j+1],self.vmArr[j] return arr def cyc_move(self,vm1,vm2): ''' 交换两个元素位置 ''' vm1.generate_target() vm1.target.next_to(vm2,ORIGIN,aligned_edge=DOWN)
vm2.generate_target() vm2.target.next_to(vm1,ORIGIN,aligned_edge=DOWN)
self.play(MoveToTarget(vm1),MoveToTarget(vm2)) self.wait()
复制代码



发布于: 17 小时前阅读数: 44
用户头像

ooooooh灰灰

关注

不干活,就没饭吃 2021.07.15 加入

高级社会打工码农,专注后端技术

评论

发布
暂无评论
用 manim 写一个排序算法动画_算法_ooooooh灰灰_InfoQ写作社区