A*算法思路

把起始格添加到 "开启列表" do { 寻找开启列表中F值最低的格子, 我们称它为当前格. 把它切换到关闭列表. 对当前格相邻的8格中的每一个 if (它不可通过 || 已经在 "关闭列表" 中) { 什么也不做. } if (它不在开启列表中) { 把它添加进 "开启列表", 把当前格作为这一格的父节点, 计算这一格的 FGH } if (它已经在开启列表中) { if (用 G 值为参考检查新的路径是否更好, 更低的G值意味着更好的路径) { 把这一格的父节点改成当前格, 并且重新计算这一格的 GF 值. } } } while( 目标格已经在 "开启列表", 这时候路径被找到) 如果开启列表已经空了, 说明路径不存在.

最后从目标格开始, 沿着每一格的父节点移动直到回到起始格, 这就是路径.

D*算法思路

while() { 从OPEN表中取k值最小的节点Y; 遍历Y的子节点a,计算a的h值 h(a)=h(Y)+Y到子节点a的权重C(Y,a) { if(a in OPEN) 比较两个a的h值 if( a的h值小于OPEN表a的h值 ) { 更新OPEN表中a的h值;k值取最小的h值 有未受影响的最短路经存在 break; } if(a in CLOSE) 比较两个a的h值 //注意是同一个节点的两个不同路径的估价值 if( a的h值小于CLOSE表的h值 ) { 更新CLOSE表中a的h值; k值取最小的h值;将a节点放入OPEN表 有未受影响的最短路经存在 break; } if(a not in both) 将a插入OPEN表中;　//还没有排序 } 放Y到CLOSE表； OPEN表比较k值大小进行排序； }