ぱろっと・すたじお

技術メモなどをまったりと / my site : http://parrot-studio.com/

ダンジョンの最短ルートを求めてみる(with RDGC)

きっかけはこの記事です


makeplex salon:あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ


この記事経由で元ネタを見に行きました
(エピソードそのものは知っていたものの、問題は初めて見ました)


人生を書き換える者すらいた。: 人材獲得作戦・4 試験問題ほか


「迷路を探索」というのが非常にRDGCに関連のある話だったので、
とりあえずこっちをやってみようと思ったのですが、
先日リリースしたrdgc-dmを使えば、問題の迷路は簡単に作れることに気づきまして


ちょうどrdgc-dmの使用サンプルにもなりますし、
こっちの問題を解いてみました


最終的なコードは後で全文を載せますが、
実際に動いている場所がこちらになります(´・ω・)っ


404 Not Found


何度かリロードしてもらえればわかりますが、
生成したダンジョンの最短ルートを探索している・・・はずです
動いてなかったら教えてください


解くのにかかった時間は?


お昼を食べながらロジックを考えるのに30分、
実際のコーディング+テスト+設置で1時間くらいなので、
だいたい1時間半でしょうか


ただし、本来は迷路をテキストで入出力しなければならないので、
その分は上乗せされるはずです
まあ、それでも+20分以内で、全体で2時間以内だとは思いますが・・・

ロジックのポイント


ゴールへ向かうルートは非常に簡単で、
スタート地点から再帰的に求めればいいのですが、
いくつかポイントと思われるところを

  • スタートから各座標までの最短ルートを求めるつもりで処理
    • もっと短いlengthの値が来たら、Nodeを置き換えてしまう
  • ゴールにたどり着いても、探索そのものは辞めない
    • もっと短距離のルートがあるかもしれないから

最終的に、ゴールまでの最短距離が求まると同時に、
そこまでの最短距離平面ができあがるはずです


ここまでが#searchメソッドの処理で、
最大のポイントは「最短ルートを保証する」#cleaningメソッドの処理です


#searchでは各座標の最短距離を求めただけで、
経路としてどれが最短かはわかりません


しかし、ゴールの距離は一つに決まっているので、
例えばゴールのlengthが18であれば、
その隣に必ずlength=17の座標があるはずです


なので、length=17のNodeを全部引っ張り出し、
ゴールと接するものを残して全部破棄すれば、
length=17のNodeは一つに決まります


あとはこのNodeを元にlength=16のNode・・・というように、
再帰的に巻き戻していけば、スタートからゴールへの道が一つに決まり、
しかも最短であることも保証されるわけです(`・ω・´) b


でも、たぶん原文でいうところの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)

*1:例:隣のBlockまでの距離を調べ、ダイクストラ法を適用する

広告を非表示にする