Random Maze Generator Function

[PeeJay]

This function will produce a random maze of practically any size.

EDIT: Code removed - see bugfix below

[Ian Price]

[matchy]

Cool. May come in handy with a path finder.

[Kitty Hello]

Right. Here's what I used it for already:
http://www.glbasic.com/showroom.php?lang=de&game=WoistdieSophie
Thx a LOT!

[BumbleBee]

@Gernot
Nice game, but i can't find her anywhere. The snail is always faster. But I won't give up.

Cheers

[PeeJay]

Great - I'm glad someone has made use of it - I have used it twice myself for my remakes of Maziacs and Fred - buy you can have too much of mazes!

[PeeJay]

Apologies to those that have already used this function - unfortunately there was a small bug that crept in (during porting and compacting into one function) that meant when generating an exact maze, it was possible to have empty gaps of 3x3 near the maze edges.

Here is the bugfixed version:

Code (glbasic) Select Expand

//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
//                                                                      //
// Project: Random Maze Generator Function for GLBasic                  //
//                                                                      //
// (C)opyright PeeJay December 13th 2007      www.peejays-remakes.co.uk //
//              bugfix January 21st 2008                                //
//                                                                      //
// Code is free to use for FREEWARE projects only, though credit would  //
// still be welcomed if you decide to use it                            //
//                                                                      //
// Please contact me through my website for conditions on using this    //
// code in shareware, commercial, or other revenue generating projects  //
//                                                                      //
// This function will randomly generate a 2D map of practically any     //
// size very quickly, storing the result in an array for ease of use    //
//                                                                      //
// I have used this code in DarkBasic, BlitzBasic, and now I offer it   //
// to the GLBasic community. For the first time, I have reduced the     //
// code to fit in one function for maximum simplicity                   //
//                                                                      //
// Not surprisingly, the code is fairly complex - even more so by the   //
// fact I've not added comments! However, it is a self contained,       //
// robust, standalone function, so anyone should be able to use it      //
// without needing to understand the methodology behind it              //
//                                                                      //
// The code will produce either an exact maze, or one that is more      //
// open. An exact maze is defined as one where there is only one route  //
// from any point in the maze to any other point in the maze            //
//                                                                      //
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//

DIM maze[0][0]
DIM pjcos[4]
DIM pjsin[4]

LOCAL loop,loop1,time1,time2

WHILE TRUE

REDIM maze[0][0];REDIM maze[79][59] // Reset maze

time1=GETTIMERALL()
MakeMaze(maze[],1) // Maze (maze[] must be DIMed), exact=1, not exact=0
time2=GETTIMERALL()

FOR loop=0 TO 78
FOR loop1=0 TO 58
IF maze[loop][loop1]=1
DRAWRECT 4+(loop*8),4+(loop1*8),8,8,RGB(64,64,0)
DRAWRECT 5+(loop*8),5+(loop1*8),6,6,RGB(96,48,0)
ENDIF
NEXT
NEXT

PRINT "Maze Generated in "+INTEGER(time2-time1)+" milliseconds",180,220

SHOWSCREEN

MOUSEWAIT
WEND

END

// -------------------------------------------------------------------- //

FUNCTION MakeMaze: pjmaze[], pjexact

LOCAL pjmx = BOUNDS(pjmaze[],0)-1
LOCAL pjmy = BOUNDS(pjmaze[],1)-1
LOCAL pjfx,pjfy,pjloop,pjypos,pjxpos,pjfarx,pjfary,pjallx,pjally,pjalldir
LOCAL pjgo,pjtemp,pjx,pjy,pjdir,pjresult,pjlop,pjx2,pjy2,pjtemp2

pjcos[0]=1
pjcos[2]=-1
pjsin[1]=1
pjsin[3]=-1

FOR pjfx=0 TO pjmx
pjmaze[pjfx][0]=1
pjmaze[pjfx][pjmy]=1
NEXT

FOR pjfy=0 TO pjmy
pjmaze[0][pjfy]=1
pjmaze[pjmx][pjfy]=1
NEXT

FOR pjloop=1 TO pjmy/6
pjypos=RND((pjmy-6)/2)*2
pjxpos=RND(2)*2
FOR pjfx=1 TO pjxpos
pjmaze[pjfx][pjypos]=1
NEXT
pjypos=RND((pjmy-6)/2)*2
pjxpos=pjmx-(RND(2)*2)
FOR pjfx=pjmx TO pjxpos STEP -1
pjmaze[pjfx][pjypos]=1
NEXT
NEXT
FOR pjloop=1 TO pjmx/6
pjxpos=4+RND((pjmx-8)/2)*2
pjmaze[pjxpos][pjmy-1]=1
pjmaze[pjxpos][pjmy-2]=1
NEXT

pjfarx=pjmx
pjfary=pjmy
pjallx=0
pjally=0
pjexact=pjexact+1

WHILE TRUE
WHILE TRUE

pjallx=pjallx+pjcos[pjalldir]*pjexact
pjally=pjally+pjsin[pjalldir]*pjexact
pjgo=pjgo+pjexact

IF pjgo>=pjfarx-pjexact AND (pjalldir=0 OR pjalldir=2)
pjgo=0
pjfarx=pjfarx-pjexact
pjtemp=pjalldir+1
pjalldir=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)
ENDIF
IF pjgo>=pjfary-pjexact AND (pjalldir=1 OR pjalldir=3)
pjgo=0
pjfary=pjfary-pjexact
pjtemp=pjalldir+1
pjalldir=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)
ENDIF

IF pjfarx<=0 OR pjfary<=0 THEN BREAK
IF pjmaze[pjallx][pjally]=1 AND (pjallx
WEND

IF pjfarx<=0 OR pjfary<=0 THEN BREAK
IF pjallx>=pjmx OR pjally>=pjmy THEN BREAK

pjx=pjallx
pjy=pjally
pjdir=RND(3)

WHILE TRUE

FOR pjloop=0 TO 3
pjresult=1
FOR pjlop=1 TO pjexact+1
pjx2=pjx+pjcos[pjloop]*pjlop
pjy2=pjy+pjsin[pjloop]*pjlop
IF pjx2<=0 OR pjy2<=0 OR pjx2>pjmx OR pjy2>pjmy THEN pjresult=0
IF pjresult=1
IF pjmaze[pjx2][pjy2]=1 THEN pjresult=0
ENDIF
IF pjresult=1
pjtemp=pjloop+1
pjtemp2=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)
IF pjmaze[pjx2+pjcos[pjtemp2]][pjy2+pjsin[pjtemp2]]=1 THEN pjresult=0
ENDIF
IF pjresult=1
pjtemp=pjloop-1
pjtemp2=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)
IF pjmaze[pjx2+pjcos[pjtemp2]][pjy2+pjsin[pjtemp2]]=1 THEN pjresult=0
ENDIF
NEXT
IF pjresult=1 THEN BREAK
NEXT

IF pjloop=4 THEN BREAK

pjtemp=pjdir+1-RND(2)
pjdir=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)

pjresult=1
FOR pjlop=1 TO pjexact+1
pjx2=pjx+pjcos[pjdir]*pjlop
pjy2=pjy+pjsin[pjdir]*pjlop
IF pjx2<=0 OR pjy2<=0 OR pjx2>pjmx OR pjy2>pjmy THEN pjresult=0
IF pjresult=1
IF pjmaze[pjx2][pjy2]=1 THEN pjresult=0
ENDIF
IF pjresult=1
pjtemp=pjdir+1
pjtemp2=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)
IF pjmaze[pjx2+pjcos[pjtemp2]][pjy2+pjsin[pjtemp2]]=1 THEN pjresult=0
ENDIF
IF pjresult=1
pjtemp=pjdir-1
pjtemp2=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)
IF pjmaze[pjx2+pjcos[pjtemp2]][pjy2+pjsin[pjtemp2]]=1 THEN pjresult=0
ENDIF
NEXT

IF pjresult=1
FOR pjloop=1 TO pjexact
pjx=pjx+pjcos[pjdir]
pjy=pjy+pjsin[pjdir]
pjmaze[pjx][pjy]=1
NEXT
ENDIF
WEND
WEND

IF pjexact=2
FOR pjfx=2 TO pjmx-2 STEP 2
IF pjmaze[pjfx][2]=0
pjmaze[pjfx][2]=1 ; pjmaze[pjfx][1]=1
ENDIF
IF pjmaze[pjfx][pjmy-2]=0
pjmaze[pjfx][pjmy-2]=1 ; pjmaze[pjfx][pjmy-1]=1
ENDIF
NEXT
FOR pjfy=2 TO pjmy-2 STEP 2
IF pjmaze[2][pjfy]=0
pjmaze[2][pjfy]=1 ; pjmaze[1][pjfy]=1
ENDIF
IF pjmaze[pjmx-2][pjfy]=0
pjmaze[pjmx-2][pjfy]=1 ; pjmaze[pjmx-1][pjfy]=1
ENDIF
NEXT
ENDIF

ENDFUNCTION

[retrotech]

The posted code would not compile.
Does someone know if this attempt to fix line 142 is the proper code?

Code (glbasic) Select Expand

// --------------------------------- //
// Project: maze_gen_1
// Start: Tuesday, December 07, 2010
// IDE Version: 8.174


//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
//                                                                      //
// Project: Random Maze Generator Function for GLBasic                  //
//                                                                      //
// (C)opyright PeeJay December 13th 2007      www.peejays-remakes.co.uk //
//              bugfix January 21st 2008                                //
//                                                                      //
// Code is free to use for FREEWARE projects only, though credit would  //
// still be welcomed if you decide to use it                            //
//                                                                      //
// Please contact me through my website for conditions on using this    //
// code in shareware, commercial, or other revenue generating projects  //
//                                                                      //
// This function will randomly generate a 2D map of practically any     //
// size very quickly, storing the result in an array for ease of use    //
//                                                                      //
// I have used this code in DarkBasic, BlitzBasic, and now I offer it   //
// to the GLBasic community. For the first time, I have reduced the     //
// code to fit in one function for maximum simplicity                   //
//                                                                      //
// Not surprisingly, the code is fairly complex - even more so by the   //
// fact I've not added comments! However, it is a self contained,       //
// robust, standalone function, so anyone should be able to use it      //
// without needing to understand the methodology behind it              //
//                                                                      //
// The code will produce either an exact maze, or one that is more      //
// open. An exact maze is defined as one where there is only one route  //
// from any point in the maze to any other point in the maze            //
//                                                                      //
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//

GLOBAL maze[]
GLOBAL pjcos[]
GLOBAL pjsin[]
DIM maze[0][0]
DIM pjcos[4]
DIM pjsin[4]

LOCAL loop,loop1,time1,time2

WHILE TRUE

   REDIM maze[0][0];REDIM maze[79][59]   // Reset maze

   time1=GETTIMERALL()
   MakeMaze(maze[],1) // Maze (maze[] must be DIMed), exact=1, not exact=0
   time2=GETTIMERALL()

   FOR loop=0 TO 78
      FOR loop1=0 TO 58
         IF maze[loop][loop1]=1
            DRAWRECT 4+(loop*8),4+(loop1*8),8,8,RGB(164,104,10)
            DRAWRECT 5+(loop*8),5+(loop1*8),6,6,RGB(196,148,10)
         ENDIF
      NEXT
   NEXT

   PRINT "Maze Generated in "+INTEGER(time2-time1)+" milliseconds",180,220

   SHOWSCREEN

   KEYWAIT
WEND

END

// -------------------------------------------------------------------- //

FUNCTION MakeMaze: pjmaze[], pjexact

   LOCAL pjmx = BOUNDS(pjmaze[],0)-1
   LOCAL pjmy = BOUNDS(pjmaze[],1)-1
   LOCAL pjfx,pjfy,pjloop,pjypos,pjxpos,pjfarx,pjfary,pjallx,pjally,pjalldir
   LOCAL pjgo,pjtemp,pjx,pjy,pjdir,pjresult,pjlop,pjx2,pjy2,pjtemp2

   pjcos[0]=1
   pjcos[2]=-1
   pjsin[1]=1
   pjsin[3]=-1

   FOR pjfx=0 TO pjmx
      pjmaze[pjfx][0]=1
      pjmaze[pjfx][pjmy]=1
   NEXT

   FOR pjfy=0 TO pjmy
      pjmaze[0][pjfy]=1
      pjmaze[pjmx][pjfy]=1
   NEXT
   
   FOR pjloop=1 TO pjmy/6
      pjypos=RND((pjmy-6)/2)*2
      pjxpos=RND(2)*2
      FOR pjfx=1 TO pjxpos
         pjmaze[pjfx][pjypos]=1
      NEXT
      pjypos=RND((pjmy-6)/2)*2
      pjxpos=pjmx-(RND(2)*2)
      FOR pjfx=pjmx TO pjxpos STEP -1
         pjmaze[pjfx][pjypos]=1
      NEXT
   NEXT
   FOR pjloop=1 TO pjmx/6
      pjxpos=4+RND((pjmx-8)/2)*2
      pjmaze[pjxpos][pjmy-1]=1
      pjmaze[pjxpos][pjmy-2]=1
   NEXT
   
   pjfarx=pjmx
   pjfary=pjmy
   pjallx=0
   pjally=0
   pjexact=pjexact+1

   WHILE TRUE
      WHILE TRUE

         pjallx=pjallx+pjcos[pjalldir]*pjexact
         pjally=pjally+pjsin[pjalldir]*pjexact
         pjgo=pjgo+pjexact

         IF pjgo>=pjfarx-pjexact AND (pjalldir=0 OR pjalldir=2)
            pjgo=0
            pjfarx=pjfarx-pjexact
            pjtemp=pjalldir+1
            pjalldir=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)
         ENDIF
         IF pjgo>=pjfary-pjexact AND (pjalldir=1 OR pjalldir=3)
            pjgo=0
            pjfary=pjfary-pjexact
            pjtemp=pjalldir+1
            pjalldir=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)
         ENDIF

         IF pjfarx<=0 OR pjfary<=0 THEN BREAK
         IF pjmaze[pjallx][pjally]=1 AND (pjallx>=pjfarx) THEN BREAK // ??

      WEND
     
      IF pjfarx<=0 OR pjfary<=0 THEN BREAK
      IF pjallx>=pjmx OR pjally>=pjmy THEN BREAK

      pjx=pjallx
      pjy=pjally
      pjdir=RND(3)

      WHILE TRUE

         FOR pjloop=0 TO 3
            pjresult=1
            FOR pjlop=1 TO pjexact+1
               pjx2=pjx+pjcos[pjloop]*pjlop
               pjy2=pjy+pjsin[pjloop]*pjlop
               IF pjx2<=0 OR pjy2<=0 OR pjx2>pjmx OR pjy2>pjmy THEN pjresult=0
               IF pjresult=1
                  IF pjmaze[pjx2][pjy2]=1 THEN pjresult=0
               ENDIF
               IF pjresult=1
                  pjtemp=pjloop+1
                  pjtemp2=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)
                  IF pjmaze[pjx2+pjcos[pjtemp2]][pjy2+pjsin[pjtemp2]]=1 THEN pjresult=0
               ENDIF
               IF pjresult=1
                  pjtemp=pjloop-1
                  pjtemp2=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)
                  IF pjmaze[pjx2+pjcos[pjtemp2]][pjy2+pjsin[pjtemp2]]=1 THEN pjresult=0
               ENDIF
            NEXT
            IF pjresult=1 THEN BREAK
         NEXT

         IF pjloop=4 THEN BREAK

         pjtemp=pjdir+1-RND(2)
         pjdir=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)

         pjresult=1
         FOR pjlop=1 TO pjexact+1
            pjx2=pjx+pjcos[pjdir]*pjlop
            pjy2=pjy+pjsin[pjdir]*pjlop
            IF pjx2<=0 OR pjy2<=0 OR pjx2>pjmx OR pjy2>pjmy THEN pjresult=0
            IF pjresult=1
               IF pjmaze[pjx2][pjy2]=1 THEN pjresult=0
            ENDIF
            IF pjresult=1
               pjtemp=pjdir+1
               pjtemp2=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)
               IF pjmaze[pjx2+pjcos[pjtemp2]][pjy2+pjsin[pjtemp2]]=1 THEN pjresult=0
            ENDIF
            IF pjresult=1
               pjtemp=pjdir-1
               pjtemp2=pjtemp-4*(pjtemp>3)+4*(pjtemp<0)
               IF pjmaze[pjx2+pjcos[pjtemp2]][pjy2+pjsin[pjtemp2]]=1 THEN pjresult=0
            ENDIF
         NEXT

         IF pjresult=1
            FOR pjloop=1 TO pjexact
               pjx=pjx+pjcos[pjdir]
               pjy=pjy+pjsin[pjdir]
               pjmaze[pjx][pjy]=1
            NEXT
         ENDIF
      WEND
   WEND

   IF pjexact=2
      FOR pjfx=2 TO pjmx-2 STEP 2
         IF pjmaze[pjfx][2]=0
            pjmaze[pjfx][2]=1 ; pjmaze[pjfx][1]=1
         ENDIF
         IF pjmaze[pjfx][pjmy-2]=0
            pjmaze[pjfx][pjmy-2]=1 ; pjmaze[pjfx][pjmy-1]=1
         ENDIF
      NEXT
      FOR pjfy=2 TO pjmy-2 STEP 2
         IF pjmaze[2][pjfy]=0
            pjmaze[2][pjfy]=1 ; pjmaze[1][pjfy]=1
         ENDIF
         IF pjmaze[pjmx-2][pjfy]=0
            pjmaze[pjmx-2][pjfy]=1 ; pjmaze[pjmx-1][pjfy]=1
         ENDIF
      NEXT
   ENDIF

ENDFUNCTION


[Wampus]

Welcome retrotech

Try just  IF pjmaze[pjallx][pjally]=1 THEN BREAK at line 142

It appears to work for me whereas I get some strange results, i.e. mazes that are 2/3rds complete, when I use IF pjmaze[pjallx][pjally]=1 AND (pjallx>=pjfarx) THEN BREAK

[Slydog]

If you're adventurous, here's a link that outlines a ton of different maze algorithms:
http://www.astrolog.org/labyrnth/algrithm.htm

No code is given, just some basic starting points. 
At least you can learn the terms and concepts to search for in Google.

The 'Weave' style maze is where I got my inspiration for my current game project, but just not limited to 2 dimensions (a multi-layered Weave, gets very confusing!). (Excuse my HUD, work-in-progress)

[attachment deleted by admin]

[matchy]

Weave looks real cool!!! I have something similar for a racing track. Also I use pj maze lib in: http://www.youtube.com/watch?v=z8VDyZP7zzk

[Ian Price]

Those are both lovely looking uses for mazes

[Kitty Hello]

Slydog  -that looks very very nice. I like the graphics style. I'd buy that screenshot for a dollar.

[Slydog]

Thanks, but I haven't even added the graphics yet!   I plan on adding a bump/normal mapped surface. 
Right now it's just solid green/brown with fog to control the number of polys. 
A dollar eh?  Hmm, still deciding between a free game with ads or a paid game for a dollar.  Or both a free and paid version.

This will be for the iDevices, so even the screenshot probably has too many polys and I'll have to increase the fog.  (Starting the maze will only let you see so far, but with fog power-ups you'll be able to see further)
I really don't know how many polys are displayed since it's dynamically created/generated.  I'll have to manually add them up.

Matchy:
I love your design.  Is that a random maze also?  Are the walls just single quads with the cull mode set to 'both' so you can see both sides?  (or 2 back to back quads?).  And you say you still have too many polys?  I may be in trouble! 

Mine is broke down into '3D tiles' generated at the start and each frame I just display the proper 3D maze element model depending on the maze element at that co-ordinate.  That way I can control what is displayed and cut off displaying further maze sections (kinda like fog), or don't display anything above the player, etc.  Will see how that works out.

[Kitty Hello]

nah, don't add bumps and make it realistic and whatnot (I mean - ok, maybe it's worth) but I really like it as it is.