All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
The Mazing (Posted on 2003-10-02) Difficulty: 3 of 5
A maze is to be constructed on an X by Y grid of squares by creating "walls" between them.

The process starts with an enclosed rectangle X squares wide and Y squares tall, with walls on the outside edges of the outermost squares. Here's an example of a (6 x 2) rectangle:

       +--+--+--+--+--+--+
       |                 |
       +  +  +  +  +  +  +
       |                 |
       +--+--+--+--+--+--+
We then build additional walls in the following manner:
  • Pick an existing wall (A) at random.
  • Pick (also at random) a potential non-existent wall (W) that will be adjacent to (A). (W) must be a valid wall - it must be inside the maze.
  • Ensure that (W) will not connect wall (A) to any other wall - that is that there is no existing wall (B) that is is distinct from (A) and non-adjacent to (A) but that would be adjacent to (W).
  • Place wall (W) only if the above condition is satisfied.

    By following in these steps, what is the theoretical maximum number of walls that can be placed? Is there a situation where walls can be placed in such a way that achieving this maximum will no longer be possible?

  • See The Solution Submitted by levik    
    Rating: 3.3333 (3 votes)

    Comments: ( Back to comment list | You must be logged in to post comments.)
    Solution solution | Comment 2 of 4 |
    The best way to keep track of what positions are currently occupied by walls and what vertices currently have available adjacent unoccupied vertices to which to go, is to have an array that extends from zero to 2X by zero to 2Y. Those elements of the array with both coordinates even (including zero,zero) represent points (vertices) and the number in each such element represents how many vertices that are adjacent to this one are free (have no wall already extending to them. Those elements having an even coordinate representing the vertical direction and an odd representing the horizontal direction, represent horizontal wall segments. Those with an odd vertical coordinate and even horizontal represent vertical wall segments. These can contain just a 1 to indicate a wall is there or zero to indicate there's no wall there at present. This scheme allows a wall's coordinates to be the average of those of its two end points, and the walls around a point to differ by one from those of the point.

    Also a list must be kept of those coordinates where an current wall exists and at least one of whose endpoints has at least one available free vertex to which to connect. This will be used in the randomization process, based on how many entries there are on this list.

    Each time through, for the placement of the next wall:

    A member of this list is chosen at random. Then, of all the possible free vertices that can be reached from either of its endpoints, one such vertex is chosen, and a wall built to that vertex. The four vertices surrounding this formerly free vertex have their array positions decremented by one as that vertex is no longer free. The array position representing the line added is set to one.

    This continues until no wall segments are available from which to choose (no segments with either endpoint adjacent to any free vertex).

    In the below program, I've used h and w to represent height and width rather than x and y. Height comes first in the array subscripts, but again, is stretched by 2 to allow alternating vertices and lines (and unused spots for centers of squares--can't be helped).

    After building one maze, the program continues, unless you press Escape, to ask for your request for another maze.

    DECLARE FUNCTION isFree% (row%, col%)
    DEFINT A-Z
    DECLARE SUB showMaze ()
    DECLARE SUB chooseElig (row%, col%, which%, row2%, col2%)
    DECLARE SUB showGridVals ()
    DECLARE SUB countElig (row%, col%)

    TYPE coords
      row AS INTEGER
      col AS INTEGER
    END TYPE

    DIM SHARED h, w
    RANDOMIZE TIMER

    DO
      CLS
      DO
        INPUT "Height of grid:", h
        INPUT "Width of grid:", w
        IF h <> INT(h) OR w <> INT(w) OR h < 2 OR w < 2 THEN
          PRINT \"Height and width must be integers >= 2."
        END IF
      LOOP WHILE h <> INT(h) OR w <> INT(w) OR h < 2 OR w < 2

      REDIM SHARED grid(h * 2, w * 2)
      REDIM SHARED availW(INT((h + 1) * (w + 1) * 2)) AS coords

      ' grid positions; first subscript is vertical, second horizontal
      ' even,even = vertex; number = allowable destinations from this vertex
      ' (top left vertex is 0,0)
      ' even,odd = horizontal line segments (walls) | 0 = not walled yet
      ' odd,even = vertical line segments | 1 = already walled
      ' (odd,odd would be center of square--not used)

      numElig = 0

      FOR row = 0 TO 2 * h STEP 2 * h
        FOR col = 1 TO 2 * w STEP 2
          grid(row, col) = 1 ' horizontal bar
          numElig = numElig + 1
          availW(numElig).row = row
          availW(numElig).col = col
        NEXT
      NEXT

      FOR row = 1 TO 2 * h STEP 2
        FOR col = 0 TO 2 * w STEP 2 * w
          grid(row, col) = 1 ' vertical bars
          numElig = numElig + 1
          availW(numElig).row = row
          availW(numElig).col = col
        NEXT
      NEXT

      ' Now calculate eligible number of ways away from points

      FOR row = 0 TO 2 * h STEP 2
        FOR col = 0 TO 2 * w STEP 2
          countElig row, col
        NEXT
      NEXT

      ' showGridVals
      ' showMaze

      ' Start building Maze:
      DO
        r = INT(RND(1) * numElig + 1)
        row = availW(r).row
        col = availW(r).col

        IF row MOD 2 = 0 THEN horiz = 1: ELSE horiz = 0

        IF horiz THEN
          elig1 = grid(row, col - 1): elig2 = grid(row, col + 1)
        ELSE
          elig1 = grid(row - 1, col): elig2 = grid(row + 1, col)
        END IF

        ' Assume prob of each end is proportional to number of available lines
        ' from that point

        r2 = INT(RND(1) * (elig1 + elig2) + 1)

        IF r2 > elig1 THEN
          whichEnd = 2: r2 = r2 - elig1
        ELSE
          whichEnd = 1
        END IF

        IF horiz THEN
          row1 = row
          IF whichEnd = 2 THEN
           col1 = col + 1
          ELSE
           col1 = col - 1
          END IF
        ELSE
          col1 = col
          IF whichEnd = 2 THEN
           row1 = row + 1
          ELSE
           row1 = row - 1
          END IF
        END IF

        chooseElig row1, col1, r2, row2, col2
        ' line from these coords is now occupied by a wall and the wall's
        ' coords are the average of those of the two endpoints.
        grid((row1 + row2) / 2, (col1 + col2) / 2) = 1


        ' Re-calculate eligible number of ways away from points near new endpoint
        ' adjacent vertices have one fewer neighbor available to go to

        grid(row2 - 2, col2) = grid(row2 - 2, col2) - 1
        grid(row2 + 2, col2) = grid(row2 + 2, col2) - 1
        grid(row2, col2 - 2) = grid(row2, col2 - 2) - 1
        grid(row2, col2 + 2) = grid(row2, col2 + 2) - 1

        ' The following is probably overkill, recalculating all the eligibilities:
        'which lines have eligible points
        numElig = 0
        FOR row = 0 TO 2 * h
          FOR col = 0 TO 2 * w
           IF grid(row, col) THEN
            tot = 0
            IF row MOD 2 = 1 AND col MOD 2 = 0 THEN
              tot = grid(row - 1, col) + grid(row + 1, col)
            ELSEIF row MOD 2 = 0 AND col MOD 2 = 1 THEN
              tot = grid(row, col - 1) + grid(row, col + 1)
            END IF
            IF tot > 0 THEN
              numElig = numElig + 1
              availW(numElig).row = row
              availW(numElig).col = col
            END IF
           END IF
          NEXT
        NEXT row

      ' CLS
      ' showGridVals
      ' showMaze
      ' DO: LOOP UNTIL INKEY$ > ""

      LOOP UNTIL numElig = 0

      showMaze
      PRINT "Enter for more; Esc to end."
      DO: a$ = INKEY$: LOOP UNTIL a$ > ""
    LOOP UNTIL a$ = CHR$(27)

    END

    SUB chooseElig (row, col, which, row2, col2)
      ct = 0
      IF row - 2 > 0 AND col - 1 > 0 AND col + 1 < UBOUND(grid, 2) THEN
       IF isFree(row - 2, col) THEN ct = ct + 1
      END IF
      IF ct = which THEN row2 = row - 2: col2 = col: EXIT SUB
      IF row + 2 < UBOUND(grid, 1) AND col - 1 > 0 AND col + 1 < UBOUND(grid, 2) THEN
       IF isFree(row + 2, col) THEN ct = ct + 1
      END IF
      IF ct = which THEN row2 = row + 2: col2 = col: EXIT SUB
      IF row - 1 > 0 AND row + 1 < UBOUND(grid, 1) AND col - 2 > 0 THEN
       IF isFree(row, col - 2) THEN ct = ct + 1
      END IF
      IF ct = which THEN row2 = row: col2 = col - 2: EXIT SUB
      IF row - 1 > 0 AND row + 1 < UBOUND(grid, 1) AND col + 2 < UBOUND(grid, 2) THEN
       IF isFree(row, col + 2) THEN ct = ct + 1
      END IF
      IF ct = which THEN row2 = row: col2 = col + 2: EXIT SUB
    END SUB

    SUB countElig (row, col)
      ct = 0
      IF row - 2 > 0 AND col - 1 > 0 AND col + 1 < UBOUND(grid, 2) THEN
       IF isFree(row - 2, col) THEN ct = ct + 1
      END IF
      IF row + 2 < UBOUND(grid, 1) AND col - 1 > 0 AND col + 1 < UBOUND(grid, 2) THEN
       IF isFree(row + 2, col) THEN ct = ct + 1
      END IF
      IF row - 1 > 0 AND row + 1 < UBOUND(grid, 1) AND col - 2 > 0 THEN
       IF isFree(row, col - 2) THEN ct = ct + 1
      END IF
      IF row - 1 > 0 AND row + 1 < UBOUND(grid, 1) AND col + 2 < UBOUND(grid, 2) THEN
       IF isFree(row, col + 2) THEN ct = ct + 1
      END IF
      grid(row, col) = ct
    END SUB

    FUNCTION isFree (row, col)
      IF row > 0 THEN
        IF grid(row - 1, col) THEN isFree = 0: EXIT FUNCTION
      END IF
      IF col > 0 THEN
        IF grid(row, col - 1) THEN isFree = 0: EXIT FUNCTION
      END IF
      IF row < UBOUND(grid, 1) THEN
        IF grid(row + 1, col) THEN isFree = 0: EXIT FUNCTION
      END IF
      IF col < UBOUND(grid, 2) THEN
        IF grid(row, col + 1) THEN isFree = 0: EXIT FUNCTION
      END IF
      isFree = 1
    END FUNCTION

    SUB showGridVals
    FOR row = 0 TO 2 * h
      FOR col = 0 TO 2 * w
       IF row MOD 2 = 0 AND col MOD 2 = 0 THEN COLOR 14: ELSE COLOR 7
       PRINT USING \"###\"; grid(row, col);
       COLOR 7
      NEXT
      PRINT
    NEXT

    END SUB

    SUB showMaze
      FOR row = 0 TO 2 * h
        FOR col = 0 TO 2 * w
          IF row MOD 2 = 1 THEN
            IF col MOD 2 = 0 THEN
             IF grid(row, col) THEN
              PRINT \"|\";
             ELSE
              PRINT \" \";
             END IF
            ELSE
              PRINT \" \";
            END IF
          ELSE
            IF col MOD 2 = 0 THEN
              PRINT \"+\";
            ELSE
             IF grid(row, col) THEN
              PRINT \"--\";
             ELSE
              PRINT \" \";
             END IF
            END IF
          END IF
        NEXT
        PRINT
      NEXT
    END SUB

    Here's a sample run:
    Height of grid:21
    Width of grid:15
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    | | | | | | | | | | | |
    +--+ + + + + + + +--+ + +--+ +--+ +
    | | | | | | | |
    +--+ +--+--+ +--+--+ + + + + +--+ +--+
    | | | | | | |
    +--+--+--+ +--+--+ + +--+--+--+ + +--+--+
    | | | | | | | | | |
    +--+ +--+--+ + + + + + +--+ + + +--+
    | | | | | | | | | |
    +--+--+ + + + +--+ + + + +--+--+--+--+
    | | | | | | | | | |
    + + +--+ + + + +--+ + +--+ +--+--+ +
    | | | | | |
    + +--+ +--+--+ + +--+ + + +--+--+ + +
    | | | | | | | |
    +--+--+--+--+--+--+ + +--+--+--+--+--+--+--+
    | | | | |
    +--+--+--+--+--+ +--+ + +--+ + +--+--+--+
    | | | |
    +--+--+--+ +--+--+ + +--+--+--+--+--+--+--+
    | | | | | | |
    +--+ + +--+--+ + + +--+--+--+ +--+ +--+
    | | | | | | | |
    +--+--+--+--+ +--+ +--+ +--+ + + +--+ +
    | | | |
    +--+--+ + + +--+--+--+ +--+ + +--+--+--+
    | | | | | | | |
    + +--+--+--+--+--+ + +--+--+--+--+--+--+--+
    | | | | |
    +--+--+--+--+ +--+ +--+--+--+ +--+--+ +--+
    | | |
    +--+--+--+--+--+--+ + + +--+--+--+ +--+--+
    | | | | | | | |
    + +--+ + + +--+ + +--+--+ +--+--+--+ +
    | | | | | |
    + + + +--+--+ +--+ + + + +--+ + +--+
    | | | | | | | | | | |
    + +--+ +--+--+ + + +--+ +--+--+ + +--+
    | | | | | | | | |
    +--+ + + +--+ + + + + + + +--+ +--+
    | | | | | | | | | | | |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    Enter for more; Esc to end.

    ----------
    To see progress as you go along, the commented out lines (commented by an apostrophe) for CLS, showMaze, and the DO LOOP below them can be uncommented. The one for showGridVals can be uncommented also to see the internal changes in the array, so long as the height isn't too much to interfere with the rest of the printing. (DOS windows can be made up to 50 lines high).
      Posted by Charlie on 2003-10-02 22:16:07
    Please log in:
    Login:
    Password:
    Remember me:
    Sign up! | Forgot password


    Search:
    Search body:
    Forums (0)
    Newest Problems
    Random Problem
    FAQ | About This Site
    Site Statistics
    New Comments (3)
    Unsolved Problems
    Top Rated Problems
    This month's top
    Most Commented On

    Chatterbox:
    Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information