分享自己写的A星算法

sky6595418

大家好啊,我自己写的 A星算法,  地图小的话50*50 的速度还行, 如果是800*800的 大地图 ,每次计算要挺多时间的,, 大家看看我的有什么改进的地方吗?
大概的思路就是:先把起点的XY 作为 父节点 放进关闭列表中, 然后扫描 父节点 的八个方向 坐标,  判断 不跨界并且不在开放和关闭列表中,后放进开放列表中, 然后 取F=G+H  的F最小的 坐标
作为下一次的父节点 , 把这个节点从开放列表剔除,加入到关闭列表中,   循环扫描直到 扫描到终点

  

窗口程序集名	保 留	保 留	备 注
A星

子程序名	返回值类型	公开	备 注
路径计算	坐标型
参数名	类 型	参考	可空	数组	备 注
起点x
起点y
终点x
终点y

变量名	类 型	静态	数组	备 注
子节点方向数组X			8
子节点方向数组Y			8
子节点x
子节点y
关闭列表	文本型		0
开放列表	文本型		0
f列表	整数型		0
符合条件的xy列表	文本型		0
符合条件的fxy列表	文本型		0
地图大小
关闭列表下标
开放列表下标
符合条件的列表下标
父节点x	整数型
父节点y	整数型
父节点xy	文本型
子节点xy	文本型
i	整数型
在不在开放列表中
在不在关闭列表中
g	整数型
h	整数型
f	整数型
j	整数型
最小F值位置
temp	整数型
分割文本数组	文本型		0
条件
起点xy	文本型
终点xy	文本型
路径数组	文本型		0
路径数组下标
下一步坐标数组	文本型		10
返回坐标	坐标型
jj

' 12,22
' 39,24
条件 ＝ 0
起点xy ＝ 到文本 (起点x) ＋ “,” ＋ 到文本 (起点y) ＋ “,”
父节点x ＝ 起点x
父节点y ＝ 起点y  ' 起点设置第一个父节点
父节点xy ＝ 到文本 (起点x) ＋ “,” ＋ 到文本 (起点y) ＋ “,”
终点xy ＝ 到文本 (终点x) ＋ “,” ＋ 到文本 (终点y) ＋ “,”
子节点方向数组X ＝ { -1, 0, 1, 1, 1, 0, -1, -1 }
子节点方向数组Y ＝ { -1, -1, -1, 0, 1, 1, 1, 0 }
地图大小 ＝ 地图位图.取宽度 () × 地图位图.取高度 ()
重定义数组 (关闭列表, 假, 地图大小)
重定义数组 (开放列表, 假, 地图大小)
重定义数组 (f列表, 假, 地图大小)
重定义数组 (符合条件的xy列表, 假, 地图大小)
重定义数组 (符合条件的fxy列表, 假, 地图大小)
重定义数组 (路径数组, 假, 地图大小)
关闭列表下标 ＝ 1
开放列表下标 ＝ 1
符合条件的列表下标 ＝ 1
关闭列表 [关闭列表下标] ＝ 父节点xy  ' 把第一个父节点放进关闭列表
关闭列表下标 ＝ 关闭列表下标 ＋ 1
判断循环首 (条件 ＝ 0)
jj ＝ jj ＋ 1
_启动窗口.标签_info.标题 ＝ 到文本 (jj)
计次循环首 (8, i)  ' '遍历父节点周围8个方向的节点,如果没跨界,不是障碍物,不在关闭和开放列表中,然后放进开放列表中,  同时放进 符合条件的数值列表
子节点x ＝ 父节点x ＋ 子节点方向数组X [i]
子节点y ＝ 父节点y ＋ 子节点方向数组Y [i]
子节点xy ＝ 到文本 (子节点x) ＋ “,” ＋ 到文本 (子节点y) ＋ “,”
如果真 (子节点x ≥ 0 且 子节点y ≥ 0 且 子节点x ≤ 地图位图.取宽度 () 且 子节点y ≤ 地图位图.取高度 ())  ' 不跨界
如果真 (地图分析 [子节点x ＋ 2] [子节点y ＋ 2] ＝ 0)  ' 没有障碍物
在不在开放列表中 ＝ 0
计次循环首 (开放列表下标, j)
如果真 (倒找文本 (开放列表 [j], 子节点xy, , 假) ≠ -1)
在不在开放列表中 ＝ 1
跳出循环 ()

计次循环尾 ()
在不在关闭列表中 ＝ 0
计次循环首 (关闭列表下标, j)
如果真 (倒找文本 (关闭列表 [j], 子节点xy, , 假) ≠ -1)
在不在关闭列表中 ＝ 1
跳出循环 ()

计次循环尾 ()
如果真 (在不在开放列表中 ＝ 0 且 在不在关闭列表中 ＝ 0)  ' 不在开放和关闭列表中
如果 (子节点方向数组X [i] ＝ 0 或 子节点方向数组Y [i] ＝ 0)
g ＝ 10
g ＝ 14
h ＝ (取绝对值 (子节点x － 终点x) ＋ 取绝对值 (子节点y － 终点y)) × 10
f ＝ g ＋ h
f列表 [开放列表下标] ＝ f
开放列表 [开放列表下标] ＝ 子节点xy  ' F值和开放列表同步
开放列表下标 ＝ 开放列表下标 ＋ 1
符合条件的xy列表 [符合条件的列表下标] ＝ 子节点xy
符合条件的fxy列表 [符合条件的列表下标] ＝ 父节点xy
符合条件的列表下标 ＝ 符合条件的列表下标 ＋ 1



计次循环尾 ()
_启动窗口.标签_info.标题 ＝ “aaa”
temp ＝ f列表 [1]
计次循环首 (开放列表下标 － 1, i)
如果真 (f列表 [i] ≤ temp)
temp ＝ f列表 [i]
最小F值位置 ＝ i

计次循环尾 ()  ' 计算开放列表中最小值的位置
父节点xy ＝ 开放列表 [最小F值位置]  ' 把最小值 给下一次的父节点
关闭列表 [关闭列表下标] ＝ 父节点xy  ' 把最小值放进关闭列表
关闭列表下标 ＝ 关闭列表下标 ＋ 1
计次循环首 (开放列表下标 － 1, i)
如果真 (i ≥ 最小F值位置)
开放列表 [i] ＝ 开放列表 [i ＋ 1]
f列表 [i] ＝ f列表 [i ＋ 1]

计次循环尾 ()  ' 把刚才放进关闭列表的值 从开放列表和F列表中删除
开放列表 [i] ＝ “”
f列表 [i] ＝ 0
开放列表下标 ＝ 开放列表下标 － 1  ' 把最后一位清空
分割文本数组 ＝ 分割文本 (父节点xy, “,”, )
父节点x ＝ 到整数 (分割文本数组 [1])
父节点y ＝ 到整数 (分割文本数组 [2])
如果真 (到整数 (分割文本数组 [1]) ＝ 终点x 且 到整数 (分割文本数组 [2]) ＝ 终点y)
调试输出 (“找到终点了跳出”)
跳出循环 ()  ' 找到终点了跳出

如果真 (开放列表 [1] ＝ “”)
返回坐标.x ＝ -1
返回坐标.y ＝ -1
返回 (返回坐标)
调试输出 (“没有路,跳出”)
跳出循环 ()  ' 没有路,跳出

判断循环尾 ()
路径数组下标 ＝ 1
判断循环首 (终点xy ≠ 起点xy)
计次循环首 (符合条件的列表下标, i)
如果真 (符合条件的xy列表 [i] ＝ 终点xy)
路径数组 [路径数组下标] ＝ 符合条件的xy列表 [i]
路径数组下标 ＝ 路径数组下标 ＋ 1
终点xy ＝ 符合条件的fxy列表 [i]

计次循环尾 ()
判断循环尾 ()
下一步坐标数组 ＝ 分割文本 (路径数组 [路径数组下标 － 1], “,”, )
返回坐标.x ＝ 到整数 (下一步坐标数组 [1])
返回坐标.y ＝ 到整数 (下一步坐标数组 [2])
返回 (返回坐标)

i支持库列表	支持库注释
BmpOperate	位图操作支持库
spec	特殊功能支持库

.版本 2<br /> .支持库 BmpOperate<br /> .支持库 spec<br /> <br /> .程序集 A星<br /> <br /> .子程序 路径计算, 坐标型<br /> .参数 起点x<br /> .参数 起点y<br /> .参数 终点x<br /> .参数 终点y<br /> .局部变量 子节点方向数组X, , , "8"<br /> .局部变量 子节点方向数组Y, , , "8"<br /> .局部变量 子节点x<br /> .局部变量 子节点y<br /> .局部变量 关闭列表, 文本型, , "0"<br /> .局部变量 开放列表, 文本型, , "0"<br /> .局部变量 f列表, 整数型, , "0"<br /> .局部变量 符合条件的xy列表, 文本型, , "0"<br /> .局部变量 符合条件的fxy列表, 文本型, , "0"<br /> .局部变量 地图大小<br /> .局部变量 关闭列表下标<br /> .局部变量 开放列表下标<br /> .局部变量 符合条件的列表下标<br /> .局部变量 父节点x, 整数型<br /> .局部变量 父节点y, 整数型<br /> .局部变量 父节点xy, 文本型<br /> .局部变量 子节点xy, 文本型<br /> .局部变量 i, 整数型<br /> .局部变量 在不在开放列表中<br /> .局部变量 在不在关闭列表中<br /> .局部变量 g, 整数型<br /> .局部变量 h, 整数型<br /> .局部变量 f, 整数型<br /> .局部变量 j, 整数型<br /> .局部变量 最小F值位置<br /> .局部变量 temp, 整数型<br /> .局部变量 分割文本数组, 文本型, , "0"<br /> .局部变量 条件<br /> .局部变量 起点xy, 文本型<br /> .局部变量 终点xy, 文本型<br /> .局部变量 路径数组, 文本型, , "0"<br /> .局部变量 路径数组下标<br /> .局部变量 下一步坐标数组, 文本型, , "10"<br /> .局部变量 返回坐标, 坐标型<br /> .局部变量 jj<br /> <br /> ' 12,22<br /> ' 39,24<br /> 条件 ＝ 0<br /> 起点xy ＝ 到文本 (起点x) ＋ “,” ＋ 到文本 (起点y) ＋ “,”<br /> 父节点x ＝ 起点x<br /> 父节点y ＝ 起点y  ' 起点设置第一个父节点<br /> 父节点xy ＝ 到文本 (起点x) ＋ “,” ＋ 到文本 (起点y) ＋ “,”<br /> 终点xy ＝ 到文本 (终点x) ＋ “,” ＋ 到文本 (终点y) ＋ “,”<br /> <br /> 子节点方向数组X ＝ { -1, 0, 1, 1, 1, 0, -1, -1 }<br /> 子节点方向数组Y ＝ { -1, -1, -1, 0, 1, 1, 1, 0 }<br /> 地图大小 ＝ 地图位图.取宽度 () × 地图位图.取高度 ()<br /> 重定义数组 (关闭列表, 假, 地图大小)<br /> 重定义数组 (开放列表, 假, 地图大小)<br /> 重定义数组 (f列表, 假, 地图大小)<br /> 重定义数组 (符合条件的xy列表, 假, 地图大小)<br /> 重定义数组 (符合条件的fxy列表, 假, 地图大小)<br /> 重定义数组 (路径数组, 假, 地图大小)<br /> <br /> 关闭列表下标 ＝ 1<br /> 开放列表下标 ＝ 1<br /> 符合条件的列表下标 ＝ 1<br /> <br /> 关闭列表 [关闭列表下标] ＝ 父节点xy  ' 把第一个父节点放进关闭列表<br /> 关闭列表下标 ＝ 关闭列表下标 ＋ 1<br /> <br /> <br /> <br /> .判断循环首 (条件 ＝ 0)<br />     jj ＝ jj ＋ 1<br />     _启动窗口.标签_info.标题 ＝ 到文本 (jj)<br />     .计次循环首 (8, i)  ' '遍历父节点周围8个方向的节点,如果没跨界,不是障碍物,不在关闭和开放列表中,然后放进开放列表中,  同时放进 符合条件的数值列表<br /> <br />         子节点x ＝ 父节点x ＋ 子节点方向数组X <i><br />         子节点y ＝ 父节点y ＋ 子节点方向数组Y <i><br />         子节点xy ＝ 到文本 (子节点x) ＋ “,” ＋ 到文本 (子节点y) ＋ “,”<br /> <br />         .如果真 (子节点x ≥ 0 且 子节点y ≥ 0 且 子节点x ≤ 地图位图.取宽度 () 且 子节点y ≤ 地图位图.取高度 ())  ' 不跨界<br />             .如果真 (地图分析 [子节点x ＋ 2] [子节点y ＋ 2] ＝ 0)  ' 没有障碍物<br />                 在不在开放列表中 ＝ 0<br />                 .计次循环首 (开放列表下标, j)<br />                     .如果真 (倒找文本 (开放列表 [j], 子节点xy, , 假) ≠ -1)<br />                         在不在开放列表中 ＝ 1<br />                         跳出循环 ()<br />                     .如果真结束<br /> <br />                 .计次循环尾 ()<br />                 在不在关闭列表中 ＝ 0<br />                 .计次循环首 (关闭列表下标, j)<br />                     .如果真 (倒找文本 (关闭列表 [j], 子节点xy, , 假) ≠ -1)<br />                         在不在关闭列表中 ＝ 1<br />                         跳出循环 ()<br />                     .如果真结束<br /> <br />                 .计次循环尾 ()<br /> <br />                 .如果真 (在不在开放列表中 ＝ 0 且 在不在关闭列表中 ＝ 0)  ' 不在开放和关闭列表中<br />                     .如果 (子节点方向数组X <i> ＝ 0 或 子节点方向数组Y <i> ＝ 0)<br />                         g ＝ 10<br />                     .否则<br />                         g ＝ 14<br />                     .如果结束<br />                     h ＝ (取绝对值 (子节点x － 终点x) ＋ 取绝对值 (子节点y － 终点y)) × 10<br />                     f ＝ g ＋ h<br />                     f列表 [开放列表下标] ＝ f<br />                     开放列表 [开放列表下标] ＝ 子节点xy  ' F值和开放列表同步<br />                     开放列表下标 ＝ 开放列表下标 ＋ 1<br />                     符合条件的xy列表 [符合条件的列表下标] ＝ 子节点xy<br />                     符合条件的fxy列表 [符合条件的列表下标] ＝ 父节点xy<br />                     符合条件的列表下标 ＝ 符合条件的列表下标 ＋ 1<br /> <br />                 .如果真结束<br /> <br />             .如果真结束<br /> <br />         .如果真结束<br /> <br /> <br /> <br /> <br />     .计次循环尾 ()<br />     _启动窗口.标签_info.标题 ＝ “aaa”<br />     temp ＝ f列表 [1]<br />     .计次循环首 (开放列表下标 － 1, i)<br />         .如果真 (f列表 <i> ≤ temp)<br />             temp ＝ f列表 <i><br />             最小F值位置 ＝ i<br />         .如果真结束<br /> <br />     .计次循环尾 ()  ' 计算开放列表中最小值的位置<br /> <br />     父节点xy ＝ 开放列表 [最小F值位置]  ' 把最小值 给下一次的父节点<br />     关闭列表 [关闭列表下标] ＝ 父节点xy  ' 把最小值放进关闭列表<br />     关闭列表下标 ＝ 关闭列表下标 ＋ 1<br /> <br />     .计次循环首 (开放列表下标 － 1, i)<br />         .如果真 (i ≥ 最小F值位置)<br />             开放列表 <i> ＝ 开放列表 [i ＋ 1]<br />             f列表 <i> ＝ f列表 [i ＋ 1]<br />         .如果真结束<br /> <br />     .计次循环尾 ()  ' 把刚才放进关闭列表的值 从开放列表和F列表中删除<br />     开放列表 <i> ＝ “”<br />     f列表 <i> ＝ 0<br />     开放列表下标 ＝ 开放列表下标 － 1  ' 把最后一位清空<br /> <br />     分割文本数组 ＝ 分割文本 (父节点xy, “,”, )<br />     父节点x ＝ 到整数 (分割文本数组 [1])<br />     父节点y ＝ 到整数 (分割文本数组 [2])<br /> <br /> <br />     .如果真 (到整数 (分割文本数组 [1]) ＝ 终点x 且 到整数 (分割文本数组 [2]) ＝ 终点y)<br />         调试输出 (“找到终点了跳出”)<br />         跳出循环 ()  ' 找到终点了跳出<br />     .如果真结束<br /> <br /> <br />     .如果真 (开放列表 [1] ＝ “”)<br />         返回坐标.x ＝ -1<br />         返回坐标.y ＝ -1<br />         返回 (返回坐标)<br />         调试输出 (“没有路,跳出”)<br />         跳出循环 ()  ' 没有路,跳出<br />     .如果真结束<br /> <br /> <br /> <br /> <br /> <br /> .判断循环尾 ()<br /> <br /> <br /> <br /> <br /> 路径数组下标 ＝ 1<br /> .判断循环首 (终点xy ≠ 起点xy)<br /> <br />     .计次循环首 (符合条件的列表下标, i)<br />         .如果真 (符合条件的xy列表 <i> ＝ 终点xy)<br />             路径数组 [路径数组下标] ＝ 符合条件的xy列表 <i><br />             路径数组下标 ＝ 路径数组下标 ＋ 1<br />             终点xy ＝ 符合条件的fxy列表 <i><br /> <br />         .如果真结束<br /> <br />     .计次循环尾 ()<br /> <br /> .判断循环尾 ()<br /> <br /> <br /> <br /> 下一步坐标数组 ＝ 分割文本 (路径数组 [路径数组下标 － 1], “,”, )<br /> 返回坐标.x ＝ 到整数 (下一步坐标数组 [1])<br /> 返回坐标.y ＝ 到整数 (下一步坐标数组 [2])<br /> 返回 (返回坐标)

天边浪子

移不动

感谢分享心得

jyyilntj

谢谢大神~~~~~~~~~~~~``````````````````````

一粒红尘

有很多成品例子 学这优化一下

wjswzj0

感谢分享心得

574567812

支持开源！~感谢分享

gaoqing

谢谢分享学习

玄冰

冒险岛能用吧

zmoli775

H=0就变成了迪杰斯特拉算法·哈哈哈！不错！