Slashdot Mirror
How Does a Single Line of BASIC Make an Intricate Maze?
JameskPratt writes "This Slate article talks about a single line of code — 10 PRINT CHR$ (205.5 + RND (1)); : GOTO 10 — and how it manages to create a complicated maze without the use of a loop, variables and without very complicated syntax." Now that amazing snippet of code is the basis of a book, and the book is freely downloadable.
Don't have a Commodore Basic interpreter? this Perl 1-liner will do the same thing:
print ["/","\\"]->[rand(2)] while 1;
It has no start or end point, and for two arbitrary points you can't guarantee that a path exists.
This article fails in English and fails in the content. Booya.
it's not a maze, it's a pattern of random forward and backward slashes, "/" and "\". There's no guarantee that a path exists anywhere near the top to anywhere near the bottom. In fact, because it's random, you'd be blocked off at some point.
Also, it can't string together a single grammatically correct sentence. Complete failure on both technical and English levels!
The book is, however, quite interesting (just go straight to the open-access PDF and skip the mediocre Slate article).
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
I think there is a bit of a story in the fact that while in function, it is extremely simple though in result/appearance it creates what most perceive to be a complex maze of passages. The code puts out random positive space objects while the mind sees a single, complex negative space.
It sort of reminds me of similar little tricks used to generate landscapes and other such things... mandelbrot comes to mind.
int main(){for(;;)putchar("\\/"[rand()%2]);}
Actually, when the code is idiomatic, it is a reflection on that language/frameworks that go with it. Having spent a bad 5 years in enterprise java trenches I can vouch for the realism of that code. It gave me flashbacks. I'm still fucking shivering.
http://rareformnewmedia.com/
Indeed, it isn't exactly rocket science -- zillions of kids under 10 picked up the basics of BASIC from type-in programs in kids books and magazines back in the 80's.
What bugs me most is that instead of doing the obvious (making a binary tree maze) it's some weird artifact of how the / and \ combine on-screen that makes something that vaguely resembles a maze -- full of loops (no big deal) large winding sections without any junctions (bad), and isolations (terrible!).
Just for fun:
IBM PC users! You can modify the C64 program in the summary to both run on your micro and produce a binary tree maze with this simple change: PRINT CHR$(220 + INT(RND(1)*2) );
You won't be able to get the same effect with alternating forward- and back-slashes with something like PRINT CHR$(47 + INT(RND(1)*2)*45); as they don't connect at all -- neither on the same line nor between lines.
Required reading for internet skeptics
A simple addition makes the TI-99/4A version look visually just like the C64's. That is to simply define the forward and backward slash characters to look more the C64's and span the whole area of the character's bitmap.
10 CALL CHAR(47, "C0E070381C0E0703")
20 CALL CHAR(92, "03070E1C3870E0C0")
30 PRINT CHR$(INT(RND+.5)*45+47);
40 GOTO 30
Finally, if we're going to go to the trouble of defining character images, then we might as well use contiguous character codes so we don't need the extra math. We could use the C64's exact values, however the TI's character set only has 128 characters. So we'll use values 100 less than the C64 version. Also, the TI rounds floating values to integers, whereas the C64 simply truncates them. So we don't need to add .5 to the random value.
10 CALL CHAR(105, "C0E070381C0E0703")
20 CALL CHAR(106, "03070E1C3870E0C0")
30 PRINT CHR$(105+RND);
40 GOTO 30
Better known as 318230.
A binary tree maze algorithm will generate a "perfect maze" (no loops, isolations, and only a single path between any two cells), though you need a long hallway along two sides (depending on which edges you use for walls).
Mazes with square cells share edges, so by assuming some rules about the outside walls of a maze, you can represent each cell in a maze with only two bits. You need only store, for example, just the south and west walls of each cell.
To make a binary tree maze, first assume an outer wall and a long hall (no south walls) in the first column, and along the bottom row (no west walls). For all remaining cells, randomly add a west or south wall. You don't need any information about adjacent cells -- just flip a coin and draw a wall for each remaining cell. This will produce a "perfect maze". It's pretty cool.
The code I posed will generate a binary tree maze, though it won't show the two long halls. (In this case, the program uses west and south walls, so the halls will be the in the first column and the along the bottom row.)
The lameness filter doesn't want me to show you an example. Still, it's pretty easy to make a nice binary tree maze generator yourself. Give it a try and you'll see how it works.
For fun, you can make four binary tree mazes and arrange them so that you have two long halls (one East to West, the other North to South) intersecting at the center of the maze, just by choosing which pair of walls to randomly generate in each quadrant. It makes a much more interesting looking maze without adding much complexity (just figure out which quadrant the current cell is in) and retaining all of the properties of a perfect maze.
I hope that helps.
Required reading for internet skeptics
Try something like this. (Keeping with the BASIC theme)
10 CLS
20 W = 10
30 H = 10
40 RANDOMIZE TIMER
50 FOR I = 1 TO W: PRINT " __"; : NEXT I
60 PRINT ""
70 FOR I = 1 TO H
80 PRINT "| ";
90 FOR J = 1 TO W - 1
100 IF INT(RND(1) * 2) = 0 THEN PRINT " __"; ELSE PRINT "| ";
110 NEXT J
120 PRINT "|"
130 NEXT I
140 PRINT "|";
150 FOR I = 1 TO W - 1: PRINT "__ "; : NEXT I
160 PRINT "__|"
Lines 20 and 30 specify the width and height of the maze
Lines 50 and 60 draw the north outer wall of the maze
Lines 70 - 130 draw the maze by randomly drawing either a west or south wall.
Line 80 draws the first cell in a row, which won't have a south wall, to make a long empty hall
Line 120 draws the east-most outer wall at the end of each row
Lines 140 - 160 draw the last row, just a long empty hall.
You'll see that the maze has no loops or isolations. Every cell is reachable from every other cell by a single path.
Hope that helps. Happy maze making!
Required reading for internet skeptics