在教育技术领域中,教育游戏作为其热点之一,受到广泛的关注。连线游戏和拼图游戏作为教育游戏中较简单的类型,以其图形多样、界面美观而深受喜爱。研究连线游戏和拼图游戏中的关键算法,可提高图形的多样性及游戏的自动化程度。在传统的连线游戏和拼图游戏中,游戏的难度往往是通过图形的复杂性来提高,不同关卡也是通过图形的变换来改变的,玩家不能针对同一图形进行不同难度的选择,使得游戏缺少了灵活性。本文研究的算法不仅可以使玩家能够自主改变连线游戏中采样点集的疏密程度,也可以根据自身情况改变拼图游戏中图形分割的块数,增加了游戏的自由度及可玩性。本文的工作主要包括以下几个方面:1.连线游戏中采样算法研究:在连线游戏中,初始采样点集是通过对图像轮廓进行采样而获得,并且所得采样点能够反映图像形状及走向信息,即在图像边缘局部曲率大的地方需采样密集,在图像边缘曲率小的地方需采样稀疏。因此,文中首先通过Canny算子提取图像的轮廓线,然后根据轮廓线所围图形的中轴信息,捕捉轮廓线的局部几何特征,得到初始采样点集,最后根据一定条件添加部分采样点,即得到最终采样点集。本文中的采样算法可以通过设置参数,来控制采样点的疏密程度,从而提高或降低游戏难度。2.连线游戏中重建算法研究:在获得上述采样点集后,需要查找正确的采样点的连接顺序,以自动化判断玩家连线是否正确。无序采样点中,每个采样点与其它采样点之间均有多种连接的可能性,且存在距离相近但不相连接,距离较远但相连接的点。因此,本文首先通过逐次连接采样点集中距离较近的点,形成初始的闭合图形,然后通过一定的方法删除闭合图形内部多余的连线,最后通过修改闭合图形及内部点的连接顺序,最终正确连接采样点集。3.拼图游戏中图像分割算法研究:在拼图游戏中,如何对图像进行分割,生成若干个拼块是一个重要的问题。本文通过多边形叠加和CVT的方法来实现上述分割:多边形叠加方法是通过对原图形和多个图形进行叠加,将原图形分成多个不规则的拼块;CVT方法是运用Voronoi图的原理,对图形所在区域进行划分,最终将图形划分成多个互不重叠的凸多边形拼块。在上述算法的基础上,本文对连线游戏和拼图游戏进行了界面与功能的设计,展示上述算法在连线游戏和拼图游戏中的应用。