module BFS
def self.find_path(character, tx, ty)
ox, oy = character.x, character.y
return if (tx > $game_map.width - 1) || (ty > $game_map.height - 1)
return if !($game_map.passable?(tx, ty, 0, character))
return if (tx == ox) && (ty == oy)
checked = []
father = []
for i in 0...$game_map.width
checked << []
father << []
for j in 0...$game_map.height
checked[-1] << 0
father[-1] << nil
end
end
path = []
found = false
checked[ox][oy] = 1
empty = false
loop do
empty = true
for i in 0...$game_map.width
for j in 0...$game_map.height
if checked[i][j] == 1
checked[i][j] = 2
if $game_map.passable?(i, j + 1, 2, character) &&
checked[i][j + 1] == 0
checked[i][j + 1] = 1
father[i][j + 1] = [i, j]
end
if $game_map.passable?(i - 1, j, 4, character) &&
checked[i - 1][j] == 0
checked[i - 1][j] = 1
father[i - 1][j] = [i, j]
end
if $game_map.passable?(i, j - 1, 8, character) &&
checked[i][j - 1] == 0
checked[i][j - 1] = 1
father[i][j - 1] = [i, j]
end
if $game_map.passable?(i + 1, j, 6, character) &&
checked[i + 1][j] == 0
checked[i + 1][j] = 1
father[i + 1][j] = [i, j]
end
end
if checked[tx][ty] == 1
found = true
break
end
end
end
for i in 0...$game_map.width
empty = false if checked[i].include?(1)
end
if found || empty
break
end
end
return if !found
if found
x, y = tx, ty
while [x, y] != [ox, oy]
dx, dy = father[x][y][0] - x, father[x][y][1] - y
step = 2 if dy == -1
step = 4 if dx == 1
step = 8 if dy == 1
step = 6 if dx == -1
path << step
x, y = father[x][y][0], father[x][y][1]
end
path.reverse!
end
list = []
path.each{|e|
code = 1 if e == 2
code = 2 if e == 4
code = 4 if e == 8
code = 3 if e == 6
list << RPG::MoveCommand.new(code)
}
list << RPG::MoveCommand.new(0)
skippable = false
repeat = false
commands = RPG::MoveRoute.new
commands.skippable = skippable
commands.repeat = repeat
commands.list = list
if character == nil
return true
end
character.force_move_route(commands)
return true
end
end
FindPath.rar
(192.79 KB, 下载次数: 389)
