ダンジョンの最短ルートを求めてみる（with RDGC）
きっかけはこの記事です
makeplex salon：あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ
この記事経由で元ネタを見に行きました
（エピソードそのものは知っていたものの、問題は初めて見ました）
人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか
「迷路を探索」というのが非常にRDGCに関連のある話だったので、
とりあえずこっちをやってみようと思ったのですが、
先日リリースしたrdgc-dmを使えば、問題の迷路は簡単に作れることに気づきまして
ちょうどrdgc-dmの使用サンプルにもなりますし、
こっちの問題を解いてみました
最終的なコードは後で全文を載せますが、
実際に動いている場所がこちらになります(´･ω･)っ
何度かリロードしてもらえればわかりますが、
生成したダンジョンの最短ルートを探索している・・・はずです
動いてなかったら教えてください
解くのにかかった時間は？
お昼を食べながらロジックを考えるのに30分、
実際のコーディング＋テスト＋設置で1時間くらいなので、
だいたい1時間半でしょうか
ただし、本来は迷路をテキストで入出力しなければならないので、
その分は上乗せされるはずです
まあ、それでも+20分以内で、全体で2時間以内だとは思いますが・・・
ロジックのポイント
ゴールへ向かうルートは非常に簡単で、
スタート地点から再帰的に求めればいいのですが、
いくつかポイントと思われるところを
- スタートから各座標までの最短ルートを求めるつもりで処理
- もっと短いlengthの値が来たら、Nodeを置き換えてしまう
- ゴールにたどり着いても、探索そのものは辞めない
- もっと短距離のルートがあるかもしれないから
最終的に、ゴールまでの最短距離が求まると同時に、
そこまでの最短距離平面ができあがるはずです
ここまでが#searchメソッドの処理で、
最大のポイントは「最短ルートを保証する」#cleaningメソッドの処理です
#searchでは各座標の最短距離を求めただけで、
経路としてどれが最短かはわかりません
しかし、ゴールの距離は一つに決まっているので、
例えばゴールのlengthが18であれば、
その隣に必ずlength=17の座標があるはずです
なので、length=17のNodeを全部引っ張り出し、
ゴールと接するものを残して全部破棄すれば、
length=17のNodeは一つに決まります
あとはこのNodeを元にlength=16のNode・・・というように、
再帰的に巻き戻していけば、スタートからゴールへの道が一つに決まり、
しかも最短であることも保証されるわけです(｀･ω･´) ｂ
でも、たぶん原文でいうところのLv3にしか到達してない気がします
実は、このダンジョンは道主体で生成していて、
部屋が大量になると、探索にかなり時間がかかってしまうのです
（スペースがたくさんあると〜に該当？）
RDGCに限っていえば解決策はある*1のですが、
それは原題からずれてくるので、結果的にLv3ですかね
余談：じゃあ、この処理をRDGCの索敵ロジックに入れれば？
結論から言えば、ありえません
計算量が多すぎて、このロジックでは使い物になりません
そもそも、RDGC・・・というか、ゲームの中で敵が探すものは、
モンスターだけではありません
敵が混乱して同士討ちなんてのはRPGなら普通にありますし、
ROでいうところの「ルートモンスター」ならば、
落ちているアイテムを拾いに行くかもしれません
なにより、RDGCの索敵で欲しいのは「次の一歩をどっちにするか」だけで、
ある対象までの完全な経路ではないので、
ここまで厳密な処理はいらないのです
実際の処理はRDGC Ver0.1に含まれる「StrategyBoard」クラスが担当してますが、
これもリファクタリングしたい部分なので、
SourceForge.JPで確認する方は、現段階での参考程度で
追記
Blogを書きながらもうちょっといいコードを思いついた・・・
まあ、制限時間内にって縛りがあるので、今回はこれで
＜改善案＞
- queueではなく、StrategyBoardのように平面に距離を埋める処理に
- hash[x][y]で距離を導けるので、queueをselectするより相当コストが低くなる
- 一度でもゴールにたどり着いたら、その距離を超える探索を全て中断
- それ以上はどうせ消すし
以下、解答コード
解答コード
長いですが、全文を
# http://www.parrot-studio.com/cgi-bin/d_test_r/solve_test.rb #!/usr/bin/ruby -- # coding: UTF-8 require 'rubygems' HTML = <<EOF Content-type: text/html <html> <head> <title>Random Dungeon Resolve Test (with rdgc-dm 0.1.0)</title> </head> <body> <h2>Random Dungeon Resolve Test (with rdgc-dm 0.1.0)</h2> see:<a href="http://github.com/parrot-studio/rdgc-dm" target="_blank">http://github.com/parrot-studio/rdgc-dm</a><br/> <br /> o:経路 X:壁 .:通路 ・:部屋<br/> <hr /> EOF # ---- 準備 ----------------------------------------------------------- # 迷路を作るgem require 'rdgc-dm' ######################################## # RDGCからコードを拝借 # rdgc-dm 0.2以降には含まれるはずなので、その場合は削除 module RDGC module Map class Direction attr_reader :x, :y private def self.create(x, y) obj = self.new obj.instance_eval do @x = x @y = y end obj.freeze obj end public SELF = self.create(0, 0) LEFT = self.create(-1, 0) RIGHT = self.create(1, 0) UPPER = self.create(0, -1) BOTTOM = self.create(0, 1) def self.each return to_enum(:each) unless block_given? self.all.each do |d| yield(d) end end def self.all [LEFT, UPPER, RIGHT, BOTTOM] end def apply_to(sx, sy, times = 1) times = 1 if times <= 0 [sx + (self.x * times), sy + (self.y * times)] end def opposite case self when LEFT RIGHT when RIGHT LEFT when UPPER BOTTOM when BOTTOM UPPER when SELF SELF end end end end end ######################################## # ---- 解答 ----------------------------------------------------------- class Node attr_accessor :x, :y, :length def self.create(x, y, l) obj = self.new obj.x = x obj.y = y obj.length = l obj end def equal_point?(node) return false unless self.x == node.x return false unless self.y == node.y true end def point?(x, y) return false unless self.x == x return false unless self.y == y true end end class DungeonDrifter def execute(width, height, param = nil) # 迷路作成 @board = RDGC::Maker::DivideDungeonMaker.create(width, height, param) # スタートとゴール rooms = @board.rooms.dup @sx, @sy = rooms.pickup!.random_point @gx, @gy = rooms.pickup!.random_point # ノードqueue @node_queue = [] @node_queue << Node.create(@sx, @sy, 0) @end_queue = [] # 探索 search # 最短のみにクリーニング creaning # 出力 view end def search loop do # 全経路終わったか？ break if @node_queue.empty? # queueからnodeを出す node = @node_queue.shift @end_queue << node # nodeがゴールならこの経路は完了 # 他の最短経路があるかもしれないので続行 next if @gx == node.x && @gy == node.y # 周囲の道をqueueに入れる RDGC::Map::Direction.each do |dir| # 次の座標 dx = node.x + dir.x dy = node.y + dir.y # 道がないなら無視 next unless @board.movable?(dx, dy) # 次のnode生成 next_node = Node.create(dx, dy, node.length + 1) # queueに同じ座標があるか？ eql_points = @end_queue.select{|n| n.equal_point?(next_node)} if eql_points.size > 0 # 距離を比較して、小さいものだけ残す list = [eql_points, next_node].flatten.sort_by(&:length) min_node = list.shift # 残りは削除 list.each{|n| @end_queue.delete(n)} # もう最短の距離が分かっていれば処理しない next if min_node.length <= next_node.length @node_queue << next_node else # 次の処理へ @node_queue << next_node end end end # 最短のゴールを探す @goal_point = @end_queue.select{|n| n.point?(@gx, @gy)}.min_by{|n| n.length} return unless @goal_point # これより大きいnodeは全削除 @end_queue.delete_if{|n| n.length >= @goal_point.length} @end_queue << @goal_point end # end search def creaning # ゴールにたどり着けなかった unless @goal_point @end_queue = [] return end # この時点でgoalより遠いnodeは存在しない # が、途中の経路にゴミがある # よって、goalから逆にたどって一つの経路を確定させる _creaning(@goal_point) end # end creaning def _creaning(prev) len = prev.length - 1 return if len <= 0 # 一つ前のlengthのnodeを全部出す nodes = @end_queue.select{|n| n.length == len} # 前のnodeに隣接しているか？ next_node = nil nodes.each do |node| RDGC::Map::Direction.each do |dir| dx = node.x + dir.x dy = node.y + dir.y next unless prev.point?(dx, dy) next_node = node break end break if next_node end raise "node not found => #{len}" unless next_node # 一つだけnodeを残す nodes.each{|n| @end_queue.delete(n)} @end_queue << next_node # 再帰処理 _creaning(next_node) end def view print HTML print"<table>" @board.each_y do |y| print"<tr>" @board.each_x do |x| # start & goal if @sx == x && @sy == y print "<td bgcolor='pink'>S</td>" next end if @gx == x && @gy == y print "<td bgcolor='pink'>G</td>" next end # 経路 if @end_queue.any?{|n| n.point?(x, y)} print "<td bgcolor='pink'>o</td>" next end # それ以外 case @board.tile(x, y) when RDGC::Map::TileType::WALL print "<td bgcolor='#aaaaaa'>X</td>" when RDGC::Map::TileType::ROOM print "<td bgcolor='white'>・</td>" when RDGC::Map::TileType::ROAD print "<td bgcolor='#eeeeee'>.</td>" end end print"</tr>" end print "</table></body></html>" end end # 最小サイズの部屋を2つ作って、残りBlockは道に # 普通にRoomを作ってしまうと、Webではとても公開できない遅さに DungeonDrifter.new.execute(40, 40, :max_room_count => 2, :max_room_size => 4, :cross_road_ratio => 9)
