实现A*(A-Star)寻路算法 - 游戏技巧

⭐✔️

本帖最后由贰逼于 2018-7-29 20:15 编辑

https://www.bilibili.com/html/player.html?aid=15034808&wmode=transparent&as_wide=1&page=1
推荐前往主站观看 [点击此处]

原理在视频中，若是看不懂可以百度相关文献
存档下载：
链接：http://pan.baidu.com/s/1c270UJ2 密码：br05

源码：

function cood //获取世界坐标
function a_ //用户控制
function a_2 //2D寻路
function a_3 //3D寻路

以a_2为例：
a_ //主模块

scoreboard objectives add coox dummy
scoreboard objectives add cooz dummy
scoreboard objectives add parx dummy
scoreboard objectives add parz dummy
scoreboard objectives add F dummy
scoreboard objectives add i dummy
#寻路
#建立子节点
execute @e[tag=asterisk_selectedN] ~ ~ ~ function a_2:a_createRoot
#F=G+H
function a_2:a_getF
#求最优F
summon area_effect_cloud ~ ~ ~ {Duration:1,Age:1s,Tags:[Fmin]}
scoreboard players set @e[tag=Fmin] F 2147483647
execute @e[tag=asterisk_H] ~ ~ ~ scoreboard players operation @e[tag=Fmin] F < @e[tag=asterisk_H,c=1] F
scoreboard objectives add M dummy
execute @e[tag=asterisk_H] ~ ~ ~ scoreboard players operation @e[tag=asterisk_H,c=1] M = @e[tag=asterisk_H,c=1] F
execute @e[tag=asterisk_H] ~ ~ ~ scoreboard players operation @e[tag=asterisk_H,c=1] M -= @e[tag=Fmin] F
scoreboard players tag @e[tag=asterisk_H,score_M_min=0,score_M=0] add asterisk_selectedN
scoreboard players tag @e[tag=asterisk_H,score_M_min=0,score_M=0] add asterisk_selected
#反向查找
#获取父节点
execute @e[tag=asterisk_pN] ~ ~ ~ function a_2:a_getpath
execute @e[tag=asterisk_destination] ~ ~ ~ execute @e[tag=asterisk_selected,dx=0,dy=0] ~ ~ ~ scoreboard players tag @e[tag=asterisk_destination] add asterisk_p
execute @e[tag=asterisk_destination] ~ ~ ~ execute @e[tag=asterisk_selected,dx=0,dy=0] ~ ~ ~ function a_2:a_getpath
#完成
scoreboard players tag @e[tag=asterisk_origin] add End {Tags:[asterisk_p]}
execute @e[tag=End] ~ ~ ~ scoreboard players tag @e[tag=asterisk_pN] remove asterisk_pN

复制代码

a_createRoot //创建节点

scoreboard players add index i 1
execute @s ~ ~ ~ summon area_effect_cloud ~1 ~ ~ {Duration:210000000,Age:1s,Tags:[asterisk_point,asterisk_pointN,asterisk_mk,asterisk1,r1]}
execute @s ~ ~ ~ summon area_effect_cloud ~-1 ~ ~ {Duration:210000000,Age:1s,Tags:[asterisk_point,asterisk_pointN,asterisk_mk,asterisk2,r2]}
execute @s ~ ~ ~ summon area_effect_cloud ~ ~ ~1 {Duration:210000000,Age:1s,Tags:[asterisk_point,asterisk_pointN,asterisk_mk,asterisk3,r3]}
execute @s ~ ~ ~ summon area_effect_cloud ~ ~ ~-1 {Duration:210000000,Age:1s,Tags:[asterisk_point,asterisk_pointN,asterisk_mk,asterisk4,r4]}
execute @s ~ ~ ~ summon area_effect_cloud ~1 ~ ~1 {Duration:210000000,Age:1s,Tags:[asterisk_point,asterisk_pointN,asterisk_mk,asterisk5,r5]}
execute @s ~ ~ ~ summon area_effect_cloud ~-1 ~ ~1 {Duration:210000000,Age:1s,Tags:[asterisk_point,asterisk_pointN,asterisk_mk,asterisk6,r6]}
execute @s ~ ~ ~ summon area_effect_cloud ~1 ~ ~-1 {Duration:210000000,Age:1s,Tags:[asterisk_point,asterisk_pointN,asterisk_mk,asterisk7,r7]}
execute @s ~ ~ ~ summon area_effect_cloud ~-1 ~ ~-1 {Duration:210000000,Age:1s,Tags:[asterisk_point,asterisk_pointN,asterisk_mk,asterisk8,r8]}
#删除重复
execute @e[tag=asterisk_H] ~ ~ ~ kill @e[tag=asterisk_mk,r=0]
execute @e[tag=asterisk_selected] ~ ~ ~ kill @e[tag=asterisk_mk,r=0]
execute @e[tag=asterisk_root] ~ ~ ~ kill @e[tag=asterisk_mk,r=0]
#删除障碍
execute @e[tag=asterisk_mk] ~ ~ ~ detect ~ ~ ~ air 0 scoreboard players tag @e[tag=asterisk_mk,c=1] remove asterisk_mk
scoreboard players tag @e[tag=asterisk_mk] add asterisk_m1 {Tags:[asterisk1]}
scoreboard players tag @e[tag=asterisk_mk] add asterisk_m2 {Tags:[asterisk2]}
scoreboard players tag @e[tag=asterisk_mk] add asterisk_m3 {Tags:[asterisk3]}
scoreboard players tag @e[tag=asterisk_mk] add asterisk_m4 {Tags:[asterisk4]}
execute @e[tag=asterisk_m1] ~ ~ ~ kill @e[tag=asterisk_point,dx=0,dz=1,rm=0]
execute @e[tag=asterisk_m1] ~ ~ ~ kill @e[tag=asterisk_point,dx=0,dz=-1,rm=0]
execute @e[tag=asterisk_m2] ~ ~ ~ kill @e[tag=asterisk_point,dx=0,dz=1,rm=0]
execute @e[tag=asterisk_m2] ~ ~ ~ kill @e[tag=asterisk_point,dx=0,dz=-1,rm=0]
execute @e[tag=asterisk_m3] ~ ~ ~ kill @e[tag=asterisk_point,dx=1,dz=0,rm=0]
execute @e[tag=asterisk_m3] ~ ~ ~ kill @e[tag=asterisk_point,dx=-1,dz=0,rm=0]
execute @e[tag=asterisk_m4] ~ ~ ~ kill @e[tag=asterisk_point,dx=1,dz=0,rm=0]
execute @e[tag=asterisk_m4] ~ ~ ~ kill @e[tag=asterisk_point,dx=-1,dz=0,rm=0]
kill @e[tag=asterisk_mk]
scoreboard players tag @e[tag=asterisk_point] add asterisk_root
#得到坐标
#继承
execute @s ~ ~ ~ scoreboard players operation @e[tag=asterisk_pointN] coox = @s coox
execute @s ~ ~ ~ scoreboard players operation @e[tag=asterisk_pointN] cooz = @s cooz
execute @s ~ ~ ~ scoreboard players operation @e[tag=asterisk_pointN] parx = @s coox
execute @s ~ ~ ~ scoreboard players operation @e[tag=asterisk_pointN] parz = @s cooz
#变换
scoreboard players add @e[tag=asterisk1] coox 1
scoreboard players add @e[tag=asterisk5] coox 1
scoreboard players add @e[tag=asterisk7] coox 1
scoreboard players remove @e[tag=asterisk2] coox 1
scoreboard players remove @e[tag=asterisk6] coox 1
scoreboard players remove @e[tag=asterisk8] coox 1
scoreboard players add @e[tag=asterisk3] cooz 1
scoreboard players add @e[tag=asterisk5] cooz 1
scoreboard players add @e[tag=asterisk6] cooz 1
scoreboard players remove @e[tag=asterisk4] cooz 1
scoreboard players remove @e[tag=asterisk7] cooz 1
scoreboard players remove @e[tag=asterisk8] cooz 1
scoreboard players tag @e[tag=asterisk_pointN] remove asterisk_pointN
scoreboard players tag @e[tag=asterisk1] remove asterisk1
scoreboard players tag @e[tag=asterisk2] remove asterisk2
scoreboard players tag @e[tag=asterisk3] remove asterisk3
scoreboard players tag @e[tag=asterisk4] remove asterisk4
scoreboard players tag @e[tag=asterisk5] remove asterisk5
scoreboard players tag @e[tag=asterisk6] remove asterisk6
scoreboard players tag @e[tag=asterisk7] remove asterisk7
scoreboard players tag @e[tag=asterisk8] remove asterisk8
scoreboard players tag @s remove asterisk_H
scoreboard players tag @s remove asterisk_selectedN
#世界坐标->相对坐标
#execute @e[tag=asterisk_origin] ~ ~ ~ function cood:coox
#execute @e[tag=asterisk_origin] ~ ~ ~ function cood:cooy
#execute @e[tag=asterisk_origin] ~ ~ ~ function cood:cooz
#execute @e[tag=asterisk_point] ~ ~ ~ function cood:coox
#execute @e[tag=asterisk_point] ~ ~ ~ function cood:cooy
#execute @e[tag=asterisk_point] ~ ~ ~ function cood:cooz
#scoreboard players operation @e[tag=asterisk_point] coox -= @e[tag=asterisk_origin] coox
#scoreboard players operation @e[tag=asterisk_point] cooy -= @e[tag=asterisk_origin] cooy
#scoreboard players operation @e[tag=asterisk_point] cooz -= @e[tag=asterisk_origin] cooz
#scoreboard players set @e[tag=asterisk_origin] coox 0
#scoreboard players set @e[tag=asterisk_origin] cooy 0
#scoreboard players set @e[tag=asterisk_origin] cooz 0

复制代码

//a_getCood 世界坐标转相对坐标

execute @e[tag=asterisk_origin] ~ ~ ~ function cood:coox
execute @e[tag=asterisk_origin] ~ ~ ~ function cood:cooy
execute @e[tag=asterisk_origin] ~ ~ ~ function cood:cooz
execute @e[tag=asterisk_destination] ~ ~ ~ function cood:coox
execute @e[tag=asterisk_destination] ~ ~ ~ function cood:cooy
execute @e[tag=asterisk_destination] ~ ~ ~ function cood:cooz
scoreboard players operation @e[tag=asterisk_destination] coox -= @e[tag=asterisk_origin] coox
scoreboard players operation @e[tag=asterisk_destination] cooy -= @e[tag=asterisk_origin] cooy
scoreboard players operation @e[tag=asterisk_destination] cooz -= @e[tag=asterisk_origin] cooz
scoreboard players set @e[tag=asterisk_origin] coox 0
scoreboard players set @e[tag=asterisk_origin] cooy 0
scoreboard players set @e[tag=asterisk_origin] cooz 0

复制代码

//a_getF 获取F(N)

scoreboard objectives add Gx dummy
scoreboard objectives add Gz dummy
scoreboard objectives add Hx dummy
scoreboard objectives add Hz dummy
scoreboard objectives add GMx dummy
scoreboard objectives add GMz dummy
scoreboard objectives add HMx dummy
scoreboard objectives add HMz dummy
scoreboard objectives add prd dummy
scoreboard players set @e[tag=asterisk_point] GMx 0
scoreboard players set @e[tag=asterisk_point] GMz 0
scoreboard players set @e[tag=asterisk_point] HMx 0
scoreboard players set @e[tag=asterisk_point] HMz 0
scoreboard players set 10 prd 10
scoreboard players set 14 prd 14
#获取到起点的G
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] Gx = @e[tag=asterisk_point,c=1] coox
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] Gz = @e[tag=asterisk_point,c=1] cooz
execute @e[tag=asterisk_point,score_Gx=-1] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] GMx -= @e[tag=asterisk_point,c=1] Gx
execute @e[tag=asterisk_point,score_Gz=-1] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] GMz -= @e[tag=asterisk_point,c=1] Gz
execute @e[tag=asterisk_point,score_Gx_min=0] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] GMx = @e[tag=asterisk_point,c=1] Gx
execute @e[tag=asterisk_point,score_Gz_min=0] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] GMz = @e[tag=asterisk_point,c=1] Gz
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] Gx = @e[tag=asterisk_point,c=1] GMx
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] Gz = @e[tag=asterisk_point,c=1] GMz
execute @e[tag=asterisk_point,score_Gx=-1] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] GMx -= @e[tag=asterisk_point,c=1] GMz
scoreboard players set @e[tag=asterisk_point] GMz 0
execute @e[tag=asterisk_point,score_GMx=-1] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] GMz -= @e[tag=asterisk_point,c=1] GMx
execute @e[tag=asterisk_point,score_GMx_min=0] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] GMz = @e[tag=asterisk_point,c=1] GMx
execute @e[tag=asterisk_point,score_GMx=-1] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] GMx = @e[tag=asterisk_point,c=1] Gx
execute @e[tag=asterisk_point,score_GMx_min=0] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] GMx = @e[tag=asterisk_point,c=1] Gz
#获取到终点的H
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] Hx = @e[tag=asterisk_point,c=1] coox
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] Hz = @e[tag=asterisk_point,c=1] cooz
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] Hx -= @e[tag=asterisk_destination] coox
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] Hz -= @e[tag=asterisk_destination] cooz
execute @e[tag=asterisk_point,score_Hx=-1] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] HMx -= @e[tag=asterisk_point,c=1] Hx
execute @e[tag=asterisk_point,score_Hz=-1] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] HMz -= @e[tag=asterisk_point,c=1] Hz
execute @e[tag=asterisk_point,score_Hx_min=0] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] HMx = @e[tag=asterisk_point,c=1] Hx
execute @e[tag=asterisk_point,score_Hz_min=0] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] HMz = @e[tag=asterisk_point,c=1] Hz
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] Hx = @e[tag=asterisk_point,c=1] HMx
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] Hz = @e[tag=asterisk_point,c=1] HMz
execute @e[tag=asterisk_point,score_Hx=-1] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] HMx -= @e[tag=asterisk_point,c=1] HMz
scoreboard players set @e[tag=asterisk_point] HMz 0
execute @e[tag=asterisk_point,score_HMx=-1] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] HMz -= @e[tag=asterisk_point,c=1] HMx
execute @e[tag=asterisk_point,score_HMx_min=0] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] HMz = @e[tag=asterisk_point,c=1] HMx
execute @e[tag=asterisk_point,score_HMx=-1] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] HMx = @e[tag=asterisk_point,c=1] Hx
execute @e[tag=asterisk_point,score_HMx_min=0] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] HMx = @e[tag=asterisk_point,c=1] Hz
#最终的F
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] GMx *= 10 prd
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] HMx *= 10 prd
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] GMz *= 14 prd
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] HMz *= 14 prd
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] F = @e[tag=asterisk_point,c=1] GMx
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] F += @e[tag=asterisk_point,c=1] GMz
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] F += @e[tag=asterisk_point,c=1] HMx
execute @e[tag=asterisk_point] ~ ~ ~ scoreboard players operation @e[tag=asterisk_point,c=1] F += @e[tag=asterisk_point,c=1] HMz
scoreboard players tag @e[tag=asterisk_point] add asterisk_H
scoreboard players tag @e[tag=asterisk_point] remove asterisk_point
scoreboard objectives remove Gx dummy
scoreboard objectives remove Gz dummy
scoreboard objectives remove Hx dummy
scoreboard objectives remove Hz dummy
scoreboard objectives remove GMx dummy
scoreboard objectives remove GMz dummy
scoreboard objectives remove HMx dummy
scoreboard objectives remove HMz dummy
scoreboard objectives remove prd dummy

复制代码

a_a_getpath //追踪父节点

scoreboard objectives add patx dummy
scoreboard objectives add patz dummy
execute @s ~ ~ ~ execute @e[tag=asterisk_selected,r=2] ~ ~ ~ scoreboard players operation @e[tag=asterisk_selected,c=1] patx = @e[tag=asterisk_selected,c=1] coox
execute @s ~ ~ ~ execute @e[tag=asterisk_selected,r=2] ~ ~ ~ scoreboard players operation @e[tag=asterisk_selected,c=1] patz = @e[tag=asterisk_selected,c=1] cooz
execute @s ~ ~ ~ scoreboard players operation @e[tag=asterisk_selected,r=2] patx -= @s parx
execute @s ~ ~ ~ scoreboard players operation @e[tag=asterisk_selected,r=2] patz -= @s parz
scoreboard players tag @e[score_patx_min=0,score_patx=0,score_patz_min=0,score_patz=0] add asterisk_p
scoreboard players tag @e[score_patx_min=0,score_patx=0,score_patz_min=0,score_patz=0] add asterisk_pN
scoreboard players tag @s remove asterisk_pN
scoreboard players tag @s remove asterisk_selected
scoreboard players tag @e[tag=asterisk_selectedN] remove asterisk_selectedN
scoreboard objectives remove patx dummy
scoreboard objectives remove patz dummy
#路径可视化标记
execute @e[tag=asterisk_pN] ~ ~ ~ execute @e[tag=r1,r=0] ~ ~ ~ setblock ~ ~ ~ wool 1
execute @e[tag=asterisk_pN] ~ ~ ~ execute @e[tag=r2,r=0] ~ ~ ~ setblock ~ ~ ~ wool 2
execute @e[tag=asterisk_pN] ~ ~ ~ execute @e[tag=r3,r=0] ~ ~ ~ setblock ~ ~ ~ wool 3
execute @e[tag=asterisk_pN] ~ ~ ~ execute @e[tag=r4,r=0] ~ ~ ~ setblock ~ ~ ~ wool 4
execute @e[tag=asterisk_pN] ~ ~ ~ execute @e[tag=r5,r=0] ~ ~ ~ setblock ~ ~ ~ wool 5
execute @e[tag=asterisk_pN] ~ ~ ~ execute @e[tag=r6,r=0] ~ ~ ~ setblock ~ ~ ~ wool 6
execute @e[tag=asterisk_pN] ~ ~ ~ execute @e[tag=r7,r=0] ~ ~ ~ setblock ~ ~ ~ wool 7
execute @e[tag=asterisk_pN] ~ ~ ~ execute @e[tag=r8,r=0] ~ ~ ~ setblock ~ ~ ~ wool 8
#资源消耗高的方式
#scoreboard objectives add iL dummy
#scoreboard players set 2147483647 iL 2147483647
#execute @s ~ ~ ~ scoreboard players tag @e[dx=-1,dz=1,rm=0,tag=asterisk_selected] add asterisk_pf
#execute @s ~ ~ ~ scoreboard players tag @e[dx=-1,dz=-1,rm=0,tag=asterisk_selected] add asterisk_pf
#execute @s ~ ~ ~ scoreboard players tag @e[dx=1,dz=1,rm=0,tag=asterisk_selected] add asterisk_pf
#execute @s ~ ~ ~ scoreboard players tag @e[dx=1,dz=-1,rm=0,tag=asterisk_selected] add asterisk_pf
#execute @s ~ ~ ~ scoreboard players tag @e[dz=1,rm=0,tag=asterisk_selected] add asterisk_pf
#execute @s ~ ~ ~ scoreboard players tag @e[dz=-1,rm=0,tag=asterisk_selected] add asterisk_pf
#execute @e[tag=asterisk_pf] ~ ~ ~ scoreboard players operation @e[tag=asterisk_pf,c=1] iL = @e[tag=asterisk_pf,c=1] i
#execute @e[tag=asterisk_pf] ~ ~ ~ scoreboard players operation 2147483647 iL < @e[tag=asterisk_pf,c=1] iL
#execute @e[tag=asterisk_pf] ~ ~ ~ scoreboard players operation @e[tag=asterisk_pf,c=1] iL -= 2147483647 iL
#execute @e[tag=asterisk_pf] ~ ~ ~ scoreboard players tag @e[tag=asterisk_pN] remove asterisk_pN
#scoreboard players tag @e[score_iL=0,score_iL_min=0] add asterisk_p
#scoreboard players tag @e[score_iL=0,score_iL_min=0] add asterisk_pN
#scoreboard players tag @e[tag=asterisk_pf] remove asterisk_pf
#scoreboard objectives remove iL

复制代码

关注我的动态：http://weibo.com/TrembleSt

来自群组: Command Block Logic

袋里的鲨

标题再次迷之屏蔽？

⭐✔️

袋里的鲨发表于 2017-10-3 20:49
标题再次迷之屏蔽？

这个算法名字就叫A*(A-Star)

RainbowEna

啥是a算法
是某种新型怪物寻路系统吗

xgmzmn

dalao这个的原理是扫描，计算每个点的f然后求最小的总f值，找出最简路径吗？
前排鸡冻\(≧▽≦)/

5571314

没有看水一下

縻风

可惜，这东西要是能用到RPG地图里就完美了

山雀雀

说到寻路我第一想法竟然是跑dijkstra。。。

18036216609

哇瑟，厉害

V_院長

是我的错觉吗？感觉BBS的人越来越少了，都没人发帖了

顽石

老师 :哪位同学请不要玩 Minecraft了
学生 :我正在复习寻路算法呢
老师 :玩游戏就是玩游戏
学生 :你看我屏幕
老师 :................
小剧场结束------EHD----------
我╮(╯_╰)╭没有水贴

Smokey_Days

本帖最后由 Smokey_Days 于 2017-10-4 21:25 编辑

IDA* ?
分层DFS ?
说到设权值我就想起spfa
我看看源码

快辰

或许这就是大佬吧，感觉很牛的样子。。。看不懂看不懂

Antonie

MC居然用起了A*
不愧是大佬XD

langyo_v3

A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。
公式表示为：
f(n)=g(n)+h(n),

其中f(n) 是节点n从初始点到目标点的估价函数，
g(n) 是在状态空间中从初始节点到n节点的实际代价，
h(n)是从n到目标节点最佳路径的估计代价。
保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：
估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
如果估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
估价值与实际值越接近，估价函数取得就越好。
例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。

来自A*（A Star）算法：启发式（heuristic）算法

其实又是一个搜索算法……但是这确实蛮不错的

可置顶科普（雾）