{"size": 6669, "ext": "scrbl", "max_stars_repo_path": "examples/sokoban.scrbl", "max_stars_repo_name": "jackfirth/planning", "max_stars_repo_stars_event_min_datetime": "2020-05-12T11:12:24.000Z", "max_stars_repo_stars_event_max_datetime": "2022-02-09T00:40:10.000Z", "max_issues_repo_path": "examples/sokoban.scrbl", "max_issues_repo_name": "jackfirth/planning", "max_issues_repo_issues_event_min_datetime": "2020-05-29T05:08:55.000Z", "max_issues_repo_issues_event_max_datetime": "2020-05-29T05:54:18.000Z", "max_forks_repo_path": "examples/sokoban.scrbl", "max_forks_repo_name": "jackfirth/planning", "max_forks_repo_forks_event_min_datetime": null, "max_forks_repo_forks_event_max_datetime": null}
{"max_stars_count": 5, "max_issues_count": 2, "max_forks_count": null, "avg_line_length": 38.549132948, "max_line_length": 80, "alphanum_fraction": 0.6372769531}
#lang scribble/manual

@(require (for-label pict
                     planning/examples/sokoban
                     planning/hash/action
                     planning/hash/condition
                     planning/hash/problem
                     racket/base
                     racket/contract/base
                     racket/set
                     racket/math)
          (submod planning/private doc)
          scribble/example)

@(define make-evaluator
   (make-module-sharing-evaluator-factory
    #:public (list 'planning/examples/sokoban
                   'planning/hash/action
                   'planning/hash/condition
                   'planning/hash/problem
                   '(submod planning/hash/visualize headless)
                   'racket/set)
    #:private (list 'racket/base)))

@title{Sokoban}
@defmodule[planning/examples/sokoban]

Sokoban is a puzzle game in which the player must push crates around a
warehouse, trying to put them in storage locations. It was created in 1981 and
has since found a home in the AI research community as a useful problem domain
for testing @tech{automated planners}.

The Sokoban world is a rectangular grid containing walls, crates, a player, and
storage locations. The goal is to push the crates to the storage locations. The
player can move around the world and push crates up, down, left, and right, but
only if the crate isn't blocked by a wall or another crate.

@(examples
  #:eval (make-evaluator) #:once
  (eval:no-prompt
   (define state
     (sokoban-level (space 1 1) player
                    (space 2 2) crate
                    (space 3 3) storage-location
                    #:width 5
                    #:height 5))
   (define problem
     (hash-planning-problem
      #:state state
      #:actions (sokoban-possible-actions state)
      #:goal sokoban-goal)))

  (hash-visualize-plan! problem #:draw-state-with sokoban-pict))

@defproc[(space? [v any/c]) boolean?]{
 A predicate for grid spaces in a Sokoban level. A space is a pair of an X
 coordinate and a Y coordinate.}

@defproc[(space [x natural?] [y natural?]) space?]{
 Constructs a grid space with @racket[x] and @racket[y] coordinates. The origin
 @racket[(space 0 0)] represents the @bold{top left corner} of a Sokoban level.}

@deftogether[[
 @defproc[(space-x [s space?]) natural?]
 @defproc[(space-y [s space?]) natural?]]]{
 Returns the X and Y coordinates of @racket[s], respectively.}

@defproc[(sokoban-object? [v any/c]) boolean?]{
 A predicate for objects in the Sokoban world.}

@deftogether[[
 @defthing[wall sokoban-object?]
 @defthing[player sokoban-object?]
 @defthing[crate sokoban-object?]
 @defthing[storage-location sokoban-object?]
 @defthing[player-in-storage sokoban-object?]
 @defthing[crate-in-storage sokoban-object?]]]{
 The various objects that can exist in a Sokoban level. The
 @racket[player-in-storage] and @racket[crate-in-storage] objects are like the
 @racket[player] and @racket[crate] objects, except they represent cases where
 the player or crate is standing on top of a storage location space. Distinct
 objects for these cases are necessary because the Sokoban world uses the
 @tech{hash state representation}, so a single space cannot contain multiple
 objects.}

@defproc[(sokoban-level [s space?] [object sokoban-object?] ... ...
                        [#:width width exact-positive-integer?]
                        [#:height height exact-positive-integer?])
         (hash/c space? sokoban-object?)]{
 Constructs a hash table representing a Sokoban level with dimensions of
 @racket[width] and @racket[height]. In addition to each of the space-object
 pairs specified by the @racket[s] and @racket[object] arguments, walls are
 placed on the edges of the level.

 @(examples
   #:eval (make-evaluator) #:once
   (sokoban-pict
    (sokoban-level (space 1 1) player
                   (space 1 3) wall
                   (space 2 3) wall
                   (space 2 2) crate
                   (space 3 5) storage-location
                   (space 2 4) crate
                   (space 1 4) storage-location
                   #:width 5
                   #:height 7)))}

@defproc[(sokoban-applicable-actions [state (hash/c space? sokoban-object?)])
         (set/c hash-action?)]{
 Constructs a set of all actions that are @tech{applicable} in @racket[state].

 @(examples
   #:eval (make-evaluator) #:once
   (eval:no-prompt
    (define state
      (sokoban-level (space 1 1) player
                     (space 2 2) crate
                     (space 3 2) storage-location
                     #:width 5
                     #:height 4)))

   (sokoban-pict state)
   (set-count (sokoban-applicable-actions state)))}

@defproc[(sokoban-possible-actions
          [initial-state (hash/c space? sokoban-object?)])
         (set/c hash-action?)]{
 Constructs a set of all possible actions that could be performed over the
 course of a Sokoban game starting from @racket[initial-state]. This includes
 actions that are not mmediately applicable, but which can be applied if other
 actions are
 performed first.

 The set of possible actions returned is an @emph{optimistic estimate}. Every
 possible action is returned, but some impossible actions may also be returned.
 An estimate is returned because computing the exact set of possible actions can
 be complex and prohibitively expensive.

 @(examples
   #:eval (make-evaluator) #:once
   (eval:no-prompt
    (define state
      (sokoban-level (space 1 1) player
                     (space 2 2) crate
                     (space 3 2) storage-location
                     #:width 5
                     #:height 4)))
   
   (sokoban-pict state)
   (set-count (sokoban-possible-actions state)))}

@; TODO(https://github.com/jackfirth/planning/issues/2): Use hash-goal/c here.
@defthing[sokoban-goal hash-goal?
          #:value (hash-goal #:obstructing-values (set crate))]{
 The @tech{goal} of every Sokoban level is the same: push every crate into
 storage. Because pushing a @racket[crate] into a storage location changes it
 into a @racket[crate-in-storage], this means that all that's required to win is
 for the Sokoban level's hash table to not contain any @racket[crate] values.}

@defproc[(sokoban-pict [state (hash/c space? sokoban-object?)]) pict?]{
 Draws a picture of @racket[state].

 @(examples
   #:eval (make-evaluator) #:once
   (sokoban-pict
    (sokoban-level (space 1 1) player
                   (space 2 4) crate
                   (space 4 2) crate
                   (space 1 5) storage-location
                   (space 5 4) storage-location
                   #:width 7
                   #:height 7)))}
