Maze Generator

[axipher]

Here's a little Maze generating algorythm I,ve been working on, you change the variables at the top but some variables don't work so be warned, I haven't done extensive testing to figure out the min and max values, but it works and also saves the maze data to a text file.

Code: Select all

' Change the maze properties here.
CONST cellsize = 16
CONST numcellsh = 48
CONST numcellsv = 32




RANDOMIZE TIMER
SCREENRES 800,600,8
PAINT (0,0),15
FOR cy = 0 TO numcellsv * cellsize STEP cellsize
    FOR cx = 0 TO numcellsh * cellsize STEP cellsize
        LINE (cx,0)-(cx,numcellsv * cellsize),16
        LINE (0,cy)-(numcellsh * cellsize,cy),16
    NEXT
NEXT

TYPE cellwalls
    AS UBYTE n,s,e,w
END TYPE
TYPE cellinfo
    AS INTEGER xloc,yloc,visit
    AS cellwalls wall
END TYPE
TYPE cellcoor
    AS INTEGER x,y
END TYPE

DIM SHARED AS cellinfo mazecells(numcellsh,numcellsv)
DIM SHARED AS cellcoor route(cellsize ^ 4)
DIM SHARED AS INTEGER xx,yy,routecount,direct
DIM SHARED AS INTEGER nm,ee,ss,ww,ender

SUB initmaze()
    FOR cy = 0 TO numcellsv - 1
        FOR cx = 0 TO numcellsh - 1
            WITH mazecells(cx,cy)
                .xloc = cx
                .yloc = cy
                .visit = 0
                WITH .wall
                    .n = 1
                    .s = 1
                    .e = 1
                    .w = 1
                END WITH
            END WITH
        NEXT
    NEXT
    CLOSE
    xx = RND * numcellsh
    yy = RND * numcellsv
    mazecells(xx,yy).visit = 1
    WITH route(routecount)
        .x = xx
        .y = yy
    END WITH
END SUB

SUB savemaze()
    ? curdir & "\tehmaze.maze"
    OPEN curdir & "\tehmaze.maze" FOR OUTPUT AS #1
    FOR cy = 0 TO numcellsv - 1
        FOR cx = 0 TO numcellsh - 1
            WITH mazecells(cx,cy)
                print #1, "mazecells(" & cx & "," & cy & ")"
                print #1, "X: " & .xloc
                print #1, "Y: " & .yloc
                print #1, "Visited?: " & .visit
                WITH .wall
                    ? #1, " North wall: " & .n
                    ? #1, " South wall: " & .s
                    ? #1, " East wall: " & .e
                    ? #1, " West wall: " & .w
                END WITH
            END WITH
            print #1, ""
        NEXT
    NEXT
    CLOSE
END SUB

SUB move(cellx,celly)
    DIM AS INTEGER x1,x2,y1,y2
    DIM AS INTEGER nn,ee,ss,ww,direction
    direction = INT(RND * 4)
    IF mazecells(cellx,celly - 1).visit = 0 AND celly > 0 THEN
        nn = 1
    END IF
    IF mazecells(cellx + 1,celly).visit = 0 AND cellx < (numcellsh - 1) THEN
        ee = 1
    END IF
    IF mazecells(cellx,celly + 1).visit = 0 AND celly < (numcellsv - 1) THEN
        ss = 1
    END IF
    IF mazecells(cellx - 1,celly).visit = 0 AND cellx > 0 THEN
        ww = 1
    END IF
    
    ' North
    IF direction = 0 AND nn = 1 THEN
        mazecells(cellx,celly).wall.n = 0
        mazecells(cellx,celly - 1).visit = 1
        mazecells(cellx,celly - 1).wall.s = 0
        
        x1 = cellx * cellsize + 1
        y1 = celly * cellsize
        x2 = x1 + cellsize - 2
        y2 = y1
        LINE (x1,y1)-(x2,y2),15
        yy -= 1
        
        ' East
    ELSEIF direction = 1 AND ee = 1 THEN
        mazecells(cellx,celly).wall.e = 0
        mazecells(cellx + 1,celly).visit = 1
        mazecells(cellx + 1,celly).wall.w = 0
        
        x1 = cellx * cellsize + cellsize
        y1 = celly * cellsize + 1
        x2 = x1
        y2 = y1 + cellsize - 2
        LINE (x1,y1)-(x2,y2),15
        xx += 1
        
        ' South
    ELSEIF direction = 2 AND ss = 1 THEN
        mazecells(cellx,celly).wall.s = 0
        mazecells(cellx,celly + 1).visit = 1
        mazecells(cellx,celly + 1).wall.n = 0
        
        x1 = cellx * cellsize + 1
        y1 = celly * cellsize + cellsize
        x2 = x1 + cellsize - 2
        y2 = y1
        LINE (x1,y1)-(x2,y2),15
        yy += 1
        
        ' West
    ELSEIF direction = 3 AND ww = 1 THEN
        mazecells(cellx,celly).wall.w = 0
        mazecells(cellx - 1,celly).visit = 1
        mazecells(cellx - 1,celly).wall.e = 0
        
        x1 = cellx * cellsize
        y1 = celly * cellsize + 1
        x2 = x1
        y2 = y1 + cellsize - 2
        LINE (x1,y1)-(x2,y2),15
        xx -= 1
        
        
        ' No direction available so backtrack
    ELSEIF nn = 0 AND ee = 0 AND ss = 0 AND ww = 0 THEN
        IF routecount > 0 THEN
            routecount -= 1
            WITH route(routecount)
                xx = .x
                yy = .y
            END WITH
        END IF 
        
        
        ' change direction
    ELSE
        direction += 1
        IF direction = 4 THEN direction = 0
    END IF
    
    
    ' add coordinates to the route
    IF nn = 1 OR ee = 1 OR ss = 1 OR ww = 1 THEN
        routecount += 1
        WITH route(routecount)
            .x = xx
            .y = yy
        END WITH
        ender += 1
    END IF
END SUB




' +------------------------------------------------------------------+
' |******************************************************************|
' |**************************** +------+ ****************************|
' |**************************** | Main | ****************************|
' |**************************** +------+ ****************************|
' |******************************************************************|
' +------------------------------------------------------------------+

initmaze
FOR i = 0 TO cellsize ^ 4
    LINE (xx * cellsize + 3,yy * cellsize + 3)-(xx * cellsize + 7,yy * cellsize + 7),15,bf
    move(xx,yy)
    LINE (xx * cellsize + 3,yy * cellsize + 3)-(xx * cellsize + 7,yy * cellsize + 7),4,bf
    IF MULTIKEY(1) THEN EXIT FOR
NEXT
savemaze
sleep

[counting_pine]

Nice code. I don't know how it works, but it looks clever.
You might want to restructure the IF blocks at the begining of move (lines 88-99), so that it doesn't try to access out-of-bounds indices of mazecells

[axipher]

But it won't access the array out of bound's why i have cellx/celly che after the AND in the IF's, I haven't tried compiling with the -exx switch, maybe I'll try that and see if it does flaw.

EDIT: I tried compiling with -exx and it works fine, here's the pseudo version of it:

Code: Select all

Start Stuff
1. Set-up maxe propeties as constants
2. Draw grid for the maze
3. Define types
4. Create variable types

SUB initmaze()
1. Set default info
2. Randomize starting square

SUB savemaze()
1. Open file
2. Write data to file
3. Close file

SUB move(cellx,celly)
cellx and celly are coordinates for the current maze square
1. Create variable types
2. Check for possible directions
3. Pick random direction
4. Calculate coordinates of wall to be broken if the wall is there
5. Draw over the wall
6. Backtrack 1 cell if no direction is possible
7. Change direction if no direction is possible
8. Add the new cell's coordinates to the route array

Main Program
1. call initmaze() to initalize the variables and arrays
2. A cheap counter for the production of the maze
3. Erase the marker
4. Call move(cellx,celly)
5. Exit for...next loop
6. Call savemaze()
7. Wait for a key press

That should sum it up pretty much.

[counting_pine]

Looks interesting, I'll have to give it a good read through.

It's definitely aborting when I compile it with -exx.
The problem is that it always accesses the array before it checks the bounds. Because of the check it discounts anything it finds there, which is good, but it shouldn't really access it at all.
You could do it this way:

Code: Select all

if iif(celly > 0, mazecells(cellx,celly - 1).visit = 0, 0) then

If celly <= 0, then it won't access mazecells.

[axipher]

Looks interesting, I'll have to give it a good read through.

It's definitely aborting when I compile it with -exx.
The problem is that it always accesses the array before it checks the bounds. Because of the check it discounts anything it finds there, which is good, but it shouldn't really access it at all.
You could do it this way:

Code: Select all

if iif(celly > 0, mazecells(cellx,celly - 1).visit = 0, 0) then

If celly <= 0, then it won't access mazecells.

So your sying I should have it check bounds before it checks arrays? I had it set-up diferenty before where it checked bounds first, but the for some reason if if was against a wall it would always stay against the wall until it could no longer then it would stay against the path closest to the wall.

[counting_pine]

Hmm, perhaps there was a bug in the code.

Well, alternatively, a quick workaround would be to slightly extend each dimension, so that the checks all fall within the array bounds, but checking the cellx/celly would make sure it just ignores what it finds there.

[axipher]

I found a bug in the code, using too many cells causes some cels not to be covered, I think the cellsize ^ 4 definately has something to do with this, I should be involving numcellsh and numcellsv in this but I tried and failed. Can anyone show me the light?