スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[Ruby]幅優先の経路探索を作ってみた

現在作ってるダンジョンゲーム内で迷路を作ろうと思い立ち、迷路なら経路探索だと単純な思考と勢いで幅優先探索を書いてみました。

以下ルール。
・部屋のサイズはダンジョン内で生成する一般的なサイズの部屋(大部屋とかどうしようかねぇ)
・斜め移動あり
・一度チェックした場所はチェックしないという意外枝刈り無し
・迷路の解が無いという状況は考慮しない
・最適解じゃなくても気にしない
・マップはCSVを読み込む(使ってみたかっただけ。あと、多次元配列としてそのまま読み込めるのが素敵)

……適当ですね。こんなコードになりました。
require 'csv'

class BreadthFirstSearch
def initialize(map)
@map = map
@w = @map[0].length
@h = @map.length
# すでに訪れたかどうか
@visited = Array.new(@h){Array.new(@w, false)}
# 直前の位置(x, y)を[-1, -1]で初期化
@before = Array.new(@h){Array.new(@w){Array.new(2){-1}}}
end

def find_start
@map.each_index do |i|
@map[i].each_index do |j|
return [i, j] if @map[i][j] == "S"
end
end
end

def goal_search
baf = Array.new
baf[0] = find_start
@visited[baf[0][0]][baf[0][1]] = true
while !baf.empty?
pt = baf.shift
for i in [-1, 0, 1]
for j in [-1, 0, 1]
next if i == 0 && j == 0
x = pt[1] + j
y = pt[0] + i
# 訪問してなくて、壁じゃない地点の場合、直前の地点を記録
if @visited[y][x] == false && @map[y][x] != "*"
@before[y][x][0] = pt[0]
@before[y][x][1] = pt[1]
# ゴールの場合、終了
if @map[y][x] == "G"
goal = [y, x]
return goal
else
# スペースの場合、キューに入れて訪問済みに
baf << [y, x]
@visited[y][x] = true
end
end
end
end
end
end

# ゴール地点を取得し、@beforeを遡る
def search
goal = goal_search
puts "ゴール位置:X = #{goal[1]}, Y = #{goal[0]}"
while true
goal = [@before[goal[0]][goal[1]][0], @before[goal[0]][goal[1]][1]]
break if @map[goal[0]][goal[1]] != nil
@map[goal[0]][goal[1]] = "$"
end
debug
end

def debug
@map.each do |i|
i.each do |j|
if j == nil
print " "
elsif j == "S"
print "S"
elsif j == "G"
print "G"
elsif j == "*"
print "■"
elsif j == "$"
print "$"
end
end
puts
end
end
end


map = CSV.readlines("map.csv")
map.each do |i|
i.each do |j|
if j == nil
print " "
elsif j == "S"
print "S"
elsif j == "G"
print "G"
elsif j == "*"
print "■"
end
end
puts
end

b = BreadthFirstSearch.new(map)
b.search


で、結果がこんな感じ。
■■■■■■■■■■■■■■
■S■          ■
■ ■          ■
■            ■
■■■■■■  ■■■■■■
■            ■
■■■  ■■■■■■■■■
■         G  ■
■■■■■■■■■■■■■■
ゴール位置:X = 10, Y = 7
計算時間: 0.00542722608599696 sec
■■■■■■■■■■■■■■
■S■          ■
■$■$$        ■
■ $  $       ■
■■■■■■$ ■■■■■■
■    $       ■
■■■ $■■■■■■■■■
■    $$$$$G  ■
■■■■■■■■■■■■■■

うーん、ちょっと時間がかかりすぎる。
思った以上に配列をシフトorプッシュするコストがかかってるってことかな。
ちなみに時間はこちらにあるHPCモジュールを使って測定させていただきました。多謝。

まだまだ勉強が足りないようです。次はA*かな。
スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

[書評][人工知能]恋するコンピュータ

恋するコンピュータ (ちくま文庫)恋するコンピュータ (ちくま文庫)
(2008/08/06)
黒川 伊保子

商品詳細を見る


あなたの傍らに寄り添って、あなたと同じ世界を見ている。電子空間を探索しながら、あなたがもっとも必要とする情報を見つけだす。あなたとかろやかに交歓し、時には悩みを聞いてくれる。分身にして有能なパートナー。そんなコンピュータはいかが?



そんなくだりで始まる本書は、専門的な用語を一切使うことなく、情感とイメージで人工知能の可能性を訴えかけてくれます。

自身の研究と子育ての経験に基づいて書かれている本書は、「鉄腕アトムなんていらない」、「知識獲得エンジン」など興味深い内容ばかり。ただ、それをどう実装するのかという論点には本書はなっていないので、それを望む人には少々物足りないかも。

長門やマルチ(古い?)を自らの手で作り出すのは人類永遠の夢。

あなたも本書でその夢を見てみませんか?

テーマ : ブックレビュー - ジャンル : 小説・文学

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。