Quiz 5: Amazing arrays

From newLISP on Noodles

Challenge

Here's the contents of a simple 2D array (16 rows by 16 columns):

  @@@@@@@@@@@@@@@@
  ....@@....@.@..@
  @..@@@.@@@...@.@
  @.......@..@.@.@
  @...@@....@....@
  @@.@@@@@.@....@@
  @..@.......@@..@
  @@@...@@..@@@..@
  @@@.@@@.@@@.@..@
  @@@...@@@@.@@@@@
  @.@@..@@.....@.@
  @........@@..@.@
  @.@@....@..@...@
  @@.@@@@...@.@..@
  @.......@..@....
  @@@@@@@@@@@@@@@@

If you think of the @'s as walls and the .'s as spaces, this is a simple maze. With one exit point near the top left corner, and another exit just above the bottom right corner, there might well be a valid pathway through this maze - I think there is in this case.

Your mission, should you decide to accept it, is to use newLISP to produce mazes like this to order, and work out a good way to store them. They should store quite compactly, being essentially binary. I wonder whether the hard bit will be making sure that there's at least one valid path...? A wall should extend all the way around the edge, except at the gateways.

As for solving the resulting mazes - perhaps that will be a future challenge!

Solutions

I've got as far as I can with this, and have run out of time again... So here's what I've managed so far:

A simple algorithm for creating a maze consists of defining a grid of cells, each of which have walls (North, East, West, and South). Then:

1) Start at any cell in the grid. 2) Look for one of the neighbouring cells whose walls are intact. 3) If there is one, move there, knocking down the wall that joins the two cells. If there isn't one, go back to the previous cell. 4) Repeat steps 2 and 3 until every cell in the grid has been visited.

Here's my newLISP code for this.

First create some variables and the grid:

  (set  'height 10 
        'width 10
        'maze (array height width '("ensw")))
  
  (set  'cell-stack '() 
        'total-cells (* height width)
        'current-cell (list (rand height) (rand width))
        'visited-cells 1)

cell-stack will hold the list of cells that have been visited. Each cell in the maze starts off with its four walls intact ("ensw").

A function called find-intact-neighbours finds which of the four neighbouring cells have all their walls intact:

  (define (find-intact-neighbours cell)
    (local (r c n w s e results)
    (map set '(r c) cell)
    ; find all valid neighbours
    (if (> r 0)             (set 'n (list (- r 1) c)))
    (if (> c 0)             (set 'w (list r (- c 1) )))
    (if (< r (- height 1))  (set 's (list (+ r 1) c)))
    (if (< c (- width 1))   (set 'e (list r (+ c 1))))  
    ; find ones with all their walls intact
    (dolist (c (clean nil? (list n w s e)))
      (if (= "ensw" (nth (first c) (last c) maze))
        (push c results)))
    results))

A function called remove-wall removes a wall from a cell:

  (define (remove-wall cell wall)
    (nth-set (first cell) (last cell) maze 
     (replace wall (nth (first cell) (last cell) maze) "")))

A function called join-cells removes the walls common to two cells:

 
  (define (join-cells cell1 cell2)
    (local (r1 r2 c1 c2)
    (map set '(r1 c1) cell1)
    (map set '(r2 c2) cell2)
    (if (= c1 c2) 
     (if (> r1 r2) 
      (begin 
       (remove-wall cell1 "n") (remove-wall cell2 "s"))  
      (begin 
       (remove-wall cell1 "s") (remove-wall cell2 "n")))
    (if (= r1 r2) 
     (if (> c1 c2) 
      (begin 
       (remove-wall cell1 "w") (remove-wall cell2 "e")) 
      (begin 
       (remove-wall cell1 "e") (remove-wall cell2 "w")))))))

I suppose I could write a function that accepts a list of cells and walls here...

Finally, the main loop goes through all cells, following the algorithm.

  (while (< visited-cells total-cells)
    (set 'intact-neighbours (find-intact-neighbours current-cell))
    (if (> (length intact-neighbours) 0)
      (begin
        (set 'temp-cell 
          (nth (rand (length intact-neighbours)) intact-neighbours))
        (join-cells temp-cell current-cell)
        (push current-cell cell-stack)
        (set 'current-cell temp-cell)
        (inc 'visited-cells))
      ; else
      (set 'current-cell (pop cell-stack))))

After this completes, all the cells have been visited, and the result is - apparently - a 'perfect' maze. maze now holds this list of walls:

  ( ("nw" "en" "nw" "en" "nsw" "en" "nw" "ns" "ns" "en") 
    ("ew" "sw""es" "sw" "ns" "e" "ew" "nw" "ens" "ew")
    ("ew" "nw" "ns" "en" "nsw" "e" "sw" "e" "nw" "es")
    ("ew" "w" "ens" "sw" "en" "w" "ens" "ew" "sw" "en")
    ("w" "es" "nw" "ns" "es" "esw" "nw" "s" "ens" "ew")
    ("sw" "ens" "ew" "nw" "ns" "en" "ew" "nw" "ns" "es")
    ("nw" "en" "sw" "s" "ens" "ew" "ew" "sw" "ns" "en")
    ("ew" "sw" "ns" "ns" "ns" "es" "ew" "nw" "en" "esw")
    ("w" "ns" "en" "nw" "ns" "en" "ew" "esw" "w" "en")
    ("sw" "ens" "sw" "s" "ens" "sw" "s" "ns" "es" "esw"))

What I need to do now is to generate a sensible view of the maze definition. I haven't worked out how to do this yet... Cormullion 04:35, 8 December 2006 (PST)