拼图游戏_拼图游戏java - CSDN

• 拼图游戏

2017-03-01 13:09:55
给出一张图片，将该图片的每块指定位置分割出来，放进数组中，然后按照九宫格循环摆放。点击的时候判断是否移动，简单的拼图游戏即成。


//给出一张图片，然后将该图片的每块指定位置分割出来，放进数组中，然后循环摆放。点击的时候判断是否移动，简单的拼图游戏即成。

#define VIEW_WIDTH self.view.frame.size.width

#define VIEW_HEIGHT self.view.frame.size.height

@interface
ViewController (){

UIImageView *_spaceImageView;

UIImage *_image;

}

@end

@implementation ViewController

//创建完整图片

[selfcreateSmallImageView];

//创建拼图图片

[selfcreatePuzzle];

}

- (void)createPuzzle{

UIImage *image = [UIImageimageNamed:@"beautifulGirl"];

CGSize imageSize = image.size;

//改变难易程度的关键

NSInteger cube =4;

CGFloat width = imageSize.width / cube;

NSMutableArray *imageList = [[NSMutableArrayalloc]init];

//循环创建 4＊ 4正方形

for (int i =0; i < cube * cube; i++) {

//行

int row = i / cube;

//列

int column = i % cube;

CGRect rect =CGRectMake(column * width, row * width, width, width);

//获取制定位置的切图

UIImage *subImage = [selfclipImage:image
withRect:rect];

}

for (int i =0; i < cube * cube; i++) {

int row = i / cube;

int column = i % cube;

UIImageView *subImageView = [[UIImageViewalloc]initWithFrame:CGRectMake((VIEW_WIDTH
- imageSize.width) /
2 + column * width, 50 + row * width , width, width)];

//取图片数组中的逆序，从而造成图片的乱序

subImageView.image = imageList[cube * cube -1 - i];

//允许用户交互

subImageView.userInteractionEnabled =YES;

//将最后一个清空，记录空白图片视图的坐标

if (i ==0) {

subImageView.image =nil;

_spaceImageView = subImageView;

}

//做出来分割线

subImageView.layer.borderColor = [UIColorgrayColor].CGColor;

subImageView.layer.borderWidth =1;

//添加点击手势

UITapGestureRecognizer *tap = [[UITapGestureRecognizeralloc]initWithTarget:selfaction:@selector(tapHandle:)];

}

}

- (void)tapHandle:(UITapGestureRecognizer *)tap{

if (tap.view !=_spaceImageView) {

CGFloat tapX = tap.view.frame.origin.x;

CGFloat tapY = tap.view.frame.origin.y;

CGFloat spaceX =_spaceImageView.frame.origin.x;

CGFloat spaceY =_spaceImageView.frame.origin.y;

//判断是否和空白图片视图交换

if (fabs(spaceX - tapX ) +fabs(spaceY - tapY) ==
_spaceImageView.frame.size.width)
{

CGRect frame = tap.view.frame;

tap.view.frame =_spaceImageView.frame;

_spaceImageView.frame = frame;

}

}

}

//下方显示完整的图片

- (void)createSmallImageView{

UIImageView *downImageView = [[UIImageViewalloc]initWithImage:[UIImageimageNamed:@"beautifulGirl"]];

downImageView.frame =CGRectMake((VIEW_WIDTH -100)
/ 3,VIEW_HEIGHT -
200,200,
200);

}

//给一个图片对象，给一个需要切割的大小，将图片切割成为指定大小的小图片

- (UIImage *)clipImage:(UIImage *)image withRect:(CGRect )rect{

CGImageRef CGImage =CGImageCreateWithImageInRect(image.CGImage, rect);

return [UIImageimageWithCGImage:CGImage];

}

展开全文
• NULL 博文链接：https://lovephoenix.iteye.com/blog/649391
• JAVA实现拼图游戏

千次阅读 2019-05-03 11:44:42
JAVA实现拼图游戏
                package org.test;/** * <p>Title: LoonFramework</p> * <p>Description:拼图图像处理[未优化]（优化算法已内置于loonframework-game框架中。）</p> * <p>Copyright: Copyright (c) 2007</p> * <p>Company: LoonFramework</p> * @author chenpeng   * @email：ceponline@yahoo.com.cn  * @version 0.1 */import java.awt.Canvas;import java.awt.Color;import java.awt.Event;import java.awt.Frame;import java.awt.Graphics;import java.awt.Image;import java.awt.MediaTracker;import java.awt.image.BufferedImage;import org.loon.framework.game.helper.ImageHelper;public class BlockImage extends Canvas {    /**     *      */    private static final long serialVersionUID = 1L;    private Image _img;    private Image _img2;    private Graphics bg;    private Image backimage;    private int blocks[];    private boolean isEvent;    private MediaTracker mt;    private int _width;    private int _height;    private int _RS;    private int _CS;    private Image screen = null;    private Graphics later = null;    private int _objWidth;    private int _objHeight;    private int _COUNT;    /**     * 析构函数，内部调用init方法。     *      * @param bImage     * @param overImage     * @param cs     * @param rs     */    public BlockImage(Image bImage, Image overImage, int cs, int rs) {        init(bImage, overImage, cs, rs);    }    /**     * 初始化拼图参数。     *      * @param bImage     * @param overImage     * @param cs     * @param rs     */    public void init(Image bImage, Image overImage, int cs, int rs) {        // 列数        _CS = cs;        // 行数        _RS = rs;        // 加载拼图用图像。        _img = bImage;        // 获得实际窗体宽。        _width = _img.getWidth(null);        // 获得实际窗体高。        _height = _img.getHeight(null);        // 获得单块图像宽。        _objWidth = _width / _CS;        // 获得单块图像高。        _objHeight = _height / _RS;        // 本程序直接使用backimage上一块图形区域缓冲选择项，所以实际背景图像高=图形高+额外图块高。        backimage = new BufferedImage(_width, _height + _objHeight, 1);        // 获得生成的图形        later = backimage.getGraphics();        // 再创建一块图像区域，作为图像缓存用。        screen = new BufferedImage(_width, _height, 1);        // 获得缓存的图形        bg = screen.getGraphics();        // 获得等同图片总数的数组。        _COUNT = _CS * _RS;        blocks = new int[_COUNT];        // 初始化为非点击。        isEvent = false;        // 加载完成拼图的显示图。        _img2 = overImage;        // 初始化图块参数。        for (int i = 0; i < _COUNT; i++) {            blocks[i] = i;        }        // 载入MediaTracker，用以跟踪图像状态。        mt = new MediaTracker(this);        // 加载被跟踪的图像。        mt.addImage(_img, 0);        mt.addImage(_img2, 0);        // 同步载入。        try {            mt.waitForID(0);        } catch (InterruptedException interruptedexception) {            return;        }        // 随机生成图像面板内容。        rndPannel();    }    /**     * 描绘窗体图像。     */    public void paint(Graphics g) {        // 检查图像载入。        if (mt.checkID(0)) {            // 描绘底层背景。            bg.drawImage(backimage, 0, 0, null);            // 判断是否触发完成事件。            if (!isEvent) {                // 设置背景色。                bg.setColor(Color.black);                // 循环绘制小图片于背景缓存中。                for (int i = 0; i < _CS; i++) {                    for (int j = 0; j < _RS; j++)                        bg.drawRect(i * _objWidth, j * _objHeight, _objWidth,                                _objHeight);                }            }            // 仅当完成事件触发并且有胜利图片时，载入完成提示。            if (isEvent && _img2 != null) {                bg.drawImage(_img2, 0, 0, null);            }        }        // 举凡绘制图像时，应遵循显示图像仅绘制一次的基本原则，一次性的将背景绘制到窗体。        // 简单来说，也就是采取[双缓存]的方式，所有复杂操作皆在缓存区完成，也只有这样才能避免产生延迟闪烁。        g.drawImage(screen, 0, 0, this);        g.dispose();    }    /**     * 变更图像。     */    public void update(Graphics g) {        paint(g);    }    /**     * 鼠标点击事件。     */    public boolean mouseDown(Event event, int i, int j) {        if (isEvent)            return true;        // 换算点击位置与小图片。        int k = i / _objWidth;        int l = j / _objHeight;        copy(0, 0, 0, _RS);        copy(k, l, 0, 0);        copy(0, _RS, k, l);        int i1 = blocks[0];        // 换算选中图片存储区。        blocks[0] = blocks[l * _CS + k];        blocks[l * _CS + k] = i1;        int j1;        for (j1 = 0; j1 < _COUNT; j1++) {            if (blocks[j1] != j1) {                break;            }        }        if (j1 == _COUNT)            isEvent = true;        repaint();        return true;    }    public boolean mouseUp(Event event, int i, int j) {        return true;    }    public boolean mouseDrag(Event event, int i, int j) {        return true;    }    /**     * copy换算后的图像区域。     *      * @param i     * @param j     * @param k     * @param l     */    void copy(int i, int j, int k, int l) {        later.copyArea(i * _objWidth, j * _objHeight, _objWidth, _objHeight,                (k - i) * _objWidth, (l - j) * _objHeight);    }    /**     * 事件触发状态。     * @return     */    public boolean isEvent() {        return isEvent;    }    public void setEvent(boolean isEvent) {        this.isEvent = isEvent;    }    /**     * 随机生成面板图片。     *      */    void rndPannel() {        later.drawImage(_img, 0, 0, this);        for (int i = 0; i < (_COUNT * _CS); i++) {            int j = (int) ((double) _CS * Math.random());            int k = (int) ((double) _RS * Math.random());            int l = (int) ((double) _CS * Math.random());            int i1 = (int) ((double) _RS * Math.random());            copy(j, k, 0, _RS);            copy(l, i1, j, k);            copy(0, _RS, l, i1);            int j1 = blocks[k * _CS + j];            blocks[k * _CS + j] = blocks[i1 * _CS + l];            blocks[i1 * _CS + l] = j1;        }    }    public static void main(String[] args) {        Frame frm = new Frame("简单的JAVA拼图效果实现[由Loonframework框架提供]");        frm.setSize(480, 500);        frm.setResizable(false);        /**         * PS:ImageHelper.loadImage为Loonframework框架中helper下方法，为不依赖于javax扩展包而开发。         * 可使用ImageIO相关方法代替。         */        // 加载图像。        Image backImage = ImageHelper.loadImage("C:/backimage.jpg", true);        Image overImage = ImageHelper.loadImage("C:/over.gif", true);        // BlockImage中参数分别为 用于分解的拼图，完成后显示文字，拆分图片为分几列，分拆分图片为几行。        //建议使用正方形图片作为背景图。        frm.add(new BlockImage(backImage, overImage, 4, 4));        backImage = null;        overImage = null;        // 显示窗体。        frm.setVisible(true);    }} 详细操作参见源码注释，所用图片如下（也可自由选取图形）：本代码算法支持自由成比例分隔图像行列，效果若下：


展开全文
• javascript实现web版拼图游戏

千次阅读 热门讨论 2017-12-15 17:09:25
利用javacript编写拼图游戏，主要需实现拖拽效果、图块吸附效果，拼图打乱动画，还需要做碰撞检测。本人为了让这个游戏的体验性好一点，还添加了是我的
利用javacript编写拼图游戏，主要需实现拖拽效果、图块吸附效果，拼图打乱动画，还需要做碰撞检测。本人为了让这个游戏的体验性好一点，还添加了类似淘宝网中商品的放大镜效果，鼠标移上去会出现放大图，实现的效果如下图：

下面描述该拼图游戏如何实现，HTML+CSS页面布局比较简单，就不详细描述了。重点在于javascript如何实现文中第一段提到的那些效果。
（1）拼图生成
首先需要用js生成整体拼图，如上图所示；代码如下：function init(){
var imgArr=["pt1.jpg","pt2.jpg","pt3.jpg","pt4.jpg"];
var imgIndex=parseInt(Math.random()*imgArr.length);
var wih="";
for(var i=0;i<5;i++){
for(var j=0;j<9;j++){
data.push({
"order":order,
"left":j*100,
"top":i*100
});
wih+="<span style='background-image:url(img/拼图游戏/"+					    imgArr[imgIndex]+"); background-position:"+			(-j*100)+"px "+(-i*100)+"px;' order='"+order+"'></span>";//"+(i*9+j)+"
order++;
}
}
right.innerHTML=wih;
var mDivs=document.querySelectorAll(".magnifier div");
for(var i=0;i<mDivs.length;i++){
mDivs[i].style.backgroundImage="url(img/拼图游戏/"+imgArr[imgIndex]+")";
}
ordersb(1);
}（2）拼图打乱动画打乱拼图位置，即打乱已存储所有图块的位置的数组，然后重新渲染每个图块的位置。可利用javascript中打乱数组的方法arr.sort()来实现。代码实现如下图所示：function ordersb(n){
var arr=[];
if(n==1){		//将数组按从小到大的顺序排列
arr=data.sort(function(a,b){
return a.order-b.order;
});
}else{		//打乱数组
arr=data.sort(function(){
return Math.random()-0.5;
});
}
for(var i=0;i<data.length;i++){
spans[i].style.transition="1s";
spans[i].style.left=data[i].left+"px";
spans[i].style.top=data[i].top+"px";
spans[i].setAttribute("order",data[i].order);
for (var j = 0; j < spans.length; j++) {
spans[j].style.transition = "none";
}
})
}
}点击“开始”按钮，拼图自动打乱，并带有一个打乱动画效果，如下图所示：

（3）拖拽效果
实现拖拽效果只要把握拖拽原理即可。即一个完整的拖拽包含三步：a.
鼠标按下；b. 鼠标移动；c.鼠标抬起。
（4）吸附效果
实现吸附效果，从代码角度解释就是，鼠标移动某个模块时，在一个不是任何一个图块允许存在的位置抬起鼠标，此时需要对该图块的位置进行修改，让它的位置是在图块允许的位置上。
（5）碰撞检测
所谓碰撞检测，在此处的通俗说法时，移动一个元素，使其靠近另一个元素，一旦靠近到两个元素刚开始有重叠,就需要立刻检测出来。此处不但要检测出移动的图块与哪些图块有重叠，还要判断与哪个图块重叠部分最多。因为在鼠标抬起时，移动的图块需要根据与哪个图块重叠最多，来决定与哪块图块交换位置。
为了游戏的体验更好一些，在鼠标移动图块时，就判断与哪个图块重叠最多，就把这块图块表示出来。这样用户就知道若抬起鼠标，即将会与哪块图块交换位置。如下图所示：

这三种功能的实现代码，即关键代码如下所示：
function drag(obj){
obj.οnmοusedοwn=function(ev){
obj.style.zIndex="99";
var br=obj.offsetLeft;
var bb=obj.offsetTop;
var width=obj.offsetWidth;
var height=obj.offsetHeight;
var or=right.getBoundingClientRect().left;
var ob=right.getBoundingClientRect().top;
var rMax=right.clientWidth-width;
var bMax=right.clientHeight-height;
var oOrder=obj.getAttribute("order");
var disX=ev.clientX- br-or;
var disY=ev.clientY-bb-ob;
var  l,t,eel,eet,erl;
right.οnmοusemοve=function(ev){
l=ev.clientX-disX-or;
t=ev.clientY-disY-ob;			//图块移动的边界位置范围设置
l=l>rMax?rMax:l;
l=l<0?0:l;
t=t>bMax?bMax:t;
t=t<0?0:t;
obj.style.left=l+"px";
obj.style.top=t+"px";			//修改此时图块的位置，使其在图块允许存在的位置上，并且是与某个图块重叠最多的那个图块位置
eel=Math.round(l/width)*width;
eet=Math.round(t/height)*height;			//根据图块位置找到在这个位置上的图块元素
erl=find(obj,eel,eet);
for(var i=0;i<spans.length;i++){
spans[i].style.opacity="";
}
if(erl){
erl.style.opacity=".5";
}
}
right.οnmοuseup=function(){
right.οnmοusemοve=null;
obj.style.zIndex="";
if(erl){
obj.setAttribute("order",erl.getAttribute("order"));
erl.style.left=br+"px";
erl.style.top=bb+"px";
erl.style.opacity="";
erl.setAttribute("order",oOrder);
}
obj.style.left=eel+"px";
obj.style.top=eet+"px";
}
return false;
}
}	（6）游戏输赢判断在拼图完成后，点击“验证”按钮，弹出一个弹框提示拼图是否正确。总结：
总体来说，用javascript实现拼图游戏，难度不大。本人在做的时候，遇到一个错误：图块移动到某个图块精确的位置上，此时拖拽效果和吸附效果都失效了。经过代码调试和分析，发现在对图块进行位置交换时，通过位置找到的被交换图块元素是不正确的，找到的是这个移动元素本身，导致图块的位置设置错误。找到出现bug的原因后，修改代码，在通过位置查找图块元素时，排除移动元素自身。修改后，经测试bug得到解决。
另外，在这里只贴出一些关键代码，如果需要详细源码可以留邮箱。

展开全文
• 己花了2个星期功夫利用晚上时间写了个拼图游戏(看过仗剑小猪的拼图游戏代码)，目前游戏不是很完善，但是基本框架功能都有，流程是仿照 “保卫萝卜”的目前游戏有几个问题： 1.游戏UI有问题，按钮和功能不是对应的，...
• 拼图游戏和它的AI算法

千次阅读 2017-11-20 10:19:36
写了个拼图游戏，探讨一下相关的AI算法。拼图游戏的复原问题也叫做N数码问题。 拼图游戏 N数码问题 广度优先搜索 双向广度优先搜索 A*搜索 游戏设定 实现一个拼图游戏，使它具备以下...


写了个拼图游戏，探讨一下相关的AI算法。拼图游戏的复原问题也叫做N数码问题。

拼图游戏

N数码问题

广度优先搜索

双向广度优先搜索

A*搜索

游戏设定实现一个拼图游戏，使它具备以下功能：
1、自由选取喜欢的图片来游戏
2、自由选定空格位置
3、空格邻近的方块可移动，其它方块不允许移动
4、能识别图片是否复原完成，游戏胜利时给出反馈
5、一键洗牌，打乱图片方块
6、支持重新开始游戏
7、难度分级：高、中、低
8、具备人工智能，自动完成拼图复原
9、实现几种人工智能算法：广度优先搜索、双向广度优先搜索、A*搜索
10、保存游戏进度
11、读取游戏进度

Puzzle Game.png

自动完成拼图复原
先看看完成后的效果。点自动按钮后，游戏将会把当前的拼图一步一步移动直到复原图片。

自动复原.gif

图片与方块
图片的选取可通过拍照、从相册选，或者使用内置默认图片。
由于游戏是在正方形区域内进行的，所以若想有最好的游戏效果，我们需要一张裁剪成正方形的图片。

截取正方形区域.png

选好图片后，需要把图片切割成n x n块。这里每一个方块PuzzlePiece都是一个UIButton。

由于图片是会被打散打乱的，所以每个方块应该记住它自己在原图上的初始位置，这里给方块添加一个属性ID，用于保存。

@interface PuzzlePiece : UIButton /// 本方块在原图上的位置，从0开始编号
@property (nonatomic, assign) NSInteger ID; /// 创建实例+ (instancetype)pieceWithID:(NSInteger)ID image:(UIImage *)image; @end

难度选择
切割后的图片块组成了一个n x n矩阵，亦即n阶方阵。而想要改变游戏难度，我们只需要改变方阵的阶数即可。

设计三档难度，从低到高分别对应3 x 3、4 x 4、5 x 5的方阵。

难度选择.gif

假如我们把游戏中某个时刻的方块排列顺序称为一个状态，那么当阶数为n时，游戏的总状态数就是n²的阶乘。

在不同难度下进行游戏将会有非常大的差异，无论是手动游戏还是AI进行游戏。

在低难度下，拼图共有(3*3)! = 362880个状态，并不多，即便是最慢的广搜算法也可以在短时间内搜出复原路径。

3阶方阵的搜索空间.png

在中难度下，拼图变成了4阶方阵，拼图状态数飙升到(4*4)! = 20922789888000，二十万亿。广搜算法已基本不能搜出结果，直到爆内存。

广搜算法占用的巨量内存.gif

在高难度下，拼图变成了5阶方阵，状态数是个天文数字(5*5)! = 1.551121004333098e25，10的25次方。此时无论是广搜亦或是双向广搜都已无能为力，而A*尚可一战。

高难度下的5阶方阵.png

方块移动

在选取完图片后，拼图是完整无缺的，此时让第一个被触击的方块成为空格。

从第二次触击开始，将会对所触击的方块进行移动，但只允许空格附近的方块发生移动。

每一次移动方块，实质上是让方块的位置与空格的位置进行交换。在这里思维需要转个小弯，空格并不空，它也是一个对象，只不过表示出来是一块空白而已。那么我们移动了方块，是否可以反过来想，其实是移动了空格？答案是肯定的，并且思维这样转过来后，更方便代码实现。

方块移动.gif

打乱方块顺序
这里为了让打乱顺序后的拼图有解，采用随机移动一定步数的方法来实现洗牌。

对于n阶方阵，可设计随机的步数为：n * n * 10。在实际测试当中，这个随机移动的步数已足够让拼图完全乱序，即使让随机的步数再加大10倍，其复原所需的移动步数也变化不大。复原步数与方阵的阶数有关，无论打乱多少次，复原步数都是趋于一个稳定的范围。

打乱方块顺序.gif

随机移动一定步数.png

拼图状态
我们需要定义一个类来表示拼图在某个时刻的状态。

一个状态应持有以下几个属性：

矩阵阶数

方块数组，以数组的顺序来表示本状态下方块的排列顺序

空格所在的位置，其值指向方块数组中显示成空白的那一个方块

同时它应能提供操作方块的方法，以演进游戏状态。

判断空格是否能移动到某个位置

把空格移动到某个位置

移除所有方块

打乱所有方块，变成一个随机状态

与另一个状态对象进行比较，判断是否状态等同

/// 表示游戏过程中，某一个时刻，所有方块的排列状态 @interface PuzzleStatus : NSObject <JXPathSearcherStatus, JXAStarSearcherStatus> /// 矩阵阶数 @property (nonatomic, assign) NSInteger matrixOrder; /// 方块数组，按从上到下，从左到右，顺序排列
@property (nonatomic, strong) NSMutableArray<PuzzlePiece *> *pieceArray; /// 空格位置，无空格时为-1 @property (nonatomic, assign) NSInteger emptyIndex; /// 创建实例，matrixOrder至少为3，image非空+ (instancetype)statusWithMatrixOrder:(NSInteger)matrixOrder image:(UIImage *)image;
/// 复制本实例 - (instancetype)copyStatus ;/// 判断是否与另一个状态相同 - (BOOL)equalWithStatus:(PuzzleStatus *)status; /// 打乱，传入随机移动的步数 - (void)shuffleCount:(NSInteger)count; /// 移除所有方块 - (void)removeAllPieces; /// 空格是否能移动到某个位置 - (BOOL)canMoveToIndex:(NSInteger)index; ///
把空格移动到某个位置 - (void)moveToIndex:(NSInteger)index; @end

使游戏具备人工智能
我们把拼图在某个时刻的方块排列称为一个状态，那么一旦发生方块移动，就会生成一个新的状态。

对于每个状态来说，它都能够通过改变空格的位置而衍生出另一个状态，而衍生出的状态又能够衍生出另一些状态。这种行为非常像一棵树的生成，当然这里的树指的是数据结构上的树结构。

拼图状态树.png

推演移动路径的过程，就是根据当前状态不断衍生状态，然后判断新状态是否为我们的目标状态(拼图完全复原时的状态)。如果找到了目标，就可以原路返回，依次找出目标所经过的所有状态。

由此，状态树中的每一个结点都需要提供以下属性和方法：

父结点引用。要实现从目标状态逆向找回所有经过的状态，需要让每一个状态都持有它上一状态的引用，即持有它的父结点引用。

结点的唯一标识。用于算法过程中识别状态等同，以及哈希策略去重。

子结点的生成方法。用于衍生出新的结点，演进搜索。

/// 状态协议 @protocol JXPathSearcherStatus <NSObject> /// 父状态 @property (nonatomic, strong) id<JXPathSearcherStatus> parentStatus; /// 此状态的唯一标识 - (NSString *)statusIdentifier; /// 取所有邻近状态(子状态)，排除父状态。每一个状态都需要给parentStatus赋值。
- (NSMutableArray<id<JXPathSearcherStatus>> *)childStatus;@end

对于一个路径搜索算法来说，它应该知道开始于哪里，和结束于哪里。

再有，作为一个通用的算法，不仅限于拼图游戏的话，它还需要算法使用者传入一个比较器，用于判断两个搜索状态是否等同，因为算法并不清楚它所搜索的是什么东西，也就不知道如何确定任意两个状态是否一样的。

给路径搜索算法作如下属性和方法定义：

/// 比较器定义 typedef BOOL(^JXPathSearcherEqualComparator)(id<JXPathSearcherStatus> status1, id<JXPathSearcherStatus> status2); /// 路径搜索 @interface JXPathSearcher : NSObject /// 开始状态 @property
(nonatomic, strong) id<JXPathSearcherStatus> startStatus; /// 目标状态 @property (nonatomic, strong) id<JXPathSearcherStatus> targetStatus; /// 比较器 @property (nonatomic, strong) JXPathSearcherEqualComparator equalComparator; /// 开始搜索，返回搜索结果。无法搜索时返回 nil- (NSMutableArray
*)search; /// 构建路径。isLast表示传入的status是否路径的最后一个元素 - (NSMutableArray *)constructPathWithStatus:(id<JXPathSearcherStatus>)status isLast(BOOL)isLast; @end

关于“搜索”两字，在代码上可以理解为拿着某个状态与目标状态进行比较，如果这两个状态一致，则搜索成功；如果不一致，则继续取另一个状态与目标状态比较，如此循环下去直到找出与目标一致的状态。

各算法的区别，主要在于它们对搜索空间内的状态结点有不同的搜索顺序。

广度优先搜索
广度优先搜索是一种盲目搜索算法，它认为所有状态(或者说结点)都是等价的，不存在优劣之分。

假如我们把所有需要搜索的状态组成一棵树来看，广搜就是一层搜完再搜下一层，直到找出目标结点，或搜完整棵树为止。

1、我们可以使用一个先进先出(First Input First Output, FIFO)的队列来存放待搜索的状态，这个队列可以给它一个名称叫开放队列，也有人把它叫做开放列表(Open List)。

2、然后还需要把所有已搜索过的状态记录下来，以确保不会对已搜索过的状态作重复扩展，注意这里的扩展即为衍生出子状态，对应于拼图游戏来说就是空格移动了一格。

由于每搜到一个状态，都需要拿着这个状态去已搜记录中查询是否有这个状态存在，那么已搜记录要使用怎样的存储方式才能适应这种高频率查找需求呢？

假如我们使用数组来存储所有已搜记录，那么每一次查找都需要遍历整个数组。当已搜记录表的数据有10万条时，再去搜一个新状态，就需要做10万次循环来确定新状态是从来没有被搜索过的。显然这样做的效率是非常低的。

一种高效的方法是哈希策略，哈希表(Hash Table)能通过键值映射直接查找到目标对象，免去遍历整个存储空间。在Cocoa框架中，已经有能满足这种键值映射的数据结构--字典。这里我没有再去实现一个哈希表，而是使用NSMutableDictionary来存放已搜记录。我们可以给这个存储空间起个名字叫关闭堆，也有人把它叫做关闭列表(Close List)。

1、搜索开始时，开放队列是空的，然后我们把起始状态入队，此时开放队列有了一个待搜索的状态，搜索循环开始。

2、每一次循环的目的，就是搜索一个状态。所谓搜索，前面已经讲过，可以通俗理解为就是比较。我们需要从开放队列中取出一个状态来，假如取出的状态是已经比较过了的，则放弃此次循环，直到取出一个从来没有比较过的状态。

3、拿着取出的新状态，与目标状态比较，如果一致，则说明路径已找到。为何说路径已找到了呢？因为每一个状态都持有一个父状态的引用，意思是它记录着自己是来源于哪一个状态衍生出来的，所以每一个状态都必然知道自己上一个状态是谁，除了开始状态。

4、找到目标状态后，就可以构建路径。所谓路径，就是从开始状态到目标状态的搜索过程中，经过的所有状态连起来组成的数组。我们可以从搜索结束的状态开始，把它放入数组中，然后把这个状态的父状态放入数组中，再把其祖先状态放入数组中，直到放入开始状态。如何识别出开始状态呢？当发现某个状态是没有父状态的，就说明了它是开始状态。最后算法把构建完成的路径作为结果返回。

5、在第5步中，如果发现取出的新状态并非目标状态，这时就需要衍生新的状态来推进搜索。调用生成子状态的方法，把产生的子状态入队，依次追加到队列尾，这些入队的子状态将会在以后的循环中被搜索。由于队列的FIFO特性，在循环进行过程中，将会优先把某个状态的子状态全部出列完后，再出列其子状态的子状态。入列和出列的两步操作决定了算法的搜索顺序，这里的操作实现了广度优先搜索。

广度优先搜索：

- (NSMutableArray *)search {
if (!self.startStatus || !self.targetStatus || !self.equalComparator) {
return nil;
}
NSMutableArray *path = [NSMutableArray array];
// 关闭堆，存放已搜索过的状态
NSMutableDictionary *close = [NSMutableDictionary dictionary];
// 开放队列，存放由已搜索过的状态所扩展出来的未搜索状态
NSMutableArray *open = [NSMutableArray array];
while (open.count > 0) {
// 出列
id status = [open firstObject];
[open removeObjectAtIndex:0];
// 排除已经搜索过的状态
NSString *statusIdentifier = [status statusIdentifier];
if (close[statusIdentifier]) {
continue;
}
close[statusIdentifier] = status;
// 如果找到目标状态
if (self.equalComparator(self.targetStatus, status)) {
path = [self constructPathWithStatus:status isLast:YES];
break;
}
// 否则，扩展出子状态
}
NSLog(@"总共搜索了: %@个状态", @(close.count));
return path; }

构建路径：

/// 构建路径。isLast表示传入的status是否路径的最后一个元素
- (NSMutableArray *)constructPathWithStatus:(id<JXPathSearcherStatus>)status isLast:(BOOL)isLast {
NSMutableArray *path = [NSMutableArray array];
if (!status) {
return path;
}
do {
if (isLast) {
[path insertObject:status atIndex:0];
}
else {
}
status = [status parentStatus];
} while (status);
returnpath; }

3阶方阵，广搜平均需要搜索10万个状态

双向广度优先搜索
双向广度优先搜索是对广度优先搜索的优化，但是有一个使用条件：搜索路径可逆。

搜索原理
双向广搜是同时从开始状态和目标状态展开搜索的，这样就会产生两棵搜索状态树。我们想象一下，让起始于开始状态的树从上往下生长，再让起始于目标状态的树从下往上生长，同时在它们的生长空间中遍布着一个一个的状态结点，等待着这两棵树延伸去触及。
由于任一个状态都是唯一存在的，当两棵搜索树都触及到了某个状态时，这两棵树就出现了交叉，搜索即告结束。

让两棵树从发生交叉的状态结点各自原路返回构建路径，然后算法把两条路径拼接起来，即为结果路径。

可用条件
对于拼图游戏来说，已经知道了开始状态(某个乱序的状态)和目标状态(图片复原时的状态)，而这两个状态其实是可以互换的，完全可以从目标复原状态开始搜索，反向推进，直到找出拼图开始时的乱序状态。所以，我们的拼图游戏是路径可逆的，适合双向广搜。

单线程下的双向广搜
要实现双向广搜，并不需要真的用两条线程分别从开始状态和目标状态对向展开搜索，在单线程下也完全可以实现，实现的关键是于让两个开放队列交替出列元素。

在每一次循环中，比较两个开放队列的长度，每一次都选择最短的队列进行搜索，优先让较小的树生长出子结点。这样做能够使两个开放队列维持大致相同的长度，同步增长，达到均衡两棵搜索树的效果。

- (NSMutableArray *)search {
if (!self.startStatus || !self.targetStatus || !self.equalComparator) {
return nil;
}
NSMutableArray *path = [NSMutableArray array];
// 关闭堆，存放已搜索过的状态
NSMutableDictionary *positiveClose = [NSMutableDictionary dictionary];
NSMutableDictionary *negativeClose = [NSMutableDictionary dictionary];
// 开放队列，存放由已搜索过的状态所扩展出来的未搜索状态
NSMutableArray *positiveOpen = [NSMutableArray array];
NSMutableArray *negativeOpen = [NSMutableArray array];
while (positiveOpen.count > 0 || negativeOpen.count > 0) {
// 较短的那个扩展队列
NSMutableArray *open;
// 短队列对应的关闭堆
NSMutableDictionary *close;
// 另一个关闭堆
NSMutableDictionary *otherClose;
// 找出短队列
if (positiveOpen.count && (positiveOpen.count < negativeOpen.count)) {
open = positiveOpen;
close = positiveClose;
otherClose = negativeClose;
}
else {
open = negativeOpen;
close = negativeClose;
otherClose = positiveClose;
}
// 出列
id status = [open firstObject];
[open removeObjectAtIndex:0];
// 排除已经搜索过的状态
NSString *statusIdentifier = [status statusIdentifier];
if (close[statusIdentifier]) {
continue;
}
close[statusIdentifier] = status;
// 如果本状态同时存在于另一个已检查堆，则说明正反两棵搜索树出现交叉，搜索结束
if (otherClose[statusIdentifier]) {
NSMutableArray *positivePath = [self constructPathWithStatus:positiveClose[statusIdentifier] isLast:YES];

NSMutableArray *negativePath = [self constructPathWithStatus:negativeClose[statusIdentifier] isLast:NO];
// 拼接正反两条路径
path = positivePath;
break;
}
// 否则，扩展出子状态
}
NSLog(@"总搜索数量: %@", @(positiveClose.count + negativeClose.count - 1));
return path; }

3阶方阵，双向广搜平均需要搜索3500个状态

A*搜索（A Star）
不同于盲目搜索，A*算法是一种启发式算法(Heuristic Algorithm)。

上文提到，盲目搜索对于所有要搜索的状态结点都是一视同仁的，因此在每次搜索一个状态时，盲目搜索并不会考虑这个状态到底是有利于趋向目标的，还是偏离目标的。

而启发式搜索的启发二字，看起来是不是感觉这个算法就变得聪明一点了呢？正是这样，启发式搜索对于待搜索的状态会进行不同的优劣判断，这个判断的结果将会对算法搜索顺序起到一种启发作用，越优秀的状态将会得到越高的搜索优先级。

我们把对于状态优劣判断的方法称为启发函数，通过给它评定一个搜索代价来量化启发值。

启发函数应针对不同的使用场景来设计，那么在拼图的游戏中，如何评定某个状态的优劣性呢？粗略的评估方法有两种：

1、可以想到，某个状态它的方块位置放对的越多，说明它能复原目标的希望就越大，这个状态就越优秀，优先选择它就能减少无效的搜索，经过它而推演到目标的代价就会小。所以可求出某个状态所有方块的错位数量来作为评估值，错位越少，状态越优秀。

2、假如让拼图上的每个方块都可以穿过邻近方块，无阻碍地移动到目标位置，那么每个不在正确位置上的方块它距离正确位置都会存在一个移动距离，这个非直线的距离即为曼哈顿距离(Manhattan Distance)，我们把每个方块距离其正确位置的曼哈顿距离相加起来，所求的和可以作为搜索代价的值，值越小则可认为状态越优秀。

其实上述两种评定方法都只是对当前状态距离目标状态的代价评估，我们还忽略了一点，就是这个状态距离搜索开始的状态是否已经非常远了，亦即状态结点的深度值。

在拼图游戏中，我们进行的是路径搜索，假如搜索出来的一条移动路径其需要的步数非常多，即使最终能够把拼图复原，那也不是我们希望的路径。所以，路径搜索存在一个最优解的问题，搜索出来的路径所需要移动的步数越少，就越优。

A*算法对某个状态结点的评估，应综合考虑这个结点距离开始结点的代价与距离目标结点的代价。总估价公式可以表示为：

f(n) = g(n) + h(n)

n表示某个结点，f(n)表示对某个结点进行评价，值等于这个结点距离开始结点的已知价g(n)加上距离目标结点的估算价h(n)。

为什么说g(n)的值是确定已知的呢？在每次生成子状态结点时，子状态的g值应在它父状态的基础上+1，以此表示距离开始状态增加了一步，即深度加深了。所以每一个状态的g值并不需要估算，是实实在在确定的值。

影响算法效率的关键点在于h(n)的计算，采用不同的方法来计算h值将会让算法产生巨大的差异。

当增大h值的权重，即让h值远超g值时，算法偏向于快速寻找到目标状态，而忽略路径长度，这样搜索出来的结果就很难保证是最优解了，意味着可能会多绕一些弯路，通往目标状态的步数会比较多。

当减小h值的权重，降低启发信息量，算法将偏向于注重已搜深度，当h(n)恒为0时，A*算法其实已退化为广度优先搜索了。(这是为照应上文的方便说法。严谨的说法应是退化为Dijkstra算法，在本游戏中，广搜可等同为Dijkstra算法，关于Dijkstra这里不作深入展开。)

以下是拼图状态结点PuzzleStatus的估价方法，在实际测试中，使用方块错位数量来作估价的效果不太明显，所以这里只使用曼哈顿距离来作为h(n)估价，已能达到不错的算法效率。

/// 估算从当前状态到目标状态的代价
- (NSInteger)estimateToTargetStatus:(id<JXPathSearcherStatus>)targetStatus {
PuzzleStatus *target = (PuzzleStatus *)targetStatus;
// 计算每一个方块距离它正确位置的距离
// 曼哈顿距离
NSInteger manhattanDistance = 0;
for (NSInteger index = 0; index < self.pieceArray.count; ++ index) {
// 略过空格
if (index == self.emptyIndex) {
continue;
}
PuzzlePiece *currentPiece = self.pieceArray[index];
PuzzlePiece *targetPiece = target.pieceArray[index];
manhattanDistance +=
ABS([self rowOfIndex:currentPiece.ID] - [target rowOfIndex:targetPiece.ID]) +
ABS([self colOfIndex:currentPiece.ID] - [target colOfIndex:targetPiece.ID]);
}
// 增大权重
return 5 * manhattanDistance;
}

状态估价由状态类自己负责，A*算法只询问状态的估价结果，并进行f(n) = g(n) + h(b)操作，确保每一次搜索，都是待搜空间里代价最小的状态，即f值最小的状态。

那么问题来了，在给每个状态都计算并赋予上f值后，如何做到每一次只取f值最小的那个？

前文已讲到，所有扩展出来的新状态都会放入开放队列中的，如果A*算法也像广搜那样只放在队列尾，然后每次只取队首元素来搜索的话，那么f值完全没有起到作用。

事实上，因为每个状态都有f值的存在，它们已经有了优劣高下之分，队列在存取它们的时候，应当按其f值而有选择地进行入列出列，这时候需要用到优先队列(Priority Queue)，它能够每次出列优先级最高的元素。

关于优先队列的讲解和实现，可参考另一篇文章《借助完全二叉树，实现优先队列与堆排序》（http://www.jianshu.com/p/9a456d1b59b5），这里不再展开论述。

以下是A*搜索算法的代码实现：

- (NSMutableArray *)search {
if (!self.startStatus || !self.targetStatus || !self.equalComparator) {
return nil;
}
NSMutableArray *path = [NSMutableArray array];
[(id<JXAStarSearcherStatus>)[self startStatus] setGValue:0];
// 关闭堆，存放已搜索过的状态
NSMutableDictionary *close = [NSMutableDictionary dictionary];
// 开放队列，存放由已搜索过的状态所扩展出来的未搜索状态
// 使用优先队列
JXPriorityQueue *open = [JXPriorityQueue queueWithComparator:^NSComparisonResult(id<JXAStarSearcherStatus> obj1, id<JXAStarSearcherStatus> obj2) {

if ([obj1 fValue] == [obj2 fValue]) {
return NSOrderedSame;
}
// f值越小，优先级越高
return [obj1 fValue] < [obj2 fValue] ? NSOrderedDescending : NSOrderedAscending;    }];

[open enQueue:self.startStatus];
while (open.count > 0) {
// 出列
id status = [open deQueue];
// 排除已经搜索过的状态
NSString *statusIdentifier = [status statusIdentifier];
if (close[statusIdentifier]) {
continue;
}
close[statusIdentifier] = status;
// 如果找到目标状态
if (self.equalComparator(self.targetStatus, status)) {
path = [self constructPathWithStatus:status isLast:YES];
break;
}
// 否则，扩展出子状态
NSMutableArray *childStatus = [status childStatus];
// 对各个子状进行代价估算
[childStatus enumerateObjectsUsingBlock:^(id<JXAStarSearcherStatus>  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {

// 子状态的实际代价比本状态大1
[obj setGValue:[status gValue] + 1];
// 估算到目标状态的代价
[obj setHValue:[obj estimateToTargetStatus:self.targetStatus]];
// 总价=已知代价+未知估算代价
[obj setFValue:[obj gValue] + [obj hValue]];
// 入列
[open enQueue:obj];
}];
}
NSLog(@"总共搜索: %@", @(close.count));
return path; }

可以看到，代码基本是以广搜为模块，加入了f(n) = g(n) + h(b)的操作，并且使用了优先队列作为开放表，这样改进后，算法的效率是不可同日而语。

3阶方阵，A*算法平均需要搜索300个状态

最后，贴上高难度下依然战斗力爆表的A*算法效果图：

5阶方阵下的A*搜索算法

源码
Puzzle Game：https://github.com/JiongXing/PuzzleGame

往期精彩回顾

LSTM模型在问答系统中的应用
基于TensorFlow的神经网络解决用户流失概览问题
最全常见算法工程师面试题目整理（一）
最全常见算法工程师面试题目整理（二）
TensorFlow从1到2
| 第三章 深度学习革命的开端：卷积神经网络
装饰器
| Python高级编程
今天不如来复习下Python基础

点击“阅读原文”直接打开【北京站 | GPU CUDA 进阶课程】报名链接


展开全文
• C语言实现拼图游戏

千次阅读 多人点赞 2020-09-26 16:15:14
C语言实现拼图游戏 这篇文章主要为大家详细介绍了C语言实现拼图游戏，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下哦~ 1.实现图形界面 一维数组，二维数组，图形库里面的贴图 ...
• Android拼图游戏开发全纪录0

万次阅读 多人点赞 2014-01-30 11:29:27
最近刚完成一个Android的小项目--拼图游戏。项目并不复杂，但也是一个完整的项目，用到的知识点还是比较丰富的。 做完之后照例进行下总结： 需求定义： 1、选择图片后进入拼图界面，可以选择默认图片或者自定义图片...
• &lt;!--代码如下，最下面给出了我测试用的9张250*250的图片切片--&gt; &lt;!DOCTYPE html&gt; &lt;html&gt; &lt;head&gt; &lt;meta charset="utf-8"...
• 设计思路 1、将一张海报等分成 N*N 的矩阵 ... 方法一：利用两个组件循环完成，view组件和image组件，view组件作为盒子规定大小—-超出部分不显示，image组件展示完整的海报—-进行定位。... 方法二：利用一个组件...
• 基于MATLAB的拼图游戏设计 内容摘要：MATLAB强大的运算和图形展示功能，使图像处理变得更加的简单和直观。本博文基于MATLAB编程语言，详细介绍了如何利用MATLAB及其图像处理函数进行经典拼图游戏设计，并通过...
• 自制的MATLAB拼图游戏GUI界面版详解（上篇）

万次阅读 多人点赞 2020-02-09 21:19:23
摘要：这篇博文在早前本人写的介绍拼图游戏的基础上推出带有GUI用户界面的增强版，这里将通过上、中、下三篇博文详细介绍利用MATLAB GUI设计的拼图游戏完整实现过程，每篇都会附上相应代码及解释。上篇主要讲解拼图...
• 拼图游戏都玩过， 对于一个n*m的拼图游戏，我们将按照从左到右，从上到下的顺序给每个分格标注，可得一个二维矩阵。以3*3为例，标注结果如： 0 1 2 3 4 5 6 7 8 我们假设最大值为空白。即游戏时的样子是这样的： 0 ...
• 本课程以“拼图游戏”为项目，按照软件开发的流程，从游戏的分析和设计入手，确定游戏的背景、角色和规则；然后从准备素材到功能模块编程到调试，体验完整的项目开发过程。学习者会不断地遇到问题，分析原因，训练...
• 效果图 图片分块 创建二维数组 typeArr 和一维有序数组 pointsArr； 计算每个块区view的定位坐标（x，y）和view的背景坐标（px，py）、以及每个view的顺序 count； 填充数组 pointsArr 的对应值 ......
• [Android]自己动手做个拼图游戏

万次阅读 多人点赞 2017-10-25 19:45:23
目标在做这个游戏之前，我们先定一些小目标列出来，一个一个的解决，这样，一个小游戏就不知不觉的完成啦。我们的目标如下： 1. 游戏全屏，将图片拉伸成屏幕大小，并将其切成若干块。 2. 将拼图块随机打乱，并保证...
• 摘要：这篇博文在早前本人写的介绍拼图游戏的基础上推出带有GUI用户界面的增强版，这里将通过上、中、下三篇博文详细介绍利用MATLAB GUI设计的拼图游戏完整实现过程，每篇都会附上相应代码及解释。中篇主要讲解拼图...
• 在上一篇文章中我们已经写完了一个可以正常玩的拼图小游戏，但是这还没有结束，我们还要接着试一下让拼图游戏可以自己完成拼图。 最终效果如下图： 本部分是这篇文章的第二部分，主要讲的是实现自动拼图的功能实现...
• 自己做了一个拼图游戏，大概如下： 1 2 3 4 5 6 7 8 0 0是空白位置，每次按照随机的顺序重新排列，但是不是每次排列后都可能被还原，例如： 1 2 3 4 5 6 8 7 0 这样是复原不了的 ----------------------割---...
• 随着几个项目的提测，也闲下来了，恰好玩了一把拼图游戏，于是突发奇想打算自己写一个试试。 最终效果如下图： 实现的功能有： 普通拼图的功能 自动拼图 本部分是这篇文章的第一部分，主要讲的是实现普通拼图的...
...