a*算法 订阅
A*算法,A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近,最终搜索速度越快。 展开全文
A*算法,A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近,最终搜索速度越快。
信息
表达式
f(n)=g(n)+h(n)
运行条件
静态网路
原    理
距离估算值与实际值越接近程度
中文名
A*算法
外文名
A-star algorithm
别    称
启发式搜索
A*算法原理
A* [1]  (A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是许多其他问题的常用启发式算法。注意——是最有效的直接搜索算法,之后涌现了很多预处理算法(如ALT,CH,HL等等),在线查询效率是A*算法的数千甚至上万倍。公式表示为: f(n)=g(n)+h(n),其中, f(n) 是从初始状态经由状态n到目标状态的代价估计,g(n) 是在状态空间中从初始状态到状态n的实际代价,h(n) 是从状态n到目标状态的最佳路径的估计代价。(对于路径搜索问题,状态就是图中的节点,代价就是距离)h(n)的选取保证找到最短路径(最优解的)条件,关键在于估价函数f(n)的选取(或者说h(n)的选取)。我们以d(n)表达状态n到目标状态的距离,那么h(n)的选取大致有如下三种情况:
收起全文
精华内容
下载资源
问答
  • A*算法A*算法 A*算法

    2009-06-16 14:48:58
    A*算法A*算法A*算法A*算法A*算法A*算法A*算法A*算法A*算法A*算法
  • A*算法

    万次阅读 2018-08-21 10:07:28
    A*算法常用于二维地图路径规划,算法所采用的启发式搜索可以利用实际问题所具备的启发式信息来指导搜索,从而减少搜索范围,控制搜索规模,降低实际问题的复杂度 。 二、算法原理 A*算法的原理是设计一个代价估计函数:...

    一、算法介绍

    A*算法常用于二维地图路径规划,算法所采用的启发式搜索可以利用实际问题所具备的启发式信息来指导搜索,从而减少搜索范围,控制搜索规模,降低实际问题的复杂度 。

    二、算法原理

    A*算法的原理是设计一个代价估计函数:

    其中评估函数 F(n)是从起始节点通过节点 n 的到达目标节点的最小代价路径的估计值,函数 G(n)是从起始节点到 n 节点的已走过路径的实际代价,函数H(n)是从 n 节点到目标节点可能的最优路径的估计代价 。函数 H(n)表明了算法使用的启发信息,它来源于人们对路径规划问题的认识,依赖某种经验估计。根据 F(n)可以计算出当前节点的代价,并可以对下一次能够到达的节点进行评估。采用每次搜索都找到代价值最小的点再继续往外搜索的过程,一步一步找到最优路径。

    三、算法流程

    (1)首先创建开始节点为 START,目标节点为 GOAL,创建开启列表OPEN 列表,关闭列表 CLOSED 列表,创建关闭列表时初始化为空。

    (2)将开始节点 START 加入 OPEN 中。

    (3)查询 OPEN 中的节点。如果 OPEN 为空,则退出并说明没有找到路径。

    (4)如果 OPEN 不为空,从 OPEN 中选择 F(n)函数值最小的节点 n。

    (5)把节点 n 从 OPEN 中去除,并将其添加到 CLOSED 中。

    (6)判断节点 n 是否是目标节点 GOAL,如果节点 n 是目标节点 GOAL,则退出,并说明找到最优路径。如果节点 n 不是目标节点 GOAL,则转到(7)。

    (7)扩展节点 n,生成 n 节点的子节点集。设 n 节点的子节点为 m,对所有字节点 m 计算 F(m)。之后根据节点 m 的分类情况往下运行:

    1)若节点 m 既不在 OPEN 中也不在 CLOSED 中,将其加入 OPEN中,并为节点 m 分配一个指向其父节点 n 的指针。之后算法运行找到目标节点后根据该指针逐次返回,构成最优路径。

    2)若节点 m 在 OPEN 中,则比较刚计算的 F(m)值和之前已存在的F(m)旧值。若 F(m)新值比旧值小,表明算法找到一条更好的路径,将 F(m)新值作为节点 m 的代价值;若 F(m)新值比旧值大,将 F(m)旧值作为节点 m 的代价值。修改节点 m 的指针,将指针指向它的父节点 n。

    3)若节点 m 在 CLOSED 中,则忽略该节点并转到(7)。

    (8)转到(3)继续运行,直至算法获得最优路径或无解退出。其中,在算法运行中创建的列表 OPEN 用于保存要搜索的节点,这些节点与算法运行的当前节点相邻并且不在列表 CLOSED 中。列表 CLOSED 用来储存算法获得最佳路径点。

    四、简单实现

    main.cpp

    #include "AStarAlgorithm.h"
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    
    using namespace std;
    
    /**
      * Although this problem is better solved with dynamic programming,
      * it illustrates perfectly how to inherit from that template in order to solve a problem.
      *
      * Let's assume a currency composed of coins whose values are 2, 7, 8 and 19. 
      * The problem consists of finding a minimal set of these coins whose total value equals a given amount.
      */
    
    class CCoinDistribution	{
    public:
    	size_t coins2;
    	size_t coins7;
    	size_t coins8;
    	size_t coins19;
    	CCoinDistribution():coins2(0),coins7(0),coins8(0),coins19(0)	{}
    	size_t money() const	{
    		return 2*coins2+7*coins7+8*coins8+19*coins19;
    	}
    	inline bool operator==(const CCoinDistribution &mon) const	{
    		return (coins2==mon.coins2)&&(coins7==mon.coins7)&&(coins8==mon.coins8)&&(coins19==mon.coins19);
    	}
    };
    class CAStarExample:public CAStarAlgorithm<CCoinDistribution>	{
    private:
    	const size_t N;
    public:
    	CAStarExample(size_t goal):N(goal)	{}
    	virtual bool isSolutionEnded(const CCoinDistribution &s)	{	
    		return s.money()==N;
    	}
    	virtual bool isSolutionValid(const CCoinDistribution &s)	{	
    			return s.money()<=N;
    	}
    	virtual void generateChildren(const CCoinDistribution &s,vector<CCoinDistribution> &sols)	{	
    		sols=vector<CCoinDistribution>(4,s);
    		sols[0].coins2++;	
    		sols[1].coins7++;	
    		sols[2].coins8++;	
    		sols[3].coins19++;	
    	}
    	virtual double getHeuristic(const CCoinDistribution &s)	{	
    		return static_cast<double>(N-s.money())/19.0;
    	}
    	virtual double getCost(const CCoinDistribution &s)	{	
    		return s.coins2+s.coins7+s.coins8+s.coins19;
    	}
    };
    
    int main(int argc,char **argv)	{
    	for (;;)	{
    		char text[11];
    		printf("Input an integer number to solve a problem, or \"e\" to end.\n");
    		if (1!=scanf("%10s",text))  
    		{
    			printf("Please, input a positive integer.\n\n");
    			continue;
    		}
    		if (strlen(text)==1&&(text[0]=='e'||text[0]=='E')) break;
    		int val=atoi(text);
    		if (val<=0)	{
    			printf("Please, input a positive integer.\n\n");
    			continue;
    		}
    
    		CCoinDistribution solIni,solFin;
    		CAStarExample prob(static_cast<size_t>(val));
    		switch (prob.getOptimalSolution(solIni,solFin,HUGE_VAL,15))	{
    			case 0:
    				printf("No solution has been found. Either the number is too small, or the time elapsed has exceeded 15 seconds.\n\n");
    				break;
    			case 1:
    				printf("An optimal solution has been found:\n");
    				printf("\t%u coins of 2 piastres.\n\t%u coins of 7 piastres.\n\t%u coins of 8 piastres.\n\t%u coins of 19 piastres.\n\n",(unsigned)solFin.coins2,(unsigned)solFin.coins7,(unsigned)solFin.coins8,(unsigned)solFin.coins19);
    				break;
    			case 2:
    				printf("A solution has been found, although it may not be optimal:\n");
    				printf("\t%u coins of 2 piastres.\n\t%u coins of 7 piastres.\n\t%u coins of 8 piastres.\n\t%u coins of 19 piastres.\n\n",(unsigned)solFin.coins2,(unsigned)solFin.coins7,(unsigned)solFin.coins8,(unsigned)solFin.coins19);
    				break;
    		}
    	}
    	return 0;
    }
    
    

    AStarAlgorithm.h

    
    #ifndef CASTARALGORITHM_H
    #define CASTARALGORITHM_H
    #include <map>
    #include <vector>
    #include <cmath>
    
    template<typename T> class CAStarAlgorithm	{
    public:
    	virtual bool isSolutionEnded(const T &sol)=0;
    	virtual bool isSolutionValid(const T &sol)=0;
    	virtual void generateChildren(const T &sol,std::vector<T> &sols)=0;
    	virtual double getHeuristic(const T &sol)=0;
    	virtual double getCost(const T &sol)=0;
    private:
    	inline double getTotalCost(const T &sol)	{
    		return getHeuristic(sol)+getCost(sol);
    	}
    public:
    	int getOptimalSolution(const T &initialSol,T &finalSol,double upperLevel=HUGE_VAL,double maxComputationTime=HUGE_VAL)	{
    		std::multimap<double,T> partialSols;
    		partialSols.insert(std::pair<double,T>(getTotalCost(initialSol),initialSol));
    		double currentOptimal=upperLevel;
    		bool found=false;
    		std::vector<T> children;
    		while (!partialSols.empty())	{
    			typename std::multimap<double,T>::iterator it=partialSols.begin();
    			double tempCost=it->first;
    			if (tempCost>=currentOptimal) return found?1:0;
    			T tempSol=it->second;
    			partialSols.erase(it);
    			if (isSolutionEnded(tempSol))	{
    				currentOptimal=tempCost;
    				finalSol=tempSol;
    				found=true;
    				continue;
    			}
    			generateChildren(tempSol,children);
    			for (typename std::vector<T>::const_iterator it2=children.begin();it2!=children.end();++it2) if (isSolutionValid(*it2))	{
    				bool alreadyPresent=false;
    				double cost=getTotalCost(*it2);
    				typename std::pair<typename std::multimap<double,T>::const_iterator,typename std::multimap<double,T>::const_iterator> range = partialSols.equal_range(cost);
    				for (typename std::multimap<double,T>::const_iterator it3=range.first;it3!=range.second;++it3) if (it3->second==*it2)	{
    					alreadyPresent=true;
    					break;
    				}
    				if (!alreadyPresent) partialSols.insert(std::pair<double,T>(getTotalCost(*it2),*it2));
    			}
    		}
    		return found?1:0;
    	}
    };
    
    #endif
    
    

     

     

     

    展开全文
  • 背景:项目需要接触此算法,以下是一些自学成果,如有不足之处,欢迎指出,必虚心接受。做了一份PPT来汇报,此处直接使用自己PPT的截图。部分图片来源网络,如有侵权立马删除,以下博文仅作为学习...A*算法的定义伪...

    背景:项目需要接触此算法,以下是一些自学成果,如有不足之处,欢迎指出,必虚心接受。做了一份PPT来汇报,此处直接使用自己PPT的截图。部分图片来源网络,如有侵权立马删除,以下博文仅作为学习笔记。后期又新增了完整PPT。https://blog.csdn.net/dujuancao11/article/details/114842884

    目录

    A*寻路算法 

    A*算法解决什么问题

    A*算法的基本原理

    A*算法的详细原理

    A*算法的详细原理之定义

    ​A*算法的详细原理之初始设定 

    ​A*算法的详细原理之寻路原理

    A*算法的详细原理之结束条件

    A*算法的寻路详细步骤

    A*算法的举例说明 

    A*算法的伪代码

    A*算法的定义伪代码 (C++)

    A*算法的寻路伪代码(C++)

    Python+PyQt代码实现

    代码内容(可运行)

    运行结果 

    可执行文件

    拓展

    Dijkstra算法和A*算法的比较


     

    A*寻路算法 

    A*算法解决什么问题

    A*算法的基本原理

    A*算法的详细原理

    A*算法的详细原理之定义

    A*算法的详细原理之初始设定 

    A*算法的详细原理之寻路原理

    A*算法的详细原理之结束条件

     

    A*算法的寻路详细步骤

    S(start)起点              E(End)终点

    A*算法的举例说明 

    如果还不懂的话,可以参考我手写的计算步骤,再不懂可以私信我。(手稿字有点丑) 

     

     

     

     

    A*算法的伪代码

    A*算法的定义伪代码 (C++)

    int open_list;//一个记录下所有被考虑来寻找最短路径的格子
    int close_list; //一个记录下不会再被考虑的格子
    typedef struct point{
    	bool Is_Wall;
    	struct point* father;//父节点
    	int G;// 表示从起点 A 移动到网格上指定方格的移动耗费 (上下左右,还可沿斜方向移动)
    	int old_G;//旧G 第一次:从起点 A 直接移动到 A 四周方格的移动耗费 ;上次更新得到的G 
    	int new_G; //新G  从起点 A 经过当前搜索中心点到其四周指定点的移动耗费 
    	int H;//表示从指定的方格移动到终点 B 的预计耗费 (H 有很多计算方法, 这里我们设定只可以上下左右移动)
    	int F=G+H;//表示该点的总耗费
    }Point;
    point* start_point;
    point* end_point;
    point* min_point; 
    point* now_point; 

    A*算法的寻路伪代码(C++)

    //FindPath
    do{
    	//确定中心搜索点,上一个中心点关闭,新的中心点开启 
    	查找:Find the minimumm "point" of "F" from the "open_list" center;
    	"now_point" = "min_point";//minimumm point 
    	"now_point"添加到"close_list";
    	
    	//新中心点的周围点开启,新中心点关闭 
    	循环遍历:"now_point"相邻的周围8格"s_now_point"中的每一个;
    	//这一块它指的就是now_point周围8点当前搜索点 s_now_point,为了简单直接用它表示 
    	if (它不可通过||它已经在"close_list"中){
    		什么也不做;
    	} else if (它不在开启列表中){
    		把它添加进"open_list";
    		把"now_point"作为这它的"father",计算它的"F","G","H";
    	}else if (它已经在开启列表中){//通过G来判断是否需要更新 
    		if (new_G < old_G){
    			更新它的"father"为当前中心搜索点"now_point";
    			更新它的"G"与"F" ;
    		} else{
    			不更新,保持原来的"father", "G"与"F" ;
    		} 
    	}
    } while(目标格"end_point"已经在"open_list"||"open_list"==NULL)
    //存在路径:目标格"end_point"已经在"open_list"
    //不存在路径: "open_list"==NULL,搜索了所有可能的点 
    

    Python+PyQt代码实现

    代码内容(可运行)

    import time,sys
    from PyQt5.QtWidgets import QDialogButtonBox,QDialog,QMainWindow,QGridLayout,QTextEdit,QLineEdit,QWidget, QMessageBox, QApplication,QLabel,QPushButton,QHBoxLayout,QVBoxLayout
    from PyQt5.QtCore import Qt,QTimer,QObject,pyqtSignal,QBasicTimer
    from PyQt5.QtGui import QPainter, QColor, QFont,QPen
    import json
    class config:
    	WIDTH=20#地图列数
    	HEIGHT=20#地图行数
    	blockLength=30#绘制画面时每一个节点方块的边长
    class point:#点类(每一个唯一坐标只有对应的一个实例)
    	_list=[]#储存所有的point类实例
    	_tag=True#标记最新创建的实例是否为_list中的已有的实例,True表示不是已有实例
    	def __new__(cls,x,y):#重写new方法实现对于同样的坐标只有唯一的一个实例
    		for i in point._list:
    			if i.x==x and i.y==y:
    				point._tag=False
    				return i
    		nt=super(point,cls).__new__(cls)
    		point._list.append(nt)
    		return nt
    	def __init__(self,x,y):
    		if point._tag:
    			self.x=x
    			self.y=y
    			self.father=None
    			self.F=0#当前点的评分  F=G+H
    			self.G=0#起点到当前节点所花费的消耗
    			self.cost=0#父节点到此节点的消耗
    		else:
    			point._tag=True
    	@classmethod
    	def clear(cls):#clear方法,每次搜索结束后,将所有点数据清除,以便进行下一次搜索的时候点数据不会冲突。
    		point._list=[]
    	def __eq__(self,T):#重写==运算以便实现point类的in运算
    		if type(self)==type(T):
    			return (self.x,self.y)==(T.x,T.y)
    		else:
    			return False
    	def __str__(self):
    		return'(%d,%d)[F=%d,G=%d,cost=%d][father:(%s)]'%(self.x,self.y,self.F,self.G,self.cost,str((self.father.x,self.father.y)) if self.father!=None else 'null')
    class A_Search:#核心部分,寻路类
    	def __init__(self,arg_start,arg_end,arg_map):
    		self.start=arg_start#储存此次搜索的开始点
    		self.end=arg_end#储存此次搜索的目的点
    		self.Map=arg_map#一个二维数组,为此次搜索的地图引用
    		self.open=[]#开放列表:储存即将被搜索的节点
    		self.close=[]#关闭列表:储存已经搜索过的节点
    		self.result=[]#当计算完成后,将最终得到的路径写入到此属性中
    		self.count=0#记录此次搜索所搜索过的节点数
    		self.useTime=0#记录此次搜索花费的时间--在此演示中无意义,因为process方法变成了一个逐步处理的生成器,统计时间无意义。
    		#开始进行初始数据处理
    		self.open.append(arg_start)
    	def cal_F(self,loc):
    		print('计算值:',loc)
    		G=loc.father.G+loc.cost
    		H=self.getEstimate(loc)
    		F=G+H
    		print("F=%d G=%d H=%d"%(F,G,H))
    		return {'G':G,'H':H,'F':F}
    	def F_Min(self):#搜索open列表中F值最小的点并将其返回,同时判断open列表是否为空,为空则代表搜索失败
    		if len(self.open)<=0:
    			return None
    		t=self.open[0]
    		for i in self.open:
    			if i.F<t.F:
    				t=i
    		return t
    	def getAroundPoint(self,loc):#获取指定点周围所有可通行的点,并将其对应的移动消耗进行赋值。
    		l=[(loc.x,loc.y+1,10),(loc.x+1,loc.y+1,14),(loc.x+1,loc.y,10),(loc.x+1,loc.y-1,14),(loc.x,loc.y-1,10),(loc.x-1,loc.y-1,14),(loc.x-1,loc.y,10),(loc.x-1,loc.y+1,14)]
    		for i in l[::-1]:
    			if i[0]<0 or i[0]>=config.HEIGHT or i[1]<0 or i[1]>=config.WIDTH:
    				l.remove(i)
    		nl=[]
    		for i in l:
    			if self.Map[i[0]][i[1]]==0:
    				nt=point(i[0],i[1])
    				nt.cost=i[2]
    				nl.append(nt)
    		return nl
    
    	def addToOpen(self,l,father):#此次判断的点周围的可通行点加入到open列表中,如此点已经在open列表中则对其进行判断,如果此次路径得到的F值较之之前的F值更小,则将其父节点更新为此次判断的点,同时更新F、G值。
    		for i in l:
    			if i not in self.open:
    				if i not in self.close:
    					i.father=father
    					self.open.append(i)
    					r=self.cal_F(i)
    					i.G=r['G']
    					i.F=r['F']
    			else:
    				tf=i.father
    				i.father=father
    				r=self.cal_F(i)
    				if i.F>r['F']:
    					i.G=r['G']
    					i.F=r['F']
    					# i.father=father
    				else:
    					i.father=tf
    	def getEstimate(self,loc):#H :从点loc移动到终点的预估花费
    		return (abs(loc.x-self.end.x)+abs(loc.y-self.end.y))*10
    	def DisplayPath(self):#在此演示中无意义
    		print('搜索花费的时间:%.2fs.迭代次数%d,路径长度:%d'%(self.useTime,self.count,len(self.result)))
    		if self.result!=None:
    			for i in self.result:
    				self.Map[i.x][i.y]=8
    			for i in self.Map:
    				for j in i:
    					if j==0:
    						print('%s'%'□',end='')
    					elif j==1:
    						print('%s'%'▽',end='')
    					elif j==8:
    						print('%s'%'★',end='')
    				print('')
    		else:
    			print('搜索失败,无可通行路径')
    	def process(self):#使用yield将process方法变成一个生成器,可以逐步的对搜索过程进行处理并返回关键数据
    		while True:
    			self.count+=1
    			tar=self.F_Min()#先获取open列表中F值最低的点tar
    			if tar==None:
    				self.result=None
    				self.count=-1
    				break
    			else:
    				aroundP=self.getAroundPoint(tar)#获取tar周围的可用点列表aroundP
    				self.addToOpen(aroundP,tar)#把aroundP加入到open列表中并更新F值以及设定父节点
    				self.open.remove(tar)#将tar从open列表中移除
    				self.close.append(tar)#已经迭代过的节点tar放入close列表中
    				if self.end in self.open:#判断终点是否已经处于open列表中
    					e=self.end
    					self.result.append(e)
    					while True:
    						e=e.father
    						if e==None:
    							break
    						self.result.append(e)
    					yield (tar,self.open,self.close)
    					break
    
    			# self.repaint()
    			# print('返回')
    			yield (tar,self.open,self.close)
    			time.sleep(5)#暂停
    		self.useTime=time2-time1
    class GameBoard(QMainWindow):#可视化类,pyqt5进行编写。
    	def __init__(self):
    		print('初始化地图...')
    		self.Map=[]
    		for i in range(config.HEIGHT):
    			col=[]
    			for j in range(config.WIDTH):
    				col.append(0)
    			self.Map.append(col)
    		self.startPoint=None
    		self.endPoint=None
    		self.search=None
    		self.centerTimer=None
    		self.yi=None
    		self.special=None
    		self.displayFlush=False
    		super().__init__()
    		print('初始化UI...')
    		self.initUI()
    	def initUI(self):
    		#开始初始化UI部分
    			#创建UI控件
    		self.label_tips=QLabel("<p style='color:green'>使用说明:</p>右键单击格子选定起始点,左键格子选定格子为墙壁或删除墙壁。\n<p style='color:green'>颜色说明:</p>\n黄色代表起点,绿色代表终点,黑色代表墙壁,红色代表待搜索的open列表,灰色代表已搜索过的close列表,蓝色代表当前搜索到的路径",self)
    		self.label_display=QLabel("",self)
    		self.button_start=QPushButton("开始搜索",self)
    		self.button_clearSE=QPushButton("重选起始点",self)
    		self.button_clearWall=QPushButton("清空地图墙壁",self)
    		self.button_saveMap=QPushButton("保存地图",self)
    		self.button_loadMap=QPushButton("加载地图",self)
    
    
    			#设置控件属性
    		self.label_tips.setWordWrap(True)
    		self.label_display.setWordWrap(True)
    			#设置控件样式
    		self.label_display.setStyleSheet("border:1px solid black")
    		self.label_display.setAlignment(Qt.AlignLeft)
    		self.label_display.setAlignment(Qt.AlignTop)
    			#设置控件的尺寸和位置
    		self.label_tips.resize(200,150)
    		self.button_saveMap.resize(80,30)
    		self.button_loadMap.resize(80,30)
    		self.label_display.resize(200,300)
    
    		self.label_tips.move(100+(config.WIDTH-1)*config.blockLength,0)
    		self.label_display.move(100+(config.WIDTH-1)*config.blockLength,400)
    		self.button_start.move(100+(config.WIDTH-1)*config.blockLength,200)
    		self.button_clearSE.move(100+(config.WIDTH-1)*config.blockLength,250)
    		self.button_clearWall.move(100+(config.WIDTH-1)*config.blockLength,300)
    		self.button_saveMap.move(100+(config.WIDTH-1)*config.blockLength,350)
    		self.button_loadMap.move(200+(config.WIDTH-1)*config.blockLength,350)
    			#给控件绑定事件
    		self.button_start.clicked.connect(self.button_StartEvent)
    		self.button_clearSE.clicked.connect(self.button_Clear)
    		self.button_clearWall.clicked.connect(self.button_Clear)
    		self.button_saveMap.clicked.connect(self.button_SaveMap)
    		self.button_loadMap.clicked.connect(self.button_LoadMap)
    		#UI初始化完成
    		self.setGeometry(0, 0, 150+(config.WIDTH*config.blockLength-config.blockLength)+200, 150+(config.HEIGHT*config.blockLength-config.blockLength))
    		self.setMinimumSize(150+(config.WIDTH*config.blockLength-config.blockLength)+200, 150+(config.HEIGHT*config.blockLength-config.blockLength))
    		self.setMaximumSize(150+(config.WIDTH*config.blockLength-config.blockLength)+200, 150+(config.HEIGHT*config.blockLength-config.blockLength))
    		self.setWindowTitle('A*搜索')
    		self.show()
    	def addDisplayText(self,text):
    		if self.displayFlush:
    			self.label_display.setText(text+'\n')
    			self.displayFlush=False
    		else:
    			self.label_display.setText(self.label_display.text()+text+'\n')
    	def mousePressEvent(self,event):
    		x,y=event.x()-50,event.y()-50
    		x=x//config.blockLength
    		y=y//config.blockLength
    		if x>=0 and x<config.WIDTH and y>=0 and y<config.HEIGHT:
    			if event.button()==Qt.LeftButton:
    				if (x,y)!=self.startPoint and (x,y)!=self.endPoint:
    					self.Map[y][x]=(1 if self.Map[y][x]==0 else 0)
    			if event.button()==Qt.RightButton:
    				if self.Map[y][x]==0:
    					if self.startPoint==None:
    						self.startPoint=(x,y)
    						self.addDisplayText('添加了一个起点:(%d,%d)'%(x,y))
    					elif self.endPoint==None and self.startPoint!=(x,y):
    						self.endPoint=(x,y)
    						self.addDisplayText('添加了一个终点:(%d,%d)'%(x,y))
    			self.repaint()
    	def button_StartEvent(self):
    		sender=self.sender()
    		print(sender)
    		if self.startPoint!=None and self.endPoint!=None:
    			if self.centerTimer==None:
    				self.centerTimer=QBasicTimer()
    			self.button_start.setEnabled(False)
    			self.button_clearSE.setEnabled(False)
    			self.button_clearWall.setEnabled(False)
    			self.centerTimer.start(200,self)
    			self.search=A_Search(point(self.startPoint[1],self.startPoint[0]),point(self.endPoint[1],self.endPoint[0]),self.Map)
    			self.yi=self.search.process()
    			self.addDisplayText('开始进行搜索')
    	def button_SaveMap(self):
    		with open('map.txt','w') as f:
    			f.write(json.dumps(self.Map))
    			self.addDisplayText('地图保存成功-->map.txt')
    		# else:
    			# self.addDisplayText('地图保存失败')
    	def button_LoadMap(self):
    		try:
    			with open('map.txt','r') as f:
    				self.Map=json.loads(f.read())
    				config.HEIGHT=len(self.Map)
    				config.WIDTH=len(self.Map[0])
    				self.addDisplayText('地图加载成功')
    				self.repaint()
    		except Exception as e:
    			print('失败',e,type(e))
    			if type(e)==FileNotFoundError:
    				self.addDisplayText('地图加载失败:地图文件不存在')
    			elif type(e)==json.decoder.JSONDecodeError:
    				self.addDisplayText('地图加载失败:错误的地图文件')
    	def button_Clear(self):
    		sender=self.sender()
    		print(self.button_clearSE,type(self.button_clearSE))
    		if sender==self.button_clearSE:
    			self.startPoint=None
    			self.endPoint=None
    			self.repaint()
    			self.addDisplayText('清空起始点')
    		elif sender==self.button_clearWall:
    			for i in range(len(self.Map)):
    				for j in range(len(self.Map[i])):
    					self.Map[i][j]=0
    			self.repaint()
    			self.addDisplayText('清空所有墙壁')
    	def paintEvent(self, event):
    		qp = QPainter()
    		qp.begin(self)
    		self.drawBoard(event,qp)
    		qp.end()
    	def drawBoard(self, event, qp):
    	    self.drawMap(qp)
    	def drawMap(self,qp):#画面绘制方法,每次地图有所改动都将重绘
    		time1=time.time()
    		if self.search!=None:
    			if self.special!=None:
    				e=self.special[0]
    				path=[e]
    				while True:
    					e=e.father
    					if e!=None:
    						path.append(e)
    					else:
    						break
    			else:
    				path=None
    			pen=QPen(QColor(0,0,0),1,Qt.SolidLine)
    			qp.setPen(pen)
    			for i in range(len(self.Map)):
    				for j in range(len(self.Map[i])):
    					wordTag=False
    					if i==self.search.start.x and j==self.search.start.y:
    						qp.setBrush(QColor(255,255,0))
    					elif i==self.search.end.x and j==self.search.end.y:
    						qp.setBrush(QColor(100,200,50))
    					else:
    						if self.Map[i][j]==0:
    							tagx=True
    							if path:
    								for k in path:
    									if k.x==i and k.y==j:
    										tagx=False
    										qp.setBrush(QColor(0,100,255))
    							if tagx:
    								if self.special!=None:
    									if i==self.special[0].x and j==self.special[0].y:
    										qp.setBrush(QColor(0,255,0))
    									else:
    										tag=True
    										for k in self.special[1]:
    											if k.x==i and k.y==j:
    												tag=False
    												wordTag=True
    												word=str(k.F)
    
    												qp.setBrush(QColor(150,0,0))
    												break
    											else:
    												qp.setBrush(QColor(220,220,220))
    										if tag:
    											for k in self.special[2]:
    												if k.x==i and k.y==j:
    													qp.setBrush(QColor(150,150,150))
    													break
    												else:
    													qp.setBrush(QColor(220,220,220))
    								else:
    									qp.setBrush(QColor(220,220,220))
    						elif self.Map[i][j]==1:
    							qp.setBrush(QColor(0,0,0))
    						else:
    							qp.setBrush(QColor(255,0,0))
    					qp.drawRect(50+j*config.blockLength,50+i*config.blockLength,config.blockLength,config.blockLength)
    					if wordTag:
    						qp.setFont(QFont('楷体',5,QFont.Light))
    						qp.drawText(50+10+j*config.blockLength,50+10+i*config.blockLength,word)
    						wordTag=False
    		#time.sleep(20)
    		else:
    			for i in range(len(self.Map)):
    				for j in range(len(self.Map[i])):
    					if (j,i)==self.startPoint:
    						qp.setBrush(QColor(255,255,0))
    					elif (j,i)==self.endPoint:
    						qp.setBrush(QColor(100,200,50))
    					else:
    						if self.Map[i][j]==0:
    							qp.setBrush(QColor(220,220,220))
    						elif self.Map[i][j]==1:
    							qp.setBrush(QColor(0,0,0))
    						else:
    							qp.setBrush(QColor(255,0,0))
    
    					qp.drawRect(50+j*config.blockLength,50+i*config.blockLength,config.blockLength,config.blockLength)
    		time2=time.time()
    	#time.sleep(20)
    		# print('绘制时间:',time2-time1)
    	def timerEvent(self,e):
    		try:
    			data=next(self.yi)
    		except Exception as e:
    			self.addDisplayText('搜索结束:')
    			print('搜索结束!')
    			if self.search.result==None:
    				self.addDisplayText('未找到可行路径')
    				print('搜索结束!')
    			else:
    				self.addDisplayText('总计搜索节点数:%d'%self.search.count)
    				self.addDisplayText('最终路径长度:%d'%len(self.search.result))
    			self.centerTimer.stop()
    			self.search=None
    			self.yi=None
    			self.special=None
    			point.clear()
    			self.button_start.setEnabled(True)
    			self.button_clearSE.setEnabled(True)
    			self.button_clearWall.setEnabled(True)
    			self.displayFlush=True
    		else:
    			self.special=data
    			self.repaint()
    if __name__ == '__main__':
    	app = QApplication(sys.argv)
    	ex = GameBoard()
    	sys.exit(app.exec_())
    
    

    注意:代码运行可以设置动态遍历的时候暂停时间(大概在145行的time.sleep(5)语句)

    运行结果 

    输出每次计算的每个点的F和父结点,直接看图吧!

    详细列表

    初始化地图...
    初始化UI...
    <PyQt5.QtWidgets.QPushButton object at 0x0000017CC699AC18>
    计算值: (2,3)[F=0,G=0,cost=10][father:((2, 2))]
    F=40 G=10 H=30
    计算值: (3,3)[F=0,G=0,cost=14][father:((2, 2))]
    F=54 G=14 H=40
    计算值: (3,2)[F=0,G=0,cost=10][father:((2, 2))]
    F=60 G=10 H=50
    计算值: (3,1)[F=0,G=0,cost=14][father:((2, 2))]
    F=74 G=14 H=60
    计算值: (2,1)[F=0,G=0,cost=10][father:((2, 2))]
    F=60 G=10 H=50
    计算值: (1,1)[F=0,G=0,cost=14][father:((2, 2))]
    F=74 G=14 H=60
    计算值: (1,2)[F=0,G=0,cost=10][father:((2, 2))]
    F=60 G=10 H=50
    计算值: (1,3)[F=0,G=0,cost=14][father:((2, 2))]
    F=54 G=14 H=40
    计算值: (3,3)[F=54,G=14,cost=10][father:((2, 3))]
    F=60 G=20 H=40
    计算值: (3,2)[F=60,G=10,cost=14][father:((2, 3))]
    F=74 G=24 H=50
    计算值: (1,2)[F=60,G=10,cost=14][father:((2, 3))]
    F=74 G=24 H=50
    计算值: (1,3)[F=54,G=14,cost=10][father:((2, 3))]
    F=60 G=20 H=40
    计算值: (4,4)[F=0,G=0,cost=14][father:((3, 3))]
    F=68 G=28 H=40
    计算值: (4,3)[F=0,G=0,cost=10][father:((3, 3))]
    F=74 G=24 H=50
    计算值: (4,2)[F=0,G=0,cost=14][father:((3, 3))]
    F=88 G=28 H=60
    计算值: (3,2)[F=60,G=10,cost=10][father:((3, 3))]
    F=74 G=24 H=50
    计算值: (1,2)[F=60,G=10,cost=10][father:((1, 3))]
    F=74 G=24 H=50
    计算值: (0,2)[F=0,G=0,cost=14][father:((1, 3))]
    F=88 G=28 H=60
    计算值: (0,3)[F=0,G=0,cost=10][father:((1, 3))]
    F=74 G=24 H=50
    计算值: (0,4)[F=0,G=0,cost=14][father:((1, 3))]
    F=68 G=28 H=40
    计算值: (4,3)[F=74,G=24,cost=14][father:((3, 2))]
    F=74 G=24 H=50
    计算值: (4,2)[F=88,G=28,cost=10][father:((3, 2))]
    F=80 G=20 H=60
    计算值: (4,1)[F=0,G=0,cost=14][father:((3, 2))]
    F=94 G=24 H=70
    计算值: (3,1)[F=74,G=14,cost=10][father:((3, 2))]
    F=80 G=20 H=60
    计算值: (2,1)[F=60,G=10,cost=14][father:((3, 2))]
    F=74 G=24 H=50
    计算值: (3,1)[F=74,G=14,cost=10][father:((2, 1))]
    F=80 G=20 H=60
    计算值: (3,0)[F=0,G=0,cost=14][father:((2, 1))]
    F=94 G=24 H=70
    计算值: (2,0)[F=0,G=0,cost=10][father:((2, 1))]
    F=80 G=20 H=60
    计算值: (1,0)[F=0,G=0,cost=14][father:((2, 1))]
    F=94 G=24 H=70
    计算值: (1,1)[F=74,G=14,cost=10][father:((2, 1))]
    F=80 G=20 H=60
    计算值: (1,2)[F=60,G=10,cost=14][father:((2, 1))]
    F=74 G=24 H=50
    计算值: (1,1)[F=74,G=14,cost=10][father:((1, 2))]
    F=80 G=20 H=60
    计算值: (0,1)[F=0,G=0,cost=14][father:((1, 2))]
    F=94 G=24 H=70
    计算值: (0,2)[F=88,G=28,cost=10][father:((1, 2))]
    F=80 G=20 H=60
    计算值: (0,3)[F=74,G=24,cost=14][father:((1, 2))]
    F=74 G=24 H=50
    计算值: (4,5)[F=0,G=0,cost=10][father:((4, 4))]
    F=68 G=38 H=30
    计算值: (5,5)[F=0,G=0,cost=14][father:((4, 4))]
    F=82 G=42 H=40
    计算值: (5,4)[F=0,G=0,cost=10][father:((4, 4))]
    F=88 G=38 H=50
    计算值: (5,3)[F=0,G=0,cost=14][father:((4, 4))]
    F=102 G=42 H=60
    计算值: (4,3)[F=74,G=24,cost=10][father:((4, 4))]
    F=88 G=38 H=50
    计算值: (3,5)[F=0,G=0,cost=14][father:((4, 4))]
    F=62 G=42 H=20
    计算值: (3,6)[F=0,G=0,cost=10][father:((3, 5))]
    F=62 G=52 H=10
    计算值: (4,6)[F=0,G=0,cost=14][father:((3, 5))]
    F=76 G=56 H=20
    计算值: (4,5)[F=68,G=38,cost=10][father:((3, 5))]
    F=82 G=52 H=30
    计算值: (2,5)[F=0,G=0,cost=10][father:((3, 5))]
    F=62 G=52 H=10
    计算值: (2,6)[F=0,G=0,cost=14][father:((3, 5))]
    F=56 G=56 H=0
    搜索结束!

    可执行文件

    已经将程序打包成exe可执行文件,点击即可用,不需要py环境。

    链接:https://pan.baidu.com/s/1UqvI5vtoxwXu0PPUFHfxdg 
    提取码:fwwm 
    复制这段内容后打开百度网盘手机App,操作更方便哦

    拓展

    Dijkstra算法和A*算法的比较

    Dijkstra算法和A*都是最短路径问题的常用算法,下面就对这两种算法的特点进行一下比较。
    1.Dijkstra算法计算源点到其他所有点的最短路径长度,A*关注点到点的最短路径(包括具体路径)。
    2.Dijkstra算法建立在较为抽象的图论层面,A*算法可以更轻松地用在诸如游戏地图寻路中。
    3.Dijkstra算法的实质是广度优先搜索,是一种发散式的搜索,所以空间复杂度和时间复杂度都比较高。对路径上的当前点,A*算法不但记录其到源点的代价,还计算当前点到目标点的期望代价,是一种启发式算法,也可以认为是一种深度优先的算法。
    4.由第一点,当目标点很多时,A*算法会带入大量重复数据和复杂的估价函数,所以如果不要求获得具体路径而只比较路径长度时,Dijkstra算法会成为更好的选择。

    参考:https://blog.csdn.net/weixin_42382758/article/details/88840581

    展开全文
  • A*算法详解(个人认为最透彻的一个)

    万次阅读 多人点赞 2019-04-18 16:47:21
    A* 寻路算法 原文地址: http://www.gamedev.net/reference/articles/article2003.asp 概述 虽然掌握了 A算法的人认为它容易,但是对于初学者来说, A算法还是很复杂的。 搜索区域...

    A* 寻路算法

    原文地址: http://www.gamedev.net/reference/articles/article2003.asp

    概述

    虽然掌握了 A* 算法的人认为它容易,但是对于初学者来说, A* 算法还是很复杂的。

    搜索区域(The Search Area)

    我们假设某人要从 A 点移动到 B 点,但是这两点之间被一堵墙隔开。如图 1 ,绿色是 A ,红色是 B ,中间蓝色是墙。

    image001.jpg

    图 1

    你应该注意到了,我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步,简化搜索区域,就像我们这里做的一样。这个特殊的方法把我们的搜索区域简化为了 2 维数组。数组的每一项代表一个格子,它的状态就是可走 (walkalbe) 和不可走 (unwalkable) 。通过计算出从 A 到 B需要走过哪些方格,就找到了路径。一旦路径找到了,人物便从一个方格的中心移动到另一个方格的中心,直至到达目的地。

    方格的中心点我们成为“节点 (nodes) ”。如果你读过其他关于 A* 寻路算法的文章,你会发现人们常常都在讨论节点。为什么不直接描述为方格呢?因为我们有可能把搜索区域划为为其他多变形而不是正方形,例如可以是六边形,矩形,甚至可以是任意多变形。而节点可以放在任意多边形里面,可以放在多变形的中心,也可以放在多边形的边上。我们使用这个系统,因为它最简单。

    开始搜索(Starting the Search)

    一旦我们把搜寻区域简化为一组可以量化的节点后,就像上面做的一样,我们下一步要做的便是查找最短路径。在 A* 中,我们从起点开始,检查其相邻的方格,然后向四周扩展,直至找到目标。

    我们这样开始我们的寻路旅途:

    1.       从起点 A 开始,并把它就加入到一个由方格组成的 open list( 开放列表 ) 中。这个 open list 有点像是一个购物单。当然现在 open list 里只有一项,它就是起点 A ,后面会慢慢加入更多的项。 Open list 里的格子是路径可能会是沿途经过的,也有可能不经过。基本上 open list 是一个待检查的方格列表。

    2.       查看与起点 A 相邻的方格 ( 忽略其中墙壁所占领的方格,河流所占领的方格及其他非法地形占领的方格 ) ,把其中可走的 (walkable) 或可到达的 (reachable) 方格也加入到 open list 中。把起点 A 设置为这些方格的父亲 (parent node 或 parent square) 。当我们在追踪路径时,这些父节点的内容是很重要的。稍后解释。

    3.       把 A 从 open list 中移除,加入到 close list( 封闭列表 ) 中, close list 中的每个方格都是现在不需要再关注的。

    如下图所示,深绿色的方格为起点,它的外框是亮蓝色,表示该方格被加入到了 close list 。与它相邻的黑色方格是需要被检查的,他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点,这里是起点 A 。

    image002.jpg

    图 2 。

    下一步,我们需要从 open list 中选一个与起点 A 相邻的方格,按下面描述的一样或多或少的重复前面的步骤。但是到底选择哪个方格好呢?具有最小 F 值的那个。

     

    路径排序(Path Sorting)

    计算出组成路径的方格的关键是下面这个等式:

    F = G + H

    这里,

    G = 从起点 A 移动到指定方格的移动代价,沿着到达该方格而生成的路径。

    H = 从指定的方格移动到终点 B 的估算成本。这个通常被称为试探法,有点让人混淆。为什么这么叫呢,因为这是个猜测。直到我们找到了路径我们才会知道真正的距离,因为途中有各种各样的东西 ( 比如墙壁,水等 ) 。本教程将教你一种计算 H 的方法,你也可以在网上找到其他方法。

    我们的路径是这么产生的:反复遍历 open list ,选择 F 值最小的方格。这个过程稍后详细描述。我们还是先看看怎么去计算上面的等式。

    如上所述, G 是从起点A移动到指定方格的移动代价。在本例中,横向和纵向的移动代价为 10 ,对角线的移动代价为 14 。之所以使用这些数据,是因为实际的对角移动距离是 2 的平方根,或者是近似的 1.414 倍的横向或纵向移动代价。使用 10 和 14 就是为了简单起见。比例是对的,我们避免了开放和小数的计算。这并不是我们没有这个能力或是不喜欢数学。使用这些数字也可以使计算机更快。稍后你便会发现,如果不使用这些技巧,寻路算法将很慢。

     

    既然我们是沿着到达指定方格的路径来计算 G 值,那么计算出该方格的 G 值的方法就是找出其父亲的 G 值,然后按父亲是直线方向还是斜线方向加上 10 或 14 。随着我们离开起点而得到更多的方格,这个方法会变得更加明朗。

     

    有很多方法可以估算 H 值。这里我们使用 Manhattan 方法,计算从当前方格横向或纵向移动到达目标所经过的方格数,忽略对角移动,然后把总数乘以 10 。之所以叫做 Manhattan 方法,是因为这很像统计从一个地点到另一个地点所穿过的街区数,而你不能斜向穿过街区。重要的是,计算 H 是,要忽略路径中的障碍物。这是对剩余距离的估算值,而不是实际值,因此才称为试探法。

     

    把 G 和 H 相加便得到 F 。我们第一步的结果如下图所示。每个方格都标上了 F , G , H 的值,就像起点右边的方格那样,左上角是 F ,左下角是 G ,右下角是 H 。

    image003.jpg

    图 3

    好,现在让我们看看其中的一些方格。在标有字母的方格, G = 10 。这是因为水平方向从起点到那里只有一个方格的距离。与起点直接相邻的上方,下方,左方的方格的 G 值都是 10 ,对角线的方格 G 值都是 14 。

     

    H 值通过估算起点于终点 ( 红色方格 ) 的 Manhattan 距离得到,仅作横向和纵向移动,并且忽略沿途的墙壁。使用这种方式,起点右边的方格到终点有 3 个方格的距离,因此 H = 30 。这个方格上方的方格到终点有 4 个方格的距离 ( 注意只计算横向和纵向距离 ) ,因此 H = 40 。对于其他的方格,你可以用同样的方法知道 H 值是如何得来的。

     

    每个方格的 F 值,再说一次,直接把 G 值和 H 值相加就可以了。

     

    继续搜索(Continuing the Search)

    为了继续搜索,我们从 open list 中选择 F 值最小的 ( 方格 ) 节点,然后对所选择的方格作如下操作:

    4.       把它从 open list 里取出,放到 close list 中。

    5.       检查所有与它相邻的方格,忽略其中在 close list 中或是不可走 (unwalkable) 的方格 ( 比如墙,水,或是其他非法地形 ) ,如果方格不在open lsit 中,则把它们加入到 open list 中。

    把我们选定的方格设置为这些新加入的方格的父亲。

    6.       如果某个相邻的方格已经在 open list 中,则检查这条路径是否更优,也就是说经由当前方格 ( 我们选中的方格 ) 到达那个方格是否具有更小的 G 值。如果没有,不做任何操作。

    相反,如果 G 值更小,则把那个方格的父亲设为当前方格 ( 我们选中的方格 ) ,然后重新计算那个方格的 F 值和 G 值。如果你还是很混淆,请参考下图。

    image004.jpg

    图 4

    Ok ,让我们看看它是怎么工作的。在我们最初的 9 个方格中,还有 8 个在 open list 中,起点被放入了 close list 中。在这些方格中,起点右边的格子的 F 值 40 最小,因此我们选择这个方格作为下一个要处理的方格。它的外框用蓝线打亮。

     

    首先,我们把它从 open list 移到 close list 中 ( 这就是为什么用蓝线打亮的原因了 ) 。然后我们检查与它相邻的方格。它右边的方格是墙壁,我们忽略。它左边的方格是起点,在 close list 中,我们也忽略。其他 4 个相邻的方格均在 open list 中,我们需要检查经由这个方格到达那里的路径是否更好,使用 G 值来判定。让我们看看上面的方格。它现在的 G 值为 14 。如果我们经由当前方格到达那里, G 值将会为 20(其中 10 为到达当前方格的 G 值,此外还要加上从当前方格纵向移动到上面方格的 G 值 10) 。显然 20 比 14 大,因此这不是最优的路径。如果你看图你就会明白。直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。

     

    当把 4 个已经在 open list 中的相邻方格都检查后,没有发现经由当前方格的更好路径,因此我们不做任何改变。现在我们已经检查了当前方格的所有相邻的方格,并也对他们作了处理,是时候选择下一个待处理的方格了。

     

    因此再次遍历我们的 open list ,现在它只有 7 个方格了,我们需要选择 F 值最小的那个。有趣的是,这次有两个方格的 F 值都 54 ,选哪个呢?没什么关系。从速度上考虑,选择最后加入 open list 的方格更快。这导致了在寻路过程中,当靠近目标时,优先使用新找到的方格的偏好。但是这并不重要。 ( 对相同数据的不同对待,导致两中版本的 A* 找到等长的不同路径 ) 。

     

    我们选择起点右下方的方格,如下图所示。

    image005.jpg

    图 5

     

    这次,当我们检查相邻的方格时,我们发现它右边的方格是墙,忽略之。上面的也一样。

    我们把墙下面的一格也忽略掉。为什么?因为如果不穿越墙角的话,你不能直接从当前方格移动到那个方格。你需要先往下走,然后再移动到那个方格,这样来绕过墙角。 ( 注意:穿越墙角的规则是可选的,依赖于你的节点是怎么放置的 )

     

    这样还剩下 5 个相邻的方格。当前方格下面的 2 个方格还没有加入 open list ,所以把它们加入,同时把当前方格设为他们的父亲。在剩下的3 个方格中,有 2 个已经在 close list 中 ( 一个是起点,一个是当前方格上面的方格,外框被加亮的 ) ,我们忽略它们。最后一个方格,也就是当前方格左边的方格,我们检查经由当前方格到达那里是否具有更小的 G 值。没有。因此我们准备从 open list 中选择下一个待处理的方格。

     

    不断重复这个过程,直到把终点也加入到了 open list 中,此时如下图所示。

    image006.jpg

    图 6

     

    注意,在起点下面 2 格的方格的父亲已经与前面不同了。之前它的 G 值是 28 并且指向它右上方的方格。现在它的 G 值为 20 ,并且指向它正上方的方格。这在寻路过程中的某处发生,使用新路径时 G 值经过检查并且变得更低,因此父节点被重新设置, G 和 F 值被重新计算。尽管这一变化在本例中并不重要,但是在很多场合中,这种变化会导致寻路结果的巨大变化。

     

    那么我们怎么样去确定实际路径呢?很简单,从终点开始,按着箭头向父节点移动,这样你就被带回到了起点,这就是你的路径。如下图所示。从起点 A 移动到终点 B 就是简单从路径上的一个方格的中心移动到另一个方格的中心,直至目标。就是这么简单!

    image007.jpg

    图 7

     

    A*算法总结(Summary of the A* Method)

    Ok ,现在你已经看完了整个的介绍,现在我们把所有步骤放在一起:

    1.         把起点加入 open list 。

    2.         重复如下过程:

    a.         遍历 open list ,查找 F 值最小的节点,把它作为当前要处理的节点。

    b.         把这个节点移到 close list 。

    c.         对当前方格的 8 个相邻方格的每一个方格?

    ◆     如果它是不可抵达的或者它在 close list 中,忽略它。否则,做如下操作。

    ◆     如果它不在 open list 中,把它加入 open list ,并且把当前方格设置为它的父亲,记录该方格的 F , G 和 H 值。

    ◆     如果它已经在 open list 中,检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好,用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样,把它的父亲设置为当前方格,并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话,改变后你可能需要重新排序。

    d.         停止,当你

    ◆     把终点加入到了 open list 中,此时路径已经找到了,或者

    ◆     查找终点失败,并且 open list 是空的,此时没有路径。

    3.         保存路径。从终点开始,每个方格沿着父节点移动直至起点,这就是你的路径。

     

     

    题外话(Small Rant)

    请原谅我的离题,当你在网上或论坛上看到各种关于 A* 算法的讨论时,你偶尔会发现一些 A* 的代码,实际上他们不是。要使用 A* ,你必须包含上面讨论的所有元素 ---- 尤其是 open list , close list 和路径代价 G , H 和 F 。也有很多其他的寻路算法,这些算法并不是 A* 算法, A* 被认为是最好的。在本文末尾引用的一些文章中 Bryan Stout 讨论了他们的一部分,包括他们的优缺点。在某些时候你可以二中择一,但你必须明白自己在做什么。 Ok ,不废话了。回到文章。

     

    实现的注解(Notes on Implemetation)

    现在你已经明白了基本方法,这里是你在写自己的程序是需要考虑的一些额外的东西。下面的材料引用了一些我用 C++ 和 Basic 写的程序,但是对其他语言同样有效。

     

    1.    维护 Open List :这是 A* 中最重要的部分。每次你访问 Open list ,你都要找出具有最小    F 值的方格。有几种做法可以做到这个。你可以随意保存路径元素,当你需要找到具     有最小 F 值的方格时,遍历整个 open list 。这个很简单,但对于很长的路径会很慢。这个方法可以通过维护一个排好序的表来改进,每次当你需要找到具有最小 F 值的方格时,仅取出表的第一项即可。我写程序时,这是我用的第一个方法。

          

           对于小地图,这可以很好的工作,但这不是最快的方案。追求速度的 A* 程序员使用了叫做二叉堆的东西,我的程序里也用了这个。以我的经验,这种方法在多数场合下会快 2—3 倍,对于更长的路径速度成几何级数增长 (10 倍甚至更快 ) 。如果你想更多的了解二叉堆,请阅读Using Binary Heaps in A* Pathfinding 。

    2.       其他单位:如果你碰巧很仔细的看了我的程序,你会注意到我完全忽略了其他单位。我的寻路者实际上可以互相穿越。这取决于游戏,也许可以,也许不可以。如果你想考虑其他单位,并想使他们移动时绕过彼此,我建议你的寻路程序忽略它们,再写一些新的程序来判断两个单位是否会发生碰撞。如果发生碰撞,你可以产生一个新的路径,或者是使用一些标准的运动法则(比如永远向右移动,等等)直至障碍物不在途中,然后产生一个新的路径。为什么在计算初始路径是不包括其他单位呢?因为其他单位是可以动的,当你到达的时候它们可能不在自己的位置上。这可以产生一些怪异的结果,一个单位突然转向来避免和一个已不存在的单位碰撞,在它的路径计算出来后和穿越它路径的那些单位碰撞了。

    在寻路代码中忽略其他单位,意味着你必须写另一份代码来处理碰撞。这是游戏的细节,所以我把解决方案留给你。本文末尾引用的 Bryan Stout's 的文章中的几种解决方案非常值得了解。

    3.       一些速度方面的提示:如果你在开发自己的 A* 程序或者是改编我写的程序,最后你会发现寻路占用了大量的 CPU 时间,尤其是当你有相当多的寻路者和一块很大的地图时。如果你阅读过网上的资料,你会发现就算是开发星际争霸,帝国时代的专家也是这样。如果你发现事情由于寻路而变慢了,这里有些主意很不错:

    ◆     使用小地图或者更少的寻路者。

    ◆     千万不要同时给多个寻路者寻路。取而代之的是把它们放入队列中,分散到几个游戏周期中。如果你的游戏以每秒 40 周期的速度运行,没人能察觉到。但是如果同时有大量的寻路者在寻路的话,他们会马上就发现游戏慢下来了。

    ◆     考虑在地图中使用更大的方格。这减少了寻路时需要搜索的方格数量。如果你是有雄心的话,你可以设计多套寻路方案,根据路径的长度而使用在不同场合。这也是专业人士的做法,对长路径使用大方格,当你接近目标时使用小方格。如果你对这个有兴趣,请看 Two-Tiered A* Pathfinding 。

    ◆     对于很长的路径,考虑使用路径点系统,或者可以预先计算路径并加入游戏中。

    ◆     预先处理你的地图,指出哪些区域是不可到达的。这些区域称为“孤岛”。实际上,他们可以是岛屿,或者是被墙壁等包围而不可到达的任意区域。 A* 的下限是,你告诉他搜寻通往哪些区域的路径时,他会搜索整个地图,直到所有可以抵达的方格都通过 open list 或 close list 得到了处理。这会浪费大量的 CPU 时间。这可以通过预先设定不可到达的区域来解决。在某种数组中记录这些信息,在寻路前检查它。在我的 Blitz 版程序中,我写了个地图预处理程序来完成这个。它可以提前识别寻路算法会忽略的死路径,这又进一步提高了速度。

    4.    不同的地形损耗:在这个教程和我的程序中,地形只有 2 种:可抵达的和不可抵达        的。但是如果你有些可抵达的地形,移动代价会更高些,沼泽,山丘,地牢的楼梯

           等都是可抵达的地形,但是移动代价比平地就要高。类似的,道路的移动代价就比        它周围的地形低。

    在你计算给定方格的 G 值时加上地形的代价就很容易解决了这个问题。简单的给这些方格加上一些额外的代价就可以了。 A* 算法用来查找代价最低的路径,应该很容易处理这些。在我的简单例子中,地形只有可达和不可达两种, A* 会搜寻最短和最直接的路径。但是在有地形代价的环境中,代价最低的的路径可能会很长。

    就像沿着公路绕过沼泽而不是直接穿越它。

    另一个需要考虑的是专家所谓的“ influence Mapping ”,就像上面描述的可变成本地形一样,你可以创建一个额外的计分系统,把它应用到寻路的 AI 中。假设你有这样一张地图,地图上由个通道穿过山丘,有大批的寻路者要通过这个通道,电脑每次产生一个通过那个通道的路径都会变得很拥挤。如果需要,你可以产生一个 influence map ,它惩罚那些会发生大屠杀的方格。这会让电脑选择更安全的路径,也可以帮助它避免因为路径短(当然也更危险)而持续把队伍或寻路者送往某一特定路径。

    5.    维护未探测的区域:你玩 PC 游戏的时候是否发现电脑总是能精确的选择路径,甚至地图都未被探测。对于游戏来说,寻路过于精确反而不真实。幸运的是,这个问题很容易修正。答案就是为每个玩家和电脑(每个玩家,不是每个单位 --- 那会浪费很多内存)创建一个独立的 knownWalkability 数组。每个数组包含了玩家已经探测的区域的信息,和假设是可到达的其他区域,直到被证实。使用这种方法,单位会在路的死端徘徊,并会做出错误的选择,直到在它周围找到了路径。地图一旦被探测了,寻路又向平常一样工作。

    6.    平滑路径: A* 自动给你花费最小的,最短的路径,但它不会自动给你最平滑的路径。看看我们的例子所找到的路径(图 7 )。在这条路径上,第一步在起点的右下方,如果第一步在起点的正下方是不是路径会更平滑呢?

           有几个方法解决这个问题。在你计算路径时,你可以惩罚那些改变方向的方格,把它的 G 值增加一个额外的开销。另一种选择是,你可以遍历你生成的路径,查找那些用相邻的方格替代会使路径更平滑的地方。要了解更多,请看 Toward More Realistic Pathfinding 。

    7.    非方形搜索区域:在我们的例子中,我们使用都是 2D 的方形的区域。你可以使用不规则的区域。想想冒险游戏中的那些国家,你可以设计一个像那样的寻路关卡。你需要建立一张表格来保存国家相邻关系,以及从一个国家移动到另一个国家的 G 值。你还需要一个方法了估算 H 值。其他的都可以向上面的例子一样处理。当你向 open list 添加新项时,不是使用相邻的方格,而是查看表里相邻的国家。

    类似的,你可以为一张固定地形的地图的路径建立路径点系统。路径点通常是道路或地牢通道的转折点。作为游戏设计者,你可以预先设定路径点。如果两个路径点的连线没有障碍物的话它们被视为相邻的。在冒险游戏的例子中,你可以保存这些相邻信息在某种表中,当 open list 增加新项时使用。然后记录 G 值(可能用两个结点间的直线距离)和 H 值(可能使用从节点到目标的直线距离)。其它的都想往常一样处理。

    进一步阅读(Further Reading)

    Ok ,现在你已经对 A* 有了个基本的了解,同时也认识了一些高级的主题。我强烈建议你看看我的代码,压缩包里包含了 2 个版本的实现,一个是 C++ ,另一个是 Blitz Basic 。 2 个版本都有注释,你以该可以很容易就看懂。下面是链接:

    Sample Code: A* Pathfinder (2D) Version 1.71 。

     

    如果你不会使用 C++ 或是 BlitzBasic ,在 C++ 版本下你可以找到两个 exe 文件。 BlitzBasic 版本必须去网站 Blitz Basic 下载 BlitzBasic 3D 的免费 Demo 才能运行。 在这里 here 你可以看到一个 Ben O'Neill 的 A* 在线验证实例。

     

    你应该阅读下面这几个站点的文章。在你读完本教程后你可以更容易理解他们。

    Amit's A* Pages : Amit Patel 的这篇文章被广泛引用,但是如果你没有阅读本教程的话,你可能会感到很迷惑。尤其是你可以看到 Amit Patel自己的一些想法。

    Smart Moves: Intelligent Path Finding : Bryan Stout 的这篇需要去 Gamasutra.com 注册才能阅读。 Bryan 用 Delphi 写的程序帮助我学习了A* ,同时给了我一些我的程序中的一些灵感。他也阐述了 A* 的其他选择。

    Terrain Analysis : Dave Pottinger 一篇非常高阶的,有吸引力的文章。他是 Ensemble Studios 的一名专家。这个家伙调整了游戏帝国时代和王者时代。不要期望能够读懂这里的每一样东西,但是这是一篇能给你一些不错的主意的很有吸引力的文章。它讨论了包 mip-mapping ,

    influence mapping ,和其他高阶 AI 寻路主题。他的 flood filling 给了我在处理死路径 ”dead ends” 和孤岛 ”island” 时的灵感。这包含在我的 Blitz版本的程序里。

     

    下面的一些站点也值得去看看:

    ·                     aiGuru: Pathfinding

    ·                     Game AI Resource: Pathfinding

    ·                     GameDev.net: Pathfinding 


    谢谢。

    展开全文
  • A*算法详解(讲的一级棒 )

    万次阅读 多人点赞 2018-08-23 16:03:28
    虽然掌握了 A* 算法的人认为它容易,但是对于初学者来说, A* 算法还是很复杂的。 搜索区域(The Search Area) 我们假设某人要从 A 点移动到 B 点,但是这两点之间被一堵墙隔开。如图 1 ,绿色是 A ,红色是 B ,...

    转自:https://blog.csdn.net/hitwhylz/article/details/23089415

    概述

    虽然掌握了 A* 算法的人认为它容易,但是对于初学者来说, A* 算法还是很复杂的。

    搜索区域(The Search Area)

    我们假设某人要从 A 点移动到 B 点,但是这两点之间被一堵墙隔开。如图 1 ,绿色是 A ,红色是 B ,中间蓝色是墙。
    这里写图片描述
    图 1

    你应该注意到了,我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步,简化搜索区域,就像我们这里做的一样。这个特殊的方法把我们的搜索区域简化为了 2 维数组。数组的每一项代表一个格子,它的状态就是可走 (walkalbe) 和不可走 (unwalkable) 。通过计算出从 A 到 B需要走过哪些方格,就找到了路径。一旦路径找到了,人物便从一个方格的中心移动到另一个方格的中心,直至到达目的地。

    方格的中心点我们成为“节点 (nodes) ”。如果你读过其他关于 A* 寻路算法的文章,你会发现人们常常都在讨论节点。为什么不直接描述为方格呢?因为我们有可能把搜索区域划为为其他多变形而不是正方形,例如可以是六边形,矩形,甚至可以是任意多变形。而节点可以放在任意多边形里面,可以放在多变形的中心,也可以放在多边形的边上。我们使用这个系统,因为它最简单。

    一旦我们把搜寻区域简化为一组可以量化的节点后,就像上面做的一样,我们下一步要做的便是查找最短路径。在 A* 中,我们从起点开始,检查其相邻的方格,然后向四周扩展,直至找到目标。

    我们这样开始我们的寻路旅途:

    1. 从起点 A 开始,并把它就加入到一个由方格组成的 open list( 开放列表 ) 中。这个 open list 有点像是一个购物单。当然现在 open list 里只有一项,它就是起点 A ,后面会慢慢加入更多的项。 Open list 里的格子是路径可能会是沿途经过的,也有可能不经过。基本上 open list 是一个待检查的方格列表。

    2. 查看与起点 A 相邻的方格 ( 忽略其中墙壁所占领的方格,河流所占领的方格及其他非法地形占领的方格 ) ,把其中可走的 (walkable) 或可到达的 (reachable) 方格也加入到 open list 中。把起点 A 设置为这些方格的父亲 (parent node 或 parent square) 。当我们在追踪路径时,这些父节点的内容是很重要的。稍后解释。

    3. 把 A 从 open list 中移除,加入到 close list( 封闭列表 ) 中, close list 中的每个方格都是现在不需要再关注的。

    如下图所示,深绿色的方格为起点,它的外框是亮蓝色,表示该方格被加入到了 close list 。与它相邻的黑色方格是需要被检查的,他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点,这里是起点 A 。
    这里写图片描述
    图 2 。

    下一步,我们需要从 open list 中选一个与起点 A 相邻的方格,按下面描述的一样或多或少的重复前面的步骤。但是到底选择哪个方格好呢?具有最小 F 值的那个。

    路径排序(Path Sorting)

    计算出组成路径的方格的关键是下面这个等式:

    F = G + H

    这里,

    G = 从起点 A 移动到指定方格的移动代价,沿着到达该方格而生成的路径。

    H = 从指定的方格移动到终点 B 的估算成本。这个通常被称为试探法,有点让人混淆。为什么这么叫呢,因为这是个猜测。直到我们找到了路径我们才会知道真正的距离,因为途中有各种各样的东西 ( 比如墙壁,水等 ) 。本教程将教你一种计算 H 的方法,你也可以在网上找到其他方法。

    我们的路径是这么产生的:反复遍历 open list ,选择 F 值最小的方格。这个过程稍后详细描述。我们还是先看看怎么去计算上面的等式。

    如上所述, G 是从起点A移动到指定方格的移动代价。在本例中,横向和纵向的移动代价为 10 ,对角线的移动代价为 14 。之所以使用这些数据,是因为实际的对角移动距离是 2 的平方根,或者是近似的 1.414 倍的横向或纵向移动代价。使用 10 和 14 就是为了简单起见。比例是对的,我们避免了开放和小数的计算。这并不是我们没有这个能力或是不喜欢数学。使用这些数字也可以使计算机更快。稍后你便会发现,如果不使用这些技巧,寻路算法将很慢。

    既然我们是沿着到达指定方格的路径来计算 G 值,那么计算出该方格的 G 值的方法就是找出其父亲的 G 值,然后按父亲是直线方向还是斜线方向加上 10 或 14 。随着我们离开起点而得到更多的方格,这个方法会变得更加明朗。

    有很多方法可以估算 H 值。这里我们使用 Manhattan 方法,计算从当前方格横向或纵向移动到达目标所经过的方格数,忽略对角移动,然后把总数乘以 10 。之所以叫做 Manhattan 方法,是因为这很像统计从一个地点到另一个地点所穿过的街区数,而你不能斜向穿过街区。重要的是,计算 H 是,要忽略路径中的障碍物。这是对剩余距离的估算值,而不是实际值,因此才称为试探法。

    把 G 和 H 相加便得到 F 。我们第一步的结果如下图所示。每个方格都标上了 F , G , H 的值,就像起点右边的方格那样,左上角是 F ,左下角是 G ,右下角是 H 。
    这里写图片描述
    图 3

    好,现在让我们看看其中的一些方格。在标有字母的方格, G = 10 。这是因为水平方向从起点到那里只有一个方格的距离。与起点直接相邻的上方,下方,左方的方格的 G 值都是 10 ,对角线的方格 G 值都是 14 。

    H 值通过估算起点于终点 ( 红色方格 ) 的 Manhattan 距离得到,仅作横向和纵向移动,并且忽略沿途的墙壁。使用这种方式,起点右边的方格到终点有 3 个方格的距离,因此 H = 30 。这个方格上方的方格到终点有 4 个方格的距离 ( 注意只计算横向和纵向距离 ) ,因此 H = 40 。对于其他的方格,你可以用同样的方法知道 H 值是如何得来的。

    每个方格的 F 值,再说一次,直接把 G 值和 H 值相加就可以了。

    为了继续搜索,我们从 open list 中选择 F 值最小的 ( 方格 ) 节点,然后对所选择的方格作如下操作:

    1. 把它从 open list 里取出,放到 close list 中。

    2. 检查所有与它相邻的方格,忽略其中在 close list 中或是不可走 (unwalkable) 的方格 ( 比如墙,水,或是其他非法地形 ) ,如果方格不在open lsit 中,则把它们加入到 open list 中。

    把我们选定的方格设置为这些新加入的方格的父亲。

    1. 如果某个相邻的方格已经在 open list 中,则检查这条路径是否更优,也就是说经由当前方格 ( 我们选中的方格 ) 到达那个方格是否具有更小的 G 值。如果没有,不做任何操作。

    相反,如果 G 值更小,则把那个方格的父亲设为当前方格 ( 我们选中的方格 ) ,然后重新计算那个方格的 F 值和 G 值。如果你还是很混淆,请参考下图。
    这里写图片描述
    图 4

    Ok ,让我们看看它是怎么工作的。在我们最初的 9 个方格中,还有 8 个在 open list 中,起点被放入了 close list 中。在这些方格中,起点右边的格子的 F 值 40 最小,因此我们选择这个方格作为下一个要处理的方格。它的外框用蓝线打亮。

    首先,我们把它从 open list 移到 close list 中 ( 这就是为什么用蓝线打亮的原因了 ) 。然后我们检查与它相邻的方格。它右边的方格是墙壁,我们忽略。它左边的方格是起点,在 close list 中,我们也忽略。其他 4 个相邻的方格均在 open list 中,我们需要检查经由这个方格到达那里的路径是否更好,使用 G 值来判定。让我们看看上面的方格。它现在的 G 值为 14 。如果我们经由当前方格到达那里, G 值将会为 20(其中 10 为到达当前方格的 G 值,此外还要加上从当前方格纵向移动到上面方格的 G 值 10) 。显然 20 比 14 大,因此这不是最优的路径。如果你看图你就会明白。直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。

    当把 4 个已经在 open list 中的相邻方格都检查后,没有发现经由当前方格的更好路径,因此我们不做任何改变。现在我们已经检查了当前方格的所有相邻的方格,并也对他们作了处理,是时候选择下一个待处理的方格了。

    因此再次遍历我们的 open list ,现在它只有 7 个方格了,我们需要选择 F 值最小的那个。有趣的是,这次有两个方格的 F 值都 54 ,选哪个呢?没什么关系。从速度上考虑,选择最后加入 open list 的方格更快。这导致了在寻路过程中,当靠近目标时,优先使用新找到的方格的偏好。但是这并不重要。 ( 对相同数据的不同对待,导致两中版本的 A* 找到等长的不同路径 ) 。

    我们选择起点右下方的方格,如下图所示。
    这里写图片描述
    图 5

    这次,当我们检查相邻的方格时,我们发现它右边的方格是墙,忽略之。上面的也一样。

    我们把墙下面的一格也忽略掉。为什么?因为如果不穿越墙角的话,你不能直接从当前方格移动到那个方格。你需要先往下走,然后再移动到那个方格,这样来绕过墙角。 ( 注意:穿越墙角的规则是可选的,依赖于你的节点是怎么放置的 )

    这样还剩下 5 个相邻的方格。当前方格下面的 2 个方格还没有加入 open list ,所以把它们加入,同时把当前方格设为他们的父亲。在剩下的3 个方格中,有 2 个已经在 close list 中 ( 一个是起点,一个是当前方格上面的方格,外框被加亮的 ) ,我们忽略它们。最后一个方格,也就是当前方格左边的方格,我们检查经由当前方格到达那里是否具有更小的 G 值。没有。因此我们准备从 open list 中选择下一个待处理的方格。

    不断重复这个过程,直到把终点也加入到了 open list 中,此时如下图所示。
    这里写图片描述
    图 6

    注意,在起点下面 2 格的方格的父亲已经与前面不同了。之前它的 G 值是 28 并且指向它右上方的方格。现在它的 G 值为 20 ,并且指向它正上方的方格。这在寻路过程中的某处发生,使用新路径时 G 值经过检查并且变得更低,因此父节点被重新设置, G 和 F 值被重新计算。尽管这一变化在本例中并不重要,但是在很多场合中,这种变化会导致寻路结果的巨大变化。

    那么我们怎么样去确定实际路径呢?很简单,从终点开始,按着箭头向父节点移动,这样你就被带回到了起点,这就是你的路径。如下图所示。从起点 A 移动到终点 B 就是简单从路径上的一个方格的中心移动到另一个方格的中心,直至目标。就是这么简单!
    这里写图片描述
    图 7

    A*算法总结(Summary of the A* Method)

    Ok ,现在你已经看完了整个的介绍,现在我们把所有步骤放在一起:

    1. 把起点加入 open list 。

    2. 重复如下过程:

    a. 遍历 open list ,查找 F 值最小的节点,把它作为当前要处理的节点。

    b. 把这个节点移到 close list 。

    c. 对当前方格的 8 个相邻方格的每一个方格?

    ◆ 如果它是不可抵达的或者它在 close list 中,忽略它。否则,做如下操作。

    ◆ 如果它不在 open list 中,把它加入 open list ,并且把当前方格设置为它的父亲,记录该方格的 F , G 和 H 值。

    ◆ 如果它已经在 open list 中,检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好,用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样,把它的父亲设置为当前方格,并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话,改变后你可能需要重新排序。

    d. 停止,当你

    ◆ 把终点加入到了 open list 中,此时路径已经找到了,或者

    ◆ 查找终点失败,并且 open list 是空的,此时没有路径。

    3.保存路径。从终点开始,每个方格沿着父节点移动直至起点,这就是你的路径。

    题外话(Small Rant)

    请原谅我的离题,当你在网上或论坛上看到各种关于 A* 算法的讨论时,你偶尔会发现一些 A* 的代码,实际上他们不是。要使用 A* ,你必须包含上面讨论的所有元素 —- 尤其是 open list , close list 和路径代价 G , H 和 F 。也有很多其他的寻路算法,这些算法并不是 A* 算法, A* 被认为是最好的。在本文末尾引用的一些文章中 Bryan Stout 讨论了他们的一部分,包括他们的优缺点。在某些时候你可以二中择一,但你必须明白自己在做什么。

    展开全文
  • A*算法 和 IDA*算法

    千次阅读 2013-12-05 14:41:02
    A*算法概述:  采用广度优先搜索策略,在搜索过程中使用启发函数,即有大致方向的向前进虽然目标有时候不是很明确。 A*算法核心:  A*算法的关键在于启发函数,启发函数的优劣直接影响A*算法的效率。  f(n)=g(n)+...
  • A*算法 matlab版

    2018-11-21 10:14:46
    A*算法,动态路径规划算法的一种,程序直接放到matlab即可运行。
  • A*算法matlab

    热门讨论 2012-10-31 16:56:44
    A*算法matlab
  • A*算法源码

    热门讨论 2013-08-11 15:44:19
    A星寻路算法A*算法)源码实现,用MFC程序模拟动态寻路过程。只实现了最简单的A*算法,MFC消息处理的也不好,仅作参考。
  • A算法与A*算法区别

    万次阅读 多人点赞 2017-03-15 19:15:58
    A*算法 A算法
  • 试题中的A*算法,什么是A*算法??

    千次阅读 2014-07-15 23:00:28
    今天做题遇到了一个算法题目,“请描述意思下A*算法,它是什么类型的算法??”,当时我看的时候,隐约记得以前好像看过这个算法,因为印象不是很深刻,就直接写了深度优先,最短路径算法。这个写得不严谨,回来之后...
  • A算法 c语言实现 a*算法

    热门讨论 2009-02-11 20:28:15
    A算法 用c语言实现 用到了队列 a*算法 A算法 用c语言实现 用到了队列 a*算法
  • A*算法(一)算法导言

    万次阅读 2019-09-03 23:20:50
    问题场景、结点图、Dijkstra算法、BFS算法、存在障碍的情况、取长补短、A*算法
  • 以实际物流AGV运行环境为实际背景,经典最短路径搜索算法如迪杰特斯拉算法,在搜索AGV最短路径源节点与...A*算法在经典路径搜索算法上增加了评估条件,或者说代价,或者说评估公式:h(n)=f(n)+g(n),其中f(n...
  • A*算法原理概述

    万次阅读 多人点赞 2019-05-06 19:57:27
    这里是目录路径规划A*算法原理路线规划理论概述Dijkstra算法最佳优先搜索算法A*算法理论概述 路径规划A*算法原理 路线规划理论概述 移动一个物体直观上很容易的,但是物品的路线规划是复杂的。如下图3-1所示,物体...
  • A*算法的Matlab实现

    千次阅读 多人点赞 2019-03-26 22:40:33
    A*算法的Matlab实现A*算法的Matlab实现一、参考博客二、代码如下:1.pathfinding.m2.AStar.m3.FindList.m4.GetBoundary.m5.GetObstacle.m6.GetPath7.h.m8.isObstacle9.isopen10.MotionModel11.plot_map.m ...
  • 这个是机器人轨迹规划A*算法代码,它是由matlab编写的,文档见我的博客: https://blog.csdn.net/caokaifa/article/details/82314809
  • A*算法的C#实现

    千次阅读 2018-09-01 21:04:55
     本文的主要内容是讲述A *寻路算法的基本原理,实现步骤以及对应的C#代码,适合读者用于学习A *算法或 使用此代码提供的接口完成游戏中的寻路功能。  详细的A *算法的原理,请参照:https://blog.csdn.net/d...
  • A*算法的C++实现,注释详尽,直接编译运行
  • A*算法:Dijkstra改进算法

    万次阅读 2017-08-16 10:50:11
    A*算法:Dijkstra改进算法A算法Dijkstra改进算法 寻路模型 A算法 算法简介 算法步骤 格点模型 格点模型分析 改进思路方向 导航网络算法步骤及其优缺点 A算法启发函数的选取 伪代码 参考外链寻路模型最优路规划问题...
  • A算法和A*算法详解

    千次阅读 多人点赞 2019-12-02 18:07:08
    A算法和A*算法都适用 1、用初始节点初始化搜索图G (动态变化),将初始节点放入open表(还没有扩展的节点)中,然后初试closed(已经扩展完成的节点)表赋空NULL 2、如果open表不为空进入循环 2.1 将open表中的第...
  • 用Matlab实现A*算法和Dijkstra算法

    千次阅读 多人点赞 2019-02-26 20:03:20
    1. A*算法的伪代码 2. Dijkstra算法的伪代码 3. 具体实现 3.1 AStarGrid.m文件 function [route,numExpanded] = AStarGrid (input_map, start_coords, dest_coords) % Run A* algorithm on a grid. % ...
  • A*算法理解(unity C#)

    千次阅读 2018-10-19 17:54:56
    这里只谈A*算法的实现,不谈A算法的优化* 这里的工程是unity版本的,当然理解A*算法是通用的 这里先放上A*算法的unity工程(unity2017.3.1) Github工程 0X01 A*算法基本概念 启发式搜索: 启发式搜索就是在...
  • A*算法和dijkstra算法

    千次阅读 2018-08-10 16:42:55
    A*算法和dijkstra算法都是启发式搜索,dijkstra算法可以看成是广度优先搜索,而A*可以认为是深度优先搜索。 A*可以轻松地用在比如无人机航路规划中,而dijkstra建立在较为抽象的图论层面。 A*算法主要是有两张表,...
  • A*算法 matlab版代码

    千次阅读 2018-11-21 10:40:07
    A*算法用于路径规划,随机生成障碍、起点和终点,寻找最优路径 A* 算法是一种最优解算法,即如果起始点到目标点的最优路径存在,A* 算法能够保证找到该最优路径;但其所规划路径拐点多、拐角大,不符合机器人的运动...
  • 改进A*算法

    千次阅读 2018-06-22 11:15:19
    最短路径搜索问题是智能交通技术应用中的一个关键问题,而A*算法是一种静态路网中求解最短路径最有效的直接搜索方法.传统的A*算法未考虑到实际路网中交通灯的影响,求得的最短路径并不一定是行程时间最短.但是路径选取...
  • 终身规划A*算法(LPA*):Lifelong Planning A*

    千次阅读 多人点赞 2018-12-21 21:49:06
    终身规划A*算法(LPA*):Lifelong Planning A*1.描述2.父代节点与子代节点3.起始距离估计4.优先队列5.节点状态及扩展6.初始化运行7.最短路径搜索8.伪代码9.性质10.符号表示11.算法示例推演12.总结13.对公式的进一步...
  • a*算法流程图(只是流程图)A*算法是一种在静态路网中求解最短路径最有效的直接搜索方法,也是解决许多其他搜索问题的有效算法算法中的距离估算值与实际值越接近,扩展的节点数越少, 搜索速度越快。
  • Dijkstra算法A*算法总结

    万次阅读 多人点赞 2018-01-03 13:48:27
    Dijkstra算法A*算法都是最短路径问题的常用算法,下面就对这两种算法的特点进行一下比较。 1.Dijkstra算法计算源点到其他所有点的最短路径长度,A*关注点到点的最短路径(包括具体路径)。 2.Dijkstra算法建立在较为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,103,376
精华内容 841,350
关键字:

a*算法