那个自动寻路要怎么做呀

langdeluoyin · 发表于 2010-1-10 22:01:07

由于我做的地图太大了，所以想做一个自动寻路方便一点，请问要怎样才能做出自动寻路的效果，只要开启任务就能自己到达目的地！

酆城浪子 · 发表于 2010-1-10 22:21:30

可以直接场所移动。。。比自动寻路方便多了。。。

secondsen · 发表于 2010-1-10 22:36:44

我写过。。。前两天写的，当然是仿照别人的。。。找找看。。。。

只写了算法。。。没有应用到游戏中

secondsen · 发表于 2010-1-10 22:37:21

Graphics.transition(10)
#地图
$tm = [
'############################################################',
'#..........................................................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.......S.....................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#.............................#............................#',
'#######.#######################################............#',
'#....#........#............................................#',
'#....#........#............................................#',
'#....##########............................................#',
'#..........................................................#',
'#..........................................................#',
'#..........................................................#',
'#..........................................................#',
'#..........................................................#',
'#...............................##############.............#',
'#...............................#........E...#.............#',
'#...............................#............#.............#',
'#...............................#............#.............#',
'#...............................#............#.............#',
'#...............................###########..#.............#',
'#..........................................................#',
'#..........................................................#',
'############################################################']
$sprite = Sprite.new
$sprite.bitmap = Bitmap.new(($tm[0].size + 1) * 15,($tm.size + 1) * 20)
for i in 0...$tm.size
for j in 0...$tm[i].size
$sprite.bitmap.draw_text(j * 15,i * 20,15,20,$tm[i][j].chr,1)
end
end
p "start"
Graphics.update
#因为python里string不能直接改变某一元素，所以用test_map来存储搜索时的地图
$test_map = []
#########################################################
class Node_Elem
#开放列表和关闭列表的元素类型，parent用来在成功的时候回溯路径
attr_accessor:parent
attr_accessor:x
attr_accessor:y
attr_accessor:dist
def initialize(parent, x, y, dist)
@parent = parent
@x = x
@y = y
@dist = dist
end
end
class A_Star
#A星算法实现类
attr_accessor:s_x
attr_accessor:s_y
attr_accessor:e_x
attr_accessor:e_y
attr_accessor:width
attr_accessor:height
attr_accessor:open
attr_accessor:close
attr_accessor:path
#注意w,h两个参数
#如果你修改了地图，需要传入一个正确值或者修改这里的默认参数
def initialize(s_x, s_y, e_x, e_y, w=60, h=30)
@s_x = s_x
@s_y = s_y
@e_x = e_x
@e_y = e_y
@width = w
@height = h
@open = []
@close = []
@path = []
end
#查找路径的入口函数
def find_path()
#构建开始节点
p = Node_Elem.new(nil, @s_x, @s_y, 0.0)
loop do
#扩展F值最小的节点
extend_round(p)
#如果开放列表为空，则不存在路径，返回
if not @open
return
end
#获取F值最小的节点
idx, p = get_best()
#找到路径，生成路径，返回
if is_target(p)
make_path(p)
return
end
#把此节点压入关闭列表，并从开放列表里删除
@close.push(p)
@open.delete_at(idx)
end
end
def make_path(p)
#从结束点回溯到开始点，开始点的parent == None
while p
@path.push([p.x, p.y])
p = p.parent
end
end
def is_target(i)
return true if i.x == @e_x and i.y == @e_y
end
def get_best()
best = nil
bv = 1000000 #如果你修改的地图很大，可能需要修改这个值
bi = -1
for idx in 0...@open.size
value = get_dist(@open[idx])#获取F值
if value < bv#比以前的更好，即F值更小
best = @open[idx]
bv = value
bi = idx
return bi, best
end
end
end
def get_dist(i)
# F = G + H
# G 为已经走过的路径长度， H为估计还要走多远
# 这个公式就是A*算法的精华了。
return i.dist+Math.sqrt((@e_x-i.x)*(@e_x-i.x)+(@e_y-i.y)*(@e_y-i.y))*1.2
end
def extend_round(p)
#可以从8个方向走
#xs = (-1, 0, 1, -1, 1, -1, 0, 1)
#ys = (-1,-1,-1, 0, 0, 1, 1, 1)
xys = [[-1,-1],[0,-1],[1,-1],[-1,0],[1,0],[-1,1],[0,1],[1,1]]
#只能走上下左右四个方向
# xs = (0, -1, 1, 0)
# ys = (-1, 0, 0, 1)
#xys = [[0,-1],[-1,0],[1,0],[0,1]]
for x_y in xys
x = x_y[0]
y = x_y[1]
new_x, new_y = x + p.x, y + p.y
#无效或者不可行走区域，则勿略
if !is_valid_coord(new_x, new_y)
next
end
#构造新的节点
node = Node_Elem.new(p,new_x,new_y,p.dist+get_cost(p.x,p.y,new_x,new_y))
#新节点在关闭列表，则忽略
if node_in_close(node)
next
end
i = node_in_open(node)
if i != -1
#新节点在开放列表
if @open[i].dist > node.dist
#现在的路径到比以前到这个节点的路径更好~
#则使用现在的路径
@open[i].parent = p
@open[i].dist = node.dist
end
next
end
@open.push(node)
end
end
def get_cost(x1, y1, x2, y2)
#上下左右直走，代价为1.0，斜走，代价为1.4
if x1 == x2 or y1 == y2
return 1.0
end
return 1.4
end
def node_in_close(node)
for i in @close
if node.x == i.x and node.y == i.y
return true
end
end
return false
end
def node_in_open( node)
for i in 0...@open.size
n = @open[i]
if node.x == n.x and node.y == n.y
return i
end
end
return -1
end
def is_valid_coord(x, y)
if x < 0 or x >= @width or y < 0 or y >= @height
return false
end
return true if $test_map[y][x].chr != '#'
end
def get_searched()
l = []
for i in @open
l.push([i.x, i.y])
end
for i in @close
l.push([i.x, i.y])
end
return l
end
end
#########################################################
def print_test_map()
#打印搜索后的地图
$sprite2 = Sprite.new
$sprite2.bitmap = $sprite.bitmap.clone
$sprite2.bitmap.clear
for i in 0...$test_map.size
for j in 0...$test_map[i].size
$sprite2.bitmap.draw_text(j * 15,i * 20,15,20,$test_map[i][j].chr,1)
end
end
for i in 0...1200
Graphics.update
end
end
def get_start_XY()
return get_symbol_XY('S')
end
def get_end_XY()
return get_symbol_XY('E')
end
def get_symbol_XY(s)
for y in 0...$test_map.size
line = $test_map[y]
if line.include?(s)
x = line.index(s)
break
else
next
end
end
return x, y
end
#########################################################
def mark_path(l)
mark_symbol(l, '*')
end
def mark_searched(l)
mark_symbol(l, ' ')
end
def mark_symbol(l, s)
for p in l
x = p[0]
y = p[1]
$test_map[y][x] = s
end
end
def mark_start_end(s_x, s_y, e_x, e_y)
$test_map[s_y][s_x] = 'S'
$test_map[e_y][e_x] = 'E'
end
def tm_to_test_map()
for line in $tm
$test_map.push(line)
end
end
def find_path()
s_x, s_y = get_start_XY()
e_x, e_y = get_end_XY()
a_star = A_Star.new(s_x, s_y, e_x, e_y)
a_star.find_path()
searched = a_star.get_searched()
path = a_star.path
#标记已搜索区域
mark_searched(searched)
#标记路径
mark_path(path)
print "path length is %d"%(path.size)
print "searched squares count is %d"%(searched.size)
#标记开始、结束点
mark_start_end(s_x, s_y, e_x, e_y)
end
#把字符串转成列表
tm_to_test_map()
find_path()
print_test_map()

复制代码

致使算法而已。。。原作是python写的。。我给做成RUBY的

酆城浪子 · 发表于 2010-1-10 22:56:01

说实话，如果只是任务寻找NPC的自动寻路用场所移动在方便不过了，没冲突，无伤害，不复杂，不用等移动时间，越大的地图越好使

另外，楼主想要的话我分享的那个洋娃娃整合的系统里面有自动移动脚本。

http://www.vdisk.cn/down/index/3988407A7771/洋娃娃整合系统A.rar.html

复制全部地址，打开就能进下载界面了

		自动登录	找回密码
密码			立即注册

[RMXP] 那个自动寻路要怎么做呀