基于OpenGL的Hanoi塔问题动画模拟程序的设计与实现

福建电脑２００６年第６期基于ＯｐｅｎＧＬ的Ｈａｎｏｉ塔问题动画模拟程序的设计与实现吴元斌（重庆三峡学院计算机科学系四川重庆４０４０００）【摘要】：该文介绍了实现Ｈａｎｏｉ塔问题动画模拟程序的ＯｐｅｎＧＬ相关编程函数，给出了模拟程序所采用的主要数据结构和算法。

程序在ＶｉｓｕａｌＣ＋＋．ＮＥＴ下实现，较好地模拟了Ｈａｎｏｉ塔问题的移动过程。

【关键词】：ＯｐｅｎＧＬＨａｎｏｉ塔问题双缓存动画ＶｉｓｕａｌＣ＋＋．ＮＥＴ１．引言Ｈａｎｏｉ塔问题在程序设计与算法研究中被作为经典的递归算法实例［１，２，３，７］。

Ｈａｎｏｉ塔问题的递归算法实现简单、易于理解，但其执行过程却比较费解。

笔者利用ＯｐｅｎＧＬ图形编程技术的优势，编写基于ＯｐｅｎＧＬ的Ｈａｎｏｉ塔问题动画模拟程序，对Ｈａｎｏｉ塔问题递归算法的执行过程进行了直观、形象的动画模拟，对于理解Ｈａｎｏｉ塔问题，特别是其递归算法的执行过程很有必要。

动画模拟程序在ＶｉｓｕａｌＣ＋＋．ＮＥＴ下实现，本文介绍了实现该程序的ＯｐｅｎＧＬ相关编程函数，分析了实现动画的主要数据结构和算法，并给出了程序运行时的动画场景图示。

２．相关ＯｐｅｎＧＬ编程函数ＯｐｅｎＧＬ是公认的工业标准，包含核心库、实用库、辅助库、工具库、Ｗｉｎｄｏｗｓ专用库等多个函数库，提供了丰富的图形编程函数［４，５］。

本文主要涉及建模、几何变换、双缓存动画函数。

２．１建模函数ＯｐｅｎＧＬ提供了很多复杂三维物体（如：球、锥、多面体、茶壶及复杂曲线和曲面）绘制函数。

为了表示Ｈａｎｏｉ塔中的“圆盘”、“塔柱”、“底座”，本文使用了辅助库中的３个函数：圆环函数、圆柱函数、长方体函数。

原型分别是：ｖｏｉｄａｕｘＳｏｌｉｄＣｙｌｉｎｄｅｒ（ＧＬｆｌｏａｔｒａｄｉｕｓ，ＧＬｆｌｏａｔｈｅｉｇｈｔ）、ｖｏｉｄａｕｘＳｏｌｉｄＴｏｒｕｓ（ＧＬｆｌｏａｔｉｎｎｅｒＲａｄｉｕｓ，ＧＬｆｌｏａｔｏｕｔｅｒＲａｄｉｕｓ）、ａｕｘＳｏｌｉｄＢｏｘ（ＧＬｆｌｏａｔｗｉｄｔｈ，ＧＬｆｌｏａｔｈｅｉｇｈｔ，ＧＬｆｌｏａｔｄｅｐｔｈ）。

２．２颜色设置与几何变换本文所用颜色设置函数原型为：ｖｏｉｄｇｌＣｏｌｏｒ３ｆｖ（ＧＬｆｌｏａｔｖ［３］）。

为了实现动画和表现移动过程，主要使用基本变换中的平移、旋转变换，平移和旋转函数的原型分别为：ｖｏｉｄｇｌＲｒａｎｓｌａｔｅｆｖ（ＧＬｆｌｏａｔ，ＧＬｆｌｏａｔ，ＧＬｆｌｏａｔ）、ｇｌＲｏｔａｔｅｆ（ＧＬｆｌｏａｔ，ＧＬｆｌｏａｔ，ＧＬｆｌｏａｔ，ＧＬｆｌｏａｔ）。

２．３双缓存动画双缓存动画技术是一种边画边显示的实时动画技术。

它提供了两个基本缓冲区，在显示前台缓存内容中的一帧画面时，后台缓存正在绘制下一帧画面，当绘制完毕，则后台缓存内容在屏幕上显示出来，而前台绘制下一副画面内容。

相关函数的原型为：ＳｅｔＰｉｘｅｌＦｏｒｍａｔ（）、ＳｗａｐＢｕｆｆｅｒｓ（ｈｄｃ）。

３．程序所采用的主要数据结构、算法３．１主要数据结构Ｈａｎｏｉ塔中所涉及对象是“圆盘”、“塔柱”，各自有多种属性（如：半径、高度、颜色等）。

本文将它们抽象为两种结构：Ｐｅｇ、Ｄｉｓｋ。

为了表示圆盘在塔柱之间的移动情况，在结构Ｐｅｇ中用栈结构记录其中存放的各圆盘的编号。

具体定义为：ｓｔｒｕｃｔＰｅｇ｛／／塔柱结构ＧＬｆｌｏａｔｘ０，ｙ０；／／底部的中心坐标ＧＬｆｌｏａｔｒ；／／半径ＧＬｆｌｏａｔｈｉｇｈ；／／高度ＧＬｆｌｏａｔｃｏｌｏｒ［３］；／／颜色ＧＬｆｌｏａｔｔｏｐ；／／可放圆盘的位置ｉｎｔｄｉｓｋｓＮｏ［１０］；／／目前存放的各圆盘编号，实现为栈ｉｎｔｄｉｓｋＮｕｍ；／／圆盘数，并作为栈顶指针｝；ｓｔｒｕｃｔＤｉｓｋ｛／／圆盘结构ＧＬｆｌｏａｔｘ０，ｙ０；／／中心坐标ＧＬｆｌｏａｔｉｎｒ，ｏｕｔｒ；／／内外半径ＧＬｆｌｏａｔｃｏｌｏｒ［３］；／／圆盘的颜色｝；将Ｈａｎｏｉ塔动画的相关函数组成一个类ＣＨａｎｏｉ，具体定义为：ｃｌａｓｓＣＨａｎｏｉ：ｐｕｂｌｉｃＣＷｎｄ｛ＤＥＣＬＡＲＥ＿ＤＹＮＡＭＩＣ（ＣＨａｎｏｉ）ｐｕｂｌｉｃ：ＣＨａｎｏｉ（）；ｖｉｒｔｕａｌ￣ＣＨａｎｏｉ（）；ｉｎｔＭｙＳｅｔＰｉｘｅｌＦｏｒｍａｔ（ＨＤＣｈｄｃ）；／／设置像素格式函数ＨＤＣｈｄｃ；／／绘图描述表ＨＧＬＲＣｈｇｌｒｃ；／／渲染描述表ｖｏｉｄｄｒａｗＰｅｇｓ（）；／／绘制塔柱ｖｏｉｄｄｒａｗＩｎｉｔＤｉｓｋｓ（）；／／绘制开始移动前各塔柱中的圆盘ｖｏｉｄＤｒａｗＢｏｔｔｏｍＢｏｘ（ｖｏｉｄ）；／／绘制底座ｖｏｉｄｉｎｉｔ（ｉｎｔｎ）；／／Ｈａｎｏｉ塔初始化，设置各塔柱、圆盘的各种属性等ｖｏｉｄｈａｎｏｉＧａｍｅ（ｉｎｔｈｉｇｈ，ｉｎｔＦｒｏｍ，ｉｎｔＵｓｉｎｇ，ｉｎｔＴｏ）；／／Ｈａｎｏｉ塔递归函数ｖｏｉｄｍｏｖｅＤｉｓｋ（ｉｎｔｎｏ，ｉｎｔｆｒｏｍ，ｉｎｔｔｏ）；／／第ｎｏ号圆盘从ｆｒｏｍ塔柱移动到ｔｏ塔柱ｖｏｉｄｄｒａｗＤｙｎａｍｉｃＤｉｓｋ（ｉｎｔｎｏ）；／／绘制第ｎｏ号圆盘动画ｖｏｉｄｄｒａｗＳｔａｔｉｃＤｉｓｋ（ｉｎｔｎｏ，ＧＬｆｌｏａｔｃｏｌｏｒ［］）；／／用制定颜色绘制第ｎｏ号圆盘ｐｒｏｔｅｃｔｅｄ：ＤＥＣＬＡＲＥ＿ＭＥＳＳＡＧＥ＿ＭＡＰ（）ｐｕｂｌｉｃ：ａｆｘ＿ｍｓｇｉｎｔＯｎＣｒｅａｔｅ（ＬＰＣＲＥＡＴＥＳＴＲＵＣＴｌｐＣｒｅａｔｅＳｔｒｕｃｔ）；ａｆｘ＿ｍｓｇｖｏｉｄＯｎＰａｉｎｔ（）；｝；３．２主要算法３．２．１Ｈａｎｏｉ塔递归算法ｖｏｉｄｈａｎｏｉ（ｉｎｔｄｉｓｋｎｏ，ｉｎｔｆｒｏｍ，ｉｎｔｕｓｉｎｇ，ｉｎｔｔｏ）｛ｉｆ（ｄｉｓｋｎｏ＞０）｛ｈａｎｏｉ（ｄｉｓｋｎｏ－１，ｆｒｏｍ，ｔｏ，ｕｓｉｎｇ）；ｍｏｖｅＤｉｓｋ（ｄｉｓｋｎｏ，ｆｒｏｍ，ｔｏ）；ｈａｎｏｉ（ｄｉｓｋｎｏ－１，ｕｓｉｎｇ，ｆｒｏｍ，ｔｏ）；｝｝３．２．２ｍｏｖｅＤｉｓｋ（ｄｉｓｋｎｏ，ｆｒｏｍ，Ｔｏ）函数的实现步骤编号为ｄｉｓｋｎｏ圆盘从ｆｒｏｍ塔柱移到ｔｏ塔柱上（即ｍｏｖｅＤｉｓｋ（ｄｉｓｋｎｏ，ｆｒｏｍ，Ｔｏ）函数的实现）的步骤为：（１）从当前位置上移至源柱ｆｒｏｍ顶上；（２）水平（方向依赖于ｆｏｒｍ与ｔｏ间的位置关系）移到目标柱ｔｏ顶；（３）下移至目标柱ｔｏ原有圆盘的上面；（４）修改ｆｒｏｍ、ｔｏ塔柱圆盘和可放圆盘的位置：ｆｒｏｍ塔柱的圆盘减１，可放圆盘的位置降低；ｔｏ塔柱圆盘增１，可放圆盘的位置升高。

３．２．３二次作图法移动圆盘采用二次作图法：第一次用圆盘的颜色画圆盘，交换缓存，第二次用背景色画圆盘；然后再改变圆盘位置画圆盘，于是视觉上被圆盘移动。

具体实现函数是：ｖｏｉｄｄｒａｗＤｙｎａｍｉｃＤｉｓｋ（ｉｎｔｎｏ）。

画圆盘的函数为ｖｏｉｄｄｒａｗＳｔａｔｉｃＤｉｓｋ（ｉｎｔｎｏ，ＧＬｆｌｏａｔｃｏｌｏｒ［３］）。

３．３开发环境及模拟效果该动画程序利用ＯｐｅｎＧＬ和ＶｉｓｕａｌＣ＋＋．ＮＥＴ编程技术［４，５，６］在ＶｉｓｕａｌＣ＋＋．ＮＥＴ环境下用基于对话框的应用程序模式实现（源程序清单略）。

界面中包含显示动画的区域、设（下转第８３页）１６０福建电脑２００６年第６期!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（上接第１６０页）置圆盘数框、开始动画、速度控制滑条、结束动画命令按钮。

图１是程序运行时的一个场景。

图１Ｈａｎｏｉ塔移动过程动画场景４．结语本文介绍了实现Ｈａｎｏｉ塔问题递归算法动画模拟程序的ＯｐｅｎＧＬ相关编程函数，分析了实现动画的主要数据结构和算法。

程序在ＶｉｓｕａｌＣ＋＋．ＮＥＴ下实现，圆盘数可动态设置，各圆盘、塔柱、底座的颜色在运行时随机形成，可进行速度控制，较好地模拟了Ｈａｎｏｉ塔问题递归算法的执行过程。

若对程序作适当修改，如加上光照、材质、纹理等，模拟效果将进一步增强。

参考文献：１．王晓东．计算机算法设计与分析（第２版）［Ｍ］．北京：电子工业出版社，２００４．２．严蔚敏，吴伟明．数据结构（Ｃ语言版）［Ｍ］．北京：清华大学出版社，１９９７．３．谭浩强．Ｃ程序设计（第二版）［Ｍ］．北京：清华大学出版社，１９９９．４．和平鸽工作室．ＯｐｅｎＧＬ三维图形系统开发与实用技术（基础编程篇）［Ｍ］．北京：清华大学出版社，重庆：重庆大学出版社，２００３．５．和平鸽工作室．ＯｐｅｎＧＬ高级编程与可视化系统开发（高级编程篇）［Ｍ］．北京：中国水利水电出版社，２００３．６．Ａｒｃｈｅｒ，Ｔ．等著，马云等译．ＶｉｓｕａｌＣ＋＋．ＮＥＴ宝典［Ｍ］．北京：电子工业出版社，２００３．７．王晓东，吴英杰．广义Ｈａｎｏｉ塔问题的动态规划算法［Ｊ］．小型微型计算机系统，２００５（５）．本试验总共要进行９次，将试验结本试验总共要进行９次，将试验结果———静电电位值ｙ１，ｙ２，…，ｙ９填写在正交表的最后一列中，如表２所示。

３．２．２计算极差确定最优方案引进记号Ｋｉｊ和Ｒｊ。

其中，Ｋｉｊ＝第ｊ列上水平号为ｉ的各个试验结果之和；Ｒｊ＝ｍａｘ｛Ｋｉｊ｝－ｍｉｎ｛Ｋｉｊ｝。

Ｒｊ称为第ｊ列的极差或其所在因素的极差。

对于本试验，有：Ｋ１１＝ｙ１＋ｙ２＋ｙ３＝０．０２４７＋０．２５４＋０．８６１＝１．１３９７；Ｋ２１＝ｙ４＋ｙ５＋ｙ６＝０．５８４＋０．７５６＋１．２４５＝２．５８５；Ｋ３１＝ｙ７＋ｙ８＋ｙ９＝０．８２９＋１．７２０＋１．７１９＝４．２６８；Ｒ１＝ｍａｘ｛Ｋ１Ａ，Ｋ２Ａ，Ｋ３Ａ｝－ｍｉｎ｛Ｋ１Ａ，Ｋ２Ａ，Ｋ３Ａ｝＝４．２６８－１．１３９７＝３．１２８３。

依此类推，可以确定其它的Ｋｉｊ，Ｒｊ。

它们的计算结果填写在表２中。

挑选因素的最优水平与所要求的指标有关，若指标越大越好，则应该选取使指标大的水平，即各列Ｋ１ｊ、Ｋ２ｊ、Ｋ３ｊ中最大的那个水平；否则，若指标越小越好，则应该选取使指标最小的那个水平。

试验的目标找出静电电位最大时的条件。

因为指标越大越好，所以应该挑选出每个因素的Ｋ１ｊ、Ｋ２ｊ、Ｋ３ｊ中最大的那个水平。

由于Ｋ３Ａ＞Ｋ２Ａ＞Ｋ１Ａ；Ｋ３Ｂ＞Ｋ２Ｂ＞Ｋ１Ｂ；Ｋ３Ｃ＞Ｋ１Ｃ＞Ｋ２Ｃ。

故得最优方案为Ａ３Ｂ３Ｃ３，即选取试验条件为“相对湿度２５％，摩擦速度１３０转／分钟，摩擦时间２４秒”。

３．３试验分析在静电电位试验中，若对正交试验进行理论分析得到的最优方案为Ａ３Ｂ３Ｃ３，但是，在真正把它作为方案来执行之前，往往还需要进行对比验证试验。

其步骤如下：首先是把理论最优方案Ａ３Ｂ３Ｃ３与按正交表的规定做过的９个试验中产生静电电位最高的第８号方案Ａ３Ｂ２Ｃ３做多次对比试验。

如果在试验中方案Ａ３Ｂ３Ｃ３确实比８号试验方案Ａ３Ｂ２Ｃ３产生的静电电位更高，通常就认为由理论分析确定的Ａ３Ｂ３Ｃ３为静电电位最优方案。

否则就取８号试验方案Ａ３Ｂ３Ｃ３为最优方案。

若对这两个试验方案进行多次对比试验中发现由理论分析获得的最优试验方案Ａ３Ｂ３Ｃ３产生的静电电位比第８号试验方案Ａ３Ｂ２Ｃ３要低，一般来说可能是各个因素之间存在不可忽略的交互作用，也可能是试验误差较大所引起的，那么，需要作进一步的研究，经过试验方案的一定改动，可能还可以提高试验产生的静电电位。