[QUIZ][SOLUTION] Re: Sokoban (#5)

ruby-talk
1

Well, that was fun.

Actually, my favourite part was doing

while level.move(EAST); end

and

7.times{level.move(WEST)}

in irb, before I built the CLI. I don't know why. It's interesting to use
Ruby directly to control a game.

So here is Dave's Cheap Ruby Sokoban:

http://www.dave.burt.id.au/ruby/sokoban.rb

That's cheap as in cheap beer and as in cheap speech, in case you were
wondering.

Standard Ruby, tested on 1.8.1, no dependencies apart from Sokoban levels:
get them from the Ruby Quiz place
http://www.grayproductions.net/ruby_quiz/sokoban_levels.txt
or my place
http://www.dave.burt.id.au/ruby/sokoban_levels.txt

(Note: These levels are Copyrighted by Thinking Rabbit. You may play them
but
not profit from them in any way.)

2

This looks like the makings of a Sokoban level solver to me. I was wondering if anyone would consider that for an extra feature... :slight_smile:

James Edward Gray II

···

On Nov 1, 2004, at 2:53 AM, Dave Burt wrote:

Well, that was fun.

Actually, my favourite part was doing

while level.move(EAST); end

and

7.times{level.move(WEST)}

in irb, before I built the CLI. I don't know why. It's interesting to use
Ruby directly to control a game.

3

Here is my very simple solution, you controll the player using WASD for moving up, left, down and right and R for restarting the game. It should run on any Ruby 1.8.

class Level
   def initialize(level)
     @level = level
   end

   def play
     while count_free_crates > 0
       printf "\n%s\n\n> ", self
       c = gets
       c.each_byte do |command|
         case command
           when ?w
             move(0, -1)
           when ?a
             move(-1, 0)
           when ?s
             move(0, 1)
           when ?d
             move(1, 0)
           when ?r
             return false
         end
       end
     end
     printf "\n%s\nCongratulations, on to the next level!\n", self
     return true
   end

private

   def move(dx, dy)
     x, y = find_player
     dest = self[x+dx, y+dy]
     case dest
       when ?#
         return
       when ?o, ?*
         dest2 = self[x+dx*2, y+dy*2]
         if dest2 == 32
           self[x+dx*2, y+dy*2] = ?o
         elsif dest2 == ?.
           self[x+dx*2, y+dy*2] = ?*
         else
           return
         end
         dest = (dest == ?o) ? 32 : ?.
     end
     self[x+dx, y+dy] = (dest == 32) ? ?@ : ?+
     self[x, y] = (self[x, y] == ?@) ? 32 : ?.
   end

   def count_free_crates
     @level.scan(/o/).size
   end

   def find_player
     pos = @level.index(/@|\+/)
     return pos % 19, pos / 19
   end

   def [](x, y)
     @level[x + y * 19]
   end

   def []=(x, y, v)
     @level[x + y * 19] = v
   end

   def to_s
     (0...16).map {|i| @level[i * 19, 19]}.join("\n")
   end
end

levels = File.readlines('sokoban_levels.txt')
levels = levels.map {|line| line.chomp.ljust(19)}.join("\n")
levels = levels.split(/\n {19}\n/).map{|level| level.gsub(/\n/, '')}

levels.each do |level|
   redo unless Level.new(level.ljust(19*16)).play
end

···

--
exoticorn/farbrausch

4

Here's my solution. The controls are as follows:

i - move up
j - move left
k - move right
m - move down

Q - quit
R - restart level

S - save game (you can only save one game at a time)
L - load last saved game

U - undo

I built a Sokoban module and two interfaces for it. One interface is for Unix terminals and the other is for those who have Ruby's OpenGL interface installed.

# === file: sokoban.rb ===

#!/usr/bin/env ruby

require "yaml"

class Sokoban
  WALL = "#"
  OPEN_FLOOR = " "

  MAN = "@"
  CRATE = "o"

  STORAGE = "."
  MAN_ON_STORAGE = "+"
  CRATE_ON_STORAGE = "*"

  MAX_UNDO = 10
  
  PATH = File.expand_path(File.dirname(__FILE__))
  
  attr_reader :level, :moves
  
  def self.load( file = File.join(PATH, "sokoban_saved_game.yaml") )
    game = nil

    File.open file do |f|
      game = YAML.load(f)
    end

    game ||= Sokoban.new
    game
  end
  
  def initialize( file = File.join(PATH, "sokoban_levels.txt") )
    @level_file = file

    @board = [ ]
    @level = 0
    @over = false
    
    @undos = [ ]
    @moves = 0
    
    load_level
  end
  
  def can_move_down?( ) can_move? :down end
  def can_move_left?( ) can_move? :left end
  def can_move_right?( ) can_move? :right end
  def can_move_up?( ) can_move? :up end
  
  def display
    @board.inject("") { |dis, row| dis + row.join + "\n" }
  end
  
  def level_solved?
    @board.each_with_index do |row, y|
      row.each_with_index do |cell, x|
        return false if cell == CRATE
      end
    end
    true
  end
  
  def load_level( level = @level += 1, file = @level_file )
    loaded = false

    File.open file do |f|
      count = 0
      while lvl = f.gets("")
        count += 1
        if count == level
          @board = [ ]
          lvl.chomp!
          lvl.each_line { |e| @board << e.chomp.split("") }
          loaded = true
          break
        end
      end
    end

    if loaded
      @undos = [ ]
      @moves = 0
    else
      @over = true
    end

    loaded
  end
  
  def move_down( ) move :down end
  def move_left( ) move :left end
  def move_right( ) move :right end
  def move_up( ) move :up end
  
  def over?
    @over
  end
  
  def restart_level
    load_level @level
  end
  
  def save( file = File.join(PATH, "sokoban_saved_game.yaml") )
    File.open(file, "w") do |f|
      f << YAML.dump(self)
    end
  end
  
  def undo
    if @undos.size > 0
      @board = @undos.pop
      @moves -= 1
    end
  end
  
  private
  
  def can_move?( dir )
    x, y = where_am_i
    case dir
    when :down
      first = @board[y + 1][x]
      second = y < @board.size - 2 ? @board[y + 2][x] : nil
    when :left
      first = @board[y][x - 1]
      second = x >= 2 ? @board[y][x - 2] : nil
    when :right
      first = @board[y][x + 1]
      second = x < @board[y].size - 2 ? @board[y][x + 2] : nil
    when :up
      first = @board[y - 1][x]
      second = y >= 2 ? @board[y - 2][x] : nil
    end

    if first == OPEN_FLOOR or first == STORAGE
      true
    elsif not second.nil? and
        (first == CRATE or first == CRATE_ON_STORAGE) and
        (second == OPEN_FLOOR or second == STORAGE)
      true
    else
      false
    end
  end
  
  def move( dir )
    return false unless can_move? dir
    
    @undos << Marshal.load(Marshal.dump(@board))
    @undos.shift if @undos.size > MAX_UNDO
    @moves += 1
    
    x, y = where_am_i
    case dir
    when :down
      if @board[y + 1][x] == CRATE or @board[y + 1][x] == CRATE_ON_STORAGE
        move_crate x, y + 1, x, y + 2
      end
      move_man x, y, x, y + 1
    when :left
      if @board[y][x - 1] == CRATE or @board[y][x - 1] == CRATE_ON_STORAGE
        move_crate x - 1, y, x - 2, y
      end
      move_man x, y, x - 1, y
    when :right
      if @board[y][x + 1] == CRATE or @board[y][x + 1] == CRATE_ON_STORAGE
        move_crate x + 1, y, x + 2, y
      end
      move_man x, y, x + 1, y
    when :up
      if @board[y - 1][x] == CRATE or @board[y - 1][x] == CRATE_ON_STORAGE
        move_crate x, y - 1, x, y - 2
      end
      move_man x, y, x, y - 1
    end
    true
  end
  
  def move_crate( from_x, from_y, to_x, to_y )
    if @board[to_y][to_x] == STORAGE
      @board[to_y][to_x] = CRATE_ON_STORAGE
    else
      @board[to_y][to_x] = CRATE
    end
    if @board[from_y][from_x] == CRATE_ON_STORAGE
      @board[from_y][from_x] = STORAGE
    else
      @board[from_y][from_x] = OPEN_FLOOR
    end
  end
  
  def move_man( from_x, from_y, to_x, to_y )
    if @board[to_y][to_x] == STORAGE
      @board[to_y][to_x] = MAN_ON_STORAGE
    else
      @board[to_y][to_x] = MAN
    end
    if @board[from_y][from_x] == MAN_ON_STORAGE
      @board[from_y][from_x] = STORAGE
    else
      @board[from_y][from_x] = OPEN_FLOOR
    end
  end
  
  def where_am_i
    @board.each_with_index do |row, y|
      row.each_with_index do |cell, x|
        return x, y if cell == MAN or cell == MAN_ON_STORAGE
      end
    end
  end
end

__END__

# === file: unix_term_sokoban.rb ===

#!/usr/bin/env ruby

require "sokoban"

def draw( g )
  screen = "Level #{g.level} - #{g.moves} moves\n\n" + g.display
  screen.gsub("\n", "\r\n")
end

system "stty raw -echo"

game = Sokoban.new

loop do
  system "clear"
  puts draw(game)
  
  if game.level_solved?
    puts "\r\nLevel solved. Nice Work!\r\n"
    sleep 3
    game.load_level

    break if game.over?
  end
  
  case STDIN.getc
    when ?Q, ?\C-c
      break
    when ?S
      game.save
    when ?L
      game = Sokoban.load if test ?e, "sokoban_saved_game.yaml"
    when ?R
      game.restart_level
    when ?U
      game.undo
    when ?j, ?j
      game.move_left
    when ?k, ?K
      game.move_right
    when ?m, ?m
      game.move_down
    when ?i, ?I
      game.move_up
  end
end

if game.over?
  system "clear"
  puts "\r\nYou've solved all the levels Puzzle Master!!!\r\n\r\n"
end

END { system "stty -raw echo" }

__END__

# === file: opengl_sokoban.rb ===

#!/usr/bin/env ruby

require "opengl"
require "glut"

require "sokoban"

PATH = File.expand_path(File.dirname(__FILE__))

def init
  GL.Light GL::LIGHT0, GL::AMBIENT, [0.0, 0.0, 0.0, 1.0]
  GL.Light GL::LIGHT0, GL::DIFFUSE, [1.0, 1.0, 1.0, 1.0]
  GL.Light GL::LIGHT0, GL::POSITION, [0.0, 3.0, 3.0, 0.0]
  GL.LightModel GL::LIGHT_MODEL_AMBIENT, [0.2, 0.2, 0.2, 1.0]
  GL.LightModel GL::LIGHT_MODEL_LOCAL_VIEWER, [0.0]
  
  GL.FrontFace GL::CW
  GL.Enable GL::LIGHTING
  GL.Enable GL::LIGHT0
  GL.Enable GL::AUTO_NORMAL
  GL.Enable GL::NORMALIZE
  GL.Enable GL::DEPTH_TEST
  GL.DepthFunc GL::LESS
end

def render_man
  GL.Material GL::FRONT, GL::AMBIENT, [0.0, 0.0, 0.0, 1.0]
  GL.Material GL::FRONT, GL::DIFFUSE, [0.5, 0.0, 0.0, 1.0]
  GL.Material GL::FRONT, GL::SPECULAR, [0.7, 0.6, 0.6, 1.0]
  GL.Material GL::FRONT, GL::SHININESS, 0.25 * 128.0
  
  GLUT.SolidSphere 0.5, 16, 16
end

def render_crate
  GL.Material GL::FRONT, GL::AMBIENT, [0.19125, 0.0735, 0.0225, 1.0]
  GL.Material GL::FRONT, GL::DIFFUSE, [0.7038, 0.27048, 0.0828, 1.0]
  GL.Material GL::FRONT, GL::SPECULAR, [0.256777, 0.137622, 0.086014, 1.0]
  GL.Material GL::FRONT, GL::SHININESS, 0.1 * 128.0
  
  GL.PushMatrix
    GL.Scale 0.9, 0.9, 0.9
    GL.Translate 0.0, 0.0, 0.45
    
    GLUT.SolidCube 1.0
  GL.PopMatrix
end

def render_stored_crate
  GL.Material GL::FRONT, GL::AMBIENT, [0.25, 0.20725, 0.20725, 1.0]
  GL.Material GL::FRONT, GL::DIFFUSE, [1.0, 0.829, 0.829, 1.0]
  GL.Material GL::FRONT, GL::SPECULAR, [0.296648, 0.296648, 0.296648, 1.0]
  GL.Material GL::FRONT, GL::SHININESS, 0.088 * 128.0
  
  GL.PushMatrix
    GL.Scale 0.9, 0.9, 0.9
    GL.Translate 0.0, 0.0, 0.45
    
    GLUT.SolidCube 1.0
  GL.PopMatrix
end

def render_open_floor
  GL.Material GL::FRONT, GL::AMBIENT, [0.05, 0.05, 0.05, 1.0]
  GL.Material GL::FRONT, GL::DIFFUSE, [0.5, 0.5, 0.5, 1.0]
  GL.Material GL::FRONT, GL::SPECULAR, [0.7, 0.7, 0.7, 1.0]
  GL.Material GL::FRONT, GL::SHININESS, 0.078125 * 128.0
  
  GL.PushMatrix
    GL.Scale 0.9, 0.9, 0.1
    GL.Translate 0.0, 0.0, -0.05
    
    GLUT.SolidCube 1.0
  GL.PopMatrix

  GL.Material GL::FRONT, GL::AMBIENT, [0.05375, 0.05, 0.06625, 1.0]
  GL.Material GL::FRONT, GL::DIFFUSE, [0.18275, 0.17, 0.22525, 1.0]
  GL.Material GL::FRONT, GL::SPECULAR, [0.332741, 0.328634, 0.346435, 1.0]
  GL.Material GL::FRONT, GL::SHININESS, 0.3 * 128.0

  GL.PushMatrix
    GL.Scale 1.0, 1.0, 0.1
    GL.Translate 0.0, 0.0, -0.1
    
    GLUT.SolidCube 1.0
  GL.PopMatrix
end

def render_storage
  GL.Material GL::FRONT, GL::AMBIENT, [0.05, 0.05, 0.0, 1.0]
  GL.Material GL::FRONT, GL::DIFFUSE, [0.5, 0.5, 0.4, 1.0]
  GL.Material GL::FRONT, GL::SPECULAR, [0.7, 0.7, 0.04, 1.0]
  GL.Material GL::FRONT, GL::SHININESS, 0.078125 * 128.0
  
  GL.PushMatrix
    GL.Scale 0.9, 0.9, 0.1
    GL.Translate 0.0, 0.0, -0.05
    
    GLUT.SolidCube 1.0
  GL.PopMatrix

  GL.Material GL::FRONT, GL::AMBIENT, [0.05375, 0.05, 0.06625, 1.0]
  GL.Material GL::FRONT, GL::DIFFUSE, [0.18275, 0.17, 0.22525, 1.0]
  GL.Material GL::FRONT, GL::SPECULAR, [0.332741, 0.328634, 0.346435, 1.0]
  GL.Material GL::FRONT, GL::SHININESS, 0.3 * 128.0

  GL.PushMatrix
    GL.Scale 1.0, 1.0, 0.1
    GL.Translate 0.0, 0.0, -0.1
    
    GLUT.SolidCube 1.0
  GL.PopMatrix
end

def solid_cylinder(radius, height, slices, stacks)
  GL.PushAttrib GL::POLYGON_BIT
    GL.PolygonMode GL::FRONT_AND_BACK, GL::FILL
    obj = GLU.NewQuadric
    GLU.Cylinder obj, radius, radius, height, slices, stacks
    GL.PushMatrix
      GL.Translate 0.0, 0.0, height
      GLU.Disk obj, 0.0, radius, slices, stacks
    GL.PopMatrix
    GLU.DeleteQuadric obj
  GL.PopAttrib
end

def render_wall
  GL.Material GL::FRONT, GL::AMBIENT, [0.0, 0.0, 0.0, 1.0]
  GL.Material GL::FRONT, GL::DIFFUSE, [0.1, 0.35, 0.1, 1.0]
  GL.Material GL::FRONT, GL::SPECULAR, [0.45, 0.55, 0.45, 1.0]
  GL.Material GL::FRONT, GL::SHININESS, 0.25 * 128.0
  
  GL.PushMatrix
    GL.Translate 0.0, 0.0, 0.5
    
    solid_cylinder 0.45, 1.0, 16, 4
  GL.PopMatrix
end

game = Sokoban.new

display = lambda do
  GL.Clear GL::COLOR_BUFFER_BIT | GL::DEPTH_BUFFER_BIT

  screen = game.display
  screen.each_with_index do |row, y|
    row.chomp!
    first = row =~ /^(\s+)/ ? $1.length : 0
    (first...row.length).each do |x|
      GL.PushMatrix
        GL.Translate 1.0 + x, 17.5 - y, 0.0
        
        if row[x, 1] == "." or row[x, 1] == "*" or row[x, 1] == "+"
          render_storage
        else
          render_open_floor
        end
        if row[x, 1] == "@" or row[x, 1] == "+"
          render_man
        elsif row[x, 1] == "o"
          render_crate
        elsif row[x, 1] == "*"
          render_stored_crate
        elsif row[x, 1] == "#"
          render_wall
        end
      GL.PopMatrix
    end
  end

  GL.Flush
end

reshape = lambda do |w, h|
  GL.Viewport 0, 0, w, h
  GL.MatrixMode GL::PROJECTION
  GL.LoadIdentity
  GL.Frustum(-1.0, 1.0, -1.0, 1.0, 1.5, 20.0)
  GL.MatrixMode GL::MODELVIEW
  GLU.LookAt 10.0, 10.0, 17.5, 10.0, 10.0, 0.0, 0.0, 1.0, 0.0
end

keyboard = lambda do |key, x, y|
  case key
    when ?Q, ?\C-c
      exit 0
    when ?S
      game.save
    when ?L
      if test ?e, File.join(PATH, "sokoban_saved_game.yaml")
        game = Sokoban.load
      end
    when ?R
      game.restart_level
    when ?U
      game.undo
    when ?j, ?j
      game.move_left
    when ?k, ?K
      game.move_right
    when ?m, ?m
      game.move_down
    when ?i, ?I
      game.move_up
  end

  if game.level_solved?
    game.load_level

    exit 0 if game.over?
  end
  
  GLUT.PostRedisplay
end

GLUT.Init
GLUT.InitDisplayMode GLUT::SINGLE | GLUT::RGB | GLUT::DEPTH
GLUT.CreateWindow "Sokoban"

init

GLUT.KeyboardFunc keyboard
GLUT.ReshapeFunc reshape
GLUT.DisplayFunc display

GLUT.MainLoop

__END__

James Edward Gray II

5

Again, very late, but here is my solution. A central game core and two front ends, a curses one and and FXRuby one.

Thomas Leitner

curses.rb (1.15 KB)

fox.rb (3.94 KB)

listener.rb (1.51 KB)

sokoban.rb (3.83 KB)

6

A nice submission as always Thomas, but just FYI, there is a subtle bug in it. I've been triggering it by playing level 0, filling the middle row of storage, then the top and finally the bottom. It will say I solved it one crate too soon.

Hope that helps.

James Edward Gray II

···

On Nov 3, 2004, at 6:18 PM, Thomas Leitner wrote:

Again, very late, but here is my solution. A central game core and two front ends, a curses one and and FXRuby one.

7

Thanks for pointing out that bug, James! I really enjoyed this quiz because I played Sokoban a lot and always thought it would be difficult to implement :wink:

One suggestion for the quiz solutions on your web page: It would be nice if there would be a quiz??-solutions.tar.bz2 file which has all submission in it (each solution in its own directory which is named after the developer). This way it would be much easier to try the solutions. Just my 2 cents.

Thomas Leitner

Here is the diff to fix the bug:

Index: sokoban.rb

···

On Thu, 4 Nov 2004 10:31:21 +0900 James Edward Gray II <james@grayproductions.net> wrote:

On Nov 3, 2004, at 6:18 PM, Thomas Leitner wrote:

> Again, very late, but here is my solution. A central game core and
> two front ends, a curses one and and FXRuby one.

A nice submission as always Thomas, but just FYI, there is a subtle
bug in it. I've been triggering it by playing level 0, filling the
middle row of storage, then the top and finally the bottom. It will
say I solved it one crate too soon.

Hope that helps.

James Edward Gray II

===================================================================
--- sokoban.rb (revision 5)
+++ sokoban.rb (working copy)
@@ -121,7 +121,7 @@
   end

   def level_finished?
- !( @map.any? {|item| item == Map::Storage } )
+ !( @map.any? {|item| item == Map::Storage || item == Map::ManOnStorage } )
   end

   def reset

8

Look at you creating more work for me. Shame on you. Thomas, if I didn't like you... :wink:

Seriously, I've attempted to add this feature to the scripts that run Ruby Quiz. The solutions should go up with the summary, tomorrow morning. I'll try and work my way back through the old quizzes sometime tomorrow, adding this in for them by hand.

Thanks for the great idea.

James Edward Gray II

···

On Nov 3, 2004, at 8:38 PM, Thomas Leitner wrote:

One suggestion for the quiz solutions on your web page: It would be nice if there would be a quiz??-solutions.tar.bz2 file which has all submission in it (each solution in its own directory which is named after the developer). This way it would be much easier to try the solutions. Just my 2 cents.

9

No problem. Thanks to you for making the Ruby Quiz!!!

Thomas Leitner

···

On Thu, 4 Nov 2004 12:50:42 +0900 James Edward Gray II <james@grayproductions.net> wrote:

On Nov 3, 2004, at 8:38 PM, Thomas Leitner wrote:

> One suggestion for the quiz solutions on your web page: It would be
> nice if there would be a quiz??-solutions.tar.bz2 file which has all
>
> submission in it (each solution in its own directory which is named
> after the developer). This way it would be much easier to try the
> solutions. Just my 2 cents.

Look at you creating more work for me. Shame on you. Thomas, if I
didn't like you... :wink:
Seriously, I've attempted to add this feature to the scripts that run
Ruby Quiz. The solutions should go up with the summary, tomorrow
morning. I'll try and work my way back through the old quizzes
sometime tomorrow, adding this in for them by hand.

Thanks for the great idea.