02-12-2023, 06:06 PM
I've found recursion to be very useful for path-finding types of algorithms. I used a recursive flood fill in my Minesweeper clone:
Recursive-like routines can also be achieved using a stack as I did in my Super MegaBug program:
The maze generation code could have been done with recursion as well but a stack did nicely in this case.
Code: (Select All)
SUB REVEALCELL (x%, y%)
'**
'** Reveals the results of clicking on a game grid button (performs a recursive flood-fill)
'**
'** This is an example of a recursive subroutine, that is, a subroutine that calls itself over and over to achieve a
'** task that requires the same actions continuously. In the case of this subroutine, we need to look a grid square,
'** decide what to do with it, then move to each adjoining grid square and do the same thing, then moving onto the
'** next adjoining grid squares, deciding, move to adjoining, and so on a repeating pattern. Recursion is perfect for this!
'**
SHARED Game AS GAME ' need access to game options
SHARED Cell() AS CELL ' need access to cell grid
SHARED CellPic&() ' need access to cell pictures
SHARED CellsRemaining% ' need access to cells remaining in game
DIM Mines% ' the number of mines surrounding a given grid square
IF x% < 1 OR x% > Game.width OR y% < 1 OR y% > Game.height THEN EXIT SUB ' exit if past grid boundaries
IF Cell(x%, y%).pic <> CELLOUT AND Cell(x%, y%).pic <> CELLQOUT THEN EXIT SUB ' exit if not a button that can be revealed
IF x% < Game.width THEN ' are we at right edge of grid?
IF Cell(x% + 1, y%).mine THEN Mines% = Mines% + 1 ' no, if mine to the right add to mines
IF y% > 1 THEN IF Cell(x% + 1, y% - 1).mine THEN Mines% = Mines% + 1 ' if mine above/right add to mines if not at top of grid
IF y% < Game.height THEN IF Cell(x% + 1, y% + 1).mine THEN Mines% = Mines% + 1 ' if mine below/right add to mines if not at bottom of grid
END IF
IF x% > 1 THEN ' are we at left edge of grid?
IF Cell(x% - 1, y%).mine THEN Mines% = Mines% + 1 ' no, if mine to the left add to mines
IF y% > 1 THEN IF Cell(x% - 1, y% - 1).mine THEN Mines% = Mines% + 1 ' if mine above/left add to mines if not at top of grid
IF y% < Game.height THEN IF Cell(x% - 1, y% + 1).mine THEN Mines% = Mines% + 1 ' if mine below/left add to mines if not at bottom of grid
END IF
IF y% < Game.height THEN IF Cell(x%, y% + 1).mine THEN Mines% = Mines% + 1 ' if mine above add to mines if not at top of grid
IF y% > 1 THEN IF Cell(x%, y% - 1).mine THEN Mines% = Mines% + 1 ' if mine below add to mines if not at top of grid
IF Mines% <> 0 THEN ' were any mines found?
Cell(x%, y%).pic = Mines% ' yes, set this cell's picture to number found
_PUTIMAGE (Cell(x%, y%).x, Cell(x%, y%).y), CellPic&(Cell(x%, y%).pic) ' display the cell image
CellsRemaining% = CellsRemaining% - 1 ' decrement cell remaining count
EXIT SUB ' do not check any adjacent cells
END IF
CellsRemaining% = CellsRemaining% - 1 ' decrement cell remaining count
Cell(x%, y%).pic = 10 ' no mines found, set to blank picture
_PUTIMAGE (Cell(x%, y%).x, Cell(x%, y%).y), CellPic&(10) ' display the black image at cell location
REVEALCELL x% - 1, y% ' move left to next grid cell
REVEALCELL x% + 1, y% ' move right to next grid cell
REVEALCELL x%, y% - 1 ' move up to next grid cell
REVEALCELL x%, y% + 1 ' move down to next grid cell
REVEALCELL x% - 1, y% - 1 ' move left/up to next grid cell
REVEALCELL x% - 1, y% + 1 ' move left/down to next grid cell
REVEALCELL x% + 1, y% - 1 ' move right/up to next grid cell
REVEALCELL x% + 1, y% + 1 ' move right/down to next grid cell
END SUBRecursive-like routines can also be achieved using a stack as I did in my Super MegaBug program:
Code: (Select All)
SUB CreateRandomMaze
'****************************************************************************
'* *
'* Creates a random sized braided (looping) maze by first creating a *
'* perfect maze (a maze with no loops) then visiting each dead end and *
'* randomly opening them to create loops. *
'* *
'* vcells stores valid next maze cell moves in binary (bit) format *
'* if all adjacent cell walls are turned on then that cell is saved in *
'* vcells as follows: *
'* bit 1 (2^0) = north cell has all walls on *
'* bit 2 (2^1) = east cell has all walls on *
'* bit 3 (2^2) = south cell has all walls on *
'* bit 4 (2^3) = west cell has all walls on *
'* *
'* This subroutine was generated from psuedo-code found at mazeworks.com *
'* *
'* http://www.mazeworks.com/mazegen/mazetut/index.htm *
'* *
'* I would like to thank mazeworks.com for taking the time to write their *
'* very informative tutorial on braided mazes. *
'* *
'****************************************************************************
DIM stack(1280) AS stack ' maze generation LIFO stack
DIM cellx, celly, counter AS INTEGER ' general counters
DIM ccell AS stack ' current cell being created
DIM pointer AS INTEGER ' pointer for use in LIFO stack
DIM vcells AS INTEGER ' which cells are valid moves
DIM randomwall AS INTEGER ' random valid direction mover
DIM forward AS INTEGER ' movement indicator
RANDOMIZE TIMER ' seed generator
FOR cellx = 0 TO 39 ' initialize grid
FOR celly = 0 TO 31
cell(cellx, celly).walls = 15 ' turn all walls on
cell(cellx, celly).x = 80 + cellx * 4 ' upper left x
cell(cellx, celly).y = 36 + celly * 4 ' upper left y
cell(cellx, celly).npell = False ' north pellet off
cell(cellx, celly).wpell = False ' west pellet off
cell(cellx, celly).cpell = 2 ' center pellet food
NEXT celly
NEXT cellx
ccell.x = INT(RND(1) * 39) ' random x start
ccell.y = INT(RND(1) * 31) ' random y start
visitedcells = 1 ' initialize counter
pointer = 0 ' LIFO stack pointer
forward = False ' movement indicator
WHILE visitedcells < 1280 ' until all cells
vcells = 0 ' valid move check
'**
'** The following 12 lines of code look at all four adjoining maze cells
'** (north, east, south and west) and determine if all the walls in each
'** cell are turned on. If so each corresponding bit in vcells is turned on
'** (2^0 = north, 2^1 = east, 2^2 = south, 2^3 = west). If a bit is on (1)
'** then that direction is a valid move. If a bit is off (0) then that
'** direction has already been visited (invalid move).
'**
IF ccell.y <> 0 THEN
IF cell(ccell.x, ccell.y - 1).walls = 15 THEN vcells = vcells + 1
END IF
IF ccell.x <> 39 THEN
IF cell(ccell.x + 1, ccell.y).walls = 15 THEN vcells = vcells + 2
END IF
IF ccell.y <> 31 THEN
IF cell(ccell.x, ccell.y + 1).walls = 15 THEN vcells = vcells + 4
END IF
IF ccell.x <> 0 THEN
IF cell(ccell.x - 1, ccell.y).walls = 15 THEN vcells = vcells + 8
END IF
'**
IF vcells <> 0 THEN ' a cell has walls
DO ' find random dir
randomwall = INT(RND(1) * 4) ' select random wall
LOOP UNTIL vcells AND 2 ^ randomwall ' is it valid?
stack(pointer) = ccell ' save cell in stack
pointer = pointer + 1 ' increment pointer
visitedcells = visitedcells + 1 ' increment counter
forward = True ' forward movement
RemoveWall ccell.x, ccell.y, randomwall ' remove random wall
SELECT CASE randomwall ' which direction?
CASE North ' north wall
ccell.y = ccell.y - 1 ' move north
CASE East ' east wall
ccell.x = ccell.x + 1 ' move east
CASE South ' south wall
ccell.y = ccell.y + 1 ' move south
CASE West ' west wall
ccell.x = ccell.x - 1 ' move west
END SELECT
ELSE ' no walls!
IF forward THEN ' we hit a dead end!
forward = False ' stop movement here
IF Fifty50 THEN ' make looping maze?
SELECT CASE randomwall ' which random wall?
CASE North ' remove north wall
IF ccell.y <> 0 THEN ' unless a border
RemoveWall ccell.x, ccell.y, randomwall ' remove now
END IF
CASE East ' remove east wall
IF ccell.x <> 39 THEN ' unless a border
RemoveWall ccell.x, ccell.y, randomwall ' remove now
END IF
CASE South ' remove south wall
IF ccell.y <> 31 THEN ' unless a border
RemoveWall ccell.x, ccell.y, randomwall ' remove now
END IF
CASE West ' remove west wall
IF ccell.x <> 0 THEN ' unless a border
RemoveWall ccell.x, ccell.y, randomwall ' remove now
END IF
END SELECT
END IF
END IF
pointer = pointer - 1 ' decrement pointer
ccell = stack(pointer) ' go previous cell
END IF
WEND ' all cells visited
END SUBThe maze generation code could have been done with recursion as well but a stack did nicely in this case.