剥除代码，A* 算法非常简单。算法维护两个集合：OPEN 集和 CLOSED 集。OPEN 集包含待检测节点。初始状态，OPEN集仅包含一个元素：开始位置。CLOSED集包含已检测节点。初始状态，CLOSED集为空。从图形上来看，OPEN集是已访问区域的边界，CLOSED集是已访问区域的内部。每个节点还包含一个指向父节点的指针，以确定追踪关系。

　　算法有一个主循环，重复地从OPEN集中取最优节点n（即f值最小的节点）来检测。如果n是目标节点，那么算法结束；否则，将节点n从OPEN集删除，并添加到CLOSED集中，然后查看n的所有邻节点n’。如果邻节点在CLOSED集，它已被检测过，则无需再检测（*）；如果邻节点在OPEN集，它将会被检测，则无需此时检测（*）；否则，将该邻节点加入OPEN集，设置其父节点为n，到n’的路径开销g(n’) = g(n) + movementcost(n, n’)。

　　这里有更详细的介绍，其中包含交互图。

　　（*）这里我略过了一个小细节。你应当检查节点的g值，如果新计算得到的路径开销比该g值低，那么要重新打开该节点（即重新放入OPEN集）。

具体代码实现:

1. OPEN = priority queue containing START
   

2. 
   

3. CLOSED = empty set
   

4. 
   

5. while lowest rank in OPEN is not the GOAL:
   

6. 
   

7.   current = remove lowest rank item from OPEN
   

8. 
   

9.   add current to CLOSED
   

10. 
    

11.   for neighbors of current:
    

12. 
    

13.     cost = g(current) + movementcost(current, neighbor)
    

14. 
    

15.     if neighbor in OPEN and cost less than g(neighbor):
    

16. 
    

17.       remove neighbor from OPEN, because new path is better
    

18. 
    

19.     if neighbor in CLOSED and cost less than g(neighbor): **
    

20. 
    

21.       remove neighbor from CLOSED
    

22. 
    

23.     if neighbor not in OPEN and neighbor not in CLOSED:
    

24. 
    

25.       set g(neighbor) to cost
    

26. 
    

27.       add neighbor to OPEN
    

28. 
    

29.       set priority queue rank to g(neighbor) + h(neighbor)
    

30. 
    

31.       set neighbor's parent to current
    

32. 
    

33. reconstruct reverse path from goal to start
    

34. 
    

35. by following parent pointers