关于寻路算法加入地形影响的办法……求教脚本高手。

Cs2011 · 发表于 2011-6-25 11:04:50

本帖最后由 fux2 于 2011-6-25 14:03 编辑

之前看过论坛中高手制作的A star寻路算法的脚本，并成功运用到了游戏中。但我想进一步改进下算法，加入不同地形的影响因素。

熟悉Astar算法的都知道，这个算法中有3个值，F，G，H。。其中G是起点到当前点的消耗。

一般的算法中，在计算消耗时，每一格的上下左右移动消耗都是10，斜着移动消耗值为14。

而我想将它改进下，根据要走的下一格的地形的不同而得到不同的消耗（例如如果是走向雪地，走一格消耗就是30等等……）

我的想法：

现在的问题就是无法判断一个已知格子周围的地形信息，本人才疏学浅，不知道RPG Maker里是否能判断当前格子周围地形的函数，我感觉只要判断出是哪个图块就行，到时候我就可以根据函数返回的图块来改变G值的计算方式了。希望各位高手不吝赐教，先谢过了！！！

如果高手们有其他的方法能实现我说的功能，同样欢迎！！！

附：我在论坛中找到的A star 寻路算法。

#==============================================================================
class Find_Path
#--------------------------------------------------------------------------
def initialize #初始化
@open_list = []#开启列表
@close_lise = []#关闭列表
end #结束初始化
#--------------------------------------------------------------------------
def fp_passable?(x, y, d) #开始判定通行
if [2, 4, 6, 8].include?(d)
if $game_player.passable?(x, y, d)
return true
else
return false
end
else
case d
when 1
if ($game_player.passable?(x, y, 4) and
$game_player.passable?(x - 1, y, 2)) or
($game_player.passable?(x, y, 2) and
$game_player.passable?(x, y + 1, 4))
return true
else
return false
end
when 3
if ($game_player.passable?(x, y, 6) and
$game_player.passable?(x + 1, y, 2)) or
($game_player.passable?(x, y, 2) and
$game_player.passable?(x, y + 1, 6))
return true
else
return false
end
when 7
if ($game_player.passable?(x, y, 4) and
$game_player.passable?(x - 1, y, 8)) or
($game_player.passable?(x, y, 8) and
$game_player.passable?(x, y - 1, 4))
return true
else
return false
end
when 9
if ($game_player.passable?(x, y, 6) and
$game_player.passable?(x + 1, y, 8)) or
($game_player.passable?(x, y, 8) and
$game_player.passable?(x, y - 1, 6))
return true
else
return false
end
end
end
end #结束判定通行
[color=Red][b]#这里是我想改进的地方，我的想法是加入判断周围格子地形（图块）的函数，然后根据不同的图块设定g值不同的计算方法。[/b][/color][color=Red][b]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] + ((d == 1 or d == 3 or d == 7 or d == 9) ? 14 : 10)
return g
end #结束计算G值[/b][/color]#--------------------------------------------------------------------------[/color]
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 == 9 or d == 6 or d == 3) ? 1 : ((d == 7 or d == 4 or d == 1) ? -1 : 0))
y = now_point[1] + ((d == 1 or d == 2 or d == 3) ? 1 : ((d == 7 or d == 8 or d == 9) ? -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 find_short_path(self_x, self_y, trg_x, trg_y) #开始搜索路径
return [] if not (fp_passable?(trg_x, trg_y, 8) or
fp_passable?(trg_x, trg_y, 4) or
fp_passable?(trg_x, trg_y, 6) or
fp_passable?(trg_x, trg_y, 2))
@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 #将当前点加入关闭列表
#开始搜索
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
return @path
end #结束搜索路径
#--------------------------------------------------------------------------
def find_player_short_path(trg_x, trg_y) #寻找角色的最短路径
self_x = $game_player.x
self_y = $game_player.y
return find_short_path(self_x, self_y, trg_x, 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 [1, 2, 3, 4, 6, 7, 8, 9]
x = point[0] + ((d == 9 or d == 6 or d == 3) ? 1 : ((d == 7 or d == 4 or d == 1) ? -1 : 0))
y = point[1] + ((d == 1 or d == 2 or d == 3) ? 1 : ((d == 7 or d == 8 or d == 9) ? -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)
# 如果不在开启列表中、且不在关闭列表中、且通行则添加它到新八周节点
@open_list.push new_point(x, y, 10 - d)
#如果将目标点添加到了开启列表中就返回true
return true if x == @trg_x and y == @trg_y
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

复制代码

Cs2011 · 发表于 2011-6-25 23:40:00

本帖最后由 Cs2011 于 2011-6-25 23:42 编辑

感谢1楼回复者:) ，问题解决了，为让大家交流学习，附上更新之后的代码（计算G值部分有变化，大体思路就是设定了一个地形值为5的图块，然后将它放进地图里，判断当前点周围的点，若有此图块，则G值就会变成40,或56（斜着走），其他情况还是默认的10和14）：

#==============================================================================
class Find_Path
#--------------------------------------------------------------------------
def initialize  #初始化
@open_list = []#开启列表
@close_lise = []#关闭列表
end  #结束初始化
#--------------------------------------------------------------------------
def fp_passable?(x, y, d)  #开始判定通行
if [2, 4, 6, 8].include?(d)
if $game_player.passable?(x, y, d)
   return true
else
   return false
end
else
case d
when 1
   if ($game_player.passable?(x, y, 4) and
   $game_player.passable?(x - 1, y, 2)) or
      ($game_player.passable?(x, y, 2) and
   $game_player.passable?(x, y + 1, 4))
   return true
   else
   return false
   end
when 3
   if ($game_player.passable?(x, y, 6) and
   $game_player.passable?(x + 1, y, 2)) or
      ($game_player.passable?(x, y, 2) and
   $game_player.passable?(x, y + 1, 6))
   return true
   else
   return false
   end
when 7
   if ($game_player.passable?(x, y, 4) and
   $game_player.passable?(x - 1, y, 8)) or
      ($game_player.passable?(x, y, 8) and
   $game_player.passable?(x, y - 1, 4))
   return true
   else
   return false
   end
when 9
   if ($game_player.passable?(x, y, 6) and
   $game_player.passable?(x + 1, y, 8)) or
      ($game_player.passable?(x, y, 8) and
   $game_player.passable?(x, y - 1, 6))
   return true
   else
   return false
   end
end
end
end  #结束判定通行
#--------------------------------------------------------------------------
def get_g(now_point)  #开始计算G值

d = now_point[2]
return 0 if d == 5
father_point = get_father_point(now_point)

if(($game_map.terrain_tag(now_point[0]-1, now_point[1]-1)==5)and (d==1))
   g = father_point[3]+56
elsif(($game_map.terrain_tag(now_point[0], now_point[1]-1)==5)and (d==2))
   g = father_point[3]+40
elsif(($game_map.terrain_tag(now_point[0]+1, now_point[1]-1)==5)and (d==3))
   g = father_point[3]+56
elsif(($game_map.terrain_tag(now_point[0]-1, now_point[1])==5)and (d==4))
   g = father_point[3]+40
elsif(($game_map.terrain_tag(now_point[0]+1, now_point[1])==5)and (d==6))
   g = father_point[3]+40
elsif(($game_map.terrain_tag(now_point[0]-1, now_point[1]+1)==5)and (d==7))
   g = father_point[3]+56
elsif(($game_map.terrain_tag(now_point[0], now_point[1]+1)==5)and (d==8))
   g = father_point[3]+40
elsif(($game_map.terrain_tag(now_point[0]+1, now_point[1]+1)==5)and (d==9))
   g = father_point[3]+56
else
   g = father_point[3] + ((d == 1 or d == 3 or d == 7 or d == 9) ? 14 : 10)
  end
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 == 9 or d == 6 or d == 3) ? 1 : ((d == 7 or d == 4 or d == 1) ? -1 : 0))
y = now_point[1] + ((d == 1 or d == 2 or d == 3) ? 1 : ((d == 7 or d == 8 or d == 9) ? -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 find_short_path(self_x, self_y, trg_x, trg_y)  #开始搜索路径
return [] if not (fp_passable?(trg_x, trg_y, 8) or
               fp_passable?(trg_x, trg_y, 4) or
               fp_passable?(trg_x, trg_y, 6) or
               fp_passable?(trg_x, trg_y, 2))
@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 #将当前点加入关闭列表
#开始搜索
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
return @path
end  #结束搜索路径
#--------------------------------------------------------------------------
def find_player_short_path(trg_x, trg_y)  #寻找角色的最短路径
self_x = $game_player.x
self_y = $game_player.y
return find_short_path(self_x, self_y, trg_x, 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 [1, 2, 3, 4, 6, 7, 8, 9]
x = point[0] + ((d == 9 or d == 6 or d == 3) ? 1 : ((d == 7 or d == 4 or d == 1) ? -1 : 0))
y = point[1] + ((d == 1 or d == 2 or d == 3) ? 1 : ((d == 7 or d == 8 or d == 9) ? -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)
   # 如果不在开启列表中、且不在关闭列表中、且通行则添加它到新八周节点
   @open_list.push new_point(x, y, 10 - d)
   #如果将目标点添加到了开启列表中就返回true
   return true if x == @trg_x and y == @trg_y
   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

any0 · 发表于 2011-6-25 14:12:14

嘻嘻~~很不错哦！支持一下啦！！

shoed · 发表于 2011-6-25 12:20:22

个人认为使用地型标志就可以了
在game_map中有个terrain_tag函数可以根据坐标来取得地型标志，
通过这个来判断是什么样的地型了

帐号		自动登录	找回密码
密码			注册会员

[已经过期] 关于寻路算法加入地形影响的办法……求教脚本高手。

点评