整活！我是如何用OpenCV做了数字华容道游戏！（附源码）

Vaccae

发布于 2021-05-07 10:17:53

8810

发布于 2021-05-07 10:17:53

前言

数字华容道，记得以前《最强大脑》上一个初赛题目，正好最近家里买了个数字华容道的玩具，玩着还挺有意思，于是就想干脆自己做个华容道的游戏，本来说做这样的小游戏用Unity3D我觉得更好，无奈最近在自学Pytorch深度学习框架，装了Anaconda全家桶，硬盘空间告急，于是就把Unity3D给删了。想想不如用OpenCV做这个得了，正好算是针对OpenCV做了个综合实战。

实现效果

完整视频

设计思路

微卡智享

上图中是数字华容道的一个简单的操作流程思路，我们根据上面的流程设计逐步拆分进行思考：

生成数字华容道

因为做的是4X4的数字华容道，所以我们生成一个0-15的vector<int>数组，然后随机打乱顺序，存放到vector<vector<int>>的二维数据中（即4X4的矩阵），存其中0代表着可移动的空白位。

随机打乱数组代码

vector<int> Puzzles4x4::RandVectorNum()
{
  vector<int> vts;
  //定义华容道数字
  vector<int> vtsnums{ 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
  int size = vtsnums.size();
  for (int i = 0; i < size; ++i) {
    //初始化随机数种子
    srand((int)time(0));
    int index = vtsnums.size() == 1 ? 0 : rand() % (vtsnums.size() - 1);
    vts.push_back(vtsnums[index]);
    //容器中删除已经赋值的数字
    vtsnums.erase(vtsnums.begin() + index);
  }
  return vts;
}

绘制游戏图像

#	思路
1	创建一个600X600的Mat，白底
2	根据4X4的矩形大小绘制整个棋盘的背景
3	每个格用Rect矩形绘制
4	对应Rect的数字显示用PutText函数

上面用到的OpenCV的函数主要就是rectangle和putText

鼠标操作

使用OpenCV的setMouseCallback回调事件，然后在OnMouse中设置了点击左键是移动，双击右键是重新开始游戏。

void onMouse(int event, int x, int y, int flags, void* param)
{
  switch (event)
  {
  case EVENT_LBUTTONUP:
  {
    Point point = Point(x, y);
    int col = -1;
    int row = -1;
    SelectVectorItem(point, contours, nummatrix, col, row);
    if (col >= 0 && row >= 0) {
      if (Puzzles4x4::VectorsMove(nummatrix, col, row)) {
        if (isFinish) {
          isFinish = false;
          usetime = (double)getTickCount();
          cout << "开始还原计时" << endl;
        }
        //重新生成图像显示
        DrawPuzzlesMat(src, nummatrix, contours);

        isFinish = Puzzles4x4::CheckFinished(nummatrix);
        if (isFinish) {
          usetime = ((double)getTickCount() - usetime) / getTickFrequency();
          cout << "还原完成！用时：" << usetime << "秒！" << endl;
        }

      }
    }

  }
  break;
  case EVENT_RBUTTONDBLCLK:
  {
    //生成华容道
    vector<int> tmpvets = Puzzles4x4::RandVectorNum();
    Puzzles4x4::CreateNewGame(nummatrix, tmpvets);
    //打印生成的华容道
    Puzzles4x4::Printvectors(nummatrix);
    //生成图像显示
    DrawPuzzlesMat(src, nummatrix, contours, true);

    //改变初始状态
    isFinish = true;
  }
  break;
  default:
    break;
  }
}

鼠标左键移动

这一步为最核心的步骤，实现点击获取到对应的二维数组中数字的原理主要就是用到了OpenCV中的pointPolygonTest函数（计算点是否在轮廓内）。

以前使用OpenCV做轮廓查找时都是先定义vector<vector<Point>>，然后通过findContours的函数进行查找，因为这里我们是自己绘制的Rect矩形，所以我们在初次生成Rect的时候，就可以把每个一Rect的4个点存放到定义好的vector<vector<Point>>中，然后通过pointPolygonTest来判断点击的是第几个轮廓，获取到对应的行和列序号。

void InsertContours(vector<vector<Point>>& contours, Rect rect)
{
  vector<Point> vetpt;
  Point pt1 = Point(rect.x, rect.y);
  vetpt.push_back(pt1);
  Point pt2 = Point(rect.x + rect.width, rect.y);
  vetpt.push_back(pt2);
  Point pt3 = Point(rect.x + rect.width, rect.y + rect.height);
  vetpt.push_back(pt3);
  Point pt4 = Point(rect.x, rect.y + rect.height);
  vetpt.push_back(pt4);

  contours.push_back(vetpt);
}

从上面获取到对应的行和列的序号的，就要开始计算是否可以进行移动，判断是否可以移动主要就是看点击的这个格，上下左右的方向中是否存在0的数字，如果不存在即不可移动，哪个方向为0，则直接和0的位置进行交换即可。

bool Puzzles4x4::VectorsMove(vector<vector<int>>& vts, int col, int row)
{
  bool res = true;
  //计算可移动的区域
  //1.左边
  if (col-1>=0 && vts[row][col-1]==0){
    vts[row][col - 1] = vts[row][col];
    vts[row][col] = 0;
  }
  //2.右边
    else if (col + 1 <= 3 && vts[row][col + 1] == 0) {
    vts[row][col + 1] = vts[row][col];
    vts[row][col] = 0;
  }
  //3.上边
    else if (row + 1 <= 3 && vts[row+1][col] == 0) {
    vts[row+1][col] = vts[row][col];
    vts[row][col] = 0;
  }
  //4.下边
  else if (row - 1 >= 0 && vts[row - 1][col] == 0) {
    vts[row - 1][col] = vts[row][col];
    vts[row][col] = 0;
  }
  else {
    res = false;
  }
  return res;
}

检测游戏是否完成

这个其实没有什么好说的，就是判断1-15每个数字是否在对应的格内即可。都在格内的时候0肯定是在右下角，所以我们检测函数先判断0是否在右下角，如果是的话再进行循环判断，这样可以减少循环次数，节省时间复杂度。

bool Puzzles4x4::CheckFinished(vector<vector<int>>& vts)
{
  //计算总行数
  int rows = vts.size() - 1;
  //计算总列数
  int cols = vts[rows].size() - 1;
  //先判断最后一位是否是0，如果不是下面就不再浪费时间检查
  if (vts[rows][cols] != 0) return false;;
  int checknum = 1;
  for (int row = 0; row <= rows; ++row) {
    for (int col = 0; col <= cols; ++col) {
      //最后一格已经检测，直接退出
      if (col == cols && row == rows) return true;
      if (vts[row][col] != checknum) return false;
      checknum++;
    }
  }
}

计时

这个直接采用OpenCV中的getTickCount()函数即可，当检测游戏完成时，计算一下总的用时输出。

重点说明

微卡智享

刚做完自己玩时，发现经常出现了这种无解的情况，后来通过查找相关的资料了解到：数字华容道NxN数字随机排列的阵列有解的必要条件是：N为奇数，总逆序数为偶数，N为偶数，总逆序数为奇数。

上面的数字排列：1 11 8 14 4 7 5 2 6 13 15 0 10 9 3 12。（0为空位）

计算得到的逆序对为：56

计算顺序：0+0+1+0+3+3+4+6+4+1+0+11+4+5+11+3 =56

得到的逆序对再加上0所以的行和列的位置：56+2(行号)+3(列号)=61

根据上面的结论NXN数字，N为偶数，总逆序数为奇数才有解，上面这个是没有问题的，如果为偶数，需要把最后两位数字调换一下位置即可。

计算逆序对

这个真是在LeetCode里面比较常见的题了，在我为数不多的刷题中还真刷过这个，主要是方法是暴力破解和分治思想。正好借着这个机会重新练习了一下分治思想的计算逆序对。

项目中CalcReversNum即计算逆序对的类

暴力破解

简单的双循环计算，代码简单，其实在我们这里面用这个最方便，因为始终是4X4的固定表格，计算量不会太大。

int CalcReverseNum::CheckCount(vector<int>& vts)
{
  int count = 0;

  for (int i = 0; i < vts.size(); ++i) {
    cout << vts[i] << " ";
    for (int j = 0; j < i; j++) {
      if (vts[j] > vts[i]) count++;
    }
  }
  return count;
}

分治思想

分治思想的步骤：

（1）分解，将要解决的问题划分成若干规模较小的同类问题；

（2）求解，当子问题划分得足够小时，用较简单的方法解决；

（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

#include "CalcReverseNum.h"

//静态变量需要在CPP文件中先初始化
vector<int> CalcReverseNum::tmpvts(1);

int CalcReverseNum::merge(vector<int> &vts, int left, int mid, int right)
{
  //根据传入的数组调整静态变量的大小
  tmpvts.resize(vts.size());
  for (int i = left; i <= right; i++)
    tmpvts[i] = vts[i];
  int i = left, j = mid + 1, k= left;
  int count = 0;
  //遍历比较左右两个部分
  while (i <= mid && j <= right) {
    //左半部分元素小于右半部分的元素
    if (tmpvts[i] <= tmpvts[j])
      vts[k++] = tmpvts[i++];
    else
    {
      //统计左半边能和右半边该元素构成的逆序对数
      vts[k++] = tmpvts[j++];
      count += mid - i + 1;
    }
  }

  while (i <= mid)
    vts[k++] = tmpvts[i++];
  while (j <= right)
    vts[k++] = tmpvts[j++];
  return count;
}

int CalcReverseNum::MergeSort(vector<int>& vts, int left, int right)
{
  if (left >= right) return 0;
  //通过分治思想取中间数再递归下去
  int mid = left + (right - left) / 2;
  //递归排序左半部分
  int leftnum = MergeSort(vts, left, mid);
  //递归排序右半部分
  int rightnum = MergeSort(vts, mid + 1, right);
  //计算当前部分
  int nownum = merge(vts, left, mid, right);

  return leftnum + rightnum + nownum;
}