C/C++实现游戏里的自动深度寻路算法

寻路算法分为深度寻路算法、广度寻路算法和A星寻路算法。本文以深度寻路算法来编程实现游戏里的自动寻路。

一、深度寻路思想：

1、一个一个方向去试探能不能走
2、必须给试探方向定一个顺序
3、走过了的要标记，是障碍不走，走过了不走
4、遇到死胡同需要回退
4.1 每走一步，都把坐标放到栈中
4.2 遇到死胡同回退
4.2.1 删除栈顶元素
4.2.2 跳到当前栈顶元素处

欢迎加入学习群【892643663】，获取全套免费C/C++企业实战级课程资源（素材+源码+视频）和编译大礼包

二、代码

1、深度寻路.CPP

// 深度寻路.cpp : 定义控制台应用程序的入口点。
 
#include "stdafx.h"
#include "MyStack.h"
#include <windows.h>
    
//行数   Y轴 竖
#define ROWS 12
//列数   X轴 横
#define COLS 12

//方向
enum direct{p_up,p_down,p_left,p_right};//上 下 左 右

//自定义点类型
struct MyPoint{
	int row;
	int col;
};

//自定义辅助地图类型
struct pathNode{
	int		val;	//地图上的值
	direct	dir;	//方向
	bool	isFind;	//是否走过    0 false 没有走过   1 true 走过
};

//1 地图
int map[ROWS][COLS] = {
	{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
	{ 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1 },
	{ 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1 },
	{ 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1 },
	{ 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1 },
	{ 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1 },
	{ 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1 },
	{ 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1 },
	{ 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1 },
	{ 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1 },
	{ 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1 },
	{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};
    
//2 显示地图
void printMap(int map[ROWS][COLS],MyPoint pos){
	for (int i = 0; i < ROWS; i++){		//一次 一行
		for (int j = 0; j < COLS; j++){	//一次 一格
			if (pos.row == i && pos.col == j){//是人
				printf("人");
			}else if (map[i][j] == 1){//墙壁 障碍物
				printf("墙");
			}
			else if (map[i][j] == 0){//路
				printf("  ");
			}
		}
		printf("\n");
	}
}


int _tmain(int argc, _TCHAR* argv[])
{
	//目的：找到起点到终点的路径
	    	
	//制作辅助地图
	pathNode pathMap[ROWS][COLS] = { 0 };//初始化数组 自动填充0
	for (int i = 0; i < ROWS; i++){
		for (int j = 0; j < COLS; j++){
			pathMap[i][j].val = map[i][j];
		}
	}

	//准备栈
	MyStack<MyPoint> stack;
	bool isFindEnding = false;
	//起点
	MyPoint begPos = { 1 , 1 };
	//终点
	MyPoint endPos = { 2, 10 };

	//标记起点已经走过
	pathMap[begPos.row][begPos.col].isFind = true;
	//起点入栈
	stack.push(begPos);
	//人
	MyPoint currentPos = begPos;//当前位置
	MyPoint searchPos;

	while (1){
		searchPos = currentPos;
		switch (pathMap[currentPos.row][currentPos.col].dir)
		{
		case p_up:
			searchPos.row--;
			//改试探方向
			pathMap[currentPos.row][currentPos.col].dir = p_down;
			if (pathMap[searchPos.row][searchPos.col].val == 0 && //是路
				pathMap[searchPos.row][searchPos.col].isFind == false){//没有走过
				
				//标记走过
				pathMap[searchPos.row][searchPos.col].isFind = true;
				//入栈
				stack.push(searchPos);
				//走
				currentPos = searchPos;
			}
			break;
		case p_down:
			searchPos.row++;
			//改试探方向
			pathMap[currentPos.row][currentPos.col].dir = p_left;
			if (pathMap[searchPos.row][searchPos.col].val == 0 && //是路
				pathMap[searchPos.row][searchPos.col].isFind == false){//没有走过

				//标记走过
				pathMap[searchPos.row][searchPos.col].isFind = true;
				//入栈
				stack.push(searchPos);
				//走
				currentPos = searchPos;
			}
			break;
		case p_left:
			searchPos.col--;
			//改试探方向
			pathMap[currentPos.row][currentPos.col].dir = p_right;
			if (pathMap[searchPos.row][searchPos.col].val == 0 && //是路
				pathMap[searchPos.row][searchPos.col].isFind == false){//没有走过

				//标记走过
				pathMap[searchPos.row][searchPos.col].isFind = true;
				//入栈
				stack.push(searchPos);
				//走
				currentPos = searchPos;
			}
			break;
		case p_right:
			searchPos.col++;
			
			if (pathMap[searchPos.row][searchPos.col].val == 0 && //是路
				pathMap[searchPos.row][searchPos.col].isFind == false){//没有走过

				//标记走过
				pathMap[searchPos.row][searchPos.col].isFind = true;
				//入栈
				stack.push(searchPos);
				//走
				currentPos = searchPos;
			}
			else{//死胡同
				stack.pop();//删除栈顶元素
				currentPos = stack.getTop();//跳到当前栈顶元素处
			}
			break;
		default:
			break;
		}

		printMap(map,currentPos);//显示地图
		Sleep(1000);

		if (searchPos.row == endPos.row &&
			searchPos.col == endPos.col){
			printf("找到终点啦!\n");
			isFindEnding = true;
			break;
		}

		if (stack.isEmpty())
			break;
		
	}
	
	if (isFindEnding){
		printf("路径：");
		while (!stack.isEmpty()){
			searchPos = stack.getTop();
			printf("（%d,%d） ", searchPos.row, searchPos.col);
			stack.pop();
		}
		printf("\n");
	}
	else{
		printf("找不到终点，拜拜!\n");
	}

	while (1);//停顿
	return 0;
}

2、 MyStack.h

#pragma once

template<class T>
class MyStack{
	T*		buff;		//内存段首地址
	size_t	capacity;	//容量
	size_t	len;		//元素个数
public:
	MyStack();
	~MyStack();

	void push(T const& data);//存入数据
	void pop();//取出数据
	bool isEmpty()const;//判断栈是否为空
	T getTop()const;
};

template<class T>
MyStack<T>::MyStack(){
	buff = NULL;
	capacity = len = 0;
}
template<class T>
MyStack<T>::~MyStack(){
	if (buff)
		delete[] buff;
	buff = NULL;
	capacity = len = 0;
}
template<class T>
//存入数据
void MyStack<T>::push(T const& data){
	if (len >= capacity){
		capacity = capacity + (((capacity >> 1) > 1) ? (capacity >> 1) : 1);
		T* temp = new T[capacity];
		if (buff){
			memcpy(temp, buff, sizeof(T)*len);
			delete[] buff;
		}
		buff = temp;
	}
	buff[len++] = data;
}
template<class T>
//取出数据
void MyStack<T>::pop(){
	if (len > 0) len--;
}
template<class T>
//判断栈是否为空
bool MyStack<T>::isEmpty()const{
	return (len == 0);
}
template<class T>
//获取栈顶元素
T MyStack<T>::getTop()const{
	return buff[len - 1];
}

欢迎加入学习群【892643663】，获取全套免费C/C++企业实战级课程资源（素材+源码+视频）和编译大礼包