(archive 'newLISPer)

March 30, 2009

Mazes

Filed under: newLISP — newlisper @ 20:38
Tags:

Here’s the first of what might become a series of posts about maze programming and newLISP. I’ve been fascinated by mazes ever since I was taken to Hampton Court Maze as a kid, and today I still occasionally write some maze-related code when I need a simple project to test out new languages or techniques.

Although I wrote a lot of this code last year (or the year before), I’ve updated it a bit for newLISP 10, and dusted it off to keep this blog going for a while until I get some time to write some new stuff.

Jumping right in: a Maze context contains the data and functions for a single maze, which is stored as a rectangular grid of squares, of which some can be solid ‘walls’ and the rest empty. But the maze data is stored in a flat list rather than an array. Yes, I know that arrays can be quicker, but it’s often the case that lists are more versatile – more functions work on lists than on arrays – and the performance hit that I’m incurring won’t really be an issue for me.

(context 'Maze)
(constant 'wall -2 'empty -1)
(define M)
(define height)
(define width)
(define maze-length)

(define (make (h 15) (w 15))
  (set 'height h 'width w 'maze-length (* height width))
  (set 'M (dup wall maze-length))
  M)

This function makes a pretty solid mass of walls, with no passages or corridors. Each ‘cell’ of the maze M can be accessed by a single index number n. Using newLISP’s implicit addressing, this is simply (M n).

To make life easy for my code, the maze must be completely surrounded by a solid wall. The following simple functions test a single cell to see if it’s on the outside wall:

(define (north-perimeter? n) (= (/ n width) 0))
(define (south-perimeter? n) (> n (- maze-length width)))
(define (east-perimeter?  n) (= (% n width) (- width 1)))
(define (west-perimeter?  n) (= (% n width) 0)) 

And this is a useful test: is the cell n on the outside wall?

(define (perimeter? n)
(or
  (north-perimeter? n)
  (south-perimeter? n)
  (east-perimeter? n)
  (west-perimeter? n)))

Next, to generate a maze. For now, I’m happy to have a simple randomly-generated maze. Later, I’ll create mazes with a little more thought. Passages are excavated from the solid maze by the following function:

(define (random-fill)
   (dotimes (i maze-length)
       (and (not (perimeter? i))
            (setf (M i) empty)
            (= (rand 3) 0)      ;  1 in 3
            (setf (M i) wall))))

About 1 in 3 cells are solid, which gives reasonable values. Actually, this isn’t a very good function, since it sets every cell to be empty, then sets some of them back to be solid again.

For simple debugging at the terminal, a simple show function is useful.

(define (show (maze M))
(for (n 0 (- maze-length 1))
    (cond
      ((= (maze n) wall)    (print (char (int "x2588"))))
      ((= (maze n) empty)   (print " ")))
    (if (east-perimeter? n)
        (println))))

That Unicode symbol is useful for printing out solid shapes. The procedure for making a maze is the following sequence of functions:

(make 15 15)
(random-fill)
(show)
███████████████
██   █  ██    █
█  █ █     ████
█ █   █    ████
█ █  █  █    ██
█ █   ███    ██
█  ██  ████ █ █
█ █ █ ██   ██ █
██ █  █ █ █   █
██ █      █ ███
█  █  █  █    █
██   █    █   █
█ █  █  █   █ █
█   █     █ █ █
███████████████

which, although not beautiful, is at least useful. You can generate more appealing graphical displays using any technology you fancy: I’ve been using the new HTML Canvas module for newLISP to generate output; this is much easier than trying to get OpenGL working properly. (I drew the OpenGL graphics more or less successfully, but was unable to position the eye-point in such a way that I could actually see them.)

maze00001.png

This is a useful helper function to find the empty neighbouring cells of a given cell:

(define (empty-neighbours n)
(clean nil?
  (map (fn (o)
       (if (= empty (M (- n o)))
           (- n o)))
       (list 1 -1 height (- height)))))

To choose an empty cell at random:

(apply amb (ref-all empty M))
;-> (69)

and to select two empty cells at random:

(set 'start (first (apply amb (ref-all empty M))))
;-> 69
(set 'end   (first (apply amb (ref-all empty M))))
;-> 153

Now we get to the interesting stuff. How can we find out whether there’s a path from start to end? There are, of course, many interesting maze-solving algorithms, but I’m quite fond of the following one, which is quick, clever, and a little bit baffling too. I think it’s related to an algorithm developed by someone called Bellman, but I’ve not traced a definitive reference yet. It’s a ‘tidal flooding’ algorithm, and it works as follows.

Before you start, you prepare a list that’s the same length as the maze, but empty. This list, the route map, is going to hold the solution. Then, you begin by ‘standing’ in the finishing cell. You look at each of the neighbouring cells in turn. If a cell is empty, you store its number in the current cell, make a note of how to get over there from where you’re standing, and mark it as the current ‘frontier’ cell. You repeat this process until you’re standing in the starting cell, or have looked at every cell. If you’ve reached the starting cell, you have, in the route map, values for all the cells that have been examined, with instructions (in the form of a number representing how many cells to move) on how to reach the end. It’s then easy to extract a solution from this map.

This is the solver function:

(define (flood start finish)
(local (solution current-cell frontier-cell cells route-map)
  (set 'current-cell finish 'frontier-cell finish)
  (set 'route-map (dup nil (length M)))
  (until (or (= current-cell start) (> cells (length M)))
      (inc cells)
      (map (fn (neighbour)
                (setf (M frontier-cell) neighbour)
                (setf (route-map neighbour) (- (- neighbour current-cell)))
                (set 'frontier-cell neighbour))
           (empty-neighbours current-cell))
      (set 'current-cell (M current-cell)))
  (if (= current-cell start)
      route-map)))

Run it thus:

(set 'route-map (flood start end))

If there is a solution, route-map contains a list of offsets for all visited cells. The following image superimposes the contents of this list on the maze: a value of 1 means move one cell to the right, a value of 15 means move down to the next row, and so on.

maze00008.png

This solution can be converted into a list of North/South/East/West directions, or a list of cells to follow, by these functions:

(define (get-direction n)
  (cond
    ((= n 1)  "E")
    ((> n 1)  "S")
    ((= n -1) "W")
    ((< n -1) "N")))

(define (get-solution route-map start finish)
  (local (current-cell solution)
    (set 'current-cell start)
    (until (= current-cell finish)
         (push
          (list current-cell
                (get-direction (route-map current-cell))) solution -1)
         (set 'current-cell  (+ current-cell (route-map current-cell))))
    solution))

The solution then looks like this:

 ((69 "E")
  (70 "S")
  (85 "E")
  (86 "E")
  (87 "S")
  (102 "S")
  (117 "S")
  (132 "W")
  (131 "S")
  (146 "S")
  ...

and these can be displayed graphically, or written down on a piece of cheese and fed to a maze-solving micromouse.

maze00004.png

By colouring the visited cells in blue, you can see the way the search has ‘flowed’ outward from the green starting point to the red end point, like a wave slowly flooding the maze. It’s worth noting that this version of the flooding algorithm doesn’t search the entire maze, only as much of the maze as is required. Here are some more examples:

maze00005.png

maze00006.png

maze00007.png

You can see, though, that the algorithm doesn’t always find the minimum possible number of cells.

Performance can vary, depending on the configuration of the maze and the chosen start and end points. I’m seeing solutions generated in about 600 microseconds for these simple 15 by 15 mazes, which is OK.

Next time, I’m going to be looking at another way to represent and draw mazes. Well. if I get time, I might!

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: