常用算法：深度优先搜索（Depth First Search ）_深度搜索

       最近事少，代码也写的少，当然工作这么些年写过的代码也能绕xx四五圈啊四五圈，现在则思考除了纯粹写代码之外的事情，比如总结一些常用的通用的算法，学习一下遗忘很久的数学，思考下今后的发展，比如是在哪个桥洞下讨饭什么的。

       实际上呢，很多数学和算法，我们的开发生涯中都是使用过的，但是记忆力这个东西是不可靠的，我小时候看过一本叫XYZ记忆法和记忆宫殿的书，里面讲的人的“永久记忆”也就那么二十年，而且记忆的内容需要七次及以上的反复学习才可以达到所谓的“永久记忆”，大部分情况下就是我们用到某个算法，但是并没有持续对该算法进行七次及以上的学习，可能就会导致我们突然想用某个算法的时候，就“卡壳”了。

       比如这次要讲的深度优先搜索（后面简称DFS），做游戏或者其他开发，比如数据挖掘什么的，基本上都会接触和实现过，但是某些年后突然准备再用这个算法，还真可能需要再看一遍，所以现在我就准备业余时间再次学习理解实现一遍。

       DFS在游戏中有一个应用场景就是寻路，也就是玩家给角色指定一个目标地点，角色就移动过去，这个移动的过程就涉及以下技术细节：

       ①.美术制作好场景地形，根据地形网格的顶点和三角面进行标定，确定哪些三角面是“平坦畅通”的，哪些三角面是“障碍物”，策划根据实际情况进行表格记录，将这些信息储存起来给程序使用。当然了这一个步骤程序完全可以自己处理，我们开发可以对网格三角面顶点检测，将顶点的“海拔Y轴”比较大或者比较小（也就是比较“高”或者比较“低”）的三角面标记为“凹凸物不可通过”，将Y轴差异性比较小的三角面标记为“平坦可通过的”。这个步骤一般引擎都帮我们做好了，叫做Navigation agent，一般引擎都自带这种功能。

       ②.当然也有Q游，场景比较卡通简洁，而且比较规整，可能一个场景完全就可以进行横纵二维数组标定区域可通过性。

       ③.当场景的信息标定完毕，使用DFS算法进行目标移动路径处理，找到目标路程。

       ④.角色进行行走动画和位移插值旋转插值等处理，表现出良好的寻路效果。

       这里我们只来观察学习③中的DFS路径计算技术，假设我们拥有下面一张Q版游戏地图，如下图：

        

        这是我用ps随便做的，不要介意。

        假如我们的“羊羹君”想吃到右下角的小鱼干，但是地图上到处都是水坑和路障，请问它要怎么走到目的地呢，这里顺便说一下“羊羹君”是一只年迈的老猫，它的智力已经和计算机差不多了（这里也别奇怪，计算机的“智力”是很低的，只是运算速度很快），只能“走一步看一步”，羊羹君的行走方式就是先往右走，被挡住了就往下走，再被挡住了就往左走，还是被挡出了就往上走，因为“羊羹君”年纪太大了，现在行走方式就跟一个上了发条的机器人一样，只能这样撞一下换个方向(・。・)，直到找到小鱼干，或者永远找不到小鱼干。

        这时我们就要帮助“羊羹君”找到它的小鱼干！我们首先要将地图的信息进行二维数组标定储存，然后“模拟”“羊羹君”年迈的行走方式，进行路线推算，因为我们是在计算机中进行的，所以可以很快的得到结果，直接帮助”羊羹君“确定行走线路，具体程序实现如下：

        

// CatDFS.cpp : 定义控制台应用程序的入口点。
//
 
#include "stdafx.h"
#include<Windows.h>
#include<map>
 
using namespace std;
 
//6行6列地图
const int Row = 6;
const int Col = 6;
 
//将Q版地图用二维数组进行标定，0代表畅通无阻，1代表路障，-1代表深水坑
int Qmap[Row][Col] = { 0,0,0,0,1,0,
				 0,0,-1,-1,0,0,
				 0,1,0,0,0,0,
				 0,0,0,-1,0,0,
				 0,0,0,1,0,0,
				 0,0,0,0,0,0 };
 
//这是一个和map相同容积的标记数组，作用是标记羊羹君已经走过的坐标，避免重复行走
//因为假设我们不使用一个额外的数组储存羊羹君的行走历史记录，那么可能会存在重复行走的死循环
int tag[Row][Col] = { 0 };
 
 
//记录羊羹君走过的坐标，使用索引：坐标 map记录
class Coord
{
public:
	Coord() {};
	Coord(int i, int j) :x(i), y(j) {};
	~Coord() {};
	int x;
	int y;
 
};
map<int, Coord> pathMap;
int pathIndex = 0;	
 
//记录线路步数
int totalStep = 0;
 
//羊羹君的移动方式，也就是“碰壁式移动”，先右走，再下走，再左走，在上走
//相应的坐标计算规则则是如下
int nextMove[4][2] = { {0,1},		//坐标右移
					{1,0},		//坐标下移
					{0,-1},		//坐标左移
					{-1,0} };	//坐标上移
 
//深度优先搜索算法
//因为羊羹君每走一步，都会环顾四周，观察下一步可以走哪里，所以可以递归进行
//参数首先确认当前走到了二维数组的哪个位置，也就是xy
//参数同时确认当前已经走了多少步了，方便我们找到最短路线
void Dfs(int x, int y, int step)
{
	//当我们到达[5,5]坐标时，代表我们已经找到小鱼干了
	//这是我们就打印出来羊羹君走了多少步
	//同时将羊羹君每次行走的坐标示意图也打印出来
	if (x == (Row - 1) && y == (Col - 1))
	{
		//记录最短路线步数
		if (totalStep < step)
		{
			totalStep = step;
		}
		printf("conguratulation 羊羹君 find the fish totalStep = %d\n", totalStep);
		for (int i = 0; i < Row; i++)
		{
			for (int j = 0; j < Col; j++)
			{
				printf("%d ", tag[i][j]);
			}
			printf("\n");
		}
		for (map<int, Coord>::iterator it = pathMap.begin(); it != pathMap.end(); it++)
		{
			printf("index = %d x=%d y=%d\n", it->first, it->second.x, it->second.y);
		}
		return;
	}
	int tx, ty;
	for (int i = 0; i < 3; i++)
	{
		//tx，ty表示下一步的二维坐标值
		tx = x + nextMove[i][0];
		ty = y + nextMove[i][1];
		//如果下一步坐标越界了，就直接跳过
		if (tx < 0 || tx >= Row || ty < 0 || ty >= Col)
		{
			continue;
		}
		//如果下一步坐标在地图map中标记为0通畅，同时tag标记数组表示这个坐标没有走过
		//那么我们就表示这一步行走正确，同时进行递归DFS
		if (Qmap[tx][ty] == 0 && tag[tx][ty] == 0)
		{
			tag[tx][ty] = 1;			//先标记tag数组，表示这个坐标已经行走过了，避免重复
			pathMap[pathIndex] = Coord(tx, ty);  //记录坐标map
			++pathIndex;
			Dfs(tx, ty, step + 1);		//然后进行DFS递归
			//如果DFS递归失败（没找到小鱼干，且这条路走堵死了）
			//那么回滚tag数组标记这个坐标没有行走过，并且清理路线中的坐标
			//同时继续for循环进行下一个方向的探索
			tag[tx][ty] = 0;	
			--pathIndex;
			pathMap.erase(pathIndex);
		}
	}
}
 
 
int main()
{
	for (int i = 0; i < Row; i++)
	{
		for (int j = 0; j < Col; j++)
		{
			printf("%d ", Qmap[i][j]);
		}
		printf("\n");
	}
	tag[0][0] = 1;
	pathMap[pathIndex] = Coord(0, 0);
	++pathIndex;
	Dfs(0, 0, 0);
    return 0;
}
 

       代码如上图，进行了很详细的注释，核心函数Dfs是一个递归处理的函数，因为“羊羹君”每走一步都是进行“碰壁式”移动，所以可以将每一步的Dfs进行递归处理，同时判断好成功条件。我们调试运行上面的代码，如下图：

     

     第一次我们行走了12步，路径字典中一共13个坐标记录。

     当然我们的Dfs函数是1分4,4分16探索方式的，因为Dfs后面的for(i++;i<3)循环，我们找到第一条路return后，函数会自动寻找其他路线，如果我们不break循环的话，那么继续运行，就会出现后面的路径，如下图：

     

     当然DFS深度优先搜索的特点就是第一次寻找的线路是最优线路，也就是最短的路径，因为DFS就是“碰壁式”寻路，就跟盲人摸着墙壁走路一样，如果这个“盲人”这摸那摸，走的路线就最远了。

     当然这里要注意，这个线路只是“年迈的羊羹君”行走的最短线路，并不是实际上的最优化线路，大家可以观察一下，“年迈的羊羹君”在(0,0) (0,1) (1,0) (1,1)这四个位置都走了一遍，而不是直接跨过到达(2,0)，这就是因为羊羹君nextMove“碰壁式”移动导致的，这就是DFS函数的最大缺点。

     那么有没有其他算法能解决这个“最优线路”的问题呢？当然有，只是相比DFS深度优先搜索更加耗费时间而已，DFS的优点就是速度快，一次探索寻路完毕，而我们想得到”最优线路“，则需要地图全局探索（当然就会带来更大的时间消耗），后面马上就开始学习讲解。

     so，我们接下来继续。