首页 > 编程语言 >【数据结构与算法】A*算法——自动寻路

【数据结构与算法】A*算法——自动寻路

时间：2024-08-16 20:52:50浏览次数：15  
标签：target point int Point itor 算法 static 数据结构 寻路

这里写目录标题

一.为什么用A*算法

上节课我们已经讲了最短路径算法,但是我们为什么还要使用A*算法呢?
那就要讲讲最短路径算法的缺点了.
很明显,我们要得到最短的,那么就需要比较,就需要我知道所有的路径,然后比较出最短的,那么我需要知道所有的路径这是非常庞杂的工作.

A*算法就巧妙的运用了人的思想,类似于人工智能一样,不需要事先知道所有的路径,只需要每一步都是朝向目的地的,同时附近可以走一步的.
虽然得出的未必是最短的一条路径,但是绝对是相对近的一条路.

二.A*算法的实现原理

那么我们需要注意的点就可以分为离终点有多远,附近的下一步能不能走通.
一般地图我们都可以当做二维数组来进行处理.
我们直接看图说话:
如果12是我们的起点,16是我们姚到的目的地,那我们是如何操作的呢?
看下面的步骤吧!
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
哎呀妈呀,可算是画完了.
这就是A*算法,接下来我们来代码实现吧.

三.A*算法的实现

头文件,我们先来看看需要做哪些事?

这是设置了从起点到改点的步数权重,就是G.
刚刚我是用的1,我们可以用10,都是一样的.
在这里插入图片描述
每个格子的属性,因为我们用的是二维数组表示地图,那么x,y代表数组下标位置.
G是起点格子到该格子的步数,H是该格子到终点格子的步数.
我们以计算总的步数F来判断下一步该走哪一个格子,也就是F最小的.
parent就是链接路径,
在这里插入图片描述
格子我们动态分配内存,同时最后我们需要清理.
当然要初始化地图和寻找路线.
在这里插入图片描述

1.初始化地图

二维数组的基本信息保存,其他函数需要用.
在这里插入图片描述
在这里插入图片描述

2.格子初始化

在这里插入图片描述

3.两个列表

在这里插入图片描述

4.起点到终点的路径

因为我们最后找到的节点是终点,但是我们需要的路径是从起点到终点,所以我们需要正序的将格子放入list容器中.
在这里插入图片描述

5.起点到终点的最佳路径★

首先将起点加入到openList.
在这里插入图片描述
如果openList不为空就一直找终点.最后为空就说明没有找到.
在这里插入图片描述
下面的都是在上面这个循环里面的.

先找到openList里面最小的F的格子.
在这里插入图片描述
对容器的遍历用迭代器
在这里插入图片描述
当这个格子判断后,我们就可以放入到closeList了,同时在openList里面排除.
在这里插入图片描述

然后我们就可以判断这个节点周围的点是否可以走通.
在这里插入图片描述
用vector容器来装可以走通的格子.
因为我们需要的这个格子周围的点,我们可以用两个for循环就包含了9个格子,但是下面我们会根据条件排除一些点.

在这里插入图片描述
如果越界了不可以,因为是一个二维数组,如果是障碍物不可以,这里我们在二维数组中设置的值为1的是障碍物.,如果在closeList的也不可以,因为我们已经走过了.
同时我们只需要上下左右就可以了.
在这里插入图片描述
判断某个格子是否在某个列表.
在这里插入图片描述
这个时候我们就得到了周围可走通格子的容器了,我们进行遍历计算其F值.

在这里插入图片描述
对于周围每个可以走通的格子我们进行判断是否在openList里面,如果没有就加入,有的话,就判断需不需要进行更新.判断的依据就是G是否更小,因为H都是一样的.

在这里插入图片描述
距离起点的步数计算.就是当前各个到下一步的步数+其父亲节点的G步数.
在这里插入图片描述
H(点到终点的距离)计算用了勾股定理.
如2~16的距离.
在这里插入图片描述

在这里插入图片描述
F的计算自不必多说.
在这里插入图片描述

遍历完周围的格子后,就清空,下一次又来用,并判断终点的格子有没有加入到openList.
如果有,就说明找到了,直接返回这个终点.
如果最后openList都为空了,那么就是没有找到终点,返回空.
在这里插入图片描述

6.资源的释放

将两个列表的格子释放内存.
在这里插入图片描述

四.完整代码

1.Astar.h

#pragma once
#include <list>

const int kCost1 = 10;
const int kCost2 = 14;

typedef struct _Point
{
	int x,y;//二维数组下标
	int F, G, H;//F=G+H
	struct _Point* parent;//parent的坐标
}Point;

//分配一个节点(格子)
Point* AllocPoint(int x, int y);

//初始化地图
void initAstarMaze(int* _maze, int _lines, int _colims);

//通过A*算法寻找路径
std::list<Point*>GetPath(Point* statPoint, Point* endPoint);

//清理资源,结束后必须调用
void ClearAstarMaze();

2.Astar.cpp

#include <math.h>
#include "Astar.h"
#include <iostream>
#include <vector>

static int* maze;//迷宫对应的二维数组,使用一级指针表示
static int cols;//二维数组对于的列数
static int lines;//二维数组对于的行数

static std::list<Point*>openList;//开放列表
static std::list<Point*>closeList;//关闭列表

//搜索从起点到终点的最佳路径
static Point* findPath(Point* startPoint, Point* endPoint);

//从开启列表中返回F值最小的节点
static Point* getLeasFpoint();

//获取当前点周围可达的节点
static std::vector<Point*>getSurroundPoints(const Point* point);

//判断某点是否可以用于下一步判断
static bool isCanreach(const Point* point, const Point* target);

//判断开放/关闭列表中是否包含某点
static Point* isInList(const std::list<Point*>& list, const Point* point);

//计算FGH值
static int calcG(Point* temp_start, Point* point);
static int calcH(Point* point, Point* end);
static int calcF(Point* point);

//分配一个节点(格子)
Point* AllocPoint(int x, int y)
{
	Point* temp = new Point;
	memset(temp, 0, sizeof(Point));//初始值清零
	temp->x = x;
	temp->y = y;
	return temp;
}


//初始化地图
void initAstarMaze(int* _maze, int _lines, int _colums)
{
	maze = _maze;
	lines = _lines;
	cols = _colums;
}

//通过A*算法寻找路径
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;
	}

	return path;
}


//搜索从起点到终点的最佳路径
static Point* findPath(Point* startPoint, Point* endPoint)
{
	openList.push_back(AllocPoint(startPoint->x,startPoint->y));
	while (!openList.empty())
	{
		//第一步,从开放列表中取最小的值
		Point* curPoint = getLeasFpoint();//找到F值最小的点

		//第二步,把当前节点放到关闭列表中
		openList.remove(curPoint);
		closeList.push_back(curPoint);

		//第三步,找到当前节点周围可达的节点
		std::vector<Point*>surroundPoints = getSurroundPoints(curPoint);
		std::vector<Point*>::const_iterator iter;
		for (iter = surroundPoints.begin(); iter != surroundPoints.end(); iter++)
		{
			Point* target = *iter;
			//对某个格子,如果不在开放列表中,就加入,设置当前格为其父节点.
			Point* exist = isInList(openList, target);
			if (!exist)
			{
				target->parent = curPoint;

				target->G = calcG(curPoint, target);
				target->H = calcH(target, endPoint);
				target->F = calcF(target);

				openList.push_back(target); 
			}
			else
			{
				int tempG = calcG(curPoint, target);
				if (tempG < target->G)
				{
					exist->parent = curPoint;
					exist->G = tempG;
					exist->F = calcF(target);
				}
				delete target;//如果已经存在了就不用了释放.
			}
		}

		surroundPoints.clear();
		Point* resPoint = isInList(openList, endPoint);
		if (resPoint)
		{
			return resPoint;
		}
	}
	return NULL;
}


//从开启列表中返回F值最小的节点
static Point* getLeasFpoint()
{
	if (!openList.empty())
	{
		Point* resPoint = openList.front();
		std::list<Point*>::const_iterator itor;
		for (itor = openList.begin(); itor != openList.end(); itor++)
		{
			if ((*itor)->F < resPoint->F)
			{
				resPoint = *itor;
			}
		}
		return resPoint;
	}
	return NULL;
}

//获取当前点周围可达的节点
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;	
}

static bool isCanreach(const Point* point, const Point* target)
{
	if (target->x<0 || target->x>(lines - 1)
		|| target->y<0 || target->y>(cols - 1)
		|| maze[target->x * cols + target->y] == 1
		|| (target->x == point->x && target->y == point->y)
		|| isInList(closeList, target))
	{
		return false;
	}

	if (abs(point->x - target->x) + abs(point->y - target->y) == 1)//abs绝对值.上下左右
	{
		return true;
	}
	else
	{
		return false;
	}
		
}

//判断开启/关闭列表中是否包含某点
static Point* isInList(const 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;
}

static int calcG(Point* temp_start, Point* point)
{
	int extraG = (abs(point->x - temp_start->x) + abs(point->y - temp_start->y)) == 1 ? kCost1 : kCost2;
	int parentG = (point->parent == NULL ? NULL : point->parent->G);
	return extraG + parentG;
}
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));
}
static int calcF(Point* point)
{
	return point->G + point->H;
}

//清理资源,结束后必须调用
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);//获取到下一个节点
	}
}

3.main.cpp

#include "Astar.h"
#include <list>
#include <iostream>
#include <Windows.h>

using namespace std;


int map[5][8] =
{
	{1,1,1,0,0,0,1,1},
	{0,0,0,0,1,0,0,0},
	{0,0,0,0,1,0,0,0},
	{0,0,0,0,1,0,0,0},
	{1,1,1,0,0,0,1,1},
};

void AStarTest()
{
	initAstarMaze(&map[0][0], 5, 8);
	//设置起始和结束点
	Point* start = AllocPoint(2, 1);
	Point* end = AllocPoint(2, 6);

	//通过A*算法寻找路径
	list<Point*>path=GetPath(start, end);

	cout << "寻路结果:" << endl;
	list<Point*>::const_iterator iter;
	for (iter = path.begin(); iter != path.end();iter++)
	{
		Point* cur = *iter;
		cout << '(' << cur->x << ',' << cur->y << ')' << endl;

		Sleep(800);
	}

	ClearAstarMaze();
}

int main()
{
	AStarTest();
	system("pause");
	return 0;
}

4.运行结果

在这里插入图片描述
就是走的这条路.
在这里插入图片描述

完结撒花
2024年8月16日17:29:59

标签：target,point,int,Point,itor,算法,static,数据结构,寻路
From： https://blog.csdn.net/qq_74047911/article/details/141259078

相关文章

  • 常见的排序算法
    插入排序时间复杂度O(n^2)空间复杂度O(1)选择排序的工作原理是在0~i的索引范围内去进行排序,将新增的数arr[i]一个个放进来排序,个人感觉有点类似于冒泡排序,但是和冒泡排序不同是选择排序是在小范围内找出最大最小完成一个小范围的有序,而冒泡排序是在整个数组中每次找......
  • 快速排序算法详解及Python实现
    目录引言快速排序算法步骤快速排序的Python实现性能分析注意事项引言快速排序（QuickSort）是一种高效的排序算法，由C.A.R.Hoare在1960年提出。它的基本思想是：通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此......
  • 文献分享: DiskANN查询算法的复杂度下界
    文章目录0.写在前面0.1.预备知识0.2.一些记号0.3.本文的研究概述1.DiskANN\text{DiskANN}DiskANN回顾1.0.Intro1.1.......
  • 2024“钉耙编程”中国大学生算法设计超级联赛（9）
    Preface最后一场HDU多校了，前期一直犯病但也堪堪签了前六题，但后期又是酣畅淋漓的后期三开三卡我写04，祁神写09，徐神写10，最后一个没调出来，赛后祁神和徐神都发现了很多修改点但因为题目还没公开、数据和题解也没法，就先坑着之后再来补了树异或价值首先不难发现\(k\)位这个限......
  • 基于三帧差算法的运动目标检测系统FPGA实现,包含testbench和MATLAB辅助验证程序
    目录1.算法运行效果图预览2.算法运行软件版本3.部分程序4.算法理论概述5.算法完整程序工程1.算法运行效果图预览(完整程序运行后无水印)将FPGA的仿真结果导入到MATLAB中，分别得到MATLAB的结果和FPGA的结果：2.算法运行软件版本vivado2019.2matlab2022a3.部分程序......
  • 算法笔记——可持久化线段树
    维护历史值当要修改一个节点时，把跟他有关的线段树中所有节点舍弃，并建立新节点连接.代码如下：#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+5;intn,m,a[N],root[N],top;structnode{ intl,r,val;}t[N*40];intclone(intx)//新建节点{ top++; t......
  • 力扣面试经典算法150题：找出字符串中第一个匹配项的下标
    找出字符串中第一个匹配项的下标今天的题目是力扣面试经典150题中的数组的简单题:找出字符串中第一个匹配项的下标题目链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/?envType=study-plan-v2&envId=top-interview-......
  • 数据结构（C++版）——顺序表
    一、顺序表有关的基本操作1、InitList(&L)：初始化线性表，构造一个空的线性表L2、DestroyList(&L)：销毁线性表L3、ClearList(&L)：将线性表L重置为空表4、ListEmpty(L)：若L为空表，则返回TURE，否则返回FALSE5、GetElem(L,i,&e)：用e返回L中第i个数据元素的值6、LocateElem(L,e)：在线性......
  • KMP算法
    KMP算法介绍KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在主串（text）中查找模式串（pattern）。KMP通过预处理模式串，避免了在匹配失败时回溯主串，提高了匹配效率。其时间复杂度为O(n+m)，其中n是主串的长度，m是模式串的长度。KMP算法的关键思想KMP算法的核心思想......
  • CRC算法原理、推导及实现
    CRC,CyclicRedundancyCheck,循环冗余校验1.基本原理CRC的本质是除法，把待检验的数据当作一个很大（很长）的被除数，两边选定一个除数（有的文献叫poly），最后得到的余数就是CRC的校验值。判定方法：将消息和校验和分开。计算消息的校验和（在附加W个零后），并比较两个校验和。把校验......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99