Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Why does my Loop end after 11 Loops?
#59
I've found recursion to be very useful for path-finding types of algorithms. I used a recursive flood fill in my Minesweeper clone:

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 SUB

Recursive-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 SUB

The maze generation code could have been done with recursion as well but a stack did nicely in this case.
New to QB64pe? Visit the QB64 tutorial to get started.
QB64 Tutorial
Reply


Messages In This Thread
Why does my Loop end after 11 Loops? - by Dimster - 02-06-2023, 07:08 PM
RE: Why does my Loop end after 11 Loops? - by TerryRitchie - 02-12-2023, 06:06 PM



Users browsing this thread: 4 Guest(s)