基于opencv的C++走迷宫

发表于 | 分类于 | 评论数： | 阅读次数：

背景

同事在朋友圈贴了一个迷宫的图，看看能否用程序实现，觉的有趣就试了试。

效果

upload successful

方法

  • 使用opencv对图像进行二值化

  • 使用bfs算法进行路径搜索

  • 对路径进行回溯，并显示路径

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
// ConsoleApplication1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <windows.h>
#include <queue>
#include <opencv2/opencv.hpp>

#define GRAY_COLOR 240

struct Node {
	int x = 0;
	int y = 0;
	bool operator == (Node& right)
	{
		if (this->x == right.x && this->y == right.y)
		{
			return true;
		}
		return false;
	}
};

//设置访问过的颜色
void setVisit(Node node, cv::Mat& imgSrc)
{
	imgSrc.at<uchar>(node.y, node.x) = GRAY_COLOR;
}

//设置步数
void SetStep(Node node,std::vector<std::vector<int> > &oFullStep, int nStep)
{
	oFullStep[node.x][node.y] = nStep;
}

bool isValid(Node node, cv::Mat& imgSrc)
{
	if (node.x < 0 || node.y < 50 )		  // 设置不能比起点更小的y值。 原图应该先处理，避免跑到圆圈外面，我通过坐标来限制
	{
		return false;
	}
	if (node.x >= imgSrc.cols || node.y >= imgSrc.rows)
	{
		return false;
	}

	if (int(imgSrc.at<uchar>(node.y, node.x)) > 0)
	{
		return false;
	}
	return true;
}

bool isVisit(Node node, cv::Mat& imgSrc)
{
	if (int(imgSrc.at<uchar>(node.y, node.x)) == GRAY_COLOR)
	{
		return true;
	}
	return false;
}

bool pushNode(Node Vw, Node Vd, std::queue<Node>& Q, cv::Mat& imgSrc,std::vector<std::vector<int> > &oFullPath,int nStep)
{
	if (Vw == Vd) {//找到终点了！  
		setVisit(Vw, imgSrc);
		SetStep(Vw, oFullPath, nStep);
		return true;//返回  
	}

	if (isValid(Vw, imgSrc) && !isVisit(Vw, imgSrc)) {
		//Vw是一个合法的节点并且为白色节点  
		Q.push(Vw);//加入队列Q  
		setVisit(Vw, imgSrc);//设置节点颜色
		SetStep(Vw, oFullPath, nStep);
	}
	return false;
}

// 	  Vs 开始，Vd 结束
bool BFS(Node &Vs,Node &Vd, cv::Mat& imgSrc,std::vector<std::vector<int> > &oFullPath)
{
	std::queue<Node> Q;		 
	Node Vn, Vw;
	

	//初始状态将起点放进队列Q  
	Q.push(Vs);
    setVisit(Vs, imgSrc);
	SetStep(Vs, oFullPath, 1);

	while (!Q.empty()) {//队列不为空，继续搜索！  
		//取出队列的头Vn  
		Vn = Q.front();
		int nStep = oFullPath[Vn.x][Vn.y];
		//从队列中移除  
		Q.pop();

		// 四个方向查找
		Vw.x = Vn.x;
		Vw.y = Vn.y - 1;
		//对搜索过的路径进行颜色修改为240，并记录步数
		if (pushNode(Vw, Vd, Q, imgSrc, oFullPath,nStep + 1))
		{
			return true;
		}
		Vw.x = Vn.x;
		Vw.y = Vn.y + 1;
		if (pushNode(Vw, Vd, Q, imgSrc,  oFullPath, nStep + 1))
		{
			return true;
		}
		Vw.x = Vn.x - 1;
		Vw.y = Vn.y ;
		if (pushNode(Vw, Vd, Q, imgSrc,  oFullPath, nStep + 1))
		{
			return true;
		}
		Vw.x = Vn.x + 1;
		Vw.y = Vn.y ;
		if (pushNode(Vw, Vd, Q, imgSrc,  oFullPath, nStep + 1))
		{
			return true;
		}

	}
	return false;//无解  
}

//从终点开始回溯，开始对上下左右四个方向进行step 比较
void findPath(Node Ve,const std::vector<std::vector<int> > &oFullStep,std::vector<Node> &oPath)
{
	int nStep = oFullStep[Ve.x][Ve.y];

	Node Vn = Ve;
	while (nStep != 0)
	{
		Node Vw;
		Vw.x = Vn.x;
		Vw.y = Vn.y - 1;

		nStep = oFullStep[Vn.x][Vn.y];

		if (oFullStep[Vw.x][Vw.y] == (nStep - 1))
		{
			Vn = Vw;
			oPath.push_back(Vn);
			continue;
		}
		Vw.x = Vn.x;
		Vw.y = Vn.y + 1;

		if (oFullStep[Vw.x][Vw.y] == (nStep - 1))
		{
			Vn = Vw;
			oPath.push_back(Vn);
			continue;
		}
		Vw.x = Vn.x-1;
		Vw.y = Vn.y ;

		if (oFullStep[Vw.x][Vw.y] == (nStep - 1))
		{
			Vn = Vw;
			oPath.push_back(Vn);
			continue;
		}
		Vw.x = Vn.x+1;
		Vw.y = Vn.y ;

		if (oFullStep[Vw.x][Vw.y] == (nStep - 1))
		{
			Vn = Vw;
			oPath.push_back(Vn);
			continue;
		}
	}

}

int main(int argc, TCHAR* argv[], TCHAR* envp[])
{
	Node Vs, Vd;
	//设置起点	 ，通过ps工具找到起点像素
	Vs.x = 505;
	Vs.y = 50;

	//设置终点	，通过ps工具找到终点点像素
	Vd.x = 570;
	Vd.y = 1115;

	std::vector<std::vector<int> > oFullPath;  //记录搜索的步数
	std::vector<Node> oStepVec;

	cv::Mat image = cv::imread("e:\\迷宫图片.jpg", cv::IMREAD_GRAYSCALE); 
	cv::Mat outImage;
	cv::threshold(image, outImage, 180, 255, cv::THRESH_BINARY_INV); // 对图片进行二值化， "180"是测试出来的 

	oFullPath.resize(outImage.cols);
	for (auto& value : oFullPath)
		value.resize(outImage.rows);

	bool bRet = BFS(Vs, Vd, outImage,oFullPath);	   // 进行BFS 搜索

	findPath(Vd,oFullPath, oStepVec);		// 对路径进行回溯

	// 设置路径的颜色为黑色
	for (auto& value : oStepVec)
	{
		outImage.at<uchar>(value.y, value.x) = 0;
	}

	cv::imshow("hello", outImage);

	cv::waitKey(0); // 等待用户按下键盘
	cv::destroyWindow("hello"); // 销毁窗口 "hello"


	return 0;
}