AL游戏中的自动寻路——A算法详解（C++实现）_数据结构中迷宫的a算法c++

作者：小蓝xlanll | 2024-05-02 21:25:58

踩

数据结构中迷宫的a*算法c++

一、A*算法的一个应用实例：迷宫寻路

【下面是A*算法的一个应用实例：迷宫寻路，将迷宫地图信息录入后即可自动实现路径的搜索。

以下是迷宫寻路中的全部代码，大家可以直接拷贝运行。

AStar.h


#pragma once
#include<list>
 
const int kCost1 = 1;	//直移一格的消耗
const int kCost2 = 2;	//斜移一格的消耗
 
 
typedef struct _Point {
	int x, y;	//点坐标，x - 横排  y - 竖排
	int F, G, H;	//F=G+H
	struct _Point* parent;
}Point;
 
/******************************
* 功能：分配一格结点
* 输入：
*		x - 二维数组行
*		y - 二维数组列
* 返回：
*		已初始化的结点的指针
******************************/
Point* AllocPoint(int x, int y);
 
/******************************
* 功能：初始化地图
* 输入：
*		_maze - 二维数组地址
*		_lines - 二维数组行数
*		_columns - 二维数组列数
* 返回：
*		无
******************************/
void InitAstarMaze(int* _maze, int _lines, int _colums);
 
/******************************
* 功能：寻找路径
* 输入：
*		startPoint - 起始位置
*		endPoint - 终点位置
* 返回：
*		返回路径链表的头节点
******************************/
std::list<Point*> GetPath(Point* startPoint, Point* endPoint);
 
/******************************
* 功能：资源清理
* 输入：
*		无
* 返回：
*		无
******************************/
void ClearAstarMaze();

AStar.cpp


#include<math.h>
#include<iostream>
#include<vector>
#include"AStar.h"
 
 
static int* maze;	// 迷宫对应的二维数组，用一级指针表示
static int cols;	// 二维数组列数
static int lines;	// 二维数组对应的行数
 
 
static std::list<Point*>openList;	// 开放列表
static std::list<Point*>closeList;	// 关闭列表
 
 
Point* AllocPoint(int x, int y);
static std::vector<Point*>getSurroundPoints(const Point* point);
static Point* isInList(std::list<Point*>& list, const Point* point);
/******************************
* 功能：查找openList中F值最小节点
* 输入：
*		无
* 返回：
*		F值最小节点
******************************/
static Point* getLeastFpoint() {
 
	if (!openList.empty()) {
		Point* resPoint = openList.front();
		std::list<Point*>::const_iterator itor;
		for (itor = openList.begin(); itor != openList.end(); ++itor) {
			Point* p = *itor;	// itor是list<Point *>类型迭代器，所以*itor是Poit *类型
			if (p->F < resPoint->F) {
				resPoint = *itor;
			}
		}
		return resPoint;
	}
 
	//是空值情况
	return NULL;
}
 
/******************************
* 功能：计算指定结点到父节点的G值
* 输入：
*		parent - 父节点
*		point - 指定结点
* 返回：
*		指定结点到父节点的G值
******************************/
static int calcG(Point* parrent, Point* point) {
	//如果可以直走额外消耗量为kCost1，如果需要斜走额外消耗量为kCost2
	//int extraG=abs(parrent->x - point->x) + abs(parrent->y - point->y) == 1 ? kCost1 : kCost2;
	int extraG = kCost2;	// 规定只能直着走
	int parentG = (point->parent == NULL ? NULL : point->parent->G);
	return parentG + extraG;
}
 
/******************************
* 功能：计算指定结点到终点结点的H值
* 输入：
*		point - 指定结点
*		endPoint - 终点结点
* 返回：
*		指定结点到终点结点的H值
******************************/
static int calcH(Point* point, Point* end) {
	//考虑斜移
	//return (int)sqrt((double)(end->x - point->x) * (double)(end->x - point->x) + (double)(end->y - point->y) + (double)(end->y - point->y));
	//规定只能直走
	return (end->x - point->x) + (end->y - point->y);
}
/******************************
* 功能：计算指定结点的F值
* 输入：
*		point - 指定结点
* 返回：
*		指定结点的F值
******************************/
static int calcF(Point* point) {
	return point->G + point->H;
}
 
 
/******************************
* 功能：A*算法实现
* 输入：
*		startPoint - 起始位置
*		endPoint - 终点位置
* 返回：
*		终点位置的结点
******************************/
static Point* findPath(Point* startPoint, Point* endPoint) {
	//置入起点，拷贝开辟一格节点，内外隔离
	openList.push_back(AllocPoint(startPoint->x, startPoint->y));
	
	//openList不为空时，不停的取openList中L的最小值
	while (!openList.empty()) {
		//查找openList中F最小值节点
		Point* curPoint = getLeastFpoint();
 
		//把最小值节点放到关闭列表中
		openList.remove(curPoint);	// 从openList中移除
		closeList.push_back(curPoint);	// 放入closeList中
 
		//找到当前节点周围可达节点处理
		std::vector<Point*>surroundPoints = getSurroundPoints(curPoint);
		std::vector<Point*>::const_iterator iter;
		for (iter = surroundPoints.begin(); iter != surroundPoints.end(); ++iter) {
			Point* target = *iter;
			//对某一结点，如果不在openList中，则加入到openList中，并设置其父节点；如果在openList中，则重新计算F值，选取min(F)的结点
			Point* exist = isInList(openList, target);
			//不在openList中
			if (!exist) {
				target->parent = curPoint;
				target->G = calcG(curPoint, target);
				target->H = calcH(target, endPoint);
				target->F = calcF(target);
				openList.push_back(target);
			}// 在开放列表中，重新计算G值，保留min(F)
			else {
				int tempG = calcG(curPoint, target);
				if (tempG < target->G) {
					exist->parent = curPoint;
					exist->G = tempG;
					exist->F = calcF(target);
				}
				delete target;
			}
		}	// end for
		surroundPoints.clear();
 
		//判断终点是否在openList中
		Point* resPoint = isInList(openList, endPoint);
		if (resPoint) {
			return resPoint;
		}
	}
	//如果while执行完毕则表明没有找到
	return NULL;
}
 
/******************************
* 功能：判断指定节点是否在指定链表中
* 输入：
*		list - 指定链表
*		point - 指定节点
* 返回：
*		Point* - 判断节点在链表中，返回该在链表中地址
*		NULL - 不在节点中
******************************/
static Point* isInList(std::list<Point*>& list, const Point* point) {
	std::list<Point*>::const_iterator itor;
	for (itor = list.begin(); itor != list.end(); ++itor) {
		if ((*itor)->x == point->x && (*itor)->y == point->y) {
			return *itor;
		}
	}
	return NULL;
}
 
/******************************
* 功能：判断某点是否可达指定点
* 输入：
*		point - 指定节点
*		target - 待判断节点
* 返回：
*		true - 可达
*		false - 不可达
******************************/
static bool isCanreach(const Point* point, const Point* target) {
	
	int x = target->x;
	int y = target->y;
	//待测节点超过二维数组，或待测节点是障碍物，或者待测节点与指定节点重合，或待测节点在closeList链表中。则不可达
	if (x < 0 || x >= lines || y < 0 || y >= cols
		|| maze[x * cols + y] == 0
		|| (x == point->x && y == point->y)
		|| isInList(closeList, target)) {
		
		return false;
	}
	if (abs(point->x - target->x) + abs(point->y - target->y) == 1) {
		//待测点与指定点相邻
		return true;
	}
	else {
		return false;
	}
}
 
/******************************
* 功能：获得当前节点的周围可达节点（这里只考虑直着走）
* 输入：
*		point - 指定节点
* 返回：
*		周围可达节点vector数组
******************************/
static std::vector<Point*>getSurroundPoints(const Point* point) {
	//定义存储可达节点的数组
	std::vector<Point*>surroundPoints; 
 
	for (int x = point->x - 1; x <= point->x + 1; ++x) {
		for (int y = point->y - 1; y <= point->y + 1; ++y) {
			Point* temp = AllocPoint(x, y);
			if (isCanreach(point, temp)) {
				surroundPoints.push_back(temp);
			}
			else {
				//不可达则释放资源
				delete temp;
			}
		}
	}
	return surroundPoints;
}
 
/******************************
* 功能：初始化地图
* 输入：
*		_maze - 二维数组地址
*		_lines - 二维数组行数
*		_columns - 二维数组列数
* 返回：
*		无
******************************/
void InitAstarMaze(int* _maze, int _lines, int _colums) {
	maze = _maze;
	cols = _colums;
	lines = _lines;
}
 
 
/******************************
* 功能：分配一格结点
* 输入：
*		x - 二维数组行
*		y - 二维数组列
* 返回：
*		已初始化的结点的指针
******************************/
Point* AllocPoint(int x, int y) {
	Point* temp = new Point;
	memset(temp, 0, sizeof(Point));	//初始值清零
	temp->x = x;
	temp->y = y;
	return temp;
}
 
/******************************
* 功能：调用A*算法，寻找路径
* 输入：
*		startPoint - 起始位置
*		endPoint - 终点位置
* 返回：
*		返回路径链表的头节点
******************************/
std::list<Point*> GetPath(Point* startPoint, Point* endPoint) {
	Point* result = findPath(startPoint, endPoint);
	std::list<Point*>path;
	//返回路径，如果没有找到路径，返回空链表
	while (result) {
		path.push_front(result);
		result = result->parent;
	}
	//path.reverse();
	return path;
}
 
 
/******************************
* 功能：资源清理
* 输入：
*		无
* 返回：
*		无
******************************/
void ClearAstarMaze() {
	maze = NULL;
	lines = 0;
	cols = 0;
	std::list<Point*>::iterator itor;
	for (itor = openList.begin(); itor != openList.end();) {
		delete* itor;
		itor = openList.erase(itor);	//从链表中删除某个结点，并返回下一个结点
 
	}
	for (itor = closeList.begin(); itor != closeList.end();) {
		delete* itor;
		itor = closeList.erase(itor);	//从链表中删除某个结点，并返回下一个结点
 
	}
}

迷宫地图代码

迷宫寻路中的图片下载地址

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/526184

AL游戏中的自动寻路——A*算法详解（C++实现）_数据结构中迷宫的a*算法c++

目录

一、A*算法的一个应用实例：迷宫寻路

AL游戏中的自动寻路——A算法详解（C++实现）_数据结构中迷宫的a算法c++