手把手教你怎么实现java九宫格自动拼图

手把手教你怎么实现九宫格自动拼图

在上一篇推文中我们带大家基本了解了近几年随着深度学习的发展,人工智能可以干很多的事:人脸识别,自动驾驶,风格迁移等等。那么有一个问题出现了,人工智能的发展,一开始就过渡到那么深奥的“机器学习”,“神经网络”吗?

肯定不是的。

现在大热的人工智能实现方法,我们称之为模拟法,它不仅要看效果,还要求实现方法也和人类或生物机体所用的方法相同或相类似。大名鼎鼎的遗传算法和人工神经网络就是这个类型。

而在机器学 习概念还没提出之前,人工智能是采用传统的编程技术,使系统呈现智能的效果,而不考虑所用方法是否与人或动物机体所用的方法相同。这种方法叫工程学方法。它已在一些领域内作出了成果,如文字识别、电脑下棋等。今天要教大家实现的,就是用传统的办法,用java编程和数据结构,来实现打乱的九宫格自动还原功能。

本推文不需要阅读者拥有Java编程基础,讲解的是实现的思路(当然在文末,会提供源码给想亲自编译的小伙伴玩一玩~)

构思游戏框架

界面

界面是拼图游戏的雏形实现,九个按钮,按钮上的图片显示出完整的图片。前八个是完整的图形,最后一个为空白图。再在上边添加控制按钮。大概就长这样:

板块怎么实现移动

移动版块,我们更换按钮上的图片。按钮类上我们设置有两个属性,a[]表示按钮的位置,b[]表示按钮上图片的编号, 空白快图片编号为8标记,点击按钮之后,点击事件得到点击的块数在哪(1-9),if -else判断相邻是否为标记的空白快。虽然代码长但是方法简单。

判断胜利

在上一段中我们提到有两个按钮属性 a,b来记录信息,在未打乱之前,ab对应,值相等。那么我们在每一次的鼠标点击拼图按钮之后进行一次判断,是否每一个a[i]都对应着自身b[i]值,如果是的话就给出胜利信号。

打乱拼图

在完成了上面的设计之后,我们已经可以开始玩耍了,但是这是游戏,得有打乱的功能。怎么实现呢。若随机置入图片,会存在图片移动次数的奇偶性问题,有一半的几率是没有解法的。采用此法,我不得不再写一个判断随机打乱之后是否有解的算法。这样会非常麻烦,并且与我之前写的版块内容不兼容。由于我们写好了移动算法,所以我们随机移动可移动的版块若干次,次数足够多的情况下便可以做到打乱拼图的效果,并且保证此法必然有解。

重头戏:实现自动还原

广度搜索算法

广度优先算法(Breadth-First Search)简称BFS,是一种图形搜索演算法,在程序员必学的经典--《数据结构》中占有很重要的位置。那它到底是什么呢?

有一个有向图如图a:

我们的目标是从v1开始,先下寻到,直到找到v8这个目标点的最短路径。人眼很容易看出来,但是机器怎么知道呢?于是就引出了广度搜索算法。

1、访问顶点vi ;

2、访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ;

3、依次从这些邻接点(在步骤②中访问的顶点)出发,访问它们的所有未被访问的邻接点; 依此类推,直到找到v8.;

这样的算法优点在于它的完全性。无论图形的种类如何,只要目标存在,则BFS一定会找到。然而缺点也在于此,若目标不存在,且图为无限大,则BFS将不会结束,若图形太过庞大,将花费巨大的时间。

拼图怎么引入广度搜索算法

现在我们将来初始打乱状态,目标状态抽象表示如下:

运用广度搜索的思想,我们可以让白块模拟走一走,判断是不是已经赢了,不是的话,我们就回去,再模拟同一层次的走法。根据白块的位置不同,可以走2,3,4中情况。比如在中间可以模拟走上下左右。同层走完之后都没有找到目标点,记录下我走了一步了,再走下一层。如此循环,最终找到目标状态。显示出走了多少步,这就是最佳最短的还原路径了。

引入广度搜索之后提示出下棋步骤

算出步数之后,我们再找到白块,模拟有效移动一次,再判断这次的局面,相比较之前最短步数是否减1。若是,则为最佳走法,若不是,则还原,再模拟一次另一个走法。其中必然有正解。伪代码如下:

数组c记录移动之前的局面;

while (true) {

while(不是有效白块移动) {

移动白块

}

获得表示当前局面的字符串;

计算最短路径d;

if(最短路径d相比较之前最短步数d0减1)

{

用记录数组c还原移动之前局面;

输出这一步移动(找到了最佳的走法了)

break; }

if(模拟之前局面最短步数d0==1)

{

用记录数组c还原移动之前局面;

break;

}else

{

用记录数组c还原移动之前局面;

}

}

找到最佳走法之后,我们让程序移动白块就可以了。

运行结果

我们是图灵智能创新团队,同时也是广东海洋大学第一个人工智能创新团队,我们团队的主要方向有:计算机视觉和自然语言处理。本公众号主要面向对人工智能感兴趣的读者,如果想了解更多,欢迎关注我们!

—END—

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180427G0YUMZ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券