A星算法笔记

参考：https://blog.csdn.net/hitwhylz/article/details/23089415

原理

heuristic 启发式
F=G+H
G: distance between start and current node
H: distance between goal and current node

//TO SEARCH & CHECK
Manhatan 距离:

基本数据结构

1.全局数组：
open list
close list
start
goal

2.局部变量
current node
neibor node

3.结构体

struct node{
  int F;
  int G;
  int H;
  node* parent
};

伪码

初始化start, goal
把start加入open list


FOR open list 
	选择 F 值最小的 ( 方格 ) 节点 current
	把它从 open list 里取出，放到 close list 中。

	for 检查所有与 current 相邻的方格 neibor
		IF 方格neibor不在open lsit 中，则把它加入到 open list 中。
		   把current设置为neibor的父亲。
		   计算neibor 的 F G H 
		   
		ELSE IF neibor已经在 open list 中
		   则比较 neibor.G 和 G1 = current.G + Manhatan(current,neibor)
		   IF G1 > G 这条路径是否更优，也就是说经由当前方格 ( 我们选中的方格 ) 到达那个方格是否具有更小的 G 值。
			   则neibor.parent=current
			   重新计算neibor的 F 值和 G 值。
		
		   ELSE
				不做任何操作。

		ELSE IF 是 close list 中或是不可走 (unwalkable) 的方格
		   忽略

//TODO
回溯及打印

TODO

完整源码,效果GIF