学更好的别人，
做更好的自己。
——《微卡智享》
本文长度为3215字，预计阅读9分钟
前言
上一篇《C++ OpenCV制作九宫格拼图游戏》已经实现了制作九宫格拼图游戏，本章就来说说九宫格拼图游戏的自自动还原方法，完整的源码在文章最后链接中。
实现效果
Q1
九宫格拼图自动还原核心是什么？
要完成九宫格拼图AI自动还原，最核心的就是两点：
1.需要计算指定图像到对应区域的路径，并实现移动。
2.按指定路径移动的过程中遇到的可能性问题的解决方法。
01
路径规划
其实路径规划的算法上次在《趣玩算法--OpenCV华容道AI自动解题》中就已经写完了，可以点击文章看实现的原理。
上一篇也说过，这个项目创建和数字华容道项目都放在一起了，并且将路径规划的类（CalcPathPlan）和计算数字的逆序数类（CalcReverseNum）都移动到Utils文件夹下，两个项目都直接添加现在项即可。
在CalcPathPlan里最核心的两个方法：
-
InitSites-----初始化地图
-
GetPath-----计算行动路径
调用方式：
通过初始化地图方式，可以将3X3九宫格，和4X4的数字华容道或是其它的二维表格都能实现路径规划。
上图中先找到了左上角的图像，现在我们要将其移动到左上角位置
调用路径规划时，左边是传入的地图，还原的顺序就是从上到下的，所以刚开始地图中不存在任何障碍点，左边的地图都是空白色，将起点和终点两个（上图中橙色框）位置传入后，计算出了行动的路径。
上面这一步只是计算出了图像应该行动的路径，接下来具体行动方式需要我们自己实现。
已经规划好的路线，接下来按规划路径走，必须让空白格出现在图像要走的下一步位置，这里重要的一点就是需要移动的图像格不能移动，实现不能移动的方法就是将其设置为地图中的障碍点后，再计算空白格到指定位置的路径规划。
按上面的方式将空白格移动过来
接下来就要按原来图像规划的路径计算下一个空白格
接上面的原理，最终将左上角的图像移动到指定位置，当位置锁定后，下面路径规划时传入的地图，锁定位置就要设置成为障碍点，不允许通过了。
02
特殊处理
当上图中右上的图像需要移动上去时，在计算空白格规划路径时没有可行动的路径，如下图所示：
这里就需要进行特殊步骤的处理
代码中使用了DealStep的函数将所有的特殊处理都在里面，除了像上面这种情况外，还有第二行中间和右边的图像有时也会遇到特殊情况。
上图中第二行中间图像现在也无法移动到指定位置
第二行最后面的图像也是无法移动到指定位置
处理完前两行后，第三行默认就可以按常规方式还原了，所以相对来说比4X4的数字华容道的处理方法要简单多。
源码地址
https://github.com/Vaccae/OpenCVNumPuzzles.git
码云地址点击文末的原文链接
完
往期推荐
C++ OpenCV制作九宫格拼图游戏
C++ OpenCV生成九宫格图像
制作一个Android Sqlite远程运维小工具