二、实验设计(原理分析及流程)
采用二维的网格表示,其中 0 表示点可走,1 表示点不可以走。点用( x, y )表示,寻
找从某一个给定的起始单元格出发, 经由行相邻或列相邻的单元格 (可以通过的),最终可以
到达目标单元格的、所走过的单元格序列。在任一个单元格中,都只能看到与它邻近的 4 个
单元格(如果位于底边,则只有 3 个;位于 4 个角上,则只有 2 个是否能通过)。
1.将开始节点放入开放列表(开始节点的 F 和 G 值都视为 0);
2.重复一下步骤:
i.在开放列表中查找具有最小 F 值的节点,并把查找到的节点作为当前节点;
ii.把当前节点从开放列表删除,加入到封闭列表;
iii.对当前节点相邻的每一个节点依次执行以下步骤:
1.如果该相邻节点不可通行或者该相邻节点已经在封闭列表中,则什么操作也不执行,
继续检验下一个节点;
2.如果该相邻节点不在开放列表中,则将该节点添加到开放列表中,并将该相邻节点
的父节点设为当前节点,同时保存该相邻节点的 G 和 F 值;
3.如果该相邻节点在开放列表中,则判断若经由当前节点到达该相邻节点的 G 值是
否小于原来保存的 G 值,若小于,则将该相邻节点的父节点设为当前节点,并重新设置该相邻节
点的 G 和 F 值.
iv.循环结束条件:当终点节点被加入到开放列表作为待检验节点时,表示路径被找到,
此时应终止循环;或者当开放列表为空,表明已无可以添加的新节点,而已检验的节点中没有终
点节点则意味着路径无法被找到,此时也结束循环;
3.从终点节点开始沿父节点遍历,并保存整个遍历到的节点坐标,遍历所得的节点就是最
后得到的路径;