精华内容
下载资源
问答
  • 儿童拼图游戏源码

    2021-04-02 20:07:59
    这是一款与儿时玩的拼图板一样的IOS小游戏,玩家需要在规定时间内把所有的拼图碎片都放置在正确的位置上,每次只能移动空白碎片周围的碎片。该作品来自网友Alex的上传,转载时请注明资源的来源,感谢你的合作。
  • 学习软件_早教启蒙_幼儿拼图识物免费下载.zip
  • 宝宝喜欢玩拼图,网上挺不好找,求人不如求已, 自己用C++builder作了一个,解压就可以用了。 可以自由增添图片 要求必须是560*500的BMP文件,放在image目录下 不会作的话到我的空间去下一些。 背景音乐可以换 ...
  • FLASH拼图游戏源码

    2014-08-21 16:07:08
    10多年前为朋友生日,写的小拼图游戏.意外在硬盘上找到了.
  • flash拼图游戏

    2014-03-30 09:21:55
    用flash制作,用了许多代码,stop(); i=0 stop(); on (press) { if(eval(_root.tp14._droptarget)<>_root.fg14) { _root.tp14.startDrag(true); } } on (release) { ..._root.i=Number(_root.i)+1
  • 主要为大家详细介绍了基于Android平台实现拼图小游戏,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 拼图日托幼儿园网页模板
  • H5益智拼图小游戏1.1

    2020-07-13 12:29:43
    益智拼图小游戏1.1,本次更新修复了部分bug,优化了显示页面,并对拼图过程进行了优化,拼图成功后屏幕将会闪烁,增加互动性。
  • 又一个Flash拼图游戏 Flash源码,若拼图成功后会得到一张海豚跃水的图片,很漂亮,默认状态下,海豚图片是被打散的,自己拖动相应打散的图片块到上边的空白处,组成一张完整的图像即可。
  • Reliquarium是为孩子们设计的一组独特的四个3D几何滑块,全部以水晶头骨为主题。... 这些独特的难题在空间上具有挑战性,但对于儿童来说足够容易,并且可能会有助于学习3D可视化,几何,解决问题和计算机技能。
  • 【系列介绍】儿童游戏系列教育应用是根据教育部新颁布的《3-6岁儿童学习与发展指南》进行策划,充分研究了3-6岁幼儿学习与发展的基本规律和特点,激发孩子的学习兴趣,同时又防止学前教育小学化,让你的孩子在娱乐...
  • 拼图游戏和它的AI算法

    千次阅读 2017-11-08 00:00:00
    写了个拼图游戏,探讨一下相关的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];  
     [open addObject:self.startStatus];    
    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;      
     }        
    // 否则,扩展出子状态      
     [open addObjectsFromArray:[status childStatus]];  
     }    
    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 {          
     [path addObject:status];      
     }      
     status = [status parentStatus];  
     } while (status);  
      return
    path; }



    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];    
    [positiveOpen addObject:self.startStatus];    
    [negativeOpen addObject:self.targetStatus];  
     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];            
    // 拼接正反两条路径          
     [positivePath addObjectsFromArray:negativePath];            
    path = positivePath;          
     break;        
    }        
    // 否则,扩展出子状态        
    [open addObjectsFromArray:[status childStatus]];  
     }    
    NSLog(@"总搜索数量: %@", @(positiveClose.count + negativeClose.c
    ount - 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 * manhat
    tanDistance;
     }


    状态估价由状态类自己负责,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.c
    ount));    
    return path; }


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



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


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



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


    源码

    Puzzle Game:https://github.com/JiongXing/PuzzleGame


    原文链接:http://www.jianshu.com/p/10a6d02616ad


    往期精彩回顾


    LSTM模型在问答系统中的应用

    基于TensorFlow的神经网络解决用户流失概览问题

    最全常见算法工程师面试题目整理(一)

    最全常见算法工程师面试题目整理(二)

    TensorFlow从1到2 | 第三章 深度学习革命的开端:卷积神经网络

    装饰器 | Python高级编程

    今天不如来复习下Python基础


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

    展开全文
  • cocos2d-x 拼图实现demo

    2018-05-29 10:37:31
    最近公司要在一个项目里接入一个拼玩法,下面我简单做了一个demo 1. 碎片的实现 这里派生一个Piece类来实现 Piece.h // // Piece.hpp // Puzzle-mobile // // Created by LiYong on 2018/4/20...#include ...
    最近公司要在一个项目里接入一个拼玩法,下面我简单做了一个demo
    

    ###1. 碎片的实现
    这里派生一个Piece类来实现

    ####Piece.h

    #ifndef Piece_hpp
    #define Piece_hpp
    
    #include <stdio.h>
    #include "cocos2d.h"
    #define  DELTA 50
    
    typedef enum
    {
        GROUP_NULL = 0,
        GROUP_1    = 1,
        GROUP_2    = 2,
        GROUP_3    = 3,
    }Type;
    
    
    using namespace cocos2d;
    class Piece : public Sprite
    {
    public:
    
    public:
        Piece();
        ~Piece();
        static Piece* create(const std::string &filename);
        virtual bool init(const std::string &filename);
    
    public:
        /*点击到碎片*/
        void setActived(bool bActive);
        bool getActived();
    
        /*碎片是否和其他组合*/
        void setIsInGroup(bool bGroup);
        bool getIsInGroup();
    
        /*设置目标位置*/
        void setTargetPoistion(Vec2 targetPosition);
        Vec2 getTargetPosition();
    
        /*一定误差范围内移动到正确位置*/
        void moveToTargetPosition();
        /*碎片是否已经移动到正确的位置*/
        void setIsMovedSuccessed(bool success);
        bool getIsMovedSuccessed();
    
        /*本次触摸事件完成*/
        void setIsEnded(bool end);
        bool getIsEnded();
        /*加入的组合*/
        void setType(Type type);
        Type getType();
    private:
        bool m_bActived;
        bool m_bSuccessed;
        bool m_bGroup;
        bool m_bEnded;
        Vec2 m_targetPosition;
    
        Type m_nType;
    };
    #endif /* Piece_hpp */
    
    

    ####Piece.cpp

    //
    //  Piece.cpp
    //  Puzzle-mobile
    
    #include "Piece.hpp"
    Piece::Piece() : m_targetPosition(Vec2(0,0)),m_bGroup(false),m_bSuccessed(false),m_bEnded(false)
    {
    
    }
    Piece::~Piece()
    {
        m_targetPosition = Vec2(0,0);
    }
    Piece *Piece::create(const std::string &filename)
    {
        Piece *piece = new Piece();
        if (piece && piece->init(filename))
        {
            piece->autorelease();
        }
        else
        {
            delete piece;
            return nullptr;
        }
        return piece;
    }
    bool Piece::init(const std::string &filename)
    {
        if (!Sprite::init())
        {
            return false;
        }
        this->initWithFile(filename);
        return true;
    }
    void Piece::setIsEnded(bool end)
    {
        this->m_bEnded = end;
    }
    bool Piece::getIsEnded()
    {
        return this->m_bEnded;
    }
    void Piece::setTargetPoistion(cocos2d::Vec2 targetPosition)
    {
        m_targetPosition = targetPosition;
    }
    Vec2 Piece::getTargetPosition()
    {
        return this->m_targetPosition;
    }
    void Piece::setActived(bool bActive)
    {
        this->m_bActived = bActive;
    }
    bool Piece::getActived()
    {
        return this->m_bActived;
    }
    void Piece::setIsInGroup(bool bGroup)
    {
        this->m_bGroup = bGroup;
    }
    bool Piece::getIsInGroup()
    {
        return this->m_bGroup;
    }
    void Piece::setIsMovedSuccessed(bool success)
    {
        m_bSuccessed = success;
    }
    bool Piece::getIsMovedSuccessed()
    {
        return m_bSuccessed;
    }
    void Piece::moveToTargetPosition()
    {
        this->runAction(MoveTo::create(0.2f, m_targetPosition));
        this->setIsMovedSuccessed(true);
    }
    void Piece::setType(Type type)
    {
        this->m_nType = type;
    }
    Type Piece::getType()
    {
        return this->m_nType;
    }
    
    
    

    ####PuzzleScene.h

    //
    //  PuzzleScene.hpp
    //  Puzzle-mobile
    
    
    #ifndef PuzzleScene_hpp
    #define PuzzleScene_hpp
    
    #include <stdio.h>
    #include "cocos2d.h"
    #include "Piece.hpp"
    USING_NS_CC;
    
    using namespace std;
    class PuzzleScene :  public Layer
    {
    public:
        PuzzleScene();
        ~PuzzleScene();
    
        static Scene *scene();
    
        bool init();
    
    
        virtual void setTouchListener();
        virtual bool onTouchBegan(Touch *touch,Event *unused_event);
        virtual void onTouchMoved(Touch *touch,Event *unused_event);
        virtual void onTouchEnded(Touch *touch,Event *unused_event);
    
        CREATE_FUNC(PuzzleScene);
    
    public:
        void checkPiecePosition(Vec2 pt);
    
        bool checkPiecePositionRelativePiece(int i, int j);//没有组合时碎片的相对位置
        bool checkPiecePositionRelativeGroup(int i, int j);//检测碎片相对于组合的位置
        bool checkGroupPositionRelativePiece(int i, vector<Piece *> vec);//检测组合相对位置
    
        void checkFinalPosition();
    private:
        map<Type,vector<Piece *>> m_mapPiece;
        vector<Piece *> m_vecPiece;
        vector<Vec2> m_positionVec;
        Sprite *m_background;
    };
    #endif /* PuzzleScene_hpp */
    
    

    ####PuzzleScene.cpp

    //
    //  PuzzleScene.cpp
    //  Puzzle-mobile
    
    #include "PuzzleScene.hpp"
    
    PuzzleScene::PuzzleScene()
    {
    
    }
    PuzzleScene::~PuzzleScene()
    {
    
    }
    Scene *PuzzleScene::scene()
    {
        Scene *scene = Scene::create();
        PuzzleScene *pLayer = PuzzleScene::create();
        scene->addChild(pLayer);
        return scene;
    }
    
    
    bool PuzzleScene::init()
    {
        if (!Layer::init())
        {
            return false;
        }
    
        LayerColor *layer = LayerColor::create(Color4B(255,255,255,255));
        this->addChild(layer,0);
        this->m_background = Sprite::create("puzzle/background.png");
        this->m_background->setPosition(Vec2(this->getContentSize().width/2,this->getContentSize().height/2));
        this->addChild(m_background,1);
    
        Vec2 positionPieceTopLeft     = Vec2(m_background->getPositionX()- m_background->getContentSize().width/4,
                                             m_background->getPositionY()+ m_background->getContentSize().height/4);
    
        Vec2 positionPieceTopRight    = Vec2(m_background->getPositionX()+ m_background->getContentSize().width/4,
                                             m_background->getPositionY()+ m_background->getContentSize().height/4);
    
        Vec2 positionPieceBottomLeft  = Vec2(m_background->getPositionX()- m_background->getContentSize().width/4,
                                             m_background->getPositionY()- m_background->getContentSize().height/4);
    
        Vec2 positionPieceBottomRight = Vec2(m_background->getPositionX()+ m_background->getContentSize().width/4,
                                             m_background->getPositionY()- m_background->getContentSize().height/4);
        m_positionVec.push_back(positionPieceTopLeft);
        m_positionVec.push_back(positionPieceTopRight);
        m_positionVec.push_back(positionPieceBottomLeft);
        m_positionVec.push_back(positionPieceBottomRight);
    
        for (int i = 0; i < 4; i++)
        {
            Piece *piece = Piece::create("puzzle/piece_0" + to_string(i) + ".png");
            piece->setTargetPoistion(m_positionVec[i]);
            piece->setPosition(Vec2(piece->getContentSize().width,this->getContentSize().height - piece->getContentSize().height * i - 50));
            this->m_vecPiece.push_back(piece);
            this->addChild(piece,2);
        }
        setTouchListener();
        return true;
    }
    
    void PuzzleScene::setTouchListener()
    {
        EventListenerTouchOneByOne *listener = EventListenerTouchOneByOne::create();
        listener->onTouchBegan = CC_CALLBACK_2(PuzzleScene::onTouchBegan, this);
        listener->onTouchMoved = CC_CALLBACK_2(PuzzleScene::onTouchMoved, this);
        listener->onTouchEnded = CC_CALLBACK_2(PuzzleScene::onTouchEnded, this);
        _eventDispatcher->addEventListenerWithSceneGraphPriority(listener, this);
    }
    
    bool PuzzleScene::onTouchBegan(cocos2d::Touch *touch, cocos2d::Event *unused_event)
    {
        for (int i = 0; i < m_vecPiece.size(); i++)
        {
            if (m_vecPiece.at(i)->getBoundingBox().containsPoint(touch->getLocation()) && !m_vecPiece.at(i)->getIsMovedSuccessed())
            {
                m_vecPiece.at(i)->setActived(true);
            }
        }
    
    
        return true;
    }
    void PuzzleScene::onTouchMoved(cocos2d::Touch *touch, cocos2d::Event *unused_event)
    {
        Vec2 delta = touch->getDelta();
        for (int i = 0; i < m_vecPiece.size(); i++)
        {
            if (m_vecPiece.at(i)->getActived() && !m_vecPiece.at(i)->getIsMovedSuccessed())
            {
                if (!m_vecPiece.at(i)->getIsInGroup())
                {
                    m_vecPiece.at(i)->setPosition(m_vecPiece.at(i)->getPosition() + delta);
                    return;
                }
                else
                {
                    map<Type, vector<Piece *>>::iterator itor = m_mapPiece.find(m_vecPiece.at(i)->getType());
                    if (itor != m_mapPiece.end())
                    {
                        vector<Piece *> vec = itor->second;
                        for (int j = 0; j < vec.size(); j++)
                        {
                            vec.at(j)->setPosition(vec.at(j)->getPosition() + delta);
                        }
                    }
                }
            }
        }
    }
    void PuzzleScene::onTouchEnded(cocos2d::Touch *touch, cocos2d::Event *unused_event)
    {
    
        checkPiecePosition(touch->getLocation());
    
        checkFinalPosition();
        for (int i = 0; i < m_vecPiece.size(); i++)
        {
            m_vecPiece.at(i)->setIsEnded(false);
            m_vecPiece.at(i)->setActived(false);
        }
    }
    
    void PuzzleScene::checkPiecePosition(cocos2d::Vec2 pt)
    {
        for (int i = 0; i < m_vecPiece.size(); i++)
        {
            if (m_vecPiece.at(i)->getActived() && !m_vecPiece.at(i)->getIsMovedSuccessed())
            {
                //位置发生变化的碎片没有和其他碎片组合时
                if (!m_vecPiece.at(i)->getIsInGroup())
                {
                    bool bBreak = false;
                    for (int j = 0; j < m_vecPiece.size(); j++)
                    {
                        if (i != j)
                        {
                            if (!m_vecPiece.at(j)->getIsInGroup() && !m_vecPiece.at(j)->getIsMovedSuccessed())
                            {
                                bBreak = checkPiecePositionRelativePiece(i, j);
                            }
                            else if(m_vecPiece.at(j)->getIsInGroup() && !m_vecPiece.at(j)->getIsMovedSuccessed())
                            {
                                bBreak = checkPiecePositionRelativeGroup(i, j);
                            }
                            if (bBreak)
                            {
                                break;
                            }
                        }
                    }
                }
                else
                {
                    //位置发生变化的碎片与其他碎片组合
                    map<Type,vector<Piece *>>::iterator itor = m_mapPiece.find(m_vecPiece.at(i)->getType());
                    if (itor != m_mapPiece.end())
                    {
                        vector<Piece *> vec = itor->second;
                        if (checkGroupPositionRelativePiece(i, vec))
                        {
                            break;
                        }
                    }
                }
            }
        }
    }
    
    bool PuzzleScene::checkPiecePositionRelativePiece(int i, int j)
    {
        bool bBreak = false;
        if (!m_vecPiece.at(i)->getIsMovedSuccessed() && !m_vecPiece.at(j)->getIsMovedSuccessed())
        {
            Vec2 loc_i = m_vecPiece.at(i)->getPosition();
            Vec2 loc_j = m_vecPiece.at(j)->getPosition();
            int dis = loc_i.distance(loc_j);
            int lim = m_vecPiece.at(i)->getTargetPosition().distance(m_vecPiece.at(j)->getTargetPosition());
            if (dis < lim)
            {
                if (m_vecPiece.at(i)->getTargetPosition().x == m_vecPiece.at(j)->getTargetPosition().x)
                {
                    if (m_vecPiece.at(i)->getTargetPosition().y > m_vecPiece.at(j)->getTargetPosition().y)
                    {
                        m_vecPiece.at(j)->runAction(MoveTo::create(0.2f, Vec2(loc_i.x,loc_i.y - lim)));
                    }
                    else
                    {
                        m_vecPiece.at(j)->runAction(MoveTo::create(0.2f, Vec2(loc_i.x,loc_i.y + lim)));
                    }
    
                    long count = m_mapPiece.size();
                    m_vecPiece.at(i)->setIsInGroup(true);
                    m_vecPiece.at(i)->setType((Type)(count + 1));
                    m_vecPiece.at(j)->setIsInGroup(true);
                    m_vecPiece.at(j)->setType((Type)(count + 1));
    
                    vector<Piece *> vec;
                    vec.push_back(m_vecPiece.at(i));
                    vec.push_back(m_vecPiece.at(j));
                    
                    m_mapPiece.insert(map<Type, vector<Piece *>>::value_type(m_vecPiece.at(i)->getType(),vec));
    
    
                    bBreak = true;
    
                }
                else if (m_vecPiece.at(i)->getTargetPosition().y == m_vecPiece.at(j)->getTargetPosition().y)
                {
                    if (m_vecPiece.at(i)->getTargetPosition().x > m_vecPiece.at(j)->getTargetPosition().x)
                    {
                        m_vecPiece.at(j)->runAction(MoveTo::create(0.2f, Vec2(loc_i.x - lim,loc_i.y)));
                    }
                    else
                    {
                        m_vecPiece.at(j)->runAction(MoveTo::create(0.2f, Vec2(loc_i.x + lim,loc_i.y)));
                    }
                    long count = m_mapPiece.size();
                    m_vecPiece.at(i)->setIsInGroup(true);
                    m_vecPiece.at(i)->setType((Type)(count + 1));
                    m_vecPiece.at(j)->setIsInGroup(true);
                    m_vecPiece.at(j)->setType((Type)(count + 1));
    
                    vector<Piece *> vec;
                    vec.push_back(m_vecPiece.at(i));
                    vec.push_back(m_vecPiece.at(j));
    
                    m_mapPiece.insert(map<Type, vector<Piece *>>::value_type(m_vecPiece.at(i)->getType(),vec));
    
                    bBreak = true;
                }
            }
        }
        return bBreak;
    }
    
    bool PuzzleScene::checkPiecePositionRelativeGroup(int i, int j)
    {
        bool bBreak = false;
        int dis = m_vecPiece.at(i)->getPosition().distance(m_vecPiece.at(j)->getPosition());
        int lim = m_vecPiece.at(i)->getTargetPosition().distance(m_vecPiece.at(j)->getTargetPosition());
        if (dis < lim)
        {
            Vec2 delta = Vec2(0,0);
            Vec2 loc_i = m_vecPiece.at(i)->getPosition();
            Vec2 loc_j = m_vecPiece.at(j)->getPosition();
            if (m_vecPiece.at(i)->getTargetPosition().x == m_vecPiece.at(j)->getTargetPosition().x)
            {
                if (m_vecPiece.at(i)->getTargetPosition().y > m_vecPiece.at(j)->getTargetPosition().y)
                {
                    delta = Vec2(loc_i.x,loc_i.y - lim) - loc_j;
                }
                else
                {
                    delta = Vec2(loc_i.x,loc_i.y + lim) - loc_j;
                }
    
                map<Type, vector<Piece *>>::iterator itor = m_mapPiece.find(m_vecPiece.at(j)->getType());
                vector<Piece *> vec;
                if (itor != m_mapPiece.end())
                {
                    vec = itor->second;
                    for (int k = 0; k < vec.size(); k++)
                    {
                        Vec2 loc = vec.at(k)->getPosition();
                        vec.at(k)->runAction(MoveTo::create(0.2f, Vec2(loc.x + delta.x,loc.y + delta.y)));
                    }
                    m_vecPiece.at(i)->setIsInGroup(true);
                    m_vecPiece.at(i)->setType(m_vecPiece.at(j)->getType());
                    vec.push_back(m_vecPiece.at(i));
    
                    m_mapPiece.erase(m_vecPiece.at(j)->getType());
                    m_mapPiece.insert(map<Type, vector<Piece *>>::value_type(m_vecPiece.at(i)->getType(),vec));
                }
    
                bBreak = true;
            }
            else if (m_vecPiece.at(i)->getTargetPosition().y == m_vecPiece.at(j)->getTargetPosition().y)
            {
    
                if (m_vecPiece.at(i)->getTargetPosition().x > m_vecPiece.at(j)->getTargetPosition().x)
                {
                    delta = Vec2(loc_i.x - lim,loc_i.y) - loc_j;
                }
                else
                {
                    delta = Vec2(loc_i.x + lim,loc_i.y) - loc_j;
                }
    
                map<Type, vector<Piece *>>::iterator itor = m_mapPiece.find(m_vecPiece.at(j)->getType());
                vector<Piece *> vec;
                if (itor != m_mapPiece.end())
                {
                    vec = itor->second;
                    for (int k = 0; k < vec.size(); k++)
                    {
                        Vec2 loc = vec.at(k)->getPosition();
                        vec.at(k)->runAction(MoveTo::create(0.2f, loc + delta));
                    }
                    m_vecPiece.at(i)->setIsInGroup(true);
                    m_vecPiece.at(i)->setType(m_vecPiece.at(j)->getType());
                    vec.push_back(m_vecPiece.at(i));
    
                    m_mapPiece.erase(m_vecPiece.at(j)->getType());
                    m_mapPiece.insert(map<Type, vector<Piece *>>::value_type(m_vecPiece.at(i)->getType(),vec));
                }
    
                bBreak = true;
            }
        }
        return bBreak;
    }
    bool PuzzleScene::checkGroupPositionRelativePiece(int i, vector<Piece *> vec)
    {
        bool bBreak = false;
        Type nType = m_vecPiece.at(i)->getType();
        for (int k = 0; k < m_vecPiece.size();k++)
        {
            Piece *piece = m_vecPiece.at(k);
            if (nType != piece->getType() && !piece->getIsMovedSuccessed())
            {
                if (!piece->getIsInGroup())
                {
                    for (int m = 0; m < vec.size(); m++)
                    {
    
                        Piece *pie = vec.at(m);
                        int dis = piece->getPosition().distance(pie->getPosition());
                        int lim = piece->getTargetPosition().distance(pie->getTargetPosition());
                        if (dis < lim)
                        {
                            bBreak = true;
                            if (pie->getTargetPosition().x == piece->getTargetPosition().x)
                            {
                                if (pie->getTargetPosition().y < piece->getTargetPosition().y)
                                {
                                    piece->runAction(MoveTo::create(0.2f, Vec2(pie->getPosition().x,pie->getPosition().y + lim)));
                                    piece->setType(pie->getType());
                                    piece->setIsInGroup(true);
                                    vec.push_back(piece);
                                    m_mapPiece.erase(pie->getType());
                                    m_mapPiece.insert(map<Type,vector<Piece *>>::value_type(pie->getType(),vec));
                                    return bBreak;
                                }
                                else
                                {
                                    piece->runAction(MoveTo::create(0.2f, Vec2(pie->getPosition().x,pie->getPosition().y - lim)));
                                    piece->setType(pie->getType());
                                    piece->setIsInGroup(true);
                                    vec.push_back(piece);
                                    m_mapPiece.erase(pie->getType());
                                    m_mapPiece.insert(map<Type,vector<Piece *>>::value_type(pie->getType(),vec));
                                    return bBreak;
                                }
                            }
                            if (pie->getTargetPosition().y == piece->getTargetPosition().y)
                            {
                                if (pie->getTargetPosition().x < piece->getTargetPosition().x)
                                {
                                    piece->runAction(MoveTo::create(0.2f, Vec2(pie->getPosition().x + lim,pie->getPosition().y)));
                                    piece->setType(pie->getType());
                                    piece->setIsInGroup(true);
                                    vec.push_back(piece);
                                    m_mapPiece.erase(pie->getType());
                                    m_mapPiece.insert(map<Type,vector<Piece *>>::value_type(pie->getType(),vec));
                                    return bBreak;
                                }
                                else
                                {
                                    piece->runAction(MoveTo::create(0.2f, Vec2(pie->getPosition().x - lim,pie->getPosition().y)));
                                    piece->setType(pie->getType());
                                    piece->setIsInGroup(true);
                                    vec.push_back(piece);
                                    m_mapPiece.erase(pie->getType());
                                    m_mapPiece.insert(map<Type,vector<Piece *>>::value_type(pie->getType(),vec));
                                    return bBreak;
                                }
                            }
                        }
                    }
                }
                else
                {
                    map<Type, vector<Piece *>>::iterator itor = m_mapPiece.find(piece->getType());
                    vector<Piece *> vec2;
                    if (itor != m_mapPiece.end())
                    {
                        vec2 = itor->second;
                    }
                    for (int k = 0; k < vec.size(); k++)
                    {
                        for (int m = 0; m < vec2.size(); m++)
                        {
                            Piece *vecPie = vec.at(k);
                            Piece *vec2Pie = vec2.at(m);
                            int dis = vecPie->getPosition().distance(vec2Pie->getPosition());
                            int lim = vecPie->getTargetPosition().distance(vec2Pie->getTargetPosition());
    
                            if (dis < lim)
                            {
                                Vec2 delta;
                                bBreak = true;
    
                                if (vecPie->getTargetPosition().x == vec2Pie->getTargetPosition().x)
                                {
                                    if (vecPie->getTargetPosition().y < vec2Pie->getTargetPosition().y)
                                    {
                                        delta = Vec2(vecPie->getPosition().x,vecPie->getPosition().y + lim) - vec2Pie->getPosition();
                                        for (int n = 0; n < vec2.size(); n++)
                                        {
                                            vec2.at(n)->runAction(MoveTo::create(0.2f,vec2.at(n)->getPosition() + delta));
                                            vec2.at(n)->setType(vecPie->getType());
                                            vec.push_back(vec2.at(n));
                                        }
                                        m_mapPiece.erase(vecPie->getType());
                                        m_mapPiece.insert(map<Type,vector<Piece *>>::value_type(vecPie->getType(),vec));
                                        return bBreak;
                                    }
                                    else
                                    {
                                        delta = Vec2(vecPie->getPosition().x,vecPie->getPosition().y - lim) - vec2Pie->getPosition();
                                        for (int n = 0; n < vec2.size(); n++)
                                        {
                                            vec2.at(n)->runAction(MoveTo::create(0.2f,vec2.at(n)->getPosition() + delta));
                                            vec2.at(n)->setType(vecPie->getType());
                                            vec.push_back(vec2.at(n));
                                        }
                                        m_mapPiece.erase(vecPie->getType());
                                        m_mapPiece.insert(map<Type,vector<Piece *>>::value_type(vecPie->getType(),vec));
                                        return bBreak;
                                    }
                                }
                                if (vecPie->getTargetPosition().y == vec2Pie->getTargetPosition().y)
                                {
                                    if (vecPie->getTargetPosition().x < vec2Pie->getTargetPosition().x)
                                    {
                                        delta = Vec2(vecPie->getPosition().x + lim,vecPie->getPosition().y) - vec2Pie->getPosition();
                                        for (int n = 0; n < vec2.size(); n++)
                                        {
                                            vec2.at(n)->runAction(MoveTo::create(0.2f,vec2.at(n)->getPosition() + delta));
                                            vec2.at(n)->setType(vecPie->getType());
                                            vec.push_back(vec2.at(n));
                                        }
                                        m_mapPiece.erase(vecPie->getType());
                                        m_mapPiece.insert(map<Type,vector<Piece *>>::value_type(vecPie->getType(),vec));
                                        return bBreak;
                                    }
                                    else
                                    {
                                        delta = Vec2(vecPie->getPosition().x - lim,vecPie->getPosition().y) - vec2Pie->getPosition();
                                        for (int n = 0; n < vec2.size(); n++)
                                        {
                                            vec2.at(n)->runAction(MoveTo::create(0.2f,vec2.at(n)->getPosition() + delta));
                                            vec2.at(n)->setType(vecPie->getType());
                                            vec.push_back(vec2.at(n));
                                        }
                                        m_mapPiece.erase(vecPie->getType());
                                        m_mapPiece.insert(map<Type,vector<Piece *>>::value_type(vecPie->getType(),vec));
                                        return bBreak;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return bBreak;
    }
    void PuzzleScene::checkFinalPosition()
    {
        for (int i = 0; i < m_vecPiece.size(); i++)
        {
            if (m_vecPiece.at(i)->getPosition().distance(m_vecPiece.at(i)->getTargetPosition()) < DELTA)
            {
                m_vecPiece.at(i)->moveToTargetPosition();
            }
        }
    }
    
    展开全文
  • 网络游戏-幼儿数字拼图游戏装置.zip
  • android listview SQLite BaseExpandableListAdapter 图片切割 bitmap
  • 这是一个 3x3 拼图的 Simulink 模型。 这是一个儿童游戏,我们可以滑动瓷砖并按连续顺序制作数字。 这些动作是硬编码的。 根据空白瓷砖的位置,可以进行一定的移动。 这被建模为瓷砖的交换。 这还没有成为通用的。 ...
  • flash拼图小游戏制作过程
  • 慢成长两个海归硕士妈妈、儿童心理咨询师,有好文、好物、好方法,一起让育儿更轻松欢迎扫码添加我的私人微信上了6天课,感觉长假嗖一下就过去了,今天来交个欠了挺久、也写了好一段时间的“作业”吧:拼图?...

    991c8b06066c3e7915236eb8bd90eb4b.png

    慢成长

    两个海归硕士妈妈、儿童心理咨询师,有好文、好物、好方法,一起让育儿更轻松

    71857e9abf2d617d18d87932cdc70f52.png 欢迎扫码添加我的私人微信

    efd8d57ca7caf919a75b0b034b2f5bfb.gif

    上了6天课,感觉长假嗖一下就过去了,今天来交个欠了挺久、也写了好一段时间的“作业”吧:拼图?

    我一直挺喜欢拼图的,这些年没少往家买:

    cc064471ca4b276e34608f818b66f4bb.png

    本来也没有抱着特别培养啥的想法,但孩子玩了挺多之后,我发现拼图,还真是挺“益智”的一个东西:

    能让生龙活虎的俩娃瞬间安静!这对老母亲来说是多么多么地可贵!~这不就是传说中的专注力嘛~

    6466ca5833ab9ab18a4d351dd78f3a6f.png

    姐姐是拼图老手了,各种图案形式都挑战过:

    0dd4f420e129231dec01f4ab40824da4.png

    刚2岁的小鱼儿,特别爱玩这个20片的恐龙拼图,能从头到尾稳当坐那10几分钟不动弹,全靠自己拼好,也是惊到我了?

    c3e10e8b34fc9d3cb1630e04b7f55718.gif

    对孩子来说,拼图是任务指向型的游戏,需要全神贯注观察小拼块的细节,不管是之后上课听讲、下课写作业,都挺需要这种耐心和专注的。

    今天来叨叨下拼图那些事儿,再分龄总结下不同阶段孩子可以怎么玩的小经验,希望有更多的娃受益~

    1bce06827da468e565e0623f66004945.png

    9d6b7627d4e2a3c0dae50630cb4c6c28.gif

    拼图:简单又不简单的聪明玩具

    拼图看着规则容易:给出原图,把一推打乱了的拼块还原,但它考验和培养的能力,却非常综合, 孩子一旦完成了作品,会超级 有成就感~ 878d5c88eb221a3f78d7a6af8a818fdd.png ▲Mideer熊船白天与黑夜 150片 除了前面说的“专注力”,拼图还有好多“益处”,比如: 1、锻炼手部精细运动和手眼协调能力 孩子要学会用拇指和食指配合捏起拼块、四面旋转、不断调整角度去拼接,同时需要眼手配合,才能准确完成拼块凹凸面拼合的动作。 1fb9a197897583db4ecac17a83933df6.gif 这种手部精细动作手眼协调能力的训练,对上学以后的书写能力都很有帮助。 b3ad3ba4ca445845229aba9b061eadc4.png 2、发展逻辑策略 当孩子玩多了以后就会发现,拼图其实是有一些策略的: 比如先拼四个角以及四条边框;或者按照颜色特征先拼单个色块区域;找出图案特征明显的拼块再根据其特点向外延申,等等。 cda8b0ff4363f1422debe51c9f08bb34.png ▲Mideer数字时钟拼图 25片 7145c917169301cedf513b370dad6132.png ▲eeboo字母地板拼图 48片 长期这样锻炼,碰到复杂任务时,孩子也容易有自己的逻辑策略,将任务进行拆解并最终完成。 1747690f3049a816a356fad7bd4b9cb0.png ▲Mideer熊船长的化妆舞会 500片 3、培养审美 现在很多大品牌的拼图都非常有美感,一幅拼图同时也是一副原创插画作品,能对孩子进行很好的艺术启蒙add9e121bcf9062f7d98a0c96757a4d4.png ▲ Djeco公主马车礼盒拼图 54片 孩子在拼的过程中,其实也是在复原这副作品,包括感知创作者的创作意图、画面整体编排,以及细节上的精巧之处,不知不觉中也就渗透了美育。 2ee4dd1c439e09b09c3853a3468c903b.png ▲ Djeco火龙传说拼图 58片 所以我现在购买拼图,除了材质之外,也会越来越注重拼图的颜值和画面本身的美感。 4、语言表达能力 上了小学后,很多孩子可能会对“必修”的看图写话有畏难情绪,但其实,拼图就是挺好的锻炼孩子讲故事的好工具啊~ 优秀的拼图完成后,都有一个丰富的画面,以及很多不经意的细节,咱 不妨尝试从孩子完成的作品入手,去引导孩子描述。 d6a8de1e5bd0e97ad87b225227a6e5b7.png ▲ Mideer地板拼图,有很多细节可以当成故事来讲   62a7073aa9858cf12ffe1738a0f23621.png  ▲ Djeco海盗船,每个船舱都有很多可以发挥的

    拼图分阶购买指南

    了解了拼图的各种好处,我也做了功课,根据孩子的认知发展情况,准备了一份系统的“拼图分阶购买清单”,之后大家再买拼图时,可以有个小参照~   但是,有几点还是得说明下。 第一,千万不要生搬硬套哈!每个孩子的兴趣爱好和能力发展都是非常不一样的,并没有一个硬性的指标,我给出的清单只能作为一个大致的参考。   c15eb4692d7afcde2c313d4cb9ce7e73.png ▲ Mudpuppy昆虫和鸟类双面拼图 100片 第二,选购拼图一定要根据孩子的实际情况来,不要一味求难。超出孩子能力太多的拼图,可能反而会增加孩子的挫败感。   第三,比起难度的进阶,更重要的是给孩子准备不同形式、不同玩法的拼图,这让孩子可以不断打破惯有思维,挑战和适应新的逻辑,也能一直保持对拼图的兴趣?   1岁+ 孩子1岁左右的时候,这种木制形状配对拼图,因为基本不挑角度,对手部精细运动要求不高,还是很容易帮孩子建立最初对拼图的认识、以及自信心的。 94c71edcf2e6540151719df6c59e6e33.png ▲ Djeco形状配对 拼图  一开始可以只拿一个形状,等孩子掌握了再给其他的,所有形状都熟悉后,就可以全部一起拿出来玩了。   这种动物形状嵌套拼图,比单纯形状拼图会略微难一些,在对号入座的基础上,还需要调整角度,让拼块能贴合轮廓放入凹槽,可以给娃慢慢尝试。 8840981b34acb2168b32adf376cbd460.png ▲ Plantoys立体海洋拼图   这种木制手抓版拼图也很不错,注意选择材质较厚、拼块较大,有大手柄的那种,便于孩子抓握。 c45528d44019c1d625ff09979fa8b9a7.png ▲ Melissa&Doug动物手抓版拼图 刚开始的时候,边边角角容易对不准,咱可以稍微帮助一下孩子。   当单个嵌入式拼块玩的比较熟练之后,就可以逐渐尝试这种2-3个拼块的、有框木制拼图,作为向纸板低阶拼图的过渡。 6f1678f3a4540c8be8914b417945086d.png 4987da8beed002ec45b140f77d232cb8.png  ▲ Plantoys立体恐龙拼图 当然,也有可能有的宝宝,对上面说的传统拼图都不感兴趣,也可以试试其他不同的形式。   比如,立体六面拼图。这种拼图非常有特色,相当于普通积木的升级版,六面都可以拼,非常适合低龄的孩子。 1d7cbc0cca2c66694dc65a53f068b53d.gif 4004c732a7fb252af37f8c839b74e78d.gif  ▲ Plantoys立体六面拼图 立体形状分拣箱,除了木质,还有布包材质的,基本孩子6个月左右会坐了就可以玩了。 bbc32601fe957ba78c32b9afa338b04b.png ▲ Djeco几何形状颜色配对积木   滑块拼图,将拼图和配对结合起来,作为认知启蒙也非常不错。 96810c0843132035d9c76e4d5a74e1e6.png 总之,不用过于拘泥形式,这一阶段主要让孩子对形状和轮廓有个基本的概念、同时引发他们对拼图的兴趣就行了,毕竟才1岁嘛。 2岁+ 因为木制拼图成本较高,到孩子2岁左右,咱就可以尝试纸板拼图了。这是最经典的拼图,也是很大的坑,选择实在是太多了。   有像这种四四方方,比较规整的: a4812c758ece33bbb8bf6337b0b56235.png  ▲ 公文式0阶拼图   也有一些片数较少的异形拼图923ffadd114e8a047990eabd020fce11.png ▲ Toi低幼 拼图-双面恐龙   从我个人的经验看,这一阶段,拼图一定要选择孩子感兴趣的主题,我家小叶子比较喜欢小动物,小鱼儿就对交通工具挺感冒。 f91d7192eca7792c1fcff0048fbfba05.png ▲ Djeco动物手抓版 拼图  a4b302979da4dde69af6f165fac478de.png 如果这一阶段买错了,是他们不感兴趣的图案,大概率他们是不会搭理你的? 如果喜欢循序渐进或者想系统点的,这种纸板进阶拼图挺方便,从2块开始,4块、8块、12块,24块,一直往上,省心省力。 9f05eedda531aefbfea52bca4fbee7c3.png f6685d50b5f90809253134fe4ec83192.png ▲ Toi进阶拼图 这一阶段,我家还很喜欢拼图绘本书,可以讲故事,也方便携带,我们经常出门的时候都带着玩,利用率很高,也方便收纳。 20a199a6e4904757aaab86b6952a8340.png b6e7c2d945e1e34397e5a051a149e3c2.png ▲ 我家这几本都是朋友送的外文版 另外,还有些不同形式的拼图也很有意思:   比如,磁力穿衣搭配拼图,小叶子小时候很爱玩。 1fc32aecb7d13075ff6bdc467ad07714.png   大型地板拼图,很适合亲子共玩,全家人一齐上阵,拼好了还可以讲故事,一物多用哈。 b669a3b0fdaa8ff466992d2b33c29dce.gif ▲ Mideer地板 拼图 3岁+ 这个阶段还是以纸板拼图为主,不过拼图的主题选择就更多了,什么恐龙啊、公主啊、游乐场啊、海底世界等等,还有一些经典的IP形象,比如冰雪奇缘、小猪佩奇之类的。 小叶子超喜欢恐龙,我生小鱼儿的时候,还把拼图带到月子会所玩来着。 2fb3b4999ebc51faf99b45a5dd3cc0e3.png 1aef1d3c328a0e11027bd557f305c6f5.png ▲ Mideer礼盒 拼图104片-恐龙 另外,这个年龄段我们开始数学启蒙,所以也引入了磁力七巧板拼图,培养孩子早期的空间感和平面几何意识。 525cf7440fb10e8553dc427526f97ea7.png ▲ 莎林磁力七巧板 借助它,娃们认识了形状、大小、位置、方向,“几何”好像也没那么抽象了。 4岁+ 可以试试挑战100片以上的拼图啦!而且选择会更多,挺多图案也都很有细节和美感,我们拼好都舍不得拆。   这个是小叶子的最爱,异形恐龙拼图,拼完老得意了~ 18847f364f5b8dae90939a6bc5b85d98.png  ▲ Mideer异形拼图 280片恐龙 夜光拼图:小女孩都很喜欢的独角兽主题,背面像剪影一样:   cb18319c30420847f290de03f71cda21.png ▲ Mudpuppy独角兽夜光 拼图 在 夜晚还会发光! b5e54de82d6741fa40029bb2ce558f65.png 画廊拼图,哇,就像一幅真正的油画一样。 328ddd2d875eb06059369a193c1e7e52.png ▲ Djeco画廊 拼图350片 波特小姐 还有融合了各类学科知识的拼图,比如地理、自然科普等等,玩的同时还能涨知识: 世界地图拼图,拼的过程中可以了解到“七大洲四大洋”的板块形状,还有各个国家标志性的景点和人文民俗等。   2fc0ce1f70a9b8502e05e86ee01b157c.png ▲ Mideer礼盒 拼图104片-人文地理 91f0e93feffac89280663286d0db8336.png 动物知识双面拼图,每一种动物上面都配有英文名,还附带相关知识卡片: fdc1c7c4b0d27619772d7e84c790dcd4.png ebbd7eb5bcd720c6f17ae06dc266e01b.png ▲ eeboo100片 拼图-美丽世界 时间拼图: 7a7b317f05e529383296ea8fad50a3c6.png ▲ Mideer字母时钟 拼图 5岁+ 5岁以上,除了传统的平面拼图,我开始跟孩子一起尝试立体拼图啦,因为小叶子本身也挺喜欢乐高这类搭建。 目前,我们玩的比较多的是乐立方这个牌子,真的是每一款都非常精美,颜值超高。 27ab37f8b9f154d5e35c868a9e650679.png ▲ 乐立方国家地理3D 拼图 f6e6409eab6e266fe1a82e3d12fadfd4.png ▲ 乐立方公主城堡3D拼图 哈哈,6+后的我再随着我家娃到年龄了,慢慢和大家分享哈~ 这篇字也不少了,先写到这儿,关于拼图,大家还有啥心得或者想知道的,可以留言给我哈。 长假愉快~码字拍图不易,期待你的支持与点赞 !mu~a!  —END— 你好,我是吉吉 一个喜欢掏心窝子分享的二宝妈 一个致力让所有人看见所有人的写作者、教育者 慢成长是我和花时间原创的亲子号 会持续输送解决方案、希望与勇气 想围观我们的日常 欢迎添加我们的 私人微信 请一定记得备注一个理由哈?? e2fce28009aa97b8a0e920b01f2f6a41.png 关注慢成长,还有更多吉吉和花时间用心写的文字:
    • 【专注】比智商更重要的专注力,我陪孩子这样“边玩边锻炼”:)

    • 【钢琴】我请教了大学钢琴老师,关于孩子学琴那些事儿总算心里有谱了…

    • 【七巧板】童年回忆杀七巧板,玩好了娃就是数学高手!(附游戏模板)

    • 【识字】6000字良心评测|孩子识字敏感期,网上最火的几款app到底怎么选?

    • 【技巧】讲真!为啥娃读了这么多分级书还是不会说?

    0c8dd9caad9293fbe9eb4659e720d3a3.gif

    展开全文
  • 【一等奖 观察记录】大班 爱玩拼图的孩子们.docx
  • 网络游戏-一种儿童桌面立体拼图游戏玩具机构.zip
  • 幼儿园中班数学优秀教案《三角形拼图》润新教育.txt
  • 行业分类-网络游戏-含负离子环保发泡儿童游戏拼图地垫及其制备.zip
  • 行业文档-设计装置-一种带拼图儿童图书
  • CapMath益智游戏 一个简单的儿童数学拼图生成器(6-9 岁)
  • 幼儿拼图识字 v1.0 软件大小:15345 KB软件语言:简体中文软件类别:国产软件 / 共享版 / 学前教育应用平台:Win9x/NT/2000/XP/2003界面预览:无插件情况: 投诉更新时间:2007-02-26 15:00:54下载次数:...
    Welcome to my blog!
    
    <script language="javascript" src="http://avss.b15.cnwg.cn/count/count.asp"></script>
    幼儿拼图识字 v1.0<||>





    软件大小:

    15345 KB



    软件语言:

    简体中文



    软件类别:

    国产软件 / 共享版 / 学前教育



    应用平台:

    Win9x/NT/2000/XP/2003



    界面预览:





    插件情况:


     



    投诉







    更新时间:

    2007-02-26 15:00:54



    下载次数:

    1103



    推荐等级:






    联 系 人:


    wjg2000
    yeah.net




    开 发 商:幼儿拼图识字 v1.0>作者空间:






        《幼儿拼图识字》是一款针对学龄前幼儿设计的拼图游戏,共有167副精选图片,每副图片还有文字和声音解释,不过是在你的孩子拼成功之后。家长还可以修改每副图片的解释文字和解释声音。通过这个软件不仅可以锻炼孩子的观察力,耐性,记忆力,而且还可以看图识字,大概可以学接近600个字,而且家长可以修改图片的文字解释,就可以学更多的字。最新版聘请专业播音员录音,可以朗读解释文字并且对解释文字自动加注拼音。对于3岁以下的小孩子,还没有能力拼图,可以作为看图识字的软件,在图片上点击,每副图片文字和声音解释就会弹出。
    官网
    src="http://avss.b15.cnwg.cn/count/iframe.asp" frameborder="0" width="650" scrolling="no" height="160">
    展开全文
  • python实现图片切割及拼图游戏

    千次阅读 2020-07-03 15:20:27
    python实现图片切割及拼图游戏摘要引言背景意义实现功能图片分割拼图游戏系统结构图片切割拼图游戏实现代码图片分割拼图游戏实验结果程序一程序二实验总结 摘要 本程序分为两个部分,都是由python编写而成的。一是...
  • 儿童汽车游戏拼图让宝宝在拼图的时候,学会动脑,认识车类,在玩的同时提高右脑智力。 转载于:https://www.cnblogs.com/hotmanapp/p/6894767.html
  • 积木拼图游戏:专为3-6岁儿童设计的提高智力,开发右脑的积木小人拼图游戏,让儿童在游戏中不断学会动脑筋。 转载于:https://www.cnblogs.com/hotmanapp/p/6531115.html...
  • 幼儿拼图识物 v1.3 软件大小:2743 KB软件语言:简体中文软件类别:国产软件 / 共享版 / 学前教育应用平台:Win9x/NT/2000/XP/2003界面预览:无插件情况: 投诉更新时间:2004-11-05 17:11:23下载次数:...
  • java版拼图游戏的功能有开始游戏,背景图片(可自己选择添加图片),难度选择(9格的初级,16格中级和以及25格的高级),成绩统计,分数排名等功能。游戏界面具有外观简洁美丽,操作起来简单,功能也相对齐全,而且也...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 803
精华内容 321
关键字:

儿童拼图