95 lines
2.5 KiB
Ruby
95 lines
2.5 KiB
Ruby
class Sokoban
|
|
def initialize(level)
|
|
board = level.lines.map(&:rstrip)
|
|
leng = board.map(&:length).max
|
|
board = board.map{|line| line.ljust(leng)}.join
|
|
@goal = []
|
|
board.each_char.with_index do |c, i|
|
|
@player = i if c == '@' or c == '+'
|
|
@goal << i if c == '.' or c == '+' or c == '*'
|
|
end
|
|
@board = board.tr(' .@#$+*', ' @#$ $')
|
|
@lurd = [[-1, 'l', 'L'], [-leng, 'u', 'U'], [1, 'r', 'R'], [leng, 'd', 'D']]
|
|
@dirs = @lurd.map(&:first)
|
|
set_dead_zone(board.tr('^#', ' '))
|
|
end
|
|
|
|
def set_dead_zone(wall)
|
|
corner = search_corner(wall)
|
|
@dead = corner.dup
|
|
begin
|
|
size = @dead.size
|
|
corner.each do |pos|
|
|
@dirs.each do |dir|
|
|
next if wall[pos + dir] == '#'
|
|
@dead.concat(check_side(wall, pos+dir, dir))
|
|
end
|
|
end
|
|
end until size == @dead.size
|
|
end
|
|
|
|
def search_corner(wall)
|
|
wall.size.times.with_object([]) do |i, corner|
|
|
next if wall[i] == '#' or @goal.include?(i)
|
|
case count_wall(wall, i)
|
|
when 2
|
|
corner << i if wall[i-1] != wall[i+1]
|
|
when 3
|
|
corner << i
|
|
end
|
|
end
|
|
end
|
|
|
|
def check_side(wall, pos, dir)
|
|
wk = []
|
|
until wall[pos] == '#' or count_wall(wall, pos) == 0 or @goal.include?(pos)
|
|
return wk if @dead.include?(pos)
|
|
wk << pos
|
|
pos += dir
|
|
end
|
|
[]
|
|
end
|
|
|
|
def count_wall(wall, pos)
|
|
@dirs.count{|dir| wall[pos + dir] == '#'}
|
|
end
|
|
|
|
def push_box(pos, dir, board)
|
|
return board if board[pos + 2*dir] != ' '
|
|
board[pos ] = ' '
|
|
board[pos + dir] = '@'
|
|
board[pos + 2*dir] = '$'
|
|
board
|
|
end
|
|
|
|
def solved?(board)
|
|
@goal.all?{|i| board[i] == '$'}
|
|
end
|
|
|
|
def solve
|
|
queue = [[@board, "", @player]]
|
|
# When the key doesn't exist in Hash, it subscribes a key but it returns false.
|
|
visited = Hash.new{|h,k| h[k]=true; false}
|
|
visited[@board] # first subscription
|
|
|
|
until queue.empty?
|
|
board, route, pos = queue.shift
|
|
@lurd.each do |dir, move, push|
|
|
work = board.dup
|
|
case work[pos+dir]
|
|
when '$' # push
|
|
work = push_box(pos, dir, work)
|
|
next if visited[work]
|
|
return route+push if solved?(work)
|
|
queue << [work, route+push, pos+dir] unless @dead.include?(pos+2*dir)
|
|
when ' ' # move
|
|
work[pos ] = ' '
|
|
work[pos+dir] = '@'
|
|
next if visited[work]
|
|
queue << [work, route+move, pos+dir]
|
|
end
|
|
end
|
|
end
|
|
"No solution"
|
|
end
|
|
end
|