ブレゼンハムの線分アルゴリズムを用いた追跡

ゲーム開発者のためのAI入門に載ってたタイルベースのLOS追跡アルゴリズムをRubyで。
まずは下準備としてタイルを表現するクラスを準備。

class Tile    
  def initialize(x, y)
    @cel = []  
    (0..y).each do |i|
      @cel[i] = Array.new(x, 0)
    end
  end
  
  def set_value(x, y, value)
    @cel[y][x] = value
  end
  
  def show
    @cel.each do |row|
      p row
    end
  end
end

次に基本的な追跡アルゴリズムの時に使用したPlayerクラスを継承し、追跡を行うAIクラスを用意。build_path_to_target()にてブレゼンハムの線分アルゴリズムを用いて追跡パスを組み立てています。

class AI < Player
  private
  def build_path_to_target(prey)
    @path = []
    delta_x = prey.x - @x
    delta_y = prey.y - @y
    
    step_x = delta_x <=> 0
    step_y = delta_y <=> 0
            
    delta_x = (delta_x * 2).abs
    delta_y = (delta_y * 2).abs
    
    next_x = @x
    next_y = @y
    @path << {"x" => next_x, "y" => next_y}
    
    if delta_x > delta_y
      fraction = delta_y - delta_x / 2
      until next_x == prey.x do
        if fraction >= 0
          next_y += step_y
          fraction -= delta_x
        end
        next_x += step_x
        fraction += delta_y
        @path << {"x" => next_x, "y" => next_y}
      end
    else
      fraction = delta_x - delta_y / 2
      until next_y == prey.y do
        if fraction >= 0
          next_x += step_x
          fraction -= delta_y
        end
        next_y += step_y
        fraction += delta_x
        @path << {"x" => next_x, "y" => next_y}
      end      
    end    
  end

  public
  def make_strategy(prey)
    @step = 0
    build_path_to_target(prey)
  end
  
  def advance
    @x = @path[@step]["x"]
    @y = @path[@step]["y"]
    @step += 1
  end  
end

メインのスクリプトはこんな感じで。X_CONST とY_CONSTでタイルの大きさを決定します。

X_CONST = Y_CONST = 15

prey = Player.new(rand(X_CONST),rand(Y_CONST), 1)
predetor = AI.new(rand(X_CONST),rand(Y_CONST), 9)

tile = Tile.new(X_CONST, Y_CONST)
tile.set_value(predetor.x, predetor.y, predetor.mark)
predetor.make_strategy(prey)
until ((predetor.x == prey.x) and (predetor.y == prey.y))
  predetor.advance
  tile.set_value(predetor.x, predetor.y, predetor.mark)
end
tile.set_value(prey.x, prey.y, prey.mark)
tile.show

実行例（タイルサイズ10*10）。9が追跡者、1がターゲットをそれぞれ表しています。

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 9]
[0, 0, 0, 0, 0, 0, 0, 0, 9, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 9, 0]
[0, 0, 0, 0, 0, 0, 0, 9, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 9, 0, 0]
[0, 0, 0, 0, 0, 0, 9, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 9, 0, 0, 0]
[0, 0, 0, 0, 0, 9, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]