Here is one more solution to the Sokoban quiz. I think people might
be interested in seeing this one because 1) it uses a different
implementation strategy then the solutions posted back in 2004, and
2) it is somewhat more complete than those solutions.
I know that the Sokoban quiz was posted a long time ago. But I didn’t
even know that Ruby existed back then. I first heard about Ruby and
became interested it in April of this year. In June, I picked up Best
of Ruby Q… It was from that book that I learned about the Sokoban
quiz.
I had a lot of fun implementing Sokoban in Ruby. The only difficulty
I encountered was in dealing with the Curses module, for which l was
not able to locate up-to-date documentation. In the end, I had to
fall back on trial-and-error to get the code involving Curses methods
to work.
Regards, Morton
--------------------------- start of code ---------------------------
#! /usr/bin/ruby -w
Author: Morton G.
Date: July 13, 2006
An implementation of the Sokoban game based on the model-view-
controller
design pattern. It also avoids using case blocks, using hashes
instead.
The user interface is implemented with Curses. Games are saved and
restored using YAML.
require ‘curses’
WELCOME = ‘Welcome to Sokoban 1.0 – press h if you need help’
The SOKOBAN environment variable must be defined and point to the
folder
where the file “levels.txt” can be found. Further, any files
written out
(such as saved games, level maps, and completion certificates) will be
written to this folder.
FOLDER = ENV[‘SOKOBAN’]
LEVELS is the name of a file containing a collection of level maps
to be
loaded during start-up.
LEVELS = “levels.txt”
GAME is the name given to a saved game. If such a file exists in
FOLDER,
the game can be restored from it at any time during play.
GAME = “sokoban.yaml”
Unit vectors representing one-step moves in the four cardinal
directions.
UVEC = {
?e => [0, 1],
?w => [0, -1],
?n => [-1, 0],
?s => [1, 0]
}
A sokoban represents the warehouse worker. It knows the following
things:
Where it is
How to move around the level map
How to push crates
class Sokoban
# Transition table for simple moves.
MOVE_TABLE = {
'@ ' => ' @',
'@.' => ' +',
'+ ' => '.@',
'+.' => '.+'
}
# Transition table for crate-pushing moves.
PUSH_TABLE = {
'@o ' => ' @o',
'@o.' => ' @*',
'@* ' => ' +o',
'@*.' => ' +*',
'+o ' => '.@o',
'+o.' => '.@*',
'+* ' => '.+o',
'+*.' => '.+*'
}
# Given a level's map, return the position of the token representing
# the sokoban. When successful, returns an array of form [row, col];
# otherwise, it returns nil.
def Sokoban.find(level_map)
level_map.each_with_index do |row, i|
j = row.index(/[@+]/)
return [i, j] if j
end
return nil
end
attr_reader :row, :col
# Argument position must be an array of the form [row, col].
def initialize(position)
@row = position[0]
@col = position[1]
end
# Perform a simple move; i.e., no crate push.
# Argument token must be is one of ?e, ?w, ?n, or ?s.
# Argument map must be a level map.
def move(token, map)
dr, dc = UVEC[token]
r, c = @row + dr, @col + dc
old = map[@row][@col, 1] + map[r][c, 1]
new = MOVE_TABLE[old]
if new then
rows = [@row, r]
cols = [@col, c]
@row = r
@col = c
return [rows, cols, old, new]
else
return [nil, nil, nil, nil]
end
end
# Perform a crate-pushing move.
# Argument token must be is one of ?e, ?w, ?n, or ?s.
# Argument map must be a level map.
def push(token, map)
dr, dc = UVEC[token]
r, c = @row + dr, @col + dc
rr, cc = r + dr, c + dc
old = map[@row][@col, 1] + map[r][c, 1] + map[rr][cc, 1]
new = PUSH_TABLE[old]
if new then
rows = [@row, r, rr]
cols = [@col, c, cc]
@row = r
@col = c
return [rows, cols, old, new]
else
return [nil, nil, nil, nil]
end
end
def to_s
"[#@row, #@col]"
end
end
A model represents the state of the level being played. It
maintains the
level map and knows the following things:
What moves are valid
When a level is complete
How to perform valid moves
How to undo previous moves
class Model
PASS = ' ' # marks empty passage cell
EMPTY = '.' # marks empty storage cell
CRATE = 'o' # marks crate in pasaage cell
FILLED = '*' # marks crate in storage cell
# The collection of level maps.
# Levels are 1-based, so level 0 is just a place holder and is
not used.
@@maps = [’#’]
# Load a collection of Sokoban level maps from the specified path.
def Model.load_maps(path)
File.open(path, "r") do |f|
map = []
f.each_line do |line|
if line =~ /^\s*#/ then
map << line.chomp
elsif ! map.empty? then
@@maps << map
map = []
end
end
@@maps << map unless map.empty?
end
end
# Returns the number of levels available for play.
def Model.levels
@@maps.length - 1
end
attr_reader :map, :rows, :cols, :sokoban, :moves_made
# Argument level must be an integer in range 1..Model.levels.
def initialize(level)
@level = level
@moves_made = 0
@history = []
# Need a deep copy because it will be destructively modified
during
# game play.
@map = @@maps[@level].collect {|r| String.new®}
@rows = @map.length
@cols = (@map.collect {|r| r.length}).max
@sokoban = Sokoban.new(Sokoban.find(@map))
end
# Returns true if the move is valid and false if it is not. A
valid move
# produces the appropriate change in the level’s map.
# Game moves are represented by single character tokens (?e, ?w, ?
n, ?s)
# indicating the direction of the move.
def move(token)
dr, dc = UVEC[token]
adjacent = @map[@sokoban.row + dr][@sokoban.col + dc, 1]
if adjacent == PASS || adjacent == EMPTY then
rows, cols, old, new = @sokoban.move(token, @map)
elsif adjacent == CRATE || adjacent == FILLED then
rows, cols, old, new = @sokoban.push(token, @map)
else
return false
end
return false unless new
# Move is valid, so update the level map.
rows.length.times do |k|
map_row = @map[rows[k]]
map_row[cols[k]] = new[k]
end
# Update the undo history.
@history << [rows, cols, old]
@moves_made = @history.length
return true
end
# Complete undo is simple to implement, but rather memory intensive.
def undo
return false if @history.empty?
rows, cols, old = @history.pop
rows.length.times do |k|
map_row = @map[rows[k]]
map_row[cols[k]] = old[k]
end
@moves_made = @history.length
@sokoban = Sokoban.new([rows[0], cols[0]])
return true
end
# The level is complete when the level map contains no crate tokens.
def level_complete?
crates = @map.collect do |row|
row.include?(CRATE)
end
! crates.any?
end
end
A view knows how to draw a visual representation of the level being
played.
class View
include Curses
# A view must be initialized with an instance of Model.
def initialize(model)
@model = model
# The spaces needed on the left side of level's map to center it.
@left_margin = ' '* ((cols - @model.cols) / 2)
# Put four blank lines before the top line of the level's map.
@top_margin = 4
end
# Draw the level's map in the screen buffer.
def draw
@model.map.each_with_index do |row, i|
setpos(@top_margin + i, 0)
addstr(@left_margin + row)
end
end
end
Provide a Curses-based approximation to the alert box widgets provided
by GUIs. Somewhat crude but useful as well as easy to use.
class AlertBox < Curses::Window
# Aids in determining the size of an alert's frame.
# Returns the height and width of a frame will closely fit the
# specified text. Provides for a border and left and right margins.
def AlertBox.size(text)
text = text.split("\n")
[text.length + 2, (text.map {|m| m.length}).max + 6]
end
# Aids in centering an alert on the screen.
# Returns a frame that will closely fit the specified text. Provides
# for a border and left and right margins.
def AlertBox.center(text)
h, w = size(text)
[(Curses::lines - h) / 2, (Curses::cols - w) / 2, h, w]
end
# rect is the alert's frame, an array of the form [top_row, top_col,
# heigth, width].
# text is the alert's content, a string consisting of one or more
# lines.
def initialize(rect, text)
@top_y = rect[0]
@top_x = rect[1]
@height = rect[2]
@width = rect[3]
@text = text.split("\n")
super(@height, @width, @top_y, @top_x)
box(?#, ?#, ?#)
end
# Display the alert on the screen.
def show
@text.length.times do |i|
setpos(i + 1, 3)
addstr(@text[i])
end
refresh
end
RESULT = {?y => true, ?n => false}
# Display the alert and wait for a key press.
# Return true if the user preses y.
# Return false if the user presses n.
# Beep on any other keystrokes.
def ask_y_or_n
show
Curses::noecho
key_chr = nil
loop do
key_chr = getch
break if key_chr == ?y || key_chr == ?n
Curses::beep
end
Curses::echo
RESULT[key_chr]
end
end
A controller gets the player’s keystrokes and translates them in to
game
actions.
class Controller
require 'yaml'
include Curses
# Keystroke command dispatch table
DISPATCH = Hash.new(:beep)
# general commands
DISPATCH[?A] = :abort # abort
DISPATCH[?h] = :key_help # show help
DISPATCH[?l] = :new_level # change level
DISPATCH[?m] = :map_help # show map legend & sokoban
position
DISPATCH[?n] = :up_level # advance to next level
DISPATCH[?p] = :dn_level # return to previous level
DISPATCH[?q] = :quit # quit
DISPATCH[?r] = :restore # restore game
DISPATCH[?s] = :save # save game
DISPATCH[?w] = :write_map # write map to file
# movement
DISPATCH[Key::RIGHT] = :go_east # right arrow = one step east
DISPATCH[Key::LEFT] = :go_west # left arrow = one step west
DISPATCH[Key::UP] = :go_north # up arrow = one step north
DISPATCH[Key::DOWN] = :go_south # down arrow = one step south
DISPATCH[?z] = :undo # undo previous move
def initialize
unless FOLDER then
puts "SOKOBAN environment variable not set"
exit(false)
end
map_file = FOLDER + LEVELS
if File.exists?(map_file) then
Model.load_maps(map_file)
else
puts "Can't find Sokoban levels file"
exit(false)
end
init_screen
begin
cbreak
stdscr.keypad(true)
@command_line = lines - 1
@status_line = lines - 2
@level = 1
@model = Model.new(@level)
@view = View.new(@model)
@key_chr = nil
say(WELCOME)
run
ensure
close_screen
puts $debug unless $debug.empty?
end
end
# Command ask-and-dispatch loop
def run
catch(:game_over) do
loop do
@view.draw
ask_cmd
send(DISPATCH[@key_chr])
end
end
end
# Handle request to abort -- exit immediately without reminding tihe
# user to save.
def abort
throw(:game_over)
end
SAVE_ALERT = <<TXT
Do you want to save your game before you quit?
Press y to save
Press n to quit without saving
TXT
# Handle request to quit -- befoe exiting, remind tihe user to save.
def quit
alert = AlertBox.new(AlertBox.center(SAVE_ALERT), SAVE_ALERT)
save if alert.ask_y_or_n
throw(:game_over)
end
KEY_INFO = <<INFO
Sokoban keystroke commands
General commands
A immediate quit
h display this message
l go to another level – you will
be asked for the level number
m show legend for level map
n go to next level
p go to previous level
q quit – you will be asked to save
r restore saved game
s save game to disk
w write level map to disk
Movement commands
Right-arrow move one step east
Left-arrow move one step west
Up-arrow move one step north
Down-arrow move one step south
z undo previous move
Press any key to dismiss
INFO
# Handle request for infomation on keystroke commands.
def key_help
alert = AlertBox.new(AlertBox.center(KEY_INFO), KEY_INFO)
alert.show
ask_cmd
clear
end
MAP_INFO = <<INFO
Sokoban map symbols
@ sokoban (warehouse worker)
. empty storage bin
o crate needing to be stored
wall or other obstacle
Press any key to dismiss
INFO
# Handle request for infomation on map symbols.
def map_help
say("Sokoban is at #{@model.sokoban}")
alert = AlertBox.new(AlertBox.center(MAP_INFO), MAP_INFO)
alert.show
ask_cmd
clear
end
# Handle request to change to another level.
def new_level
current = @level
msg = ask_level
if @level == current then
say(msg)
else
set_level(msg)
end
end
# Handle request to go to the next level.
def up_level
nxt = @level + 1
if nxt > Model.levels then
beep
else
@level = nxt
set_level("Starting level #@level")
end
end
# Handle request to go to the previous level.
def dn_level
nxt = @level - 1
if nxt < 1 then
beep
else
@level = nxt
set_level("Starting level #@level")
end
end
# Change to the requested level.
def set_level(msg)
@model = Model.new(@level)
@view = View.new(@model)
clear
say(msg)
end
# Handle request to write the current level map out to disk.
# The level map is written to FOLDER. The file name is generated
from
# the current level and the number of moves made. For example, if
a map
# is written out for level 3 at move 117, the map file is named
# “level_map.3.117.txt”.
def write_map
path = FOLDER + “level_map.#@level.#{@model.moves_made}.txt”
text =
“Level: #@level\nMove: #{@model.moves_made}\n\n” +
@model.map.join("\n")
File.open(path, ‘w’) {|f| f.write(text)}
say(“Level map written to disk”)
end
# Handle request to save the current state of game to a YAML file
from
# which it can be restored at some later time.
def save
game_file = FOLDER + GAME
game = {‘level’ => @level, ‘model’ => @model}
File.open(game_file, ‘w’) do |f|
YAML.dump(game, f)
say(“Game saved to disk”)
end
end
# Handle request to restore a game from a YAML file.
def restore
game_file = FOLDER + GAME
if File.exists?(game_file) then
game = YAML.load_file(game_file)
@level = game['level']
@model = game['model']
@view = View.new(@model)
clear
say("Game restored from disk")
else
say("Cant find game file on disk")
end
end
# Handle request to move eastward.
def go_east
go(?e, "Moved east")
end
# Handle request to move westward.
def go_west
go(?w, "Moved west")
end
# Handle request to move northward.
def go_north
go(?n, "Moved north")
end
# Handle request to move southward.
def go_south
go(?s, "Moved south")
end
CERTIFICATE_ALERT = <<TXT
Level Completed
You qualify for a certificate to commemorate your success
Press y to have the certificate issued
Press n to skip the certificate
TXT
# Ask the model to move the sokoban in the direction indicated by
token.
# if move succeeded, check for level completion.
def go(token, msg)
if @model.move(token) then
if @model.level_complete? then
@view.draw
say(“Congratulations! You have completed level #@level”)
alert = AlertBox.new(AlertBox.center(CERTIFICATE_ALERT),
CERTIFICATE_ALERT)
write_certificate if alert.ask_y_or_n
clear
up_level
else
say(msg)
end
else
beep
end
end
# Ask the model to undo the sokoban's last move. Decrement the
move count
# if successful.
def undo
if @model.undo then
say(“Undid move #{@model.moves_made + 1}”)
else
beep
end
end
# Display a message on the status line. The message will be
prefixed by
# the level number and the move count.
def say(text)
text = "Level #@level, move #{@model.moves_made}: " + text
setpos(@status_line, 0)
addstr(text.ljust(cols))
refresh
end
# Display a prompt for imput on the command line.
# Return the user's response (a string).
def ask_str(prompt)
w = prompt.length
setpos(@command_line, 0)
addstr(prompt.ljust(cols))
setpos(@command_line, w)
refresh
getstr
end
COMMAND_PROMPT = '>> '
CURSOR_COLUMN = COMMAND_PROMPT.length
# Prompt for and get a keystroke command.
def ask_cmd
setpos(@command_line, 0)
addstr(COMMAND_PROMPT.ljust(cols))
setpos(@command_line, CURSOR_COLUMN)
refresh
noecho
@key_chr = getch
echo
end
LEVEL_PROMPT = "What level do you want to play? "
# Ask the user for a level number. If the response is valid,
accept it;
# if not, the current level persists.
def ask_level
prompt = LEVEL_PROMPT + "[1 - #{Model.levels}]: "
begin
response = ask_str(prompt).to_i
if (1…Model.levels).include?(response) then
@level = response
msg = “Starting level #@level”
else
raise RangeError
end
rescue
# Resume current level.
msg = “Level change cancelled”
end
return msg
end
# Write a certificate of completion for the current level out to
disk.
# The certificate is written to FOLDER. The file name is
generated from
# the USER environment variable, the current level, and the
number of
# moves it took to complete the level. For example, if user “mg”
# completes leve 3 in 435 moves, the certificate file is named
# “mg.3.435.txt”. The file’s contents repeat the information
contained
# in the file name in a more readable format and adds the date.
def write_certificate
user = ENV[‘USER’]
date = Time.now.strftime("%d/%m/%Y")
path = FOLDER + “#{user}.#@level.#{@model.moves_made}.txt”
text = <<-TXT
Sokoban Certificate of Completiion
----------------------------------
Date: #{date}
Level: #@level
Moves: #{@model.moves_made}
Player: #{user}
TXT
text.gsub!(/^\s+/, ‘’)
File.open(path, ‘w’) {|f| f.write(text)}
end
end
$debug = []
Controller.new
--------------------------- end of code ---------------------------
