(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210402665.X (22)申请日 2022.04.18 (71)申请人 东北大学 地址 110819 辽宁省沈阳市和平区文化路 三号巷11号 (72)发明人 郭楠　丛欣宇　吕雅静　高天寒　 (74)专利代理 机构 沈阳东大知识产权代理有限 公司 21109 专利代理师 李珉 (51)Int.Cl. G06F 30/20(2020.01) G06F 9/451(2018.01) G06T 13/20(2011.01) G06F 16/957(2019.01) (54)发明名称 基于Unity的图灵 机虚拟仿真系统 (57)摘要 本发明提供一种基于Unity的图灵机虚拟仿 真系统， 涉及计算机虚拟仿真技术领域。 该系统 对图灵机进行建模， 设计图灵机进行读写及状态 转移的动作， 利用图灵机读写字符、 状态转移实 现对五种算法的仿真模拟， 最终以3D动画的形式 呈现出图灵机模拟算法的过程， 并记录图灵机读 写次数及所耗费纸带方格数来计算算法复杂 度。 利用图灵机模拟算法时， 对不同的算法设计了不 同的状态转移方程。 同时， 考虑到不同平台的设 备性能及运行环境各不相同， 为了提高使用便携 性， 基于WebGL技术将系统发布成WebGL形式。 该 系统不仅能够利用模拟多种经典算法的执行过 程， 而且还能够模拟递归函数调用过程， 实现了 图灵机算法模拟的功能。 权利要求书6页 说明书17页 附图9页 CN 114818300 A 2022.07.29 CN 114818300 A 1.一种基于Unity的图灵机虚拟仿真系 统， 其特征在于： 包括图灵机建模模块、 图灵机 读写动作与状态转移的设计模块、 UI设计模块、 状态 转移方程设计模块、 算法复杂度计算模 块和基于WebGL的优化模块； 所述图灵机建模模块根据任务需求基于Unity对图灵机进行建 模， 构建图灵机模型； 所述图灵机读写动作与状态转移的设计模块用于实现图灵机读写动 作和状态转移的设计； 所述UI设计模块用于设计图灵机的UI界面； 所述状态转移方程设计 模块计用于设计图灵机实现任务需求的状态转移方程， 进而通过图灵机完成任务需求； 所 述算法复杂度计算模块用于计算实现任务需求的算法复杂度； 所述基于WebGL的优化模块 将图灵机虚拟仿真系统发布成WebGL形式， 并在发布后利用node.js部署在服务器上， 最终 实现通过网页端能够 访问图灵 机虚拟仿真系统。 2.根据权利要求1所述的基于Unity的图灵机虚拟仿真系统， 其特征在于： 所述 图灵机 建模模块根据任务需求基于Un ity对图灵 机进行建模的具体方法为： 设定的图灵机任务需求为实现一元加法、 二分搜索图灵机算法、 二分搜索递归算法、 可 拆分背包 贪心算法和0 ‑1背包动态规划算法五种算法； 确定图灵 机的读写头及图灵 机框架模型； 利用3dsMax对图灵机的纸带、 读写头和有限状态自动 机进行建模； 建模后导出FB X模型 再导入Un ity赋予材质， 最终加以设计完成建模的工作； 在Unity中将利用3dsMax建模后的纸带、 读写头和有限状态自动 机各部分绑定在一起， 构成整体的图灵 机模型； 并添加显示自动机状态及纸带内容的text组件； 为了便于用户直观地观察到图灵机的工作过程， 将图灵机设计成三读写头和三纸带模 型， 包括输入读写头、 工作读写头、 输出读写头、 输入纸带、 工作纸带、 输出纸带、 自动机和状 态转移显示屏。 3.根据权利要求2所述的基于Unity的图灵机虚拟仿真系统， 其特征在于： 所述 图灵机 读写动作与状态转移的设计模块设计控制读写头脚本、 更新纸带内容脚本、 控制纸带移动 脚本、 状态转移脚本、 状态显示脚本、 模拟函数调用脚本以及单位时间访问数 组用于实现图 灵机读写动作和状态转移； 所述控制读写头脚本用于控制读写头上下移动仿真模拟读写操作； 首先在Unity场景 中创建一个空物体， 作为读写头移动的目标位置； 通过MoveTowards()函数给定读写头的 起始位置、 目标位置及步长， 实现改变读写头位置， 使得读写头在目标位置与起始 位置间往 复移动； 当读写头移动到目标位置时将向状态转移脚本发送信号开始进行状态转移， 当读 写头移动回初始位置时将向控制纸带移动脚本发送信号， 开始 移动纸带； 所述更新纸带内容脚本用于管理纸带上数据， 对外提供setBST()和getBST()两个接 口， setBST()通过给定写入位置与写入数据来修改纸带上目标位置元素， getBST()通过给 定指定位置来获取指 定位置上纸带数据； 每次得到状态转移脚本的更新纸带内容信号后进 行更新当前场景显示的纸带 数据； 所述控制纸带移动脚本用于控制纸带移动； 调用状态转移脚本提供的接口get I()通过 给定纸带名称来获取当前纸带应移动到的目标位置， 在收到移动纸带信号后开始移动纸 带， 移动到目标位置后发送信号给读写头使其 落下模拟下一次读写操作； 所述状态转移脚本用于控制图灵机状态转移和切换输入、 工作和输出纸带以及读写 头； 每次状态转移过程为， 首先修改当前纸带上 的内容， 然后再更新当前纸带位置， 之后发权　利　要　求　书 1/6 页 2 CN 114818300 A 2出信号允许纸带更新内容并使读写头升起回到初始位置， 最后移动纸带、 选定下个状态所 用纸带， 并且 更新图灵机状态； 在该脚本内部定义了变量nowTape用于确定当前纸带与读写 头是输入、 工作或输出纸带与读写头； 同时定义变量inputI、 workI和outputI用于标记输 入、 工作和输出纸带当前读写位置； 所述状态显示脚本利用继承至GameObject类的GetComponent方法调用状态转移脚本 提供的接口getState()获取图灵 机状态， 并且显示在状态显示屏上； 所述模拟函数调用脚本将纸带数据移动到视角外进行更新， 以达到模拟函数调用过 程； 在场景中创建一个空物体作为纸带移动的目标位置； 利用MoveTowards()函数以实现 读写头在目标位置与初始位置间的往复运动； 对于递归调用仅 将纸带上数据更新为下一层 递归输入的参数， 对应排序的调用直接更新 为排序后的结果； 所述单位 时间访问数组分为在确定状态转移下实现、 在不确定状态转移下实现和切换 纸带下实现这三种情况； 对于确定状态转移下的单位时间访问数组实现仅需在执行纸带左 移右移操作时直接移动到根据数组下标定位的位置； 对于不确定状态转移与切换纸带这两 种情况， 则需要在进入 下一状态前修改定位变量inputI、 workI和outputI， 并调用控制纸带 移动脚本提供的接口控制纸带移动， 然后进入下一状态。 4.根据权利要求3所述的基于Unity的图灵机虚拟仿真系 统， 其特征在于： 所述UI设计 模块具体用于设计算法选择界面、 算法模拟界面以及实现算法说明与交 互功能； 所述算法选择界面设计五个按钮用于选择所要模拟的算法， 通过调用Unity中 SceneMana ger包实现点击按 钮进行场景跳转的功能； 所述算法模拟界面用于显示算法模拟时各纸带数据、 时间复杂度、 空间复杂度和返回 算法选择页面的按钮， 通过小窗显示三条纸带正在读写的位置， 并提供了算法模拟开始/暂 停、 加速和减速按 钮， 具体方法为： 调用更新纸带内容脚本提供的接口读取纸带上的数据并显示在界面中对应的Text构 件上； 小窗显示采用了设置三个摄像机分别对应着三条纸带的中央位置， 利用相机属性中的 render texture获得相机的视角， 并将相机的视角渲染到界面中的图片实现利用小窗显示 纸带正在读写位置的数据； 在二分搜索递归算法中还需实现在界面中显示递归栈， 即每次调用压入递归栈的数 据； 通过执行状态call时将low、 high和mid按顺序入栈， 并在retur n时遵循先进后出的原则 出栈； 在小规模0 ‑1背包动态规划 算法中还在界面中通过二维表动态显示二维数组中的数 据； 所述实现算法说明与交互功能的具体方法为： 在算法选择界面选择要模拟的算法后， 给出所选定算法的相关说明， 当用户阅读完毕点击继续按钮观看算法模拟过程； 并且在算 法说明页面利用UI中的Inp utField组件提供了输入功能， 使用户在该页面自行输入初始输 入纸带数据。 5.根据权利要求4所述的基于Unity的图灵机虚拟仿真系统， 其特征在于： 所述算法复 杂度计算模块用于计算图灵 机模拟五种算法的复杂度的具体方法为： 在控制读写头移动脚本中， 新增变量num1并初始化为0， 当读写头落下移动 至目标位置 时令num1+1， 并提供返回num1值的接口用于给 出时间复杂度；权　利　要　求　书 2/6 页 3 CN 114818300 A 3