前言
上一篇《C OpenCV制作九宫格拼图游戏》已经实现了制作九宫格拼图游戏，本章就来说说九宫格拼图游戏的自自动还原方法，完整的源码在文章最后链接中。
实现效果
http://mpvideo.qpic.cn/0bc3xeaboaaasqanqwvnsjqvboodc64qafya.f10002.mp4?dis_k=1f842d7b1b703ba715f586b87cbb7c05&dis_t=1639384844&vid=wxv_2167422472978038784&format_id=10002&support_redirect=0&mmversion=false
Q1 九宫格拼图自动还原核心是什么？
要完成九宫格拼图AI自动还原，最核心的就是两点：
1.需要计算指定图像到对应区域的路径，并实现移动。
2.按指定路径移动的过程中遇到的可能性问题的解决方法。
核心思路讲解
01路径规划
其实路径规划的算法上次在《趣玩算法--OpenCV华容道AI自动解题》中就已经写完了，可以点击文章看实现的原理。
上一篇也说过，这个项目创建和数字华容道项目都放在一起了，并且将路径规划的类（CalcPathPlan）和计算数字的逆序数类（CalcReverseNum）都移动到Utils文件夹下，两个项目都直接添加现在项即可。
在CalcPathPlan里最核心的两个方法：
- InitSites-----初始化地图
- GetPath-----计算行动路径
调用方式：
代码语言：javascript复制//查找行动路径
std::vector<std::pair<int, int>> ImgPuzzles::FindPath(std::vector<std::vector<int>>& sites, std::pair<int, int>& startpos, std::pair<int, int>& endpos, int directfirst)
{
CalcPathPlan plan = CalcPathPlan();
plan.DirectFirst = directfirst;
plan.InitSites(sites);
return plan.GetPath(startpos, endpos);
}
通过初始化地图方式，可以将3X3九宫格，和4X4的数字华容道或是其它的二维表格都能实现路径规划。
行动原理
上图中先找到了左上角的图像，现在我们要将其移动到左上角位置
调用路径规划时，左边是传入的地图，还原的顺序就是从上到下的，所以刚开始地图中不存在任何障碍点，左边的地图都是空白色，将起点和终点两个（上图中橙色框）位置传入后，计算出了行动的路径。
上面这一步只是计算出了图像应该行动的路径，接下来具体行动方式需要我们自己实现。
已经规划好的路线，接下来按规划路径走，必须让空白格出现在图像要走的下一步位置，这里重要的一点就是需要移动的图像格不能移动，实现不能移动的方法就是将其设置为地图中的障碍点后，再计算空白格到指定位置的路径规划。
按上面的方式将空白格移动过来
接下来就要按原来图像规划的路径计算下一个空白格
接上面的原理，最终将左上角的图像移动到指定位置，当位置锁定后，下面路径规划时传入的地图，锁定位置就要设置成为障碍点，不允许通过了。
02特殊处理
当上图中右上的图像需要移动上去时，在计算空白格规划路径时没有可行动的路径，如下图所示：
这里就需要进行特殊步骤的处理
代码中使用了DealStep的函数将所有的特殊处理都在里面，除了像上面这种情况外，还有第二行中间和右边的图像有时也会遇到特殊情况。
上图中第二行中间图像现在也无法移动到指定位置
第二行最后面的图像也是无法移动到指定位置
代码语言：javascript复制void ImgPuzzles::DealStep(vector<vector<int>>& sites, int step)
{
int row = 0;
pair<int, int> sPos;
pair<int, int> endPos;
switch (step)
{
case RestoreStep::Num3:
row = step / sites.size() - 1;
//1.先将0移动到当前要处理的行的下面格
endPos = std::pair<int, int>(row 1, 0);
NullMove(sites, endPos, DirectFirst::Left);
//2.解锁处理行前面的障碍点，用0的位置优先移动到计算点
for (int i = 0; i < sites[row].size(); i) {
sites[row][i] = 0;
}
endPos.first = row;
endPos.second = 2;
NullMove(sites, endPos, DirectFirst::Up);
//3.数字0再和当前要处理的点进行位置互换，将我们3位置移动到对应后锁定
endPos.first = row 1;
endPos.second = 2;
//防止移动点是锁定的，将改为可移动
sites[endPos.first][endPos.second] = 0;
NullMove(sites, endPos, DirectFirst::Right);
//设置为锁定障碍点
sites[row][2] = 1;
//4.将数字0移动到第二步位置后还原当前行前三个数字
endPos.first = row;
endPos.second = 1;
NullMove(sites, endPos);
//5.将0优先按左移的方式把原来行前面的数字还原回来
endPos.first = row 1;
endPos.second = 0;
NullMove(sites, endPos, DirectFirst::Left);
break;
case RestoreStep::Num5:
sites[1][0] = 0;
//获取开始结束的点位置
GetPos(vtsCutMat, step, sPos, endPos);
endPos.first = 1;
endPos.second = 2;
//获取应到达位置
RestorePath = FindPath(sites, sPos, endPos, DirectFirst::Up);
//3.遍历路径每一步处理移动路径
for (int i = 0; i < RestorePath.size(); i) {
cout << RestorePath[i].first << " " << RestorePath[i].second << endl;
//3.1数字当前位置不计算
int front = i - 1;
if (front < 0) continue;
//3.3把数字当前位置设置为障碍点，这样0不允许与当前数字交换位置
//cout << "sites:" << restorepath[front].first << " " << restorepath[front].second << endl;
sites[RestorePath[front].first][RestorePath[front].second] = 1;
int stepnum = NullMove(sites, RestorePath[i]);
if (stepnum != 0) {
//3.3.3 取消当前地图上的障碍点
sites[RestorePath[front].first][RestorePath[front].second] = 0;
int row = RestorePath[front].first;
int col = RestorePath[front].second;
int curposition = vtsCutMat[row][col]->curposition;
int newposition = -1;
if (ImageMove(row, col, curposition, newposition)) {
DrawPuzzleMat(curposition, newposition);
cv::waitKey(SleepTime);
}
}
else {
//如果没有路径就是遇到特殊情况，进行单独处理
DealStep(sites, step);
}
}
break;
case RestoreStep::Num6:
row = step / sites.size() - 1;
//1.先将0移动到当前要处理的行的下面格
endPos = std::pair<int, int>(row 1, 0);
NullMove(sites, endPos, DirectFirst::Left);
//2.解锁处理行前面的障碍点，用0的位置优先移动到计算点
for (int i = 0; i < sites[row].size(); i) {
sites[row][i] = 0;
}
endPos.first = row;
endPos.second = 1;
NullMove(sites, endPos, DirectFirst::Up);
//3.将4和5锁定
sites[row][0] = 1;
sites[row 1][0] = 1;
sites[row][2] = 0;
break;
case RestoreStep::Step4and5:
//1.将空白移动到5的位置
endPos = std::pair<int, int>(1, 1);
NullMove(sites, endPos, DirectFirst::Left);
//2.解锁4和5并还原回去
sites[1][0] = 0;
sites[2][0] = 0;
pair<int, int> endPos(2, 0);
NullMove(sites, endPos, DirectFirst::Left);
//3.锁定4和5
sites[1][0] = 1;
sites[1][1] = 1;
break;
}
}处理完前两行后，第三行默认就可以按常规方式还原了，所以相对来说比4X4的数字华容道的处理方法要简单多。
源码地址
https://github.com/Vaccae/OpenCVNumPuzzles.git
