节点寻路算法

㈠ Jps要测量一百五十米的路怎么找到这条路的中心线

Jps要测量一百五十米的路怎么找到这条路的中心线：
概念
强迫邻居（Forced Neighbour）
跳点（Jump Point）
JPS 寻路算法（Jump Point Search）
实现原理
示例过程
JPS+（Jump Point Search Plus）
预处理
示例过程
总结
参考
概念
JPS（jump point search）算法实际上是对A* 寻路算法的一个改进，因此在阅读本文之前需要先了解A*算法。A* 算法在扩展节点时会把节点所有邻居都考虑进去，这样openlist中点的数量会很多，搜索效率较慢。
若不了解A*算法，可以参考博主以前写的一篇文章 A* 寻路算法 - KillerAery - 博客园
例如在无遮挡情况下（往往会有多条等价路径），而我们希望起点到终点实际只取其中一条路径，而该路径外其它节点可以没必要放入openlist（不希望加入没必要的邻居）。

其次我们还希望直线方向上中途的点不用放入openlist，如果只放入每段直线子路径的起点和终点，那openlist又可以少放很多没必要的节点：

可以看到 JPS 算法搜到的节点总是“跳跃性”的，这是因为这些关键性的节点都是需要改变行走方向的拐点，因此这也是 Jump Point 命名的来历。
在介绍JPS等算法具体实现前，我们必须先掌握下面的概念。
强迫邻居（Forced Neighbour）
强迫邻居：节点 x 的8个邻居中有障碍，且 x 的父节点 p 经过x 到达 n 的距离代价比不经过 x 到达的 n 的任意路径的距离代价小，则称 n 是 x 的强迫邻居。
看定义也许十分晦涩难懂。直观来说，实际就是因为前进方向（父节点到 x 节点的方向为前进方向）的某一边的靠后位置有障碍物，因此想要到该边靠前的空位有最短的路径，就必须得经过过 x 节点。
可能的情况见图示，黑色为障碍，红圈即为强迫邻居：

（左图为直线方向情况下的强迫邻居，右图为斜方向情况下的强迫邻居）
跳点（Jump Point）
跳点：当前点 x 满足以下三个条件之一：
节点 x 是起点/终点。
节点 x 至少有一个强迫邻居。
如果父节点在斜方向（意味着这是斜向搜索），节点x的水平或垂直方向上有满足条件a，b的点。
节点y的水平或垂直方向是斜向向量的拆解，比如向量d=(1,1)，那么水平方向则是(1,0)，并不会往左搜索，只会看右边，如果向量d=(-1,-1)，那么水平方向是(-1,0)，只会搜索左边，不看右边，其他同理。
下图举个例子，由于黄色节点的父节点是在斜方向，其对应分解成向上和向右两个方向，因为在右方向发现一个蓝色跳点，因此黄色节点也应被判断为跳点：

JPS 寻路算法（Jump Point Search）
实现原理
JPS 算法和A* 算法非常相似，步骤大概如下：
openlist取一个权值最低的节点，然后开始搜索。（这些和A*是一样的）
搜索时，先进行 直线搜索（4/8个方向，跳跃搜索），然后再 斜向搜索（4个方向，只搜索一步）。如果期间某个方向搜索到跳点或者碰到障碍（或边界），则当前方向完成搜索，若有搜到跳点就添加进openlist。
跳跃搜索是指沿直线方向一直搜下去（可能会搜到很多格），直到搜到跳点或者障碍（边界）。一开始从起点搜索，会有4个直线方向（上下左右），要是4个斜方向都前进了一步，此时直线方向会有8个。
若斜方向没完成搜索，则斜方向前进一步，重复上述过程。
因为直线方向是跳跃式搜索，所以总是能完成搜索。
若所有方向已完成搜索，则认为当前节点搜索完毕，将当前节点移除于openlist，加入closelist。
重复取openlist权值最低节点搜索，直到openlist为空或者找到终点。
下面结合图片更好说明过程2和3：首先我们从openlist取出绿色的节点，作为搜索的开始，先进行直线搜索，再斜向搜索，没有找到任何跳点。

斜方向前进一步后，重复直线搜索和斜向搜索过程，仍没发现跳点。

斜方向前进两步后，重复直线搜索和斜向搜索过程，仍没发现跳点。

斜方向前进了三步后（假设当前位置为 x），在水平直线搜索上发现了一个跳点（紫色节点为强迫邻居）。

于是 x 也被判断为跳点，添加进openlist。斜方向结束，绿色节点的搜索过程也就此结束，被移除于openlist，放入closelist。

示例过程
下面展示JPS算法更加完整的过程：
假设起点为绿色节点，终点为红色节点。

重复直线搜索和斜向搜索过程，斜方向前进了3步。在第3步判断出黄色节点为跳点（依据是水平方向有其它跳点），将黄色跳点放入openlist，然后斜方向搜索完成，绿色节点移除于openlist，放入closelist。

对openlist下一个权值最低的节点（即黄色节点）开启搜索，在直线方向上发现了蓝色节点为跳点（依据是紫色节点为强迫邻居），类似地，放入openlist。

由于斜方向还没结束，继续前进一步。最后一次直线搜索和斜向搜索都碰到了边界，因此黄色节点搜索完成，移除于openlist，放入closelist。

对openlist下一个权值最低的节点（原为蓝色节点，下图变为黄色节点）开启搜索，直线搜索碰到边界，斜向搜索无果。斜方继续前进一步，仍然直线搜索碰到边界，斜向搜索无果。

由于斜方向还没结束，继续前进一步。

最终在直线方向上发现了红色节点为跳点，因此蓝色节点先被判断为跳点，只添加蓝色节点进openlist。斜方向完成，黄色节点搜索完成。

最后openlist取出的蓝色节点开启搜索，在水平方向上发现红色节点，判断为终点，算法完成。
回忆起跳点的第三个判断条件（如果父节点在斜方向，节点x的水平或垂直方向上有满足条件a，b的点），会发现这个条件判断是最复杂的。在寻路过程中，它使寻路多次在水平节点上搜到跳点，也只能先添加它本身。其次，这也是算法中需要使用到递归的地方，是JPS算法性能瓶颈所在。

㈡ 有关A* 寻路算法。 看了这个算法 大致都明白。就是有点不大清楚。

1. B的G值是指从起点A开始，到达该点的最短距离，和B在不在最短路径上没有关系。

2. 不是遍历所有路径，而是所有点。对于m*n的矩阵， 遍历所有点的复杂度是m*n（多项式复杂度），而遍历所有路径的复杂度是4的(m*n)次幂(每个点都有4个可能的方向)。从幂指数复杂度降低到多项式复杂度，这就是A*算法的意义所在。

3. 最优路径是要从终点一步步倒退回来。比如终点的G值是k，那么最多需要4*k次查找，依然是多项式复杂度。但多数问题(对于纯算法题来说)只是需要知道到达终点的步骤，很少要你找出固定路径的。

㈢ RMXP寻路算法

#==============================================================================
# ■ Find_Path
#------------------------------------------------------------------------------
# 寻路算法--完整鼠标系统（四方向）专用版
# By whbm
#==============================================================================
class Find_Path
#--------------------------------------------------------------------------
def initialize #初始化
@open_list = []
@close_lise = []
@path = []
end #结束初始化
#--------------------------------------------------------------------------
def fp_passable?(x, y, d, tr_x = -2, tr_y = -2) #开始判定通行
return false if (tr_x == @unable_xa or
tr_x == @unable_xb or
tr_y == @unable_ya or
tr_y == @unable_yb)
if $game_player.passable?(x, y, d)
return true
else
return false
end
end #结束判定通行
#--------------------------------------------------------------------------
def get_g(now_point) #开始计算G值
d = now_point[2]
return 0 if d == 5
father_point = get_father_point(now_point)
g = father_point[3] + 10
return g
end #结束计算G值
#--------------------------------------------------------------------------
def get_h(now_point) #开始计算H值
now_x = now_point[0]
now_y = now_point[1]
#print @trg_x,now_x,@trg_y,now_y
h = (@trg_x - now_x).abs + (@trg_y - now_y).abs
return h * 10
end #结束计算H值
#--------------------------------------------------------------------------
def get_f(now_point) #开始计算F值
f = now_point[3] + now_point[4]
return f
end #结束计算F值
#--------------------------------------------------------------------------
def get_point(x, y) #取已知坐标点
if @open_list.size != 0
@open_list.each do |point|
if point[0] == x and point[1] == y
return point
break
end
end
end
if @close_list.size != 0
@close_list.each do |point|
if point[0] == x and point[1] == y
return point
break
end
end
end
end #结束取已知坐标点
#--------------------------------------------------------------------------
def get_father_point(now_point) #取已知点的父节点
d = now_point[2]
return now_point if d == 5
x = now_point[0] + (d == 6 ? 1 : (d == 4 ? -1 : 0))
y = now_point[1] + (d == 2 ? 1 : (d == 8 ? -1 : 0))
return get_point(x, y)
end #结束取已知点的父节点
#--------------------------------------------------------------------------
def new_point(x, y, d) #开始建立新节点
#print x,y,d
point = [x, y, d]
point.push get_g(point)
point.push get_h(point)
point.push get_f(point)
return point
end #结束建立新节点
#--------------------------------------------------------------------------
def get_direction(self_x, self_y, trg_x, trg_y)
if trg_x > self_x
if trg_y - self_y > - ( trg_x - self_x ) and
trg_y - self_y < ( trg_x - self_x )
return 6
end
if trg_y - self_y > ( trg_x - self_x )
return 2
end
if trg_y - self_y < - ( trg_x - self_x )
return 8
end
end
if trg_x < self_x
if trg_y - self_y > - ( self_x - trg_x ) and
trg_y - self_y < ( self_x - trg_x )
return 4
end
if trg_y - self_y > ( self_x - trg_x )
return 2
end
if trg_y - self_y < - ( self_x - trg_x )
return 8
end
end
end
#--------------------------------------------------------------------------
def get_d_x_y(x, y, d)
d_x = x + (d == 6 ? 1 : (d == 4 ? -1 : 0))
d_y = y + (d == 2 ? 1 : (d == 8 ? -1 : 0))
return d_x, d_y
end
#--------------------------------------------------------------------------
def find_short_path_other(self_x, self_y, trg_x, trg_y,
real_self_x, real_self_y, real_trg_x, real_trg_y)
@self_x = self_x
@self_y = self_y
@now_x = self_x
@now_y = self_y
@trg_x = trg_x
@trg_y = trg_y
@path = []
direction = get_direction(real_self_x, real_self_y, real_trg_x, real_trg_y)
@now_trg_x, @now_trg_y = get_d_x_y(@self_x, @self_y, direction)
while fp_passable?(@now_x, @now_y, direction)
@path.push direction
@now_x = @now_trg_x
@now_y = @now_trg_y
@now_trg_x, @now_trg_y = get_d_x_y(@now_x, @now_y, direction)
end
return @path
end
#--------------------------------------------------------------------------
def find_short_path(self_x, self_y, trg_x, trg_y,
real_self_x, real_self_y, real_trg_x, real_trg_y) #开始搜索路径

return find_short_path_other(self_x, self_y, trg_x, trg_y,
real_self_x, real_self_y, real_trg_x, real_trg_y) if not
(fp_passable?(trg_x, trg_y + 1, 8) or
fp_passable?(trg_x + 1, trg_y, 4) or
fp_passable?(trg_x - 1, trg_y, 6) or
fp_passable?(trg_x, trg_y - 1, 2)) and @goal_type != 1

#根据屏幕限定搜索面积..加速
@unable_xa = $game_map.display_x / 128 - 1
@unable_ya = $game_map.display_y / 128 - 1
@unable_xb = $game_map.display_x / 128 + 20
@unable_yb = $game_map.display_y / 128 + 20

@self_x = self_x
@self_y = self_y
@now_x = self_x
@now_y = self_y
@trg_x = trg_x
@trg_y = trg_y
@open_list = []
@close_list = []
#准备搜索
#print @self_x,@self_y
@now_point = new_point(@self_x, @self_y, 5) #令起始点为当前点
@open_list.push @now_point #将当前点加入关闭列表
#开始搜索
begin
loop do
check_trg = check_around_point(@now_point)
if check_trg == true
@path = get_path
break
end
@now_point = get_lowest_f_point
if @now_point == [] or @now_point == nil
@path = []
break
end
end
rescue Hangup
retry
end
return @path
end #结束搜索路径
#--------------------------------------------------------------------------
def find_player_short_path(trg_x, trg_y,
real_trg_x, real_trg_y) #寻找角色的最短路径
self_x = $game_player.x
self_y = $game_player.y
real_self_x = $game_player.screen_x
real_self_y = $game_player.screen_y
@goal_type, event = $game_map.check_event_custom_exist(real_trg_x, real_trg_y)
if @goal_type == 1
trg_x = event.x
trg_y = event.y
end
return find_short_path(self_x, self_y, trg_x, trg_y,
real_self_x, real_self_y, real_trg_x, real_trg_y)
end #结束角色的寻找路径
#--------------------------------------------------------------------------
def get_path #取得最终的路径
path = []
now_point = @open_list[@open_list.size - 1]
path.push(10 - now_point[2])
last_point = now_point
loop do
now_point = get_father_point(now_point)
break if now_point[2] == 5
path.push(10 - now_point[2])
end
return path.reverse
end #结束取得最终的路径
#--------------------------------------------------------------------------
def get_lowest_f_point #开始取得最低F值的点
if @open_list == []
return []
end
last_lowest_f_point = @open_list[0]
@open_list.each do |point|
last_lowest_f_point = point if point[5] < last_lowest_f_point[5]
end
return last_lowest_f_point
end #结束取得最低F值点
#--------------------------------------------------------------------------
def check_around_point(point) #开始检查已知点的八方节点
for d in [2, 4, 6, 8]
x = point[0] + (d == 6 ? 1 : (d == 4 ? -1 : 0))
y = point[1] + (d == 2 ? 1 : (d == 8 ? -1 : 0))
if in_close_list?(x, y) #在关闭列表中
next
elsif in_open_list?(x, y) #在开启列表中
get_new_g_point = new_point(x, y, 10 - d)
get_last_g_point = get_point(x, y)
if get_new_g_point[3] >= get_last_g_point[3]
next
else
#如果改变父节点是新G值更小则确定改变
@open_list[@open_list.index(get_last_g_point)] = get_new_g_point
end
else
if fp_passable?(point[0], point[1], d, x, y)
# 如果不在开启列表中、且不在关闭列表中、且通行则添加它到新八周节点
@open_list.push new_point(x, y, 10 - d)
#如果将目标点添加到了开启列表中就返回true
return true if x == @trg_x and y == @trg_y
return true if @goal_type == 1 and ([1, -1].include?(x - @trg_x) and y - @trg_y == 0) or ([1, -1].include?(y - @trg_y) and x - @trg_x == 0)
end
end
end
#此刻没有找到目标点并将当前点加入关闭列表并在开启列表中删除
@close_list.push point
@open_list.delete(point)
#此刻没找到目标点并返回false
return false
end #结束计算已知点的八方节点
#--------------------------------------------------------------------------
def in_open_list?(x, y) #开始检查谋点是否在开启列表中
@open_list.each do |point|
return true if point[0] == x and point[1] == y
end
return false
end #结束检查谋点是否在开启列表中
#--------------------------------------------------------------------------
def in_close_list?(x, y) #开始检查谋点是否在关闭列表中
@close_list.each do |point|
return true if point[0] == x and point[1] == y
end
return false
end #结束检查谋点是否在关闭列表中
#--------------------------------------------------------------------------
end

㈣ 从原点出发，遍历50个点，再回到原点的最短路径，求matlab程序

据 Drew 所知最短路经算法现在重要的应用有计算机网络路由算法，机器人探路，交通路线导航，人工智能，游戏设计等等。美国火星探测器核心的寻路算法就是采用的D*（D Star）算法。

最短路经计算分静态最短路计算和动态最短路计算。

静态路径最短路径算法是外界环境不变，计算最短路径。主要有Dijkstra算法，A*（A Star）算法。

动态路径最短路是外界环境不断发生变化，即不能计算预测的情况下计算最短路。如在游戏中敌人或障碍物不断移动的情况下。典型的有D*算法。这是Drew程序实现的10000个节点的随机路网三条互不相交最短路真实路网计算K条路径示例：节点5696到节点3006，三条最快速路，可以看出路径基本上走环线或主干路。黑线为第一条，兰线为第二条，红线为第三条。约束条件系数为1.2。共享部分路段。 显示计算部分完全由Drew自己开发的程序完成。 参见 K条路算法测试程序

Dijkstra算法求最短路径：

Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。

大概过程：
创建两个表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
1． 访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4． 重复2，3，步。直到OPEN表为空，或找到目标点。

这是在drew 程序中4000个节点的随机路网上Dijkstra算法搜索最短路的演示，黑色圆圈表示经过遍历计算过的点由图中可以看到Dijkstra算法从起始点开始向周围层层计算扩展，在计算大量节点后，到达目标点。所以速度慢效率低。

提高Dijkstra搜索速度的方法很多，据Drew所知，常用的有数据结构采用Binary heap的方法，和用Dijkstra从起始点和终点同时搜索的方法。

推荐网页：http://www.cs.ecnu.e.cn/assist/js04/ZJS045/ZJS04505/zjs045050a.htm

简明扼要介绍Dijkstra算法，有图解显示和源码下载。

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

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算法的毫无无方向的向四周搜索。

conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible

主要搜索过程：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值

if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值

if(X not in both)
求X的估价值;
并将X插入OPEN表中;//还没有排序
}

将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
}

㈤ 梦幻西游自动寻路的寻路算法怎么算

A*寻路算法 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算法的毫无无方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索过程：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
if(X not in both)
求X的估价值;
并将X插入OPEN表中; //还没有排序
}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的
节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价
中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最
好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！
我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：
f'(n) = g'(n) + h'(n)
这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做
近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别的重要）。可以证明应用这样的估价
函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。哈。你懂了吗？肯定没懂。接着看。
举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是
。当然它是一种最臭的A*算法。
再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函
数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计
算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。
}

㈥ 游戏中的常用的寻路算法有哪些

f(n)=g(n)+h(n) 从起始点到目的点的最佳评估值
– 每次都选择f(n)值最小的结点作为下一个结点，
直到最终达到目的结点
– A*算法的成功很大程度依赖于h(n)函数的构建
?;) = g(n? 在各种游戏中广泛应用 Open列表和Closed列表
– Open列表
A*算法
? h(n) = 从结点n到目的结点的耗费评估值，启发函数
?，程序返回n
else 生成结点n的每一个后继结点n;
foreach 结点n的后继结点n;{
将n’的父结点设置为n
计算启发式评估函数h(n‘)值，评估从n‘到node_goal的费用
计算g(n‘) = g(n) + 从n’到n的开销
计算f(n?? 在算法启动时，Closed列表为空 A* 算法伪代码初始化OPEN列表
初始化CLOSED列表
创建目的结点；称为node_goal
创建起始结点；称为node_start
将node_start添加到OPEN列表
while OPEN列表非空{
从OPEN列表中取出f(n)值最低的结点n
将结点n添加到CLOSED列表中
if 结点n与node_goal相等then 我们找到了路径;)
if n‘位于OPEN或者CLOSED列表and 现有f(n)较优then丢弃n’ ;) + h(n?? 包含我们还没有处理到的结点
? g(n) = 从初始结点到结点n的耗费
?? 包含我们已经处理过的结点
，处理后继n’
将结点n‘从OPEN和CLOSED中删除
添加结点n‘到OPEN列表
}
}
return failure （我们已经搜索了所有的结点?? 启发式搜索
– 在搜索中涉及到三个函数
??? 我们最开始将起始结点放入到Open列表中
– Closed列表
?

㈦ 最短路径算法

Dijkstra算法，A*算法和D*算法

Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。

大概过程：
创建两个表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
1． 访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4． 重复2，3，步。直到OPEN表为空，或找到目标点。

提高Dijkstra搜索速度的方法很多，常用的有数据结构采用Binary heap的方法，和用Dijkstra从起始点和终点同时搜索的方法。

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算法的毫无无方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索过程：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
if(X not in both)
求X的估价值;
并将X插入OPEN表中; //还没有排序
}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
}

A*算法和Dijistra算法的区别在于有无估价值，Dijistra算法相当于A*算法中估价值为0的情况。

动态路网，最短路算法 D*A* 在静态路网中非常有效（very efficient for static worlds），但不适于在动态路网，环境如权重等不断变化的动态环境下。

D*是动态A*（D-Star,Dynamic A*） 卡内及梅隆机器人中心的Stentz在1994和1995年两篇文章提出，主要用于机器人探路。是火星探测器采用的寻路算法。

主要方法：
1.先用Dijstra算法从目标节点G向起始节点搜索。储存路网中目标点到各个节点的最短路和该位置到目标点的实际值h,k（k为所有变化h之中最小的值,当前为k=h。每个节点包含上一节点到目标点的最短路信息1(2),2(5),5(4)，4（7）。则1到4的最短路为1-2-5-4。
原OPEN和CLOSE中节点信息保存。
2.机器人沿最短路开始移动，在移动的下一节点没有变化时，无需计算，利用上一步Dijstra计算出的最短路信息从出发点向后追述即可，当在Y点探测到下一节点X状态发生改变，如堵塞。机器人首先调整自己在当前位置Y到目标点G的实际值h(Y)，h(Y)=X到Y的新权值c(X,Y)+X的原实际值h(X).X为下一节点(到目标点方向Y->X->G），Y是当前点。k值取h值变化前后的最小。
3.用A*或其它算法计算，这里假设用A*算法,遍历Y的子节点，点放入CLOSE,调整Y的子节点a的h值，h(a)=h(Y)+Y到子节点a的权重C(Y,a),比较a点是否存在于OPEN和CLOSE中，方法如下：
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值大小进行排序；
}
机器人利用第一步Dijstra计算出的最短路信息从a点到目标点的最短路经进行。

D*算法在动态环境中寻路非常有效，向目标点移动中，只检查最短路径上下一节点或临近节点的变化情况，如机器人寻路等情况。对于距离远的最短路径上发生的变化，则感觉不太适用。

㈧ a*寻路算法如果f值和h值都相等怎么取最优节点

首先，G值是从开始点到当前点的移动量，H值是从当前点到终点的移动估算量。既然F=G+H.如果F值和H值都相同，那么G值也是相同的，也就是说从开始点走了同样的距离，移动到两个不同的节点，而这两个节点距离重点的距离也是相同的。那就继续往下进行算法。如果继续下去之后，这两个节点还是一样的情况，那说明有两条最优路径，不然一定会有一个节点会被淘汰。

㈨ C++寻路算法

迷宫寻找路径要不。。。。。。#include <iostream>
#include<iomanip>
using namespace std;
#define M 10
#define N 10
typedef enum{X=0,up,dn,rt,lt} tDir; //搜索方向
class Migong
{
public:
int tag; /*0 1*/
tDir comeDir; /*退回*/
int up,rt,dn,lt; //方向
int back;
};int m[M][N]={ //初始化通道数据
{0,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,0,0,0,1,0,1,1,1,1},
{1,1,1,0,1,1,1,1,1,1},
{1,0,0,0,1,0,0,0,1,1},
{1,0,1,1,1,0,1,0,1,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,0,0,1,1,0,1,0,1},
{1,1,1,1,1,1,0,1,0,1},
{1,1,1,1,1,1,1,1,0,0},
}; int ini=0,inj=0; //入点
int outi=9,outj=9; //出口
int cnt=0; //从入口到出口需多少步
int path[M][N]; //记录找到路径后的迷宫
Migong maze[10][10]; void initmaze(Migong mz[][10]) //初始化迷宫数据
{
int i;
int j;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{
mz[i][j].tag=m[i][j];
mz[i][j].comeDir=X;
mz[i][j].up=0;
mz[i][j].dn=0;
mz[i][j].rt=0;
mz[i][j].lt=0;
mz[i][j].back=0;
}
}int find(Migong mz[][10],int i,int j,tDir dir) //搜索路径
{
if(i==outi&&j==outj)
return 1; ////if 当前节点是出口 then return 1;
if(dir!=X) //if 不是是回退到本节点,then 记录来的方向 根据来的方向设定其相对方向已走
{
mz[i][j].comeDir=dir;
if(dir==up)
mz[i][j].dn=1; //向N方向没有走&&可以走，则向N递归走
if(dir==dn)
mz[i][j].up=1; //向E方向没有走&&可以走，则向N递归走
if(dir==rt)
mz[i][j].lt=1; //向S方向没有走&&可以走，则向N递归走
if(dir==lt)
mz[i][j].rt=1; //向W方向没有走&&可以走，则向N递归走
}
if(mz[i][j].up==0) //if 向up方向没走&&不越界&&可以走 则向up递归走
{
int ni;
int nj;
mz[i][j].up=1; //记录本节点
ni=i-1;
nj=j; //ni,nj表示i,j的上一个坐标
if(ni>=0 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,up))
return 1;
}
if(mz[i][j].dn==0) //if 向dn方向没走&&不越界&&可以走 则向dn递归走
{
int ni;
int nj;
mz[i][j].dn=1; //记录本节点
ni=i+1;
nj=j; //ni,nj表示i,j的下一个坐标
if(ni<10 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,dn))
return 1;
}
if(mz[i][j].rt==0) //if 向rt方向没走&&不越界&&可以走 则向rt递归走
{
int ni;
int nj;
mz[i][j].rt=1; //记录本节点
ni=i;
nj=j+1; //ni,nj表示i,j的右一个坐标
if(nj<10 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,rt))
return 1;
}
if(mz[i][j].lt==0) //if 向lt方向没走&&不越界&&可以走 则向lt递归走
{
int ni;
int nj;
mz[i][j].lt=1; //记录本节点
ni=i;
nj=j-1; //ni,nj表示i,j的左一个坐标
if(nj>=0 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,lt))
return 1;
}

//四个方向都走完了还没有结果

if(i==ini && j==inj) // if 是入口 return 0
return 0;
else // else 则回退
{
mz[i][j].back=1;
if(mz[i][j].comeDir=up) //如果回退的值等于up的值，则向up方向搜索
{
int ni;
int nj;
ni=i+1;
nj=j; //ni,nj表示i,j的下一个坐标
if(find(maze,ni,nj,X))
return 1;
}
if(mz[i][j].comeDir=dn) //如果回退的值等于dn的值，则向dn方向搜索
{
int ni;
int nj;
ni=i-1;
nj=j; //ni,nj表示i,j的上一个坐标
if(find(maze,ni,nj,X))
return 1;
}
if(mz[i][j].comeDir=rt) //如果回退的值等于rt的值，则向rt方向搜索
{
int ni;
int nj;
ni=i;
nj=j-1; //ni,nj表示i,j的左一个坐标
if(find(maze,ni,nj,X))
return 1;
}
if(mz[i][j].comeDir=lt) //如果回退的值等于lt的值，则向lt方向搜索
{
int ni;
int nj;
ni=i+1;
nj=j+1; //ni,nj表示i,j的左下角一个坐标
if(find(maze,ni,nj,X))
return 1;
}
}
return 0;
}int onway( Migong nd) //判断点是否在路径上
{
if(nd.tag!=0)
return 0; //墙
if(nd.up==0&&nd.dn==0&&nd.rt==0&&nd.lt==0)
return 0; //没访问过
if(nd.up==1&&nd.dn==1&&nd.rt==1&&nd.lt==1&&nd.back==1)
return 0; //访问过但不通
return 1;
}//打印
void print( Migong mz[][10]) //打印原迷宫
{
int i;
int j;
cout<<"0表示可通过，1表示墙"<<endl;
cout<<"-------------------------------";
cout<<endl<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
for(i=0;i<10;i++)
{
cout<<setw(10)<<"▎ ";
for(j=0;j<10;j++)

cout<<mz[i][j].tag;
cout<<" ▎"<<endl;

}
cout<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
}void print1( Migong mz[][10]) //打印含路径迷宫
{
int i;
int j;
cout<<endl<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;

for(i=0;i<10;i++)
{
cout<<setw(10)<<"▎ ";
for(j=0;j<10;j++)
{
if(i==9 && j==9) //出口
{
cnt++;
cout<<"*";
path[i][j]=0;
}
else
if(onway(mz[i][j]))
{
cout<<"*"; //*表示路径
cnt++;
path[i][j];
}
else
{
cout<<mz[i][j].tag;
path[i][j]=1; //path[i][j]=0表示可通过，path[i][j]=1表示墙
} }
cout<<" ▎"<<endl;
}cout<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
}void print2( Migong mz[][10]) //打印路径坐标
{
int i;
int j;
int di;
int dj; //di,dj的值为-1，0，1，为了搜索坐标i,j附近的坐标
int pi;
int pj; //pi,pj为上一个路径坐标
int r;
int count; //统计输出了多少个坐标
i=0;
j=0;
pi=1;
pj=0;
count=0; cout<<endl<<"路径坐标为:"<<endl<<endl;
for(r=0;r<cnt;r++)
{
if(i>=10 || j>=10) //i,j的值不可能大于10
continue;
else
{
for(di=-1;di<2;di++)
for(dj=-1;dj<2;dj++)
{
if(di==dj ) //path[i][j]的下一步不可能在它的左上角和右下角
continue;
if(di==1 && dj==-1) //path[i][j]的下一步不可能在它的左下角
continue;
if(di==-1 && dj==1) //path[i][j]的下一步不可能在它的右上角
continue;
if((i+di)<0 ||(j+dj)<0) //i+di,j+dj小于0时不符
continue;
if(path[i+di][j+dj]!=0) //i+di,j+dj不是路径上的坐标
continue;
if((i+di)==i && (j+dj)==j ) //path[i][j]的下一步不可能是它本身
continue;
else
if((i+di)==pi && (j+dj)==pj) //path[i][j]的下一步不可能是它的上一步
continue;
else
{if(i==9&&j==9)<br> cout<<"(9,9)";<br> else<br> {<br> <br> cout<<"("<<i<<","<<j<<")"<<"->";<br> count++;<br> if(count%5==0)<br> cout<<endl;<br> }
pi=i;
pj=j;
i=i+di;
j=j+dj; }
}
}
}
}int main()
{
initmaze(maze); //初始化迷宫
cout<<endl<<endl<<"原迷宫如下："<<endl;
print(maze); //打印原迷宫
if (find(maze,ini,inj,rt)) //如果迷宫有路径
{

cout<<"-------------------------------";
cout<<endl<<"含路径的迷宫,*表示通道"<<endl;
cout<<"-------------------------------";
print1(maze); // 输出含路径的迷宫
cout<<endl<<"-------------------------------"<<endl;
print2(maze); //输出路径坐标
}
else
cout<<"no way!"; //如果迷宫没路径，输出no way
cout<<endl<<endl<<endl;
cout<<"从入口到出口需"<<cnt<<"步";
cout<<endl<<endl;
return 0;
}

㈩ 星际争霸2的寻路算法思路是怎样的

首先地图整体开始前，会用多层可达矩阵算法，算出路径关键点
2，创建关键节点可达矩阵
3，再每个兵当前位置对关键节点进行路径计算
这样可以最小化资源占用就可以完成路径计算了，高数的离散数学，挺容易解的