def make_random_caves(width, height):
    '''Generate a random cave map.'''
    WALL = '#'
    EMPTY = ' '

    def eat_away(mapgrid, start:position):
        '''Recursively eat away tunnels.

        This works by consuming 2-cell mini-segments, then moving to
        the end of the 2-cell segment and recursing. The 2-cell spacing
        is enough to allow for a corridor, a turn, and then (2 cells) move
        past the wall that defines the corridor. Effectively, this means
        that only the odd (or even) cells will be eaten, with the walls
        being those cells of opposite parity.

        At each node (intersection?), all 4 cardinal directions are tried,
        starting at a random point in the cycle. Because the recursion happens
        at the end of each direction, recursive eating may cause a direction
        to be blocked when the recursion returns and the direction cycle
        advances to point that way.

        Consider:

            #####
            #2.3#
            #.#.#
            #1#4#
            #####

        In this example, eating starts at 1, eats a segment north, and
        recurses. At 2, the random direction is east, so a segment is
        consumed. At 3, the random direction is south, a segment is consumed,
        and we recurse to 4. Assuming the grid was only 5x5, there is no place
        that can be eaten from 4, since all 4 directions are either off-limits
        or already cleared. When the recursion returns to point 1, it might
        consider moving east to point 4, but because that cell is already
        cleared it will do nothing and return.
        '''

        # List of directions to try, randomly rotated.
        try_dirs = (direction.WEST, direction.EAST,
                    direction.SOUTH, direction.NORTH)
        start_dir = random.randrange(len(try_dirs))
        try_dirs = try_dirs[start_dir:] + try_dirs[:start_dir]

        for dirn in try_dirs:
            dv = dirn.vector
            p1 = start + dv
            p2 = start + 2 * dv

            if p2 not in mapgrid:
                # might go past the border - don't.
                continue

            if any(mapgrid[p] != WALL for p in (p1, p2)):
                # might already have a tunnel - don't connect them.
                continue

            for p in (p1, p2):
                mapgrid[p] = EMPTY

            eat_away(mapgrid, p2)

    mapgrid = grid(width=width, height=height, fill=WALL)
    eat_away(mapgrid, position(1, 1))