Maze generator

[SteveB]

Hi,

 

the timing thread uses a sophisticated maze generator as an example. What are simple algorithms to create a solvable, but not trivial maze with a given start and exit position?

 

I am porting a maze game which uses a fixed maze and only varies obstacles within the maze. A changing maze would be more fun. 

 

First thoughts of a "Turtle-Graphics-Maze": 

 

• fill the screen solid
• chose a starting field on the lowest line
• draw a way by determing a direction: Alternating up/down and left/right.
  • left/right: use higher chances towards the center
  • up/down: always have a slightly higher propability to go up
• End when touching the upper border (as the actual exit x-position does not matter for the game)
• Draw some random horizontal and vertical ways to obfuscate the generated path (which should allready have some crossings)

 

Any better ideas?

[Reciprocating Bill]

I know this isn't exactly what you are looking for...The video is a maze generator in assembly that uses the same maze generation algorithm that the BASIC examples use in the timing thread (I think it's faster than the BASIC version, but I didn't actually measure it, so I could be wrong .  Essentially, the Maze is generated as a tree structure, which guarantees that there is one and only one path between any two positions in the maze. It is also amenable to solution via tree search. 

 

Then follows the assembly source (assembles to an E/A Option 3 program), as well as the Commodore BASIC file from which I derived the assembly program.

 

Lastly, see the page at RosettaCode for many ideas...  

 

http://rosettacode.org/wiki/Maze_generation

 

 

SMAZEB

 

 

100 MS=10:REM MAZE SIZE

110 DIM S(MS+1,MS+1):REM SOUTH WALLS

120 DIM W(MS+1,MS+1):REM WEST WALLS

130 DIM V(MS+1,MS+1):REM VISITED CELLS

140 PRINT "INITIALIZING..."

150 GOSUB 260:REM INITIALIZE MAZE

160 PRINT "BUILDING..."

170 DIM PC(MS*MS+1):DIM PR(MS*MS+1):REM STACK

180 REM PICK RANDOM STARTING CELL

190 X = RND(-TI)

200 C=(INT(RND(1)*MS)+1)

210 R=(INT(RND(1)*MS)+1)

220 GOSUB 400:REM BUILD MAZE

230 GOSUB 540:REM DRAW MAZE

240 END

250 REM -----INITIALIZE MAZE-----

260 REM SET WALLS ON AND VISITED CELLS OFF

270 T=MS+1

280 FOR C=0 TO T:FOR R=0 TO T:

290 S(C,R)=1:W(C,R)=1:V(C,R)=0

300 NEXT R:NEXT C

310 REM SET BORDER CELLS TO VISITED

320 FOR C=0 TO T

330 V(C,0)=1:V(C,T)=1

340 NEXT C

350 FOR R=0 TO T

360 V(0,R)=1:V(T,R)=1

370 NEXT R

380 RETURN

390 REM -----BUILD MAZE-----

400 U=U+1:PC(U)=C:PR(U)=R:REM PUSH

410 V(C,R)=1

420 IF V(C,R+1)=1 AND V(C+1,R)=1 AND V(C,R-1)=1 AND V(C-1,R)=1 THEN GOTO 500

430 Z=INT(RND(1)*4)

440 IF Z=0 AND V(C,R+1)=0 THEN S(C,R)=0:R=R+1:GOTO 400

450 IF Z=1 AND V(C+1,R)=0 THEN W(C+1,R)=0:C=C+1:GOTO 400

460 IF Z=2 AND V(C,R-1)=0 THEN S(C,R-1)=0:R=R-1:GOTO 400

470 IF Z=3 AND V(C-1,R)=0 THEN W(C,R)=0:C=C-1:GOTO 400

480 GOTO 430

500 C=PC(U):R=PR(U):U=U-1:REM POP

510 IF U > 0 THEN GOTO 420

520 RETURN

530 REM -----DRAW MAZE-----

540 REM OPEN 4,4:CMD 4:REM SEND OUTPUT TO PRINTER

550 PRINT "+--+--+--+--+--+--+--+--+--+--+"

560 FOR R = 1 TO MS

570 FOR C = 1 TO MS+1

580 IF W(C,R)=0 THEN PRINT "   ";

590 IF W(C,R)=1 THEN PRINT ":  ";

600 NEXT C

610 PRINT

620 FOR C = 1 TO MS

630 IF S(C,R)=0 THEN PRINT "+  ";

640 IF S(C,R)=1 THEN PRINT "+--";

650 NEXT C

660 PRINT "+"

670 NEXT R

680 REM PRINT#4:CLOSE 4:REM CLOSE PRINTER DEVICE

690 RETURN

[HOME AUTOMATION]

I dunno...

[+TheBF]

Bill posted Commodore BASIC

Here is something that runs in XB based on the C64 program. Not ideal. I didn't make it fit on our screen perfectly.

 

Spoiler

1  REM MAZE from Rosetta CODE
2  REM Adapted from commodore BASIC
3  REM for TI-99 theBF 2020
100 MS=9::REM MAZE SIZE
101 REM changed (MS+1,MS+1)
110 DIM S(11,11)::REM south walls
120 DIM W(11,11)::REM west walls
130 DIM V(11,11)::REM visited cells
140 PRINT "INITIALIZING..."
150 GOSUB 260::REM initialize maze
160 PRINT "BUILDING..."
161 REM Changed from PC((MS*MS)+1) PR((MS*MS)+1)
170 DIM PC(101)::DIM PR(101)::REM STACK
180 REM PICK RANDOM STARTING CELL
190 X = RND*MS
200 C=(INT(RND*MS)+1)
210 R=(INT(RND*MS)+1)
220 GOSUB 400::REM BUILD MAZE
230 GOSUB 540::REM DRAW MAZE
240 GOTO 240 

250 REM -----INITIALIZE MAZE-----
260 REM SET WALLS ON AND VISITED CELLS OFF
270 T=MS
280 FOR C=0 TO T::FOR R=0 TO T::
290   S(C,R)=1
291   W(C,R)=1
292   V(C,R)=0
300  NEXT R
301 NEXT C
310 REM SET BORDER CELLS TO VISITED
320 FOR C=0 TO T
330 V(C,0)=1::V(C,T)=1
340 NEXT C
350 FOR R=0 TO T
360 V(0,R)=1::V(T,R)=1
370 NEXT R
380 RETURN
390 REM -----BUILD MAZE-----
400 U=U+1::PC(U)=C::PR(U)=R::REM PUSH
410 V(C,R)=1
420 IF V(C,R+1)=1 AND V(C+1,R)=1 AND V(C,R-1)=1 AND V(C-1,R)=1 THEN GOTO 500
430 Z=INT(RND*4)
440 IF Z=0 AND V(C,R+1)=0 THEN S(C,R)=0::R=R+1::GOTO 400
450 IF Z=1 AND V(C+1,R)=0 THEN W(C+1,R)=0::C=C+1::GOTO 400
460 IF Z=2 AND V(C,R-1)=0 THEN S(C,R-1)=0::R=R-1::GOTO 400
470 IF Z=3 AND V(C-1,R)=0 THEN W(C,R)=0::C=C-1::GOTO 400
480 GOTO 430
500 C=PC(U)::R=PR(U)::U=U-1::REM POP
510 IF U > 0 THEN GOTO 420
520 RETURN
530 REM -----DRAW MAZE-----
540 REM OPEN #1: RS232.BA=9600
550 PRINT "+--+--+--+--+--+--+--+--+--+"
560 FOR R = 1 TO MS
570 FOR C = 1 TO MS+1
580 IF W(C,R)=0 THEN PRINT "   ";
590 IF W(C,R)=1 THEN PRINT "|  ";
600 NEXT C
610 PRINT
620 FOR C = 1 TO MS
630 IF S(C,R)=0 THEN PRINT "+  ";
640 IF S(C,R)=1 THEN PRINT "+--";
650 NEXT C
660 PRINT "+"
670 NEXT R
680 REM CLOSE #1 ::REM close printer device
690 RETURN

 

 

[apersson850]

You can write

MS=10 ! Maze size

in Extended BASIC. But not computed dimensions, since dimensioning arrays is done during pre-scan, and by then the value for MS isn't known.

[matthew180]

Mazes are really cool, but *really* slow in BASIC or XB, unfortunately.  There are some kinds of mazes that can be generated on-the-fly, or room-by-room, so those algorithms would be ones to look into.  There are some threads in the forum about mazes, I'm sure I created one at some point in the last decade.  There are some clever tricks being used in some other games as well, like Hell's Halls.

[+dhe]

I did a quick port to TIC on the Geneve.

 

If you enable debugging, you can see the maze being created.

 

/* Maze_c            */
/* dhe - 20220613    */

#include <STDIO_H>
#include <VIDEO_H>
#include <TIME_H>
#include <STDLIB_H>
#define STOP '\n'
/* #define DEBUG 1 */

/* Global Vars */
/* since this an adapt of basic, pretty much all
   vars will be global */

int ms;           /* size of maze         */
int s [12] [12];  /* south wall           */
int w [12] [12];  /* west wall            */
int v [12] [12];  /* visited cells        */

int c;            /* index variable build maze (left/right) */
int r;            /* index variable build maze (up/down)    */
int u;            /* hold iter in build 0-69                */

int z;            /* used in build maze (0-4) 4 directions  */
int t;            /* used in init maze as index var (ms+1)  */

/* stack for program usage */
int pc [101];
int pr [101];

main()
{
  putchar(12);   /* Clear Screen */
  randomize();   /* Seed Random Function */

  ms=10;        /* might want to define this */

  printf("Initalizing......\n");
  init260();

#ifdef DEBUG
  Fdm2();
  Fwait("first disp");
#endif

  /* pick random starting cell */
  c = rnd(ms)+1;     /* we want values for cells to be between 1 .... 10 */
  r = rnd(ms)+1;
  u = 0;           /* u is used without init val in init400 */

  putchar(12);
  printf("Building...... \n");
  init400();

  printf("Drawing...... \n");
  putchar(12);
  Fdmaze();
  exit(0);             /* give a clean exit */

} /* end of main */

/* --- INITALIZE MAZE --- */
init260()
{
 int imc;   /* initalize maze c */
 int imr;   /* localize index vars */

 t=ms+2;    /* loop iteration maze(10) + extra floors and walls */

 /* set walls on and visited cells off */
 for (imc = 0; imc < t; ++imc)
   {
     for (imr = 0; imr < t; ++imr)
       {
          s [imc] [imr] = 1;   /*   south:  all on  */
          w [imc] [imr] = 1;   /*    west:  all on  */
          v [imc] [imr] = 0;   /* visited:  all off */
       }  /* end of for imr */
   }   /* end of for imc */

  /* set border cells to visited */
  for (imc = 0; imc < t; ++imc)
    {
      v [imc] [0] = 1;         /* set left and right to on */
      v [imc] [11] = 1;
      v [0] [imc] = 1;         /* set top and bottom to on */
      v [11] [imc] = 1;
    }  /* end of for imc */
}   /* end of init260 */

/* --- BUILD MAZE --- */
init400()
{
#ifdef DEBUG
 printf("c,r %d %d \n",c,r);
 Fwait("Enter build Maze...... \n");
#endif

  l400:
  u=u+1;
  pc [u] = c;
  pr [u] = r;      /* push need a total of u = 69 */
  v [c] [r] = 1;

#ifdef DEBUG
  printf("push Iter= %d c(r/l)= %d r(u/d)= %d \n", u, c, r);
  Fdmaze();
#endif

  l420:
  if (v[c][r+1]==1 && v[c+1][r]==1 && v[c][r-1]==1 && v[c-1][r]==1)
    { goto l500;}
  /* if all surrounding cells have been visited go back to previous
       place and try again..                                         */
  /* printf("420\n"); */

  l430:
  z = rnd(4);       /* pick a direction to look N/S/E/W */
  /* at this point of lock up - none of these conditions
     are being meet and we just keep looping  */

  if ( z==0 && v[c][r+1]==0 )
    {
      s[c][r]=0;
      r=r+1;
      goto l400;
    }


  if ( z==1 && v[c+1][r]==0 )
    {
      w[c+1][r]=0;
      c=c+1;
      goto l400;
    }


  if ( z==2 && v[c][r-1]==0 )
    {
      s[c][r-1]=0;
      r=r-1;
      goto l400;
    }


  if ( z==3 && v[c-1][r]==0 )
    {
      w[c][r]=0;
      c=c-1;
      goto l400;
    }
  goto l430;

l500:
  c=pc[u];
  r=pr[u];
  u=u-1;    /* pop ? */

#ifdef DEBUG
  printf("l500 pop ");
  printf("pop Iter= %d c= %d r= %d \n", u,c,r);
#endif

 if ( u > 0 ) goto l420;
}  /* end of init400 - build maze */

/* --- DRAW MAZE --- */
Fdmaze()
{
  int dmr;   /* index var */
  int dmc;   /* another index var */

  locate(1,1);

  /* print top floor of maze              */
  printf("+--+--+--+--+--+--+--+--+--+--+\n");
/*printf("ms=%d",ms);  */

  /* build rest of maze                   */
  for (dmr = 1; dmr < ms+1; ++dmr)
  {
/*  printf("dmr val: %d",dmr); */

    /* build Middle cells                 */
    for (dmc = 1; dmc < ms+2; ++dmc)
    {
      if (w[dmc][dmr]==0) { printf("   "); }
      if (w[dmc][dmr]==1) { printf(":  "); }

/*    printf("w[dmc][dmr]=%d",w[dmc][dmr]); */

    }  /* end of for c */
    printf("\n");   /* finished middle cells next line please */

    /* Build next roof/floor              */
    for (dmc = 0; dmc < ms; ++dmc)
    {
      if (s[dmc][dmr]==0) { printf("+  "); }
      if (s[dmc][dmr]==1) { printf("+--"); }

/*    printf("s[dmc][dmr] = %d", s[dmc][dmr]); */

    }  /* end of (2nd) for c */
    printf("+\n");

  } /* end of for r */
}  /* end of init540 */


/* Skip drawing a maze and just show me the numbers! */
Fdm2()
{
   int dm2x;
   int dm2y;

   printf("west\n");
   for (dm2x = 0; dm2x < t; ++dm2x)
   {
     for (dm2y = 0; dm2y < t; ++dm2y)
     {
       printf(" %d ", w[dm2y] [dm2x]);
/*     printf(" %d %d ", dm2y, dm2x);  */
     }
     printf("\n");
   } /* end dm2x */
   Fwait("");

   printf("south\n");
   for (dm2x = 0; dm2x < t; ++dm2x)
   {
     for (dm2y = 0; dm2y < t; ++dm2y)
     {
       printf(" %d ", s[dm2y] [dm2x]);
     }
     printf("\n");
   } /* end dm2x */
   Fwait("");

   printf("visited\n");
   for (dm2x = 0; dm2x < t; ++dm2x)
   {
     for (dm2y = 0; dm2y < t; ++dm2y)
     {
       printf(" %d ", v[dm2y] [dm2x]);
     }
     printf("\n");
   } /* end dm2x */
   Fwait("");

} /* end Fdm2 */

Fwait(mymess)
char mymess[20];
{
  char a;
  printf("\n");
  printf("%s",mymess);
  a=getchar();          /* wait to end */
}

/* ******************************************************************
   * Program By: Dan H. Eicher                                      *
   * Programs Purpose: Generate a maze.. Adapted from code original  *
   *   ly on Rosetta Code for Commodore BASIC, then adapted for TI  *
   *   BASIC by @TheBF (Atariage)..                                  *
   ****************************************************************** */

[matthew180]

On 6/12/2022 at 6:12 PM, SteveB said:

Any better ideas?

Are there restrictions?  If an assembly language *assist* is acceptable, then generating a maze can be very fast.

[SteveB]

On 6/14/2022 at 11:18 PM, matthew180 said:

Are there restrictions?  If an assembly language *assist* is acceptable, then generating a maze can be very fast.

Two restrictions ... first: I am actually porting a game from the TI to the Atari XL plattform using FastBasic ... this community is much more vivid than the Atari 8 bit development on AtariAge and the algorithm should be universal, but TMS9900 assembly won't help. Second, I want to place random obstacles in the maze as a core challange in the game, not all can be dismantled, so there must be multiple alternatives and not just a single way. Right now I use a static maze like the original game. Perhaps I design multiple static mazes.  With my naive approach (which I implemented quickly on the TI) the mazes are ugly. So perhaps I use some availabe algorithm (like this)  to create candidates 40x24 characters wide and include them statically in the program, but so far all programs I found build single-solution mazes and export only graphics...

 

I also plan to do an enhanced remake on the TI later on, perhaps than I use a compiled version of TheBF code or assembly in this version.

[Reciprocating Bill]

Perhaps by using one of the above BASIC algorithms, then randomly removing additional walls, you can enable multiple pathways while retaining a balanced appearance. 

Edited June 16, 2022 by Reciprocating Bill