Sokoban IDA* Solver (Ruby)

Clean and fully tested implementation of Sokoban game logic and IDA* solver in Ruby.

Installation

• brew install sdl2 libogg libvorbis rust (on MacOS) -> rust for munkres_ru
• Ruby. See .ruby-version for current version. rbenv is recommended to install it.
• SDL2. brew install sdl2 on MacOS (for gosu: https://github.com/gosu/gosu/wiki/Getting-Started-on-OS-X)
• imagemagick. brew install imagemagick on MacOS (for Sokoban image generator)

How It Works

Level internal representation

Standard representation of Sokoban levels is:

     #####                 # -> wall
     #   #                 $ -> box
     #$  #                 . -> goal
   ###  $##                * -> box on a goal
   #  $ $ #                @ -> pusher
 ### # ## #   ######       + -> pusher on a goal
 #   # ## #####  ..#         -> floor
 #    $          .*#
 ##### ### #@##  ..#
     #     #########
     #######

Positions in level start in the upper-left corner with (m=0, n=0). Example: (2, 4) means third rows and fifth cols starting in the upper-left corner ('#' in this level).

Once the files are loaded in our application, the actual representation is extended to dissociate "internal floor" and "external floor":

    #####                 # -> wall
    #sss#                 $ -> box
    #$ss#                 . -> goal
  ###ss$##                * -> box on a goal
  #ss$s$s#                @ -> pusher
###s#s##s#   ######       + -> pusher on a goal
#sss#s##s#####ss..#         -> external floor
#ssss$ssssssssss.*#       s -> internal floor
#####s###s#@##ss..#
    #sssss#########
    #######

But since it's more difficult to read, it's never printed like this in the console.

Play

When reflecting on a Sokoban solver, it's sometimes useful to manually try and solve specific situations. 2 helper methods exist for this purpose.

In both mode, use:

• Arrow keys to move.
• 'd' or 'backspace' to cancel the last move.
• 'esc' to quit.

Visual Game

level = Level.new("    #####          \n"\
                  "    #   #          \n"\
                  "    #$  #          \n"\
                  "  ###  $##         \n"\
                  "  #  $ $ #         \n"\
                  "### # ## #   ######\n"\
                  "#   # ## #####  ..#\n"\
                  "# $  $     @    ..#\n"\
                  "##### ### # ##  ..#\n"\
                  "    #     #########\n"\
                  "    #######        ")

level.play

It will launch a window for you to play the game.

Console Game

Also, see https://sokoban-game.com