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.

Comments

Perl analogue

[Okian Warrior]

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.

...but it definitely *looks* like a maze, so that's what it must be. The authors said so, after all...

Python version

[tepples]

The Python version is two non-comment lines:

#!/usr/bin/env python
# DataGlyphs simulator by Damian Yerrick
from random import choice
while True: print "".join(choice('/\\') for i in range(40))

Re:Without the use of a loop!?

[narcc]

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.

Re:Without the use of a loop!?

[Dan East]

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

Re:Without the use of a loop!?

[narcc]

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.