TI-BASIC maze generator from magazine article

[Michael Chaney]

Years ago, in the early 1980s, I recall typing in a simple maze generator from a magazine article.  It wasn't the one in Compute's book of TI games.  It used character definitions to create 16 different cell types, and so the entire maze was 28x24.  I cannot find it.  Does anybody remember this?

[Ed in SoDak]

Welcome! Where all did you look? That's a broad base of possibilities, excluding only Compute's book. Like you, my magazine program transcribing days took place over 30 years ago. Back then I'd buy any magazine rack title that had even a short column mentioning TI. Most any electronics title was flirting with computers and publishing listings for multiple systems, besides the ones specific to computers or dedicated to promoting one brand or another. And of course subscriber publications like Micropendium and user group newsletters not found on a newstand or magazine rack.

 

Many programs and complete disks-full have been preserved on WHT, Gamebase and elsewhere. The program's name might not even have "Maze" in it, at the whim of the author or whoever typed it in and later archived it online. I've downloaded many megs of 'em, but admit to only checking out a few dozen at best.

 

Need more info to narrow it down! What mags did you buy or read back then? Was it written in Console Basic, Extended Basic cartridge?

-Ed

[matthew180]

I'm like mazes and maze generation quite a bit.  The first maze generator I even encountered was from a COMPUTE! magazine, IIRC.  I spent a lot of time taking that code apart, and it was probably my first exposure to an actual algorithm.  I now know it was a recursive-decent generator, and to save memory (it was written in BASIC after all) it used the screen as the stack by skipping every other cell during generation, which allows the path itself to be used during back-tracking.  This also means mazes always had a full tile between paths, which it not necessarily a bad characteristic and could probably come in handy.  It does limit the complexity of the maze in a given size though.  It was slow though.  I have never found a maze algorithm that runs quickly in TI-BASIC or XB.

 

On 3/11/2020 at 9:55 PM, Michael Chaney said:

... a simple maze generator ...

... It used character definitions to create 16 different cell types ...

That does not sound particularly simple, unless the 16 different types were such that you could randomly select any of them and have it fit anywhere.  As Ed mentioned, more info is needed to narrow this down, but I hope you find it; I'm interested to know more about the method used to generate the maze.

 

Make sure you check the Internet Archive's computer magazine section, they have full scans of most of the home computer magazines from back in the day.  I will also try to find the one I first learned about years ago.

 

[+fimbulvetr]

Page 33, Volume 1 No. 4 of 99’er magazine has a type-in game called Maze Race that randomly generates a maze.

[Asmusr]

On 3/12/2020 at 5:55 AM, Michael Chaney said:

It used character definitions to create 16 different cell types

Perhaps 16 patterns with 4x4 pixels blocks, like multicolor mode?

[matthew180]

A quick search in the COMPUTE! archive for "maze" gave some results:

 

Dec 1981, Issue 19, pg 54. Maze Generator
Jul 1982, Issue 26, pg 40. Maze Race, references and uses Maze Generator
Dec 1982, Issue 31, pg 152.  Hidden Maze, references and uses Maze Generator

The first article certainly appears to use the algorithm I remember, however it is too early for me to have read; I did not discover computer magazines until early 1983.  I suppose it is possible that the last one might have crossed my path though.

 

Were there any other main-stream magazines of the time publishing type-in BASIC programs?  In looking through a few different publications, clearly COMPUTE! was the primary source, but in my vague memories it seems like there were "so many" others (probably false memories).

Edited March 17, 2020 by matthew180

[matthew180]

A few more articles (by the same author) in Creative Computing:

 

Creative Computing, June 1981, Bee Amazed
Creative Computing, Dec 1982, Pocket Computing Fun
Creative Computing, Dec 1983, PolyMaze Solver

 

[majestyx]

Family Computing (from Scholastic) published some TI program listings along with their kids-oriented sister publication K-Power. There was a game call Amazin' in a K-Power compilation special, but I don't think this is the program you're seeking. Just wanted to note that those two publications also had substantial TI listings in them.

 

https://archive.org/details/family-computing

 

https://archive.org/details/k-power-magazine

 

[+adamantyr]

It sounds familiar... I'm not sure I've seen a printed magazine listing for the TI using the technique though.

 

What it's doing is using a nybble value (0-15) to indicate open or closed spaces on the four sides of the cell. So if it was NSEW and you wanted walls on the north and east side, it would be 1010, or value 10.

 

The maze generator in Wizard's Doom uses this technique as it's very efficient in terms of storing the maze.

 

If it was written in BASIC though, that's impressive because you'd have to use adds instead of bitwise operations, which are only available in XB.

[Michael Chaney]

First, thanks for all the replies!  I should have mentioned a few things:

 

1. I've searched extensively through online magazine archives.  The program that I'm seeking was TI-specific (it used HCHAR and friends to draw the maze), although it was possibly in XBASIC.

 

2. It wasn't a game - it just generated the maze.  It took about an hour to generate the whole screen on the TI.

 

3. It started at top-left and had a certain affinity for going left.  The maze would start by going roughly across the top, down the right side, back across the bottom, and by then it usually had enough randomness to start being more of a maze.  If I remember correctly, the algorithm just tried random directions 10 times or something like that, and then gave up and went in order checking each direction.  That would cause such a pattern to emerge.

 

4. It seems like it was in a magazine where one wouldn't expect to find a TI program, like Byte.  I might be misremembering, though.  There was likewise a cool canon (music) generator one time that appeared in a magazine like that and was written specifically for the TI.  I saw it, loved it, lost it, and spent years trying off and on to find it again.

 

5. I know *a lot* about mazes.  This is me: https://github.com/mdchaney/jsmaze.  That all started from the TI program nearly 40 years ago.

 

6. One other thing - whoever mentioned above about the 4 directions and all that - there are 16 variations of 4 walls being off/on, and it's easily stored in the low nybble and set in the character set.  So 0 has no walls and 15 has all four.  14 would be the top wall open, as it's number NESW.  Moving into a new cell means knocking down the wall in the current cell as well as the corresponding wall in the cell that is being entered.  There's no recursion, but the only thing you really have to remember is how you entered a certain cell.  That was likely done in an array.

 

Thanks again for any help.  I'm wanting to do a talk on maze generation, and you can imagine how awesome it would be to fire up a TI emulator (or, an actual TI-99/4a) and show where it all began.

Edited March 21, 2020 by Michael Chaney

[+adamantyr]

Cool algorithms!

 

Yeah when I wrote Wizard's Doom, I had to write a maze generator myself. I didn't want it to NEVER cross it's own path, as that generates slightly boring mazes. So I use a tolerance level and it's only initially biased not to cross it's own path, but can do so on a random chance or if there's nowhere else it can go. It's not too fast, but it only takes at most ten minutes to generate the largest maze on level 6.

 

One of my sidelined projects is a Rougelike for the TI, which will involve a much more complex procedural generating system. Not just mazes but rooms and other features. Should be fun to write when I can get to it!

[Ed in SoDak]

The Jim Peterson Tigercub collection has quite a few maze programs. Several with a title such as Maze Maker. Might be worth a look.

-Ed

[matthew180]

19 hours ago, Michael Chaney said:

First, thanks for all the replies!  ...

Thanks for coming back!  Nothing kills the enthusiasm for a conversation or trying to help someone like having the O.P. disappear.  This is a very active and friendly community, if you post something you *will* get responses and people genuinely interested in the topic.

 

19 hours ago, Michael Chaney said:

2. It wasn't a game - it just generated the maze.  It took about an hour to generate the whole screen on the TI. ...

An HOUR?  Wow, that is pretty slow even by TI-BASIC standards.  So was the resulting maze at tile/character resolution, i.e. 32x24 tiles, or was it doing sub-tile pattern manipulations to make a higher resolution maze?

 

19 hours ago, Michael Chaney said:

3. It started at top-left and had a certain affinity for going left. ...

A lot of the older algorithms would tend to do that, it makes the code easier but the result maze less random.

20 hours ago, Michael Chaney said:

... If I remember correctly, the algorithm just tried random directions 10 times or something like that, and then gave up and went in order checking each direction. ...

If that is true, this could account for the long generation time.  TI-BASIC is not fast at making random numbers.  That also seems like a bad design based on some idea that in 10 random rolls you will try each direction.  There are better and faster ways.

 

20 hours ago, Michael Chaney said:

... I saw it, loved it, lost it, and spent years trying off and on to find it again.

I know that experience well.  We will find it though! 🙂

20 hours ago, Michael Chaney said:

5. I know *a lot* about mazes.  This is me: https://github.com/mdchaney/jsmaze.  That all started from the TI program nearly 40 years ago.

Cool, I'll have to check out your repo.  My interest in mazes and maze generation was also sparked by a program (I mentioned the story above) that I found in a magazine BITD.  13-year-old me was fascinated, and I still like maze generation today.

 

I assume you know about the Think Labyrinth website: http://www.astrolog.org/labyrnth.htm

 

Lots of great stuff there.  There are also a lot of generators on the 'net for things like dungeon generators and such, which are related to mazes but have other features like rooms, connecting paths, etc.

 

There was a guy, Jamis Buck, who had some nice generators and such, but it all disappeared one day.  Then a year or so later he had a book about mazes on Amazon (which answered why he took down all his stuff from the 'net).  The book is "ok" (I own it), but his webpages and such were better IMO.  The book does not provide any info you probably don't already know, i.e. he didn't seem to come up with anything new for the book over what he had previously put online.

 

20 hours ago, Michael Chaney said:

6. One other thing - whoever mentioned above about the 4 directions and all that - there are 16 variations of 4 walls being off/on, and it's easily stored in the low nybble and set in the character set.  So 0 has no walls and 15 has all four.  14 would be the top wall open, as it's number NESW.  Moving into a new cell means knocking down the wall in the current cell as well as the corresponding wall in the cell that is being entered. ...

Yup, that is a common pattern that I think most programmers discover on their own if they spend any time working with maze generation.  I did, then noticed a lot of other implementations also used some variation of that exact method.  It is more compact for sure, but takes more processing to manage the bit manipulations, so there is always a trade-off.  On a modern computer where a few bytes of memory is of little concern, it is easier and faster to just have a variable for each wall in your cell-structure.

 

Then again, if you don't consider each cell as a room with walls, then that whole pattern goes away.  For example, instead of managing cells you can think of a maze as just a bunch of walls, which implicitly create rooms.  There are lots of different models for mazes, which keeps it fun and interesting, IMO.

 

20 hours ago, Michael Chaney said:

I'm wanting to do a talk on maze generation, and you can imagine how awesome it would be to fire up a TI emulator (or, an actual TI-99/4a) and show where it all began.

Cool.  Please post info if this happens.

 

14 hours ago, adamantyr said:

So I use a tolerance level and it's only initially biased not to cross it's own path, but can do so on a random chance or if there's nowhere else it can go.

Most dungeon generators I have looked at generate the perfect maze first, then go back and knock down walls to create loops, rooms, wider openings, etc.  Seems easier to have a multi-stage process like that over complicating the generation algorithm; and it might help speed things up on something like a retro-computer.

[merlins_ghost]

Check here https://rosettacode.org/wiki/Maze_generation it is not exactly what you are looking for though.  At the link there are many various maze generators.  "How to Build a Maze," Byte magazine, Dec.  1981 by David Matuszek described a maze generator using 0-15 for the cells of the maze, using -1 for frontier cells, and some other number eg. 100 for the wall cells.  Nibble magazine Feb 1984 by David Krathwohl "Speed Maze" contained a maze generator using the aforementioned article as a template.   Maybe not much help, but maybe you can find articles written by one of them for TI-99/4A.  

[+TheBF]

For fun I took the Commodore BASIC version from Rosetta Code and got it to run under TI XB.

The 32 column screen is too narrow but it does output a maze.  

 

I just changed the DIM statements to use literal numbers and made RND correct for TI-99

It needs more work to make it function on the TI-99 BASIC screen but it's a beginning for someone.

 

Spoiler

1  REM MAZE from Rosetta CODE
2  REM Adapted from commodore BASIC
100 MS=10::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 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
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

 

 

[Jim Davis]

On 3/20/2020 at 7:18 PM, Michael Chaney said:

4. It seems like it was in a magazine where one wouldn't expect to find a TI program, like Byte.  I might be misremembering, though.  There was likewise a cool canon (music) generator one time that appeared in a magazine like that and was written specifically for the TI.  I saw it, loved it, lost it, and spent years trying off and on to find it again.

Not the maze part, but I think I found the music!

 

Enter magazine, April 1985, "Pocket Canon."  (I found your post here while looking for the program myself.)

Edited October 5, 2020 by Jim Davis

[Ed in SoDak]

12 hours ago, Jim Davis said:

Enter magazine, April 1985

 

Welcome and thanks for unearthing another "pocket" program. I remember typing in Pocket Sunrise and a few others. Don't recall seeing Enter magazine though. Usually if I saw they had a TI99 "anything" in their pages, I'd buy it off the periodicals rack. Off to archive.org!

-Ed