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 Quiz. 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.
···
#
# 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(r)}
@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)
+ sokban on storage bin
. empty storage bin
o crate needing to be stored
* crate stored in a bin
# 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 ---------------------------
