Course:CPSC312-2019-Sokoban

Sokoban

What is the problem?

Implementing the "warehouse keeper" game, sokoban. Comes with pre-defined levels and text display (runs in terminal). How to play sokoban.

This requires representing the game state in terms of spaces that may be occupied by one of a wall, a box, or the player. Instructions are provided upon starting the game, including the symbols representing each type of board space. The game must be able to recognise when a move is allowed (the player moving to a reachable empty space or pushing a box one space in the corresponding direction) or disallowed (the state remains unchanged). Moves may be input via "W","A","S","D". The level is complete when all goal spaces are occupied by a box.

Other actions include selecting a level from the menu, restarting the current level ("R"), undoing the previous move if one exists ("U"), and quitting the level to go back to the menu ("Q").

What is the something extra

A non-optimal level solver that provides a hint ("H") for the user's next box push. The hint is guaranteed not to lead to an unsolvable state, but may not be the best move. If the board is in an unsolvable state, no hint is given (state remains unchanged and it is up to the player to undo to a solvable state or restart the level). This is found through depth-first search with cycle-checking and basic deadlock pruning ("dead squares") to improve computation time.

What did we learn from doing this?

Haskell/functional programming is suitable for implementing our project.

• Action -> State -> Result abstraction
  • Conceptually, it works well to abstract our game into since our game works with actions that modify (or not) the state and may lead to a game end (by winning or choosing to quit)
• Immutable variables
  • Results in many arguments being passed between functions (e.g. solveLevel and solveLevel_'s visited accumulator, todo worklist; deadsquares). May be confusing, especially when constructing helper functions or mutually recursive functions. (See also: Type constructors in pattern matching)
    • At one point, deadsquares was computed once upon level load in play.hs, but was changed to be recomputed every time the player requested a hint in hints.hs because passing the list in play.hs made the code disorganised. Though the DFS search itself takes up the majority of the computation time, making this difference negligible, in other circumstances this may not be desirable.
  • There is no convenient way to remember past solutions found short of threading them through the functions as a dictionary or adding a solution element to the State type. We did not have time to try this, so our hints compute a new solution every time the user inputs "H" even if it is used more than once in a row. This is unnecessary, especially in cases where the computation time is significant (several seconds). This can also cause the hints to loop for some states, preventing the player from reaching the winning state through a series of repeated "H" alone.
• Pattern matching
  • In general: Makes code more readable (especially use of _ when a variable is unused). This was especially important for Sokoban, as there are a lot of different cases to break down such as the move inputted by the user, and the state of the board.
  • Type constructors: When a type has many elements, pattern matching to modify only one element may result in a long line (e.g. movePlayer in play.hs). It is also difficult to change the elements of the type declaration after functions have been written for it (we added previousState and level after writing most of the functions in sokoban.hs and the solver functions without deadlock checking in hints.hs, which resulted in a lot of changes to the pattern matching to include pS and l).
• Type checking
  • Haskell's strict typing is useful as many errors were caught at compile time rather than runtime, allowing for an easier testing process.
  • However, IO is more difficult. We ultimately implemented Hints to do the first box push in the solution for the player, but an alternative choice could have been to print a before/after of the board and allow the player to move themselves over to the box rather than appearing to teleport the player and the box in one move, which can be confusing. This would require modifying the signature of getNextBoard to IO Result, even though every other guard case only produces a Result since the game State is printed in the play caller.
• Higher order functions
  • map, filter, fold often useful when handling lists (especially in hints.hs to link functions together when handling moves/pushes to try, board squares, etc.)
• List comprehension
  • Useful for generating lists of board squares to check in findPotentialDeadSquares, though potentially unintuitive as it may sometimes be used to generate a fixed number of cases (no other good option available)
  • Since our board was represented as a list of lists, we became comfortable with manipulating lists through reading and writing to the board, checking for win conditions, and generating more states based on the board.

Links to code etc

Project code.

Prepared test cases

1. Invalid level
2. Levels 1-6
   1. Invalid action
   2. Undo before moving (U)
   3. Move around (W,A,S,D)
      1. Move to goal ('.' becomes '+')
      2. Move off goal ('+' becomes '.')
   4. Push boxes
      1. Valid push
         1. Push box ('$') to empty (' ' becomes '$')
         2. Push box ('$') to goal ('.' becomes '*')
         3. Push box from goal ('*' becomes '.' and '$')
      2. Invalid push (state unchanged)
         1. Push box against wall ('#')
         2. Push box against other box ('$' or '*')
   5. Undo repeatedly to level start
   6. Hint (H)
      1. Solvable state (box pushed, previousState updated by moves)
      2. Unsolvable state (state unchanged)
   7. Undo hint (by move, not push)
   8. Restart level (R)
   9. Solve/win the level
   10. Quit level
3. Quit game