Problem with setf/aref and arrays

Hello, I'm writing a dungeon crawing game.

The Dungeon class is pretty simple. It consists of a 2D array of Tile structs.
The tiles can be either solid of not solid.

My problem comes with the carve-room function.
Instead of just setting the desired Tiles in the array to be nil for :solid it sets all tiles to nil for solid.

Please look at the ascii-draw routine which draws the Dungeon to the terminal. This will show that the tiles are all getting set to non solid.

;;;; Dungeon class
(defstruct Tile (solid t))

(defclass Dungeon ()
  ((width :accessor Dungeon-width
	  :initarg :width
	  :initform nil)
   (height :accessor Dungeon-height
	   :initarg :height
	   :initform nil)
   (tile-array :accessor Dungeon-tile-array
	       :initarg :tile-array
	       :initform (make-Tile))))

;;; Methods for Dungeon
(defmethod make-floor ((d Dungeon))
  "Creates a solid uncarved floor for the Dungeon"
  (setf (Dungeon-tile-array d) (make-array `(,(Dungeon-width d) 
					      ,(Dungeon-height d))
					   :initial-element 
					   (make-Tile :solid t))))

(defmethod carve-room ((d Dungeon) x y width height)
  "Carves a room out of the floor if it fits"
  (and (>= x 0) 
       (>= y 0)
       (>= width 1)
       (>= height 1)
       (<= (+ x width) (Dungeon-width d))
       (<= (+ y height) (Dungeon-height d))
        (dotimes (xx width)
	 (dotimes (yy height)
	   (setf (Tile-solid (aref (Dungeon-tile-array d) 
				   (+ x xx)
				   (+ y yy))) nil)))))

;;; Testing here
(defmethod ascii-print ((d Dungeon))
  (dotimes (y (Dungeon-height d))
    (dotimes (x (Dungeon-width d))
      (if (Tile-solid (aref (Dungeon-tile-array d) x y))
	  (princ "x")
	  (princ ".")))
    (terpri)))
	    
(defparameter *d* (make-instance 'Dungeon :width 10 :height 10))
(make-floor *d*)
(carve-room *d* 1 1 4 4)
(ascii-print *d*)

The problem is that (make-Tile :solid t) is evaluated only once:

(make-array ... :initial-element (make-Tile :solid t))

This creates an array where all array elements point to one and the same tile. That's the reason why all tiles have the same value.

Try the following code to see that (random 10) is evaluated only once and all array elements point to the same random number:

(make-array '(10 10) :initial-element (random 10))

To get independent elements you could use:

(make-array ... :initial-contents nested-list)

but this would make it necessary to create and allocate a nested list only to get it garbage-collected afterwards.

Common Lisp doesn't provide mapping functions for multi-dimensional sequences, so the only trick to use MAP would be to create a second, one-dimensional displaced vector who's elements point to the elements of the two-dimensional array and then MAP the make-Tile function over all vector elements. But this is even more complicated than using :initial-contents.

See multidimensional array elementwise operations for an example how this works in Common Lisp.

Probably the simplest solution is to fill the array with a loop:

(let ((array (make-array '(10 10))))
  (dotimes (x 10)
    (dotimes (y 10)
      (setf (aref array x y) (random 10))))
  array)

or with dungeon tiles:

(setf (Dungeon-tile-array d)
      (make-array (list (Dungeon-width d) (Dungeon-height d))))
(dotimes (x (Dungeon-width d))
  (dotimes (y (Dungeon-height d))
    (setf (aref (Dungeon-tile-array d) x y) (make-Tile :solid t))))

Maybe somebody else has a better idea?

- edgar

Thanks edgar! That seems to have done the trick.

I made this mistake very often, so I instantly knew what the problem was.

In CLtL2, Chapter 17.3 Array Information (near the bottom of the page) I found the following code to fill multi-dimensional arrays:

(dotimes (index (array-total-size (Dungeon-tile-array d)))
  (setf (row-major-aref (Dungeon-tile-array d) index) (make-Tile :solid t)))

I think this is better than my nested DOTIMES loop above. See also CLHS ARRAY-TOTAL-SIZE and ROW-MAJOR-AREF (because CLtL2 is outdated), but with me here (SBCL 1.1.15 on Debian Wheezy) the code works.

- edgar