A*寻路算法

发表于   |   分类于   |  

1. A*算法

启发式搜索、估价函数、时间上最优、空间增长指数级别

  • Start Point, End Point, Obstacles
  • 估值函数，F=G+H, F为从Start Point到当前点的耗费，H为从当前点到End Point的耗费。
  • OpenList 存放需要估值的点 CloseList 存放估值过的点

Algorithms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
OpenList.add(StartPoint);
do {
	current_point = OpenList.lowestF();
	OpenList.remove(current_point);
	CloseList.add(current_point);
	
	for (point in Neighbourhood(current_point)) {
		if (point in CloseList || point is Obstacles) continue;
		else if (point not in OpenList) {
			calculateFGH(point);
			point.father = current_point;
			OpenList.add(point);
		}
		else {
			if (current_point.G + calculateG(current_point, point) < point.G) {
				point.G = current_point.G + calculateG(current_point, point);
				point.F = point.G + point.H;
				point.father = current_point;
			}
		}
	}
} while (OpenList.size()  &&  EndPoint not in CloseList)
find paths