コード晒し祭[2] パックマン

パックマンは手で解いた。これも結局は経路探索問題で、他の問題を解いてから最適解の探索をさせようと思っていたらあっというまに締め切りが来てしまって残念なことに。google的にはゲーム作るよりそっちのがメインだろって話で、手で解いたところであんまり評価はされないのかなあ。

まあこれで自分の作れるゲームがPONGとテトリスの他に一個増えたことを喜ぶべきなのだろう。

画面に関しては当初はruby-SDLを使おうかと思っていたんだけどMacPortsをいろいろするのが面倒なのとcurses使った方が手軽だったのであっさりと妥協した。せめてカラー化すべきだった。

ゲーム終了時に操作履歴をputsしているので、適当にコピー&ペーストするとプレイ内容が再現されるのがちょっと面白かった。他の方は「uでアンドゥ」といった機能を搭載されたようで、今になって思うとそういう便利な機能を思いつけなかった自分の至らなさに情けなくなる。

#!/usr/bin/ruby
# -*- coding: utf-8 -*-

require 'curses'

DIR_U = 0
DIR_R = 1
DIR_D = 2
DIR_L = 3
DIR_NONE = 4

#============================================================================
class Player 
  attr_reader :x, :y

  def initialize(g_, x_, y_)
    @game, @x, @y = g_, x_, y_

    @lastx = @x
    @lasty = @y
  end

  def pos
    [@x, @y]
  end

  def lastPos
    [@lastx, @lasty]
  end

  def move(c)
    vx, vy = 0, 0

    if     c==?k
      # UP 
      vx, vy =  0, -1
    elsif  c==?l
      # RIGHT
      vx, vy =  1,  0
    elsif  c==?j
      # DOWN
      vx, vy =  0,  1
    elsif  c==?h
      # LEFT
      vx, vy = -1,  0
    elsif c == ?.
      vx, vy =  0,  0
    end

    if isAccessible(@x+vx, @y+vy)
      @lastx, @lasty = @x, @y
      @x, @y = @x+vx, @y+vy
      return true
    end
    false
  end

  def isAccessible(x, y)
    @game.isAccessible(x,y)
  end

  def draw
    Curses.setpos @y, @x
    Curses.addch ?@
  end

end

#============================================================================
class Monster
  attr_reader :x, :y

  def initialize(g_, x_, y_)
    @game, @x, @y = g_, x_, y_
    @dir = DIR_NONE
    @dir_last = DIR_NONE

    @lastx = @x
    @lasty = @y
  end

  def pos
    [@x, @y]
  end

  def lastPos
    [@lastx, @lasty]
  end

  def move(t, px, py)

    @lastx, @lasty = @x, @y

    if t==0
      @dir = move0
    else
      @dir = move1(px, py)
    end

    if @dir    == DIR_U
      @y -= 1
    elsif @dir == DIR_R
      @x += 1
    elsif @dir == DIR_D
      @y += 1
    elsif @dir == DIR_L
      @x -= 1
    end

    @dir_last = @dir
  end

  def move0
    dirs = @game.getTiles(@x, @y)
    if    dirs[DIR_D] != ?#
      return DIR_D
    elsif dirs[DIR_L] != ?#
      return DIR_L
    elsif dirs[DIR_U] != ?#
      return DIR_U
    elsif dirs[DIR_R] != ?#
      return DIR_R
    end
  end

  def move1(px, py)
    cw = @game.countWall(@x, @y)

    if cw == 3 # 行き止まりマス
      dirs = @game.getTiles(@x, @y)
      return DIR_D if dirs[DIR_D] != ?#
      return DIR_L if dirs[DIR_L] != ?#
      return DIR_U if dirs[DIR_U] != ?#
      return DIR_R if dirs[DIR_R] != ?#
      exit 0 # ERROR
      
    elsif cw == 2  # 通路マス
      # 前にいたマス以外のマスへ移動する
      dirs = @game.getTiles(@x, @y)
      dirs[(@dir_last+2)%4] = ?#  # 元々来た道へ戻らないように壁に見せかける

      return DIR_D if dirs[DIR_D] != ?#
      return DIR_L if dirs[DIR_L] != ?#
      return DIR_U if dirs[DIR_U] != ?#
      return DIR_R if dirs[DIR_R] != ?#
      exit 0 # ERROR

    else # 1,0 (0は存在しないはず) 交差点マス
      return move_cross(px, py)
    end
  end

  def draw
    Curses.setpos @y, @x
    Curses.addstr @type
  end

  # ------------------------------
  def Monster.AI_V(dirs, x, y, px, py)
    dx = px-x # > 0? 1: px-x < 0? -1 : 0
    dy = py-y # > 0? 1: py-y < 0? -1 : 0

    return DIR_U if dy < 0 && dirs[DIR_U] != ?#
    return DIR_D if dy > 0 && dirs[DIR_D] != ?#

    return DIR_L if dx < 0 && dirs[DIR_L] != ?#
    return DIR_R if dx > 0 && dirs[DIR_R] != ?#

    return DIR_D if dirs[DIR_D] != ?#
    return DIR_L if dirs[DIR_L] != ?#
    return DIR_U if dirs[DIR_U] != ?#
    return DIR_R if dirs[DIR_R] != ?#
    exit 0 # ERROR
  end

  # ------------------------------
  def Monster.AI_H(dirs, x, y, px, py)
    dx = px-x
    dy = py-y

    return DIR_L if dx < 0 && dirs[DIR_L] != ?#
    return DIR_R if dx > 0 && dirs[DIR_R] != ?#

    return DIR_U if dy < 0 && dirs[DIR_U] != ?#
    return DIR_D if dy > 0 && dirs[DIR_D] != ?#

    return DIR_D if dirs[DIR_D] != ?#
    return DIR_L if dirs[DIR_L] != ?#
    return DIR_U if dirs[DIR_U] != ?#
    return DIR_R if dirs[DIR_R] != ?#
    exit 0 # ERROR
  end

  # ------------------------------
  def Monster.AI_L(dir, dirs, x, y, px, py)
    d = [ (dir-1+4) % 4, dir, (dir+1)%4]
    return d[0] if dirs[d[0]] != ?#
    return d[1] if dirs[d[1]] != ?#
    return d[2] if dirs[d[2]] != ?#
    exit 1 # ERROR
  end

  # ------------------------------
  def Monster.AI_R(dir, dirs, x, y, px, py)
    d = [ (dir+1) % 4, dir, (dir-1+4)%4]
    return d[0] if dirs[d[0]] != ?#
    return d[1] if dirs[d[1]] != ?#
    return d[2] if dirs[d[2]] != ?#
    exit 1 # ERROR
  end

end

# --------------------------------------------------
class MonsterV < Monster

  def move_cross(px, py)
    dirs = @game.getTiles(@x, @y)
    return  Monster.AI_V(dirs, @x, @y, px, py)
  end

  def draw
    Curses.setpos @y, @x
    Curses.addch ?V
  end

end

# --------------------------------------------------
class MonsterH < Monster
  def move_cross(px, py)
    dirs = @game.getTiles(@x, @y)
    return Monster.AI_H(dirs, @x, @y, px, py)
  end

  def draw
    Curses.setpos @y, @x
    Curses.addch ?H
  end
end

# --------------------------------------------------
class MonsterR < Monster
  def move_cross(px, py)
    dirs = @game.getTiles(@x, @y)
    return Monster.AI_R(@dir_last, dirs, @x, @y, px, py)
  end

  def draw
    Curses.setpos @y, @x
    Curses.addch ?R
  end
end

# --------------------------------------------------
class MonsterL < Monster
  def move_cross(px, py)
    dirs = @game.getTiles(@x, @y)
    return Monster.AI_L(@dir_last, dirs, @x, @y, px, py)
  end

  def draw
    Curses.setpos @y, @x
    Curses.addch ?L
  end
end

# --------------------------------------------------
class MonsterJ < Monster
  def initialize(g_, x_, y_)
    super g_, x_, y_
    @turn = 0
  end

  def move_cross(px, py)
    dirs = @game.getTiles(@x, @y)
    d = 0
    if @turn == 0
      d = Monster.AI_L(@dir_last, dirs, @x, @y, px, py)
    else
      d = Monster.AI_R(@dir_last, dirs, @x, @y, px, py)
    end
    @turn = (@turn==0)? 1 : 0
    d
  end

  def draw
    Curses.setpos @y, @x
    Curses.addch ?J
  end
end


# --------------------------------------------------
class Game
  attr_reader :route

  def initialize
    @t            = 0
    @field_width  = 0
    @field_height = 0
    @field        = nil
    @player       = nil
    @monsters     = nil
    @route = nil

  end

  def load(path)
    @route = nil
    @t = 0
    @limit = 0
    @player = nil
    @monsters = Array.new
    @field = Array.new
    open(path) { |f|
      @limit        = f.gets.to_i
      @field_width, @field_height = f.gets.split(" ")
      @field_width  = @field_width.to_i
      @field_height = @field_height.to_i
      y=0
      while line = f.gets
        # フィールド解析。V,H,L,R,J,@
        (0...line.length).each { |x|
          if    line[x] == ?V
            @monsters << MonsterV.new(self, x, y)
            line[x] = ' '
          elsif line[x] == ?H
            @monsters << MonsterH.new(self, x, y)
            line[x] = ' '
          elsif line[x] == ?L
            @monsters << MonsterL.new(self, x, y)
            line[x] = ' '
          elsif line[x] == ?R
            @monsters << MonsterR.new(self, x, y)
            line[x] = ' '
          elsif line[x] == ?J
            @monsters << MonsterJ.new(self, x, y)
            line[x] = ' '
          elsif line[x] == ?@
            @player = Player.new(self, x, y)
            line[x] = ' '
          end
        }

        @field << line
        y += 1
      end
    }

  end


  def draw
    y=0
    Curses.clear
    @field.each { |line|
      line.each_byte { |c|
        Curses.addch c
      }
      y += 1
    }

    @monsters.each { |monster|
      monster.draw
    }

    @player.draw

    Curses.setpos 0, @field_width + 4
    Curses.addstr "time : #{@t} / #{@limit}"

    Curses.setpos 1, @field_width + 4
    Curses.addstr "dots last = #{countDots}"
   
  end

  def countDots
    count = 0
    @field.each { |line|
      line.each_byte { |c|
        count += 1 if c == ?.
      }
    }
    count
  end

  def move(c)
    px, py = @player.x, @player.y
    ret = @player.move c
    return false if ret == false

    @monsters.each { |monster|
      monster.move @t, px, py
    }
    true
  end

  def isAccessible(x,y)
    return false if @field[y][x] == ?#
    true
  end

  def update
    # erase dot
    if @field[@player.y][@player.x] == ?.
      @field[@player.y][@player.x] = ' '
    end
  end

  def timeover?
    return (@limit <= @t)? true : false
  end

  def getTiles(x,y)
    return [@field[y-1][x], @field[y][x+1], @field[y+1][x], @field[y][x-1]]
  end

  def countWall(x, y)
    c = 0
    c+= 1 if @field[y-1][x  ] == ?#
    c+= 1 if @field[y  ][x+1] == ?#
    c+= 1 if @field[y+1][x  ] == ?#
    c+= 1 if @field[y  ][x-1] == ?#
    c
  end

  def run
    captured = false

    @route = Array.new
    draw
    while @t < @limit && 0 < countDots  

      playerLastPos = [@player.x, @player.y]
      monsterLastPos = Array.new
      @monsters.each { |m|
        monsterLastPos << [m.x, m.y]
      }

      c = Curses.getch

      exit 0 if c==?q

      next if c!=?h && c!=?j && c!=?k && c!=?l && c!=?.

      ret = move c

      next if ret == false

      @route << c

      @t += 1
      update

      # collison
      captured = false

      @monsters.each { |m|
        captured = true if [@player.x, @player.y] == [m.x, m.y]
        captured = true if @player.pos == m.lastPos && @player.lastPos == m.pos
      }

      break if captured
      draw
    end

    Curses.clear
    if captured
      Curses.addstr "captured.."

    elsif countDots == 0
      Curses.addstr "clear!"

    elsif timeover?
      Curses.addstr "time over"
    end

    c = Curses.getch

  end

end


#
#
#

route = nil

begin
  Curses::init_screen
  Curses::noecho
  game = Game.new
  game.load("q#{ARGV[0].to_i}.txt")

  game.run

  route =  game.route.pack("C*")

ensure
  Curses.close_screen

  puts route
end

実行は

ruby pacman.rb 3

とか。問題はq3.txtなどとしてファイルに入れておいた。

700
58 17
##########################################################
#........................................................#
#.###.#########.###############.########.###.#####.#####.#
#.###.#########.###############.########.###.#####.#####.#
#.....#########....J.............J.......###.............#
#####.###.......#######.#######.########.###.#######.#####
#####.###.#####J#######.#######.########.###.##   ##.#####
#####.###L#####.##   ##L##   ##.##    ##.###.##   ##.#####
#####.###..H###.##   ##.##   ##.########.###.#######J#####
#####.#########.##   ##L##   ##.########.###.###V....#####
#####.#########.#######.#######..........###.#######.#####
#####.#########.#######.#######.########.###.#######.#####
#.....................L.........########..........R......#
#L####.##########.##.##########....##....#########.#####.#
#.####.##########.##.##########.##.##.##.#########.#####.#
#.................##............##..@.##...............R.#
##########################################################