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 |
solution
