Maze Generator

Creating Games? Developing something for fun?

Moderators: FourthWorld, heatherlaine, Klaus, kevinmiller, robinmiller

Post Reply
xAction
Posts: 86
Joined: Sun Oct 03, 2021 4:14 am

Maze Generator

Post by xAction » Tue Oct 19, 2021 2:44 pm

MazeGeneratorv4_Previewpng.png
MazeGenerator_v4.zip
(20.81 KiB) Downloaded 196 times
I downloaded some BASIC langauge maze generation code...oh a decade or so ago and its been floating around hard drives forever.
I can't find where I found it online anymore but here it is. James L. Dean made a bunch of maze games, 3D ones too. This one must have been one of his first.
It produces a text based maze that looks like this:
JamesLDeanMaze.png
JamesLDeanMaze.png (11.6 KiB) Viewed 5353 times
CODING 9 LIVECODE GAMES By SCOTT MCDONALD has a Wolfenstein-esque raycasting maze game that uses text as a base for maps so I was thinking...could randomize those maps with this old BASIC maze generator.

Code: Select all

10 REM DISPLAY A MAZE.    
20 REM SEED WILL PRODUCE A DIFFERENT MAZE. 
30 REM 
40 REM WRITTEN BY JAMES L. DEAN 
70 REM DEFINT A-Z command not needed
80 PRINT 
90 PRINT "Number of columns"; 
100 INPUT C 
110 IF C > 1 THEN 140 
120 PRINT "? The number of columns must be at least 2" 
130 GOTO 90 
140 PRINT 
150 O=2*C 
160 P=O+1 
170 PRINT "Number of rows"; 
180 INPUT R 
190 IF R > 1 THEN 220 
200 PRINT "? The number of rows must be at least 2" 
210 GOTO 170 
220 PRINT 
230 W=2*R+1 
240 DIM Z(P*W+2*C*R+200) 
250 PRINT "Seed"; 
260 INPUT S 
270 PRINT 
280 S=ABS(S) 
290 FOR T=1 TO 8 
300 G=INT(S/29) 
310 H=S-29*G 
320 S=G 
330 IF H <> 0 THEN 350 
340 H=19 
350 Z(T)=H 
360 NEXT T 
370 Z(9)=-1 
380 Z(105)=0 
390 Z(10)=0 
400 Z(106)=1 
410 Z(11)=1 
420 Z(107)=0 
430 Z(12)=0 
440 Z(108)=-1 
450 V=8 
460 N=104 
470 FOR A=1 TO 4 
480   FOR B=1 TO 4 
490     IF A = B THEN 690 
500       FOR D=1 TO 4 
510         IF A = D THEN 680 
520         IF B = D THEN 680 
530           FOR E=1 TO 4 
540             IF A = E THEN 670 
550             IF B = E THEN 670 
560             IF D = E THEN 670 
570               Z(A+V)=Z(9) 
580               Z(A+N)=Z(105) 
590               Z(B+V)=Z(10) 
600               Z(B+N)=Z(106) 
610               Z(D+V)=Z(11) 
620               Z(D+N)=Z(107) 
630               Z(E+V)=Z(12) 
640               Z(E+N)=Z(108) 
650               N=N+4 
660               V=V+4 
670           NEXT E 
680       NEXT D 
690   NEXT B 
700 NEXT A 
710 T=201 
720 FOR U=1 TO W 
730   FOR M=1 TO P 
740     Z(T)=1 
750     T=T+1 
760   NEXT M 
770 NEXT U 
780 T=INT(C/2) 
790 T=C-2*T 
800 IF T <> 0 THEN 830 
810   X=C 
820 GOTO 840 
830 X=C+1 
840 T=INT(R/2) 
850 T=R-2*T 
860 IF T <> 0 THEN 890 
870   Y=R 
880 GOTO 900 
890 Y=R+1 
900 V=200+P*W 
910 F=V 
920 GOTO 1300 
930 Z(202)=0 
940 Z(200+P*(W-1)+O)=0 
950 PRINT ". "; 
960 T=1 
970 FOR M=3 TO P 
980   IF T = 0 THEN 1010 
990     PRINT "."; 
1000   GOTO 1020 
1010     PRINT "_"; 
1020   T=1-T 
1030 NEXT M 
1040 PRINT 
1050 U=3 
1060 V=200+P 
1070 N=V+P 
1080 IF U > W THEN 1760 
1090   T=1 
1100   FOR M=1 TO P 
1110     N=N+1 
1120     V=V+1 
1130     IF T <> 0 THEN 1190 
1140       IF Z(N) = 1 THEN 1170 
1150         PRINT " "; 
1160       GOTO 1230 
1170         PRINT "_"; 
1180     GOTO 1230 
1190       IF Z(V) = 1 THEN 1220 
1200         PRINT "."; 
1210       GOTO 1230 
1220         PRINT "!"; 
1230     T=1-T 
1240   NEXT M 
1250   PRINT 
1260   U=U+2 
1270   N=N+P 
1280   V=V+P 
1290 GOTO 1080 
1300 Z(200+P*(Y-1)+X)=0 
1310 I=1 
1320   J=Z(1) 
1330   G=1 
1340   FOR H=2 TO 8 
1350     T=Z(H) 
1360     Z(G)=T 
1370     J=J+T 
1380     IF J <= 29 THEN 1400 
1390       J=J-29 
1400     G=H 
1410   NEXT H 
1420   Z(8)=J 
1430 IF J > 24 THEN 1320 
1440 IF I > 4 THEN 1700 
1450   N=I+4*(J-1) 
1460   K=X+2*Z(8+N) 
1470   IF K <= 1 THEN 1680 
1480   IF K >= P THEN 1680 
1490     Q=Y+2*Z(104+N) 
1500     IF Q <= 1 THEN 1680 
1510     IF Q >= W THEN 1680 
1520       IF Z(200+P*(Q-1)+K) <> 1 THEN 1680 
1530         IF X <> K THEN 1560 
1540           Z(200+P*(((Y+Q)/2)-1)+K)=0 
1550         GOTO 1570 
1560           Z(200+P*(Q-1)+(X+K)/2)=0 
1570         X=K 
1580         Y=Q 
1590         V=V+1 
1600         Z(V)=I 
1610         V=V+1 
1620         Z(V)=J 
1630         GOTO 1300 
1640         N=I+4*(J-1) 
1650         X=X-2*Z(8+N) 
1660         Y=Y-2*Z(104+N) 
1670 GOTO 1440 
1680   I=I+1 
1690 GOTO 1440 
1700   J=Z(V) 
1710   V=V-1 
1720   I=Z(V) 
1730   V=V-1 
1740   IF F = V THEN 930 
1750 GOTO 1640 
1760 END 
So I sat dow and thought, this'll be easy, I just make handlers named after the important line numbers where things have to go to subroutine or flow from one part to another, convert X=whatever to put whatever into X and it'll all go smoothly. Nope. This BASIC program spits out a 20x20 maze in microseconds on MMBasic DOS program or a minute maybe two using a 8-bit computer emulator, but my Livecode version, after many recursion error violations and adjustments took five or more minutes to spit out a non-maze blob and I couldn't for the life of me figure out what it was doing.

So I sorta started from scratch with this idea:

Code: Select all

1. Make a grid
2. KNock down random walls
That sorta worked, but was knocking either too little or too many walls down, and my first version was drawing every wall of the grid first before doing the knocking down, and that was crazy slow, a 30 by 30 grid is like a 10 minute ordeal. Why is Livecode's create command so slow? Maybe I should have used copy?

So then I went with a another method:
  1. Create the whole map virtually
  2. Store each row and colum "wall" in a custom property array with a value of 1
  3. Visit each virtual cell, and either knock down one, or both of the walls , ie, a value of 0 in the custom property
  4. Draw the walls that remain.
Almost Instant maze---like thing! There are dead ends and unreachable pockets, I'm a cruel dungeon master.
There are also big room like gaps, which I don't entirely mind, since I'm thinking of game map more than standard wall to wall labyrinth.

Apparently there's a whole logic behind maze stuff. But I was certain I could just wing it, with my HULK SMASH! algorythym.

So then i had some mazes, great. but how could I teach the program to walk through them? I came here to the forums and found Richmond's bug but, like his problem the bug I made mashed randomly around and eventually went right over the walls.

Then I thought,, hey I have this line graphic with point values, if I draw the inverse of the maze I can just travel over the lines.
So I made a handler to just get all the zero value array walls and draw them, but you know what that made? More walls, not a path.
But hey, two mazey maps for the price of one.

So that's where we are at with this stack, lovely maze like graphics but no pratical solution for
A) perfect mazes
B) solving them through a readily available algorhythm

Next stop: reading some tried and true methods and applying them.

xAction
Posts: 86
Joined: Sun Oct 03, 2021 4:14 am

Re: Maze Generator

Post by xAction » Tue Oct 19, 2021 5:11 pm

I spent hours looking for a way to simply import Livecode graphic points as a CSV file into a 3D program to extrude the map.
Absolutely astonishing poor results. Everything for previous versions of Blender are broken, and every script on some stackexchange or whatever for multi-gigabyte installed software doesn't work.
BUT!
  1. Set the backgroundColor of graphic "MazeArea" to "white"
  2. Set the linesize of graphic "Positive" to 8
  3. Export snapshot or take a screen grab
  4. Load or paste into Inkscape
  5. Use Trace command
  6. Save to SVG
  7. Open SVG in Blender
  8. Extrude and adjust the scales
Wala! Now you have a 3D space to do a-mazing things in.
MazeGeneratorv4_Previewpng3D.png
MazeGeneratorv4_Previewpng3D.png (180.17 KiB) Viewed 5325 times
Of course there's a Blender Add-On that draws full blown mazes on any surface, maze on a shoe? maze on a football, maze on a nose? whatever. Show offs.

So we don't have SVG export huh?

richmond62
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 9250
Joined: Fri Feb 19, 2010 10:17 am
Location: Bulgaria

Re: Maze Generator

Post by richmond62 » Tue Oct 19, 2021 5:22 pm

No: No SVG exporter, and SVG import is also fairly 'dicky'.

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9567
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: Maze Generator

Post by dunbarx » Tue Oct 19, 2021 7:25 pm

@xAction

Just want to commend you on your work and efforts. I rarely see you in any guise but reporting on your gamesmanship with LC. No matter...

Craig

garmeister
Posts: 29
Joined: Sat Apr 10, 2021 6:56 pm

Re: Maze Generator

Post by garmeister » Fri Nov 05, 2021 5:32 am

I have this book on Mazes for Programmers. It's written in Ruby but the logic should be transferrable to other languages especially scripting languages like Python, Javascript ... but not sure how I would approach it in LiveCode after looking at your attempts. :)
Gary E Chike DMD
"Experience is what you get when you don't get what you want"

xAction
Posts: 86
Joined: Sun Oct 03, 2021 4:14 am

Re: Maze Generator

Post by xAction » Fri Nov 05, 2021 5:57 am

Ah, I've held that book in my hands back when there were bookstores.

The only way to know is to try. I hadn't the slightest idea except something about 'grid..visit cell..knock down wall." I understand that BASIC code only as far as what the commands do in general, but what they are doing all together in that code? ...no idea, recursing like crazy.

While I was trying, very hard, I kept thinking "Hmm maybe if I do it this way..." and sure enough over on the wikipedia page about maze algorithms those same thoughts kept someone else awake all night long long ago, with a pencil , or some sheers hacking through their shrubbery.

Hutchboy
Posts: 51
Joined: Wed Aug 01, 2018 2:57 pm
Contact:

Re: Maze Generator

Post by Hutchboy » Tue Jan 23, 2024 6:18 am

Hi all,

Since I could use a maze generator for one of my projects, I've been pouring over the Jamis Buck website and downloaded the Kindle version of his "Mazes for Programmers" book yesterday. Interesting stuff. So I took a stab at creating a maze generator, first trying the Recursive Division algorithm but only have had partial success with that. So I moved on to the Binary Tree Algorithm and was successful.

Attached is a version that I purposely didn't try to speed up so you can see the algorithm carve the path to turn a grid of walls into a maze. The card script is pretty well documented and I included references in the header.

My plan is to work through some of the other interesting algorithms and add to this stack.

- Mike
Attachments
Maze Generation with Binary Tree Algorithm.livecode.zip
(17.33 KiB) Downloaded 30 times

PaulDaMacMan
Posts: 616
Joined: Wed Apr 24, 2013 4:53 pm
Contact:

Re: Maze Generator

Post by PaulDaMacMan » Sat Feb 17, 2024 8:12 pm

xAction wrote:
Tue Oct 19, 2021 5:11 pm
I spent hours looking for a way to simply import Livecode graphic points as a CSV file into a 3D program to extrude the map.
Absolutely astonishing poor results. Everything for previous versions of Blender are broken, and every script on some stackexchange or whatever for multi-gigabyte installed software doesn't work.
BUT!
  1. Set the backgroundColor of graphic "MazeArea" to "white"
  2. Set the linesize of graphic "Positive" to 8
  3. Export snapshot or take a screen grab
  4. Load or paste into Inkscape
  5. Use Trace command
  6. Save to SVG
  7. Open SVG in Blender
  8. Extrude and adjust the scales
Wala! Now you have a 3D space to do a-mazing things in.
MazeGeneratorv4_Previewpng3D.png
Of course there's a Blender Add-On that draws full blown mazes on any surface, maze on a shoe? maze on a football, maze on a nose? whatever. Show offs.

So we don't have SVG export huh?
I wrote handler that does something similar to this, but converts 'the effective points' of a graphic control to either an SVG path string (for using with Widgets) or wrapped in some XML for writing to an SVG file. Curved lines from objects, like Rounded corners of a Rounded Rectangle graphics will look jagged when you scale the path (it looks like the engine generates a vector tracing of pixels). I actually incorporated it into that other IDE 'over there'. An .SVG File is what you wanted so you can use to extrude from in Blender, all done with script, no other intermediate apps like doing InkScape tracing. Of corse you could also maybe use some processing to smooth any star-case looking curves or diagonal lines (from being tracing of pixels).

That bolded bit is the actual syntax to use.
My GitHub Repos: https://github.com/PaulMcClernan/
Related YouTube Videos: PlayList

Post Reply

Return to “Games”