Array out of bounds in Sokoban solver and hash of arrays 
Author Message
 Array out of bounds in Sokoban solver and hash of arrays

I'm working on a sokoban solver. It is currently only brute force based,
though I plan to add some optimizations later.
I have a bug somewhere in my source that makes me move my boxes beyond a
wall, and eventually, out of the array. I then obviously get an array
out of bounds error. I've already spent several hours looking through
the source, testing small bits of it, and just can't track down the problem.
Could somone please take a look at the source? I'm fairly certain that
there's no mistake in the reader functions (get-map,  map-size,
find-reachable) as I've printed out the result and compared it to the
original. The problem still arises even without the move-further
function, so it isn't there either. I just really don't know what could
be going wrong in the rest of the program. Did I miss a possibility
somewhere?

Some parts of the program aren't implemented yet, notably  the function
that checks if a solution has been found - but I figured that adding
that won't make my array problem go away ;).

I'm going to use a hash table to check if I'm coming back to a position
I have already visited. However, I'd have to make a hash of a list of
the array that stores the boxes and the position of sokoban (or rather
some standard reachable square - such as the top left most reachable
square). This would mean that I'd have to use equalp - which is slower.
I was therefore wondering if it would be worthwhile to come up with a
number value that would represent this array and the sokoban location,
and use this for the hash, using eql for the hash table. Or would the
calculation of that number take more time than creating a hash for the
array?

Thanks in advance to anyone willing to read my source - any comments
would be appreciated - it's my first "real" lisp program, and there's
probably many things that I could do better differently. In particular,
if there is any more elegant way of reading in the maps in the first
place, rather than using the property list, and which functions would be
better as macros.

(defconstant +map-location+
'/Derek/Programming/Lisp/Sokoban/screens/screen.)
(defconstant +drive+ #\D)
(defun map-file (current-map)
    (format nil "~C~C~S~D" +drive+ #\: +map-location+ current-map))

(defun solve-map (map-number)
    "The main function that sets up all the variables and calls
rec-solve to actually solve the map."
      (defun map-size ();expects map-number
        "Gets the dimension of the map that is to be solved. Goes
through map line by line, remembering the longest line, and the total
number of lines."
        (with-open-file (in-stream (map-file map-number) :direction :input)
            (let ((max-width 0)
                    (width 0)
                    (length 0))
               (do ((char-to-be-processed (read-char in-stream)
(read-char in-stream nil 'the-end)))
                    ((not (characterp char-to-be-processed)) (list
max-width length))
                    (cond ((eql char-to-be-processed #\newline)
                            (incf length)
                            (if (< max-width width) (setq max-width width))
                            (setq width 0))
                        (T
                            (incf width)))))))
      (let ((map-size (map-size))
            (total-nodes 0)
            (move 0)
            (solution 0)
            (goals+walls nil)
            (boxes nil)
            (soko nil))
              ;;the symbols for the goals+walls map - trans for
"translate this symbol into machine code"             (setf (get
'g+w-trans-symbol '#\ ) 0)

        (setf (get 'g+w-trans-symbol '#\.) 1)
        (setf (get 'g+w-trans-symbol '#\$) 0)
        (setf (get 'g+w-trans-symbol '#\*) 1)
        (setf (get 'g+w-trans-symbol '#\#) 2)
        ;;the symbols for the boxes map
        (setf (get 'box-trans-symbol '#\ ) 0)

        (setf (get 'box-trans-symbol '#\.) 0)
        (setf (get 'box-trans-symbol '#\$) 1)
        (setf (get 'box-trans-symbol '#\*) 1)
        (setf (get 'box-trans-symbol '#\#) 0)
                             (defun get-map ();expects map-size and
map-number
            "Reads the map from file and returns an array containing the
walls (as 2s), the goals (as 1s) and empty space (as 0s);
            Also returns an array containing all the boxes (as 1s), and
a list of the location of the sokoban."
            (with-open-file (in-stream (map-file map-number) :direction
:input)
                (let (  (goals+walls    (make-array map-size
:element-type '(mod 3)))
                        (boxes          (make-array map-size
:element-type '(mod 2)))
                        (soko           nil)
                        (x              0)
                        (y              0))
                    (do ((current-char (read-char in-stream) (read-char
in-stream nil 'the-end)))
                        ((not (characterp current-char)) (values
goals+walls boxes soko))
                        (cond ((eql current-char #\newline)
                                (incf y)
                                (setq x 0))
                            (T                                (setf
(aref goals+walls x y) (get 'g+w-trans-symbol current-char))
                                (setf (aref boxes x y) (get
'box-trans-symbol current-char))

(list x y)))
                                (incf x)))))))
              (multiple-value-setq (goals+walls boxes soko) (get-map))
                 (defun make-loc-hash ()
            "Makes a hash table containing all the open spaces on the map.
            Can be used later in order to make the algorithm more
efficient by storing data in an array containing only the open spaces
            - not the walls or space outside of the reach of the
sokoban. It isn't yet being used."
            (let ((loc-hash (make-hash-table :test #'equal))
                    (stack (list soko)))
                (defun push-os (x y)
                    "Used to push this location onto the stack of
locations that should be given a hash entry."
                    (if (not (or (= (aref goals+walls x y) 2)  (gethash
(list x y) loc-hash)))
                        (push (list x y) stack)))
                (do ((current-loc soko (car stack))
                        (count 0 (1+ count)))
                    ((null current-loc) loc-hash)
                    (pop stack)
                    (setf (gethash (list (car current-loc) (cadr
current-loc)) loc-hash) count)
                    (push-os (car current-loc) (1- (cadr current-loc)))
                    (push-os (car current-loc) (1+ (cadr current-loc)))
                    (push-os (1- (car current-loc)) (cadr current-loc))
                    (push-os (1+ (car current-loc)) (cadr current-loc)))))
              (defvar loc-hash (make-loc-hash)
            "A hash of all spaces that could potentially be reached by
the sokoban, ie excluding walls, in the notation of (x y).")
              (defvar past-loc (make-hash-table :test #'equalp)
            "Another hash table not currently being used - will be used
in futur to remember posititions that have already been visited.")
              (defun rec-solver (boxes soko); expects map-size,
goals+walls, loc-hash
            "The actual recursive array that goes through all the
possible locations."

            (defun find-reachable ();needs map-size, soko, goals+walls,
boxes
                "Returns an array containing all the locations that the
sokoban can reach,
                taking into account boxes that stop his path. Reachable
locations are noted with a 1."
                (let ((reachable (make-array map-size :element-type
'(mod 2)))
                        (stack (list soko)))
                    (defun declare-reachable (x y)
                        "Oficially declare a location as reachable by
sokoban
                        - and stick on stack as a location who's
neighboors should be checked for reachability."
                        (setf (aref reachable x y) 1)
                        (push (list x y) stack))
                    (defun push-os (x y)
                        "If there is no box or wall at this location,
and it isn't reachable yet,
                        call declare-reachable to make it such, and to
push it onto the stack."
                        (if (and (= (aref reachable x y) 0) (< (aref
goals+walls x y) 2) (= (aref boxes x y) 0))
                            (declare-reachable x y)))
                    (setf (aref reachable (car soko) (cadr soko)) 1)
;set location of soko to reachable
                    (do ((current-loc soko (car stack)))
                        ((null current-loc) reachable)
                        (pop stack)
                        (push-os (car current-loc) (1- (cadr current-loc)))
                        (push-os (car current-loc) (1+ (cadr current-loc)))
                        (push-os (1- (car current-loc)) (cadr current-loc))
                        (push-os (1+ (car current-loc)) (cadr
current-loc)))))
                      (let ((reachable (find-reachable)))
                (incf total-nodes)
                              (defun is-reachable (x y); expects reachable
                    "Check if this location is reachable; return T if it
is."
                    (if (= 1 (aref reachable x y)) T nil))
                              (defun is-free (x y);expects goals+wall
and boxes
                    "Check if this location contains no box or wall.
Should probably be made into a macro."
                    (if (or (= 2 (aref goals+walls x y))
                            (= 1 (aref boxes x y)))
                        nil
                        T))
                              (defun attempt-move (x Y)
                    "Try to move the box located at square x y."
...

read more »



Tue, 18 Oct 2005 00:53:41 GMT  
 Array out of bounds in Sokoban solver and hash of arrays


Quote:
>I'm working on a sokoban solver. It is currently only brute force based,
>though I plan to add some optimizations later.
>I have a bug somewhere in my source that makes me move my boxes beyond a
>wall, and eventually, out of the array. I then obviously get an array
>out of bounds error. I've already spent several hours looking through
>the source, testing small bits of it, and just can't track down the problem.
>Could somone please take a look at the source? I'm fairly certain that
>there's no mistake in the reader functions (get-map,  map-size,
>find-reachable) as I've printed out the result and compared it to the
>original. The problem still arises even without the move-further
>function, so it isn't there either. I just really don't know what could
>be going wrong in the rest of the program. Did I miss a possibility
>somewhere?

I don't know Sokoban, and I can't really tell what your program is doing.
But I have a major style comment.

You shouldn't be defining functions and variables within the main function
with DEFUN and DEFVAR.  These are normally for defining top-level functions
and variables.  Local functions should be defined with FLET or LABELS, and
local variables with LET.  To make your code easier to read, I suggest you
pull those internal functions *out* and make them standalone functions (so
you'll have to pass in parameters rather than accessing the containing
function's local variables).

This should make it easier to debug your problem.  You use a divide and
conquer approach: test each component separately until you find the one
that's failing.

--

Genuity Managed Services, a Level(3) Company, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.



Tue, 18 Oct 2005 01:49:10 GMT  
 Array out of bounds in Sokoban solver and hash of arrays

Quote:
> I don't know Sokoban, and I can't really tell what your program is doing.
> But I have a major style comment.

Sorry - though everyone knows sokoban - here's an online version.
http://www.pimpernel.com/sokoban/sokoban.html
The point of the game is - you're in a room full of boxes/walls, and you
have to push all the boxes onto goal positions. No pulling is allowed.

Quote:
> You shouldn't be defining functions and variables within the main function
> with DEFUN and DEFVAR.  These are normally for defining top-level functions
> and variables.  Local functions should be defined with FLET or LABELS, and
> local variables with LET.  To make your code easier to read, I suggest you
> pull those internal functions *out* and make them standalone functions (so
> you'll have to pass in parameters rather than accessing the containing
> function's local variables).

Hm - didn't realize that functions could be declared in a different
manner than defun. Thanks!

Quote:
> This should make it easier to debug your problem.  You use a divide and
> conquer approach: test each component separately until you find the one
> that's failing.

That's actually how I wrote the first few functions. However, as I
expect the program to recurse to at least 1000 nodes deep, maybe more, I
figured that efficient use of memory is really important, and didn't
want to have a seperate copy of variables that I don't expect to change
for each node. That is why I wrote the rest of the code as functions
within functions. As I might call the top function several times (once
for each map I want to solve), I can't declare these as constants either.

I think I might rewrite the functions for debugging purposes as seperate
one from the other. I'll see how it runs like that, and reintegrate the
functions later if necessary ;)



Tue, 18 Oct 2005 02:16:15 GMT  
 Array out of bounds in Sokoban solver and hash of arrays


Quote:
>> This should make it easier to debug your problem.  You use a divide and
>> conquer approach: test each component separately until you find the one
>> that's failing.

>That's actually how I wrote the first few functions. However, as I
>expect the program to recurse to at least 1000 nodes deep, maybe more, I
>figured that efficient use of memory is really important, and didn't
>want to have a seperate copy of variables that I don't expect to change
>for each node.

Lisp doesn't make copies when you pass arguments.  You're passing a
reference to the same object.

--

Genuity Managed Services, a Level(3) Company, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.



Tue, 18 Oct 2005 02:41:38 GMT  
 Array out of bounds in Sokoban solver and hash of arrays

Quote:

> Lisp doesn't make copies when you pass arguments.  You're passing a
> reference to the same object.

(setq a 10)
=> 10

(defun go (x)
     (setq x (- x 5))
     (print x))
=> GO

(go a)
=>5 5

a
=>10

If you're passing a reference in go, how come changing x in go doesn't
affect a then? Doesn't lisp have to create the space necessary for x,
and copy the value of a to it in order to be able to work with it?



Tue, 18 Oct 2005 03:25:07 GMT  
 Array out of bounds in Sokoban solver and hash of arrays


Quote:

>> Lisp doesn't make copies when you pass arguments.  You're passing a
>> reference to the same object.

>(setq a 10)
>=> 10

>(defun go (x)
>     (setq x (- x 5))
>     (print x))
>=> GO

>(go a)
>=>5 5

>a
>=>10

>If you're passing a reference in go, how come changing x in go doesn't
>affect a then? Doesn't lisp have to create the space necessary for x,
>and copy the value of a to it in order to be able to work with it?

Because the assignment changes what the local variable X refers to.

(defvar *variable* (list 1 2))

(defun go (x)
  (setf (car x) 3)
  (setf x (list 10 11))
  (print x)
  nil)

(go *variable)
prints: (10 11)
(print *variable*)
prints: (3 2)

--

Genuity Managed Services, a Level(3) Company, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.



Tue, 18 Oct 2005 04:05:49 GMT  
 Array out of bounds in Sokoban solver and hash of arrays
I'm gonna look at the code a little just out of curiosity, and this will
not explain the coding error, but shouldn't the screen be:

     #####
     #   #
     #$  #
   ###  $##
   #  $ $ #
### # ## #   ######
#   # ## #####  ..#
# $  $          ..#

     #     #########
     #######

Your version has a few rows shifted left one character.

kt

Quote:

> I'm working on a sokoban solver. It is currently only brute force based,
> though I plan to add some optimizations later.
> I have a bug somewhere in my source that makes me move my boxes beyond a
> wall, and eventually, out of the array. I then obviously get an array
> out of bounds error. I've already spent several hours looking through
> the source, testing small bits of it, and just can't track down the
> problem.
> Could somone please take a look at the source? I'm fairly certain that
> there's no mistake in the reader functions (get-map,  map-size,
> find-reachable) as I've printed out the result and compared it to the
> original. The problem still arises even without the move-further
> function, so it isn't there either. I just really don't know what could
> be going wrong in the rest of the program. Did I miss a possibility
> somewhere?

> Some parts of the program aren't implemented yet, notably  the function
> that checks if a solution has been found - but I figured that adding
> that won't make my array problem go away ;).

> I'm going to use a hash table to check if I'm coming back to a position
> I have already visited. However, I'd have to make a hash of a list of
> the array that stores the boxes and the position of sokoban (or rather
> some standard reachable square - such as the top left most reachable
> square). This would mean that I'd have to use equalp - which is slower.
> I was therefore wondering if it would be worthwhile to come up with a
> number value that would represent this array and the sokoban location,
> and use this for the hash, using eql for the hash table. Or would the
> calculation of that number take more time than creating a hash for the
> array?

> Thanks in advance to anyone willing to read my source - any comments
> would be appreciated - it's my first "real" lisp program, and there's
> probably many things that I could do better differently. In particular,
> if there is any more elegant way of reading in the maps in the first
> place, rather than using the property list, and which functions would be
> better as macros.

> (defconstant +map-location+
> '/Derek/Programming/Lisp/Sokoban/screens/screen.)
> (defconstant +drive+ #\D)
> (defun map-file (current-map)
>    (format nil "~C~C~S~D" +drive+ #\: +map-location+ current-map))

> (defun solve-map (map-number)
>    "The main function that sets up all the variables and calls rec-solve
> to actually solve the map."
>      (defun map-size ();expects map-number
>        "Gets the dimension of the map that is to be solved. Goes through
> map line by line, remembering the longest line, and the total number of
> lines."
>        (with-open-file (in-stream (map-file map-number) :direction :input)
>            (let ((max-width 0)
>                    (width 0)
>                    (length 0))
>               (do ((char-to-be-processed (read-char in-stream)
> (read-char in-stream nil 'the-end)))
>                    ((not (characterp char-to-be-processed)) (list
> max-width length))
>                    (cond ((eql char-to-be-processed #\newline)
>                            (incf length)
>                            (if (< max-width width) (setq max-width width))
>                            (setq width 0))
>                        (T
>                            (incf width)))))))
>      (let ((map-size (map-size))
>            (total-nodes 0)
>            (move 0)
>            (solution 0)
>            (goals+walls nil)
>            (boxes nil)
>            (soko nil))
>              ;;the symbols for the goals+walls map - trans for
> "translate this symbol into machine code"             (setf (get
> 'g+w-trans-symbol '#\ ) 0)

>        (setf (get 'g+w-trans-symbol '#\.) 1)
>        (setf (get 'g+w-trans-symbol '#\$) 0)
>        (setf (get 'g+w-trans-symbol '#\*) 1)
>        (setf (get 'g+w-trans-symbol '#\#) 2)
>        ;;the symbols for the boxes map
>        (setf (get 'box-trans-symbol '#\ ) 0)

>        (setf (get 'box-trans-symbol '#\.) 0)
>        (setf (get 'box-trans-symbol '#\$) 1)
>        (setf (get 'box-trans-symbol '#\*) 1)
>        (setf (get 'box-trans-symbol '#\#) 0)
>                             (defun get-map ();expects map-size and
> map-number
>            "Reads the map from file and returns an array containing the
> walls (as 2s), the goals (as 1s) and empty space (as 0s);
>            Also returns an array containing all the boxes (as 1s), and a
> list of the location of the sokoban."
>            (with-open-file (in-stream (map-file map-number) :direction
> :input)
>                (let (  (goals+walls    (make-array map-size
> :element-type '(mod 3)))
>                        (boxes          (make-array map-size
> :element-type '(mod 2)))
>                        (soko           nil)
>                        (x              0)
>                        (y              0))
>                    (do ((current-char (read-char in-stream) (read-char
> in-stream nil 'the-end)))
>                        ((not (characterp current-char)) (values
> goals+walls boxes soko))
>                        (cond ((eql current-char #\newline)
>                                (incf y)
>                                (setq x 0))
>                            (T                                (setf (aref
> goals+walls x y) (get 'g+w-trans-symbol current-char))
>                                (setf (aref boxes x y) (get
> 'box-trans-symbol current-char))

> (list x y)))
>                                (incf x)))))))
>              (multiple-value-setq (goals+walls boxes soko) (get-map))
>                 (defun make-loc-hash ()
>            "Makes a hash table containing all the open spaces on the map.
>            Can be used later in order to make the algorithm more
> efficient by storing data in an array containing only the open spaces
>            - not the walls or space outside of the reach of the sokoban.
> It isn't yet being used."
>            (let ((loc-hash (make-hash-table :test #'equal))
>                    (stack (list soko)))
>                (defun push-os (x y)
>                    "Used to push this location onto the stack of
> locations that should be given a hash entry."
>                    (if (not (or (= (aref goals+walls x y) 2)  (gethash
> (list x y) loc-hash)))
>                        (push (list x y) stack)))
>                (do ((current-loc soko (car stack))
>                        (count 0 (1+ count)))
>                    ((null current-loc) loc-hash)
>                    (pop stack)
>                    (setf (gethash (list (car current-loc) (cadr
> current-loc)) loc-hash) count)
>                    (push-os (car current-loc) (1- (cadr current-loc)))
>                    (push-os (car current-loc) (1+ (cadr current-loc)))
>                    (push-os (1- (car current-loc)) (cadr current-loc))
>                    (push-os (1+ (car current-loc)) (cadr current-loc)))))
>              (defvar loc-hash (make-loc-hash)
>            "A hash of all spaces that could potentially be reached by
> the sokoban, ie excluding walls, in the notation of (x y).")
>              (defvar past-loc (make-hash-table :test #'equalp)
>            "Another hash table not currently being used - will be used
> in futur to remember posititions that have already been visited.")
>              (defun rec-solver (boxes soko); expects map-size,
> goals+walls, loc-hash
>            "The actual recursive array that goes through all the
> possible locations."

>            (defun find-reachable ();needs map-size, soko, goals+walls,
> boxes
>                "Returns an array containing all the locations that the
> sokoban can reach,
>                taking into account boxes that stop his path. Reachable
> locations are noted with a 1."
>                (let ((reachable (make-array map-size :element-type '(mod
> 2)))
>                        (stack (list soko)))
>                    (defun declare-reachable (x y)
>                        "Oficially declare a location as reachable by
> sokoban
>                        - and stick on stack as a location who's
> neighboors should be checked for reachability."
>                        (setf (aref reachable x y) 1)
>                        (push (list x y) stack))
>                    (defun push-os (x y)
>                        "If there is no box or wall at this location, and
> it isn't reachable yet,
>                        call declare-reachable to make it such, and to
> push it onto the stack."
>                        (if (and (= (aref reachable x y) 0) (< (aref
> goals+walls x y) 2) (= (aref boxes x y) 0))
>                            (declare-reachable x y)))
>                    (setf (aref reachable (car soko) (cadr soko)) 1) ;set
> location of soko to reachable
>                    (do ((current-loc soko (car stack)))
>                        ((null current-loc) reachable)
>                        (pop stack)
>                        (push-os (car current-loc) (1- (cadr current-loc)))
>                        (push-os (car current-loc) (1+ (cadr current-loc)))
>                        (push-os (1- (car current-loc)) (cadr current-loc))
>                        (push-os (1+ (car current-loc)) (cadr
> current-loc)))))
>                      (let ((reachable (find-reachable)))
>                (incf total-nodes)

...

read more »



Tue, 18 Oct 2005 04:06:05 GMT  
 Array out of bounds in Sokoban solver and hash of arrays

Quote:

>> Lisp doesn't make copies when you pass arguments.  You're passing a
>> reference to the same object.

> (setq a 10)
>=> 10

> (defun go (x)
>      (setq x (- x 5))

Incidentally, this can be written as:

       (decf x 5)

Quote:
>      (print x))
>=> GO

Which Lisp implementation allowed you to define a function called GO ?

Quote:
> (go a)
>=>5 5

> a
>=>10

> If you're passing a reference in go, how come changing x in go doesn't
> affect a then?

Lisp's parameter passing is more like Java's than C's.  Passing a
parameter to a function establishes a new binding between the
parameter name and the value passed in the argument list.  The binding
can be modified, as you've done above with SETQ, and the value
(object) itself can be changed if it's mutable.  No copy of the value
is made, though:

  > (defun change-car (list value)
       (setf (car list) value))
  CHANGE-CAR

  > (defvar some-list (list 1 2 3 4 5))
  SOME-LIST

  > some-list
  (1 2 3 4 5)

  > (change-car some-list "one")
  "one"

  > some-list
  ("one" 2 3 4 5)

If a copy of the list was passed then the changes made inside the
function would not be visible to the caller.

Quote:
> Doesn't lisp have to create the space necessary for x,
> and copy the value of a to it in order to be able to work with it?

No.

Jeremy.



Tue, 18 Oct 2005 04:08:54 GMT  
 Array out of bounds in Sokoban solver and hash of arrays
If your screen file, like mine, ended without a newline on the last line
of tokens, that line never gets processed by map-size. fwiw.

kt

Quote:

> I'm working on a sokoban solver. It is currently only brute force based,
> though I plan to add some optimizations later.
> I have a bug somewhere in my source that makes me move my boxes beyond a
> wall, and eventually, out of the array. I then obviously get an array
> out of bounds error. I've already spent several hours looking through
> the source, testing small bits of it, and just can't track down the
> problem.
> Could somone please take a look at the source? I'm fairly certain that
> there's no mistake in the reader functions (get-map,  map-size,
> find-reachable) as I've printed out the result and compared it to the
> original. The problem still arises even without the move-further
> function, so it isn't there either. I just really don't know what could
> be going wrong in the rest of the program. Did I miss a possibility
> somewhere?

> Some parts of the program aren't implemented yet, notably  the function
> that checks if a solution has been found - but I figured that adding
> that won't make my array problem go away ;).

> I'm going to use a hash table to check if I'm coming back to a position
> I have already visited. However, I'd have to make a hash of a list of
> the array that stores the boxes and the position of sokoban (or rather
> some standard reachable square - such as the top left most reachable
> square). This would mean that I'd have to use equalp - which is slower.
> I was therefore wondering if it would be worthwhile to come up with a
> number value that would represent this array and the sokoban location,
> and use this for the hash, using eql for the hash table. Or would the
> calculation of that number take more time than creating a hash for the
> array?

> Thanks in advance to anyone willing to read my source - any comments
> would be appreciated - it's my first "real" lisp program, and there's
> probably many things that I could do better differently. In particular,
> if there is any more elegant way of reading in the maps in the first
> place, rather than using the property list, and which functions would be
> better as macros.

> (defconstant +map-location+
> '/Derek/Programming/Lisp/Sokoban/screens/screen.)
> (defconstant +drive+ #\D)
> (defun map-file (current-map)
>    (format nil "~C~C~S~D" +drive+ #\: +map-location+ current-map))

> (defun solve-map (map-number)
>    "The main function that sets up all the variables and calls rec-solve
> to actually solve the map."
>      (defun map-size ();expects map-number
>        "Gets the dimension of the map that is to be solved. Goes through
> map line by line, remembering the longest line, and the total number of
> lines."
>        (with-open-file (in-stream (map-file map-number) :direction :input)
>            (let ((max-width 0)
>                    (width 0)
>                    (length 0))
>               (do ((char-to-be-processed (read-char in-stream)
> (read-char in-stream nil 'the-end)))
>                    ((not (characterp char-to-be-processed)) (list
> max-width length))
>                    (cond ((eql char-to-be-processed #\newline)
>                            (incf length)
>                            (if (< max-width width) (setq max-width width))
>                            (setq width 0))
>                        (T
>                            (incf width)))))))
>      (let ((map-size (map-size))
>            (total-nodes 0)
>            (move 0)
>            (solution 0)
>            (goals+walls nil)
>            (boxes nil)
>            (soko nil))
>              ;;the symbols for the goals+walls map - trans for
> "translate this symbol into machine code"             (setf (get
> 'g+w-trans-symbol '#\ ) 0)

>        (setf (get 'g+w-trans-symbol '#\.) 1)
>        (setf (get 'g+w-trans-symbol '#\$) 0)
>        (setf (get 'g+w-trans-symbol '#\*) 1)
>        (setf (get 'g+w-trans-symbol '#\#) 2)
>        ;;the symbols for the boxes map
>        (setf (get 'box-trans-symbol '#\ ) 0)

>        (setf (get 'box-trans-symbol '#\.) 0)
>        (setf (get 'box-trans-symbol '#\$) 1)
>        (setf (get 'box-trans-symbol '#\*) 1)
>        (setf (get 'box-trans-symbol '#\#) 0)
>                             (defun get-map ();expects map-size and
> map-number
>            "Reads the map from file and returns an array containing the
> walls (as 2s), the goals (as 1s) and empty space (as 0s);
>            Also returns an array containing all the boxes (as 1s), and a
> list of the location of the sokoban."
>            (with-open-file (in-stream (map-file map-number) :direction
> :input)
>                (let (  (goals+walls    (make-array map-size
> :element-type '(mod 3)))
>                        (boxes          (make-array map-size
> :element-type '(mod 2)))
>                        (soko           nil)
>                        (x              0)
>                        (y              0))
>                    (do ((current-char (read-char in-stream) (read-char
> in-stream nil 'the-end)))
>                        ((not (characterp current-char)) (values
> goals+walls boxes soko))
>                        (cond ((eql current-char #\newline)
>                                (incf y)
>                                (setq x 0))
>                            (T                                (setf (aref
> goals+walls x y) (get 'g+w-trans-symbol current-char))
>                                (setf (aref boxes x y) (get
> 'box-trans-symbol current-char))

> (list x y)))
>                                (incf x)))))))
>              (multiple-value-setq (goals+walls boxes soko) (get-map))
>                 (defun make-loc-hash ()
>            "Makes a hash table containing all the open spaces on the map.
>            Can be used later in order to make the algorithm more
> efficient by storing data in an array containing only the open spaces
>            - not the walls or space outside of the reach of the sokoban.
> It isn't yet being used."
>            (let ((loc-hash (make-hash-table :test #'equal))
>                    (stack (list soko)))
>                (defun push-os (x y)
>                    "Used to push this location onto the stack of
> locations that should be given a hash entry."
>                    (if (not (or (= (aref goals+walls x y) 2)  (gethash
> (list x y) loc-hash)))
>                        (push (list x y) stack)))
>                (do ((current-loc soko (car stack))
>                        (count 0 (1+ count)))
>                    ((null current-loc) loc-hash)
>                    (pop stack)
>                    (setf (gethash (list (car current-loc) (cadr
> current-loc)) loc-hash) count)
>                    (push-os (car current-loc) (1- (cadr current-loc)))
>                    (push-os (car current-loc) (1+ (cadr current-loc)))
>                    (push-os (1- (car current-loc)) (cadr current-loc))
>                    (push-os (1+ (car current-loc)) (cadr current-loc)))))
>              (defvar loc-hash (make-loc-hash)
>            "A hash of all spaces that could potentially be reached by
> the sokoban, ie excluding walls, in the notation of (x y).")
>              (defvar past-loc (make-hash-table :test #'equalp)
>            "Another hash table not currently being used - will be used
> in futur to remember posititions that have already been visited.")
>              (defun rec-solver (boxes soko); expects map-size,
> goals+walls, loc-hash
>            "The actual recursive array that goes through all the
> possible locations."

>            (defun find-reachable ();needs map-size, soko, goals+walls,
> boxes
>                "Returns an array containing all the locations that the
> sokoban can reach,
>                taking into account boxes that stop his path. Reachable
> locations are noted with a 1."
>                (let ((reachable (make-array map-size :element-type '(mod
> 2)))
>                        (stack (list soko)))
>                    (defun declare-reachable (x y)
>                        "Oficially declare a location as reachable by
> sokoban
>                        - and stick on stack as a location who's
> neighboors should be checked for reachability."
>                        (setf (aref reachable x y) 1)
>                        (push (list x y) stack))
>                    (defun push-os (x y)
>                        "If there is no box or wall at this location, and
> it isn't reachable yet,
>                        call declare-reachable to make it such, and to
> push it onto the stack."
>                        (if (and (= (aref reachable x y) 0) (< (aref
> goals+walls x y) 2) (= (aref boxes x y) 0))
>                            (declare-reachable x y)))
>                    (setf (aref reachable (car soko) (cadr soko)) 1) ;set
> location of soko to reachable
>                    (do ((current-loc soko (car stack)))
>                        ((null current-loc) reachable)
>                        (pop stack)
>                        (push-os (car current-loc) (1- (cadr current-loc)))
>                        (push-os (car current-loc) (1+ (cadr current-loc)))
>                        (push-os (1- (car current-loc)) (cadr current-loc))
>                        (push-os (1+ (car current-loc)) (cadr
> current-loc)))))
>                      (let ((reachable (find-reachable)))
>                (incf total-nodes)
>                              (defun is-reachable (x y); expects reachable
>                    "Check if this location is reachable; return T if it
> is."
>                    (if (= 1 (aref reachable x y)) T nil))
>                              (defun

...

read more »



Tue, 18 Oct 2005 04:21:11 GMT  
 Array out of bounds in Sokoban solver and hash of arrays

Quote:

> Because the assignment changes what the local variable X refers to.

> (defvar *variable* (list 1 2))

> (defun go (x)
>   (setf (car x) 3)
>   (setf x (list 10 11))
>   (print x)
>   nil)

> (go *variable)
> prints: (10 11)
> (print *variable*)
> prints: (3 2)

Oh, thanks! That would explain some problems I had previously :)


Tue, 18 Oct 2005 04:20:50 GMT  
 Array out of bounds in Sokoban solver and hash of arrays
Quote:

> I'm gonna look at the code a little just out of curiosity, and this will
> not explain the coding error, but shouldn't the screen be:

>     #####
>     #   #
>     #$  #
>   ###  $##
>   #  $ $ #
> ### # ## #   ######
> #   # ## #####  ..#
> # $  $          ..#

>     #     #########
>     #######

Indeed - something went wrong during pasting :)


Tue, 18 Oct 2005 04:22:46 GMT  
 Array out of bounds in Sokoban solver and hash of arrays

Quote:
> Which Lisp implementation allowed you to define a function called GO ?

Now that I think of it, indeed, it wasn't a very good idea to use go as
an example. Though aren't you officially aloud to redifine functions
that are part of the standard? I thought it could be done, just that it
is not "a good thing".  Besides, it's not good programming practice to
use go anyhow, right? ;)

I'm using the Corman IDE/compiler. I'm quite happy with it, and the fact
that I don't yet have to learn to know allegro's interface, though I'll
eventually get there...



Tue, 18 Oct 2005 04:31:39 GMT  
 Array out of bounds in Sokoban solver and hash of arrays

Quote:


>> I'm gonna look at the code a little just out of curiosity, and this
>> will not explain the coding error, but shouldn't the screen be:

>>     #####
>>     #   #
>>     #$  #
>>   ###  $##
>>   #  $ $ #
>> ### # ## #   ######
>> #   # ## #####  ..#
>> # $  $          ..#

>>     #     #########
>>     #######

> Indeed - something went wrong during pasting :)

 >

I wonder how that could affect only certain lines. Anyway, the output of
get-map looked pretty bad until I added ":initial-element 0" to the
make-arrays. your algorithm may have been processing garbage.

--

  kenny tilton
  clinisys, inc
  http://www.tilton-technology.com/
  ---------------------------------------------------------------
"Everything is a cell." -- Alan Kay



Tue, 18 Oct 2005 05:14:35 GMT  
 Array out of bounds in Sokoban solver and hash of arrays

Quote:
> Thanks in advance to anyone willing to read my source - any comments
> would be appreciated - it's my first "real" lisp program, and there's
> probably many things that I could do better differently.

Well, a boring observation to begin with: your lines are too long,
especially if you're going to be posting your code to Usenet :-).
I've attempted to undo the worst of the line-wrapping damage below.
The indentation seems to be rather messed up too; I've tried to
fix it a bit.

Quote:
> (defconstant +map-location+
> '/Derek/Programming/Lisp/Sokoban/screens/screen.)
> (defconstant +drive+ #\D)
> (defun map-file (current-map)
>     (format nil "~C~C~S~D" +drive+ #\: +map-location+ current-map))

(defconstant +map-base+ "D:/Derek/Programming/Lisp/Sokoban/Screens/screen")
(defun map-file (number)
  (format nil "~A.~A" +map-base+ number))

seems nicer to me. When you want a string, use a string,
not a symbol or a character. (It's possible that what you
actually want is a *pathname*, but pathnames are a bit
hairy and you may prefer to avoid them for now.) And the
trailing "." on your +map-location+ is, um, a bit icky.

I'd also advise finding a name other than MAP-FILE, which
sounds a little like a counterpart of MAPCAR for files.
Perhaps use "board" or "problem" or "layout" instead of
"map"?

Quote:
> (defun solve-map (map-number)
>     "The main function that sets up all the variables and calls
> rec-solve to actually solve the map."

As a stylistic note, I think functions' docstrings should
say what the function does, not what it is. Thus:

(defun solve-map (map-number)
  "Solve a Sokoban problem by setting up some variables
  and calling REC-SOLVE."

Quote:
>       (defun map-size ();expects map-number
>         "Gets the dimension of the map that is to be solved. Goes
> through map line by line, remembering the longest line, and the total
> number of lines."

Barry Margolin already suggested that these internal definitions
are bad style, and so they are. Most of them should be taken out
to top level, and things they need to be able to see should be
passed in as parameters or made global variables. (Possibly the
board, for instance, should be a global variable.) Some of them
might want to stay internal, and be defined locally using LABELS
or FLET.

The docstring should say exactly what the function returns.

(defun map-size ()
  "Read the map file and return a list (COLUMNS LINES)
  giving its size."

Quote:
>         (with-open-file (in-stream (map-file map-number) :direction :input)
>             (let ((max-width 0)
>                   (width 0)
>                   (length 0))
>                (do ((char-to-be-processed (read-char in-stream) (read-char in-stream nil 'the-end)))
>                     ((not (characterp char-to-be-processed)) (list max-width length))
>                     (cond ((eql char-to-be-processed #\newline)
>                             (incf length)
>                             (if (< max-width width) (setq max-width width))
>                             (setq width 0))
>                         (T
>                             (incf width)))))))

(defun read-map (map-number)
  "Read the lines from a map file, and return them in a list."
  (with-open-file (stream (map-file map-number) :direction :input)
    (let ((eof-object (list)))
      (loop for line = (read-line stream nil eof-object)
            until (eq line eof-object)
            collect line))))

(defun map-size (map-lines)
  (list (loop for line in lines maximize (length line))
        (length lines))))

Quote:
>       (let ((map-size (map-size))
>             (total-nodes 0)
>             (move 0)
>             (solution 0)
>             (goals+walls nil)
>             (boxes nil)
>             (soko nil))
>         ;;the symbols for the goals+walls map - trans for "translate this symbol into machine code"
>         (setf (get 'g+w-trans-symbol '#\ ) 0)

>         (setf (get 'g+w-trans-symbol '#\.) 1)
>         (setf (get 'g+w-trans-symbol '#\$) 0)
>         (setf (get 'g+w-trans-symbol '#\*) 1)
>         (setf (get 'g+w-trans-symbol '#\#) 2)
>         ;;the symbols for the boxes map
>         (setf (get 'box-trans-symbol '#\ ) 0)

>         (setf (get 'box-trans-symbol '#\.) 0)
>         (setf (get 'box-trans-symbol '#\$) 1)
>         (setf (get 'box-trans-symbol '#\*) 1)
>         (setf (get 'box-trans-symbol '#\#) 0)

Property lists are on the whole best avoided. Especially when
all the properties are on one or two symbols! Further, there's
a really subtle trap you've fallen into: character objects
are a particularly bad choice of indicator for property lists,
because two instances of the same character are *not guaranteed
to be identical* (i.e., not guaranteed to compare equal using
EQ). So using them as indicators in a property list is unsafe.
Uh-oh. :-)

I also think it's bad style to have all these magic
numbers flying around. I'd prefer to see something along
the following lines:

(defvar *symbol-props*
  '((#\  nil nil nil)

    (#\. t   nil nil)
    (#\$ nil nil t)
    (#\* t   nil t)
    (#\# nil t   nil))
  "List of (char goal? wall? box?).")

(defun char-goalp (c) (second (assoc c *symbol-props*)))
(defun char-wallp (c) (third  (assoc c *symbol-props*)))
(defun char-boxp  (c) (fourth (assoc c *symbol-props*)))

I don't like any of the names I've used, but it's not
completely clear to me what these things are for. You
can probably come up with better names. All this ASSOC
and FOURTH stuff is somewhat less than optimally efficient,
but I conjecture that this doesn't matter at all.

- Show quoted text -

Quote:
>         (defun get-map ();expects map-size and map-number
>             "Reads the map from file and returns an array containing the walls (as 2s),
>             the goals (as 1s) and empty space (as 0s);
>             Also returns an array containing all the boxes (as 1s), and
>             a list of the location of the sokoban."
>             (with-open-file (in-stream (map-file map-number) :direction :input)
>                 (let (  (goals+walls    (make-array map-size :element-type '(mod 3)))
>                         (boxes          (make-array map-size :element-type '(mod 2)))
>                         (soko           nil)
>                         (x              0)
>                         (y              0))
>                     (do ((current-char (read-char in-stream) (read-char  in-stream nil 'the-end)))
>                         ((not (characterp current-char)) (values  goals+walls boxes soko))
>                         (cond ((eql current-char #\newline)
>                                 (incf y)
>                                 (setq x 0))
>                               (T
>                                 (setf  (aref goals+walls x y) (get 'g+w-trans-symbol current-char))
>                                 (setf (aref boxes x y) (get  'box-trans-symbol current-char))

>                                 (incf x)))))))

Looping over characters is such a very C-ish thing to do.
Here's another place where you'd rather have a list of lines,
as conveniently provided by the READ-MAP function I defined
earlier, and use nested loops. This also lets us avoid
reading the file twice. (You'll notice that my version
of MAP-SIZE takes a list of lines, not something that
specifies a file to read.)

I think it's better to have a single array containing all the
information about each square. And, rather than using magic numbers
to contain that information, do something like this:

(defstruct square
  goalp wallp boxp)

(defun get-map (map-number)
  "Read a map file. Return three values: a 2-dimensional array
  containing SQUARE objects indexed as (column, row), and a
  list (column row) giving the player's initial position."
  (let* ((map-lines (read-map map-number))
         (size      (map-size map-lines))
         (result    (make-array size))
         (position  nil))
    (loop for line-number upfrom 0 for line in map-lines do
      (loop for column-number below (first size) do
        (let ((c (if (< column-number (length line))
                   (char line column-number)
                   #\ )))
          (setf (aref result column-number line-number)
                (make-square :goalp (char-goalp c)
                             :wallp (char-wallp c)
                             :boxp  (char-boxp c)))

            (setq position (list column-number line-number))))))
    (values result position)))

I also happen to find DO unreadable, which is another reason why
I prefer those nested LOOPs. Opinions vary on this. :-)

- Show quoted text -

Quote:
>         (multiple-value-setq (goals+walls boxes soko) (get-map))
>         (defun make-loc-hash ()
>             "Makes a hash table containing all the open spaces on the map.
>             Can be used later in order to make the algorithm more efficient by storing data in an array containing only the open spaces
>             - not the walls or space outside of the reach of the sokoban. It isn't yet being used."
>             (let ((loc-hash (make-hash-table :test #'equal))
>                     (stack (list soko)))
>                 (defun push-os (x y)
>                     "Used to push this location onto the stack of locations that should be given a hash entry."
>                     (if (not (or (= (aref goals+walls x y) 2)  (gethash (list x y) loc-hash)))
>                         (push (list x y) stack)))
>                 (do ((current-loc soko (car stack))
>                         (count 0 (1+ count)))
>                     ((null current-loc) loc-hash)
>                     (pop stack)
>                     (setf (gethash (list (car current-loc) (cadr current-loc)) loc-hash) count)
>                     (push-os (car current-loc) (1- (cadr current-loc)))
>                     (push-os (car

...

read more »



Tue, 18 Oct 2005 04:47:12 GMT  
 Array out of bounds in Sokoban solver and hash of arrays

Quote:

>        (setf (get 'g+w-trans-symbol '#\.) 1)
>        (setf (get 'g+w-trans-symbol '#\$) 0)
>        (setf (get 'g+w-trans-symbol '#\*) 1)
>        (setf (get 'g+w-trans-symbol '#\#) 2)

Above needs an entry for #\Space (a little more readable than #\ , btw).
Without it ACL whines about me trying to store a nil in a '(mod 3) typed
array.

btw, you are treating the major index as the column and the minor index
as the row. i guess it does not matter, but that's hard for me to
visualize. any chance you tripped up on that in your indexing?

kt

--

  kenny tilton
  clinisys, inc
  http://www.tilton-technology.com/
  ---------------------------------------------------------------
"Everything is a cell." -- Alan Kay



Tue, 18 Oct 2005 05:21:24 GMT  
 
 [ 38 post ]  Go to page: [1] [2] [3]

 Relevant Pages 

1. for every element of array find bounds in another array

2. Problem with with Array of U8 to Array of Array of Boolean

3. convert 2d array to 1d array without using shift registers and build array

4. Arrays: Build array in multiple for loops or replace array elements

5. Multidimensional array vs. array of array

6. Question about array ops on arrays of types of arrays of ...(ack)

7. adjustable-array-p, adjust-array and array-destruction

8. Error BASE/1132 Bound error: array access

9. Error BASE/1133 Bound error: array assign

10. Bound Array Error??

11. Two questions (mutiple values, array index bounds)

12. runtime bounds on arrays

 

 
Powered by phpBB® Forum Software