Generating mazes (BBC BASIC)

Discuss all aspects of programming here. From 8-bit through to modern architectures.
Post Reply
User avatar
lurkio
Posts: 1974
Joined: Tue Apr 09, 2013 11:30 pm
Location: Doomawangara
Contact:

Generating mazes (BBC BASIC)

Post by lurkio » Tue Apr 16, 2019 11:56 pm

Here's a BBC BASIC translation of the Recursive Backtracker maze-generation algorithm, as explicated by Jamis Buck in his book Mazes For Programmers, and on his blog, and as used in Maze Of Madness.

Code: Select all

 10 REM Recursive Backtracker maze algorithm
 11 REM via Jamis Buck
 12 REM BBC BASIC version by lurkio @ Stardot, 2019
 15 REM -------------------------------------------
 20 MODE0
 40 CLEAR:VDU23,0,10,8;0;0;0:INPUT'"Size of maze? "mSize%
 45 IF mSize%<2ORmSize%>15 mSize%=1+RND(14):VDU7,11:PRINTSTRING$(14,CHR$9);mSize%;" "
 50 DIM grid% mSize%^2
 60 FOR I%=0TOmSize%^2STEP4:I%!grid%=0:NEXT
 70 DIM stack%(mSize%^2)
 90 VDU23,0,10,0;0;0;0
100 PROCprint(1):PRINTSTRING$(2*mSize%+1,CHR$11);:PRINTTAB(0);:H%=VPOS
105 REM -------------------
120 REM ## GENERATE MAZE ##
140 DIM buff%(3):REM cells surrounding current cell
150 sp%=0:REM stack pointer
170 cell%=RND(mSize%^2)-1:REM current cell
180 V%=1:REM number of cells visited
190 num%=0
210 REPEAT
230   stack%(sp%)=cell%:sp%=sp%+1
240   R%=cell% DIV mSize%:C%=cell%-R%*mSize%
260   IF num%>0 V%=V%+1
280   PRINTTAB(1+C%*4,H%+(mSize%-R%)*2-1);:IFV%>1PRINT" . ";ELSEPRINT" * ";
290   VDU8
300   IF cell%?grid% AND 1 VDU8,8,11,32,32,32,8,8,8,10,9,9
310   IF cell%?grid% AND 8 VDU8,8,8,32,9,9
320   IF cell%?grid% AND 4 VDU9,32,8,8
330   IF cell%?grid% AND 2 VDU8,8,10,32,32,32,8,8,8,11,9,9
350   num%=0
360   FORI%=0TO3:buff%(I%)=-1:NEXT
370   cell_n%=mSize%*(R%+1)+C%
380   IF R%<mSize%-1 AND cell_n%?grid%=0 buff%(0)=cell_n%:num%=num%+1
390   cell_s%=mSize%*(R%-1)+C%
400   IF R%>0 AND cell_s%?grid%=0 buff%(1)=cell_s%:num%=num%+1
410   cell_e%=mSize%*R%+C%+1
420   IF C%<mSize%-1 AND cell_e%?grid%=0 buff%(2)=cell_e%:num%=num%+1
430   cell_w%=mSize%*R%+C%-1
440   IF C%>0 AND cell_w%?grid%=0 buff%(3)=cell_w%:num%=num%+1
460   rand%=-1:IF num%=1 rand%=1 ELSE IF num%>1 rand%=RND(num%)
470   nextI%=-1
480   FORI%=0TO3:IF buff%(I%)>-1 rand%=rand%-1
490     IF rand%=0 next%=buff%(I%):nextI%=I%:rand%=-1
500   NEXT
510   IF nextI%=0 cell%?grid%=cell%?grid% EOR 1:next%?grid%=next%?grid% EOR 2
520   IF nextI%=1 cell%?grid%=cell%?grid% EOR 2:next%?grid%=next%?grid% EOR 1
530   IF nextI%=2 cell%?grid%=cell%?grid% EOR 4:next%?grid%=next%?grid% EOR 8
540   IF nextI%=3 cell%?grid%=cell%?grid% EOR 8:next%?grid%=next%?grid% EOR 4
550   IF num%>0 cell%=next%
560   IF num%=0 sp%=sp%-2:IF sp%>=0 cell%=stack%(sp%):VDU8,32
580   REMU. sp%<0:V.8,32
590 UNTILV%=mSize%^2
REM 610 FORI%=0TOmSize%^2:stack%(I%)=0:NEXT
630 REM -------------------
650 *FX15
660 SOUND1,-15,100,1
670 IFGET PRINTTAB(0,H%);:PROCprint(0)
680 *FX15
690 SOUND1,-15,100,1
700 IFGET PRINTTAB(0,H%+2*mSize%):GOTO 40
730 REM ## End ##
735 REM -------------------
750 DEFPROCprint(w%):REM blocks? 0/1
760 VDU23,255,255,255,255,255,255,255,255,255
770 DIM T% 2+4*mSize%
780 DIM B% 2+4*mSize%
790 PRINT "+";STRING$(mSize%,"---+");
800 FOR R%=mSize%-1 TO 0 STEP-1:REM top down
810   $T%="|":$B%="+"
820   FOR C%=0 TO mSize%-1
830     IF w%=0 W$="   " ELSE W$=CHR$255+CHR$255+CHR$255
840     cell%=grid%+C%+R%*mSize%
850     IF ?cell% AND 4 THEN E$=" " ELSE E$="|"
860     $T%=$T%+W$+E$
870     IF ?cell% AND 2 THEN S$="   " ELSE S$="---"
880     $B%=$B%+S$+"+"
890   NEXT:REM column
900   PRINT'$T%'$B%;
910 NEXT:REM row
920 ENDPROC
Run the program in JSBeeb:
The program also works in BBC BASIC For Windows but fails in BBC BASIC For SDL 2.0 (MacOS version 1.02a) with a not-enough-memory error at line 50.

:?:

Untitled.png
BeebEm screenshot

User avatar
FourthStone
Posts: 721
Joined: Thu Nov 17, 2016 2:29 am
Location: Brisbane, Australia
Contact:

Re: Generating mazes (BBC BASIC)

Post by FourthStone » Wed Apr 17, 2019 12:16 am

I have vague recollections of a mag type in, maybe called Minotaur although that could be blurred memories, I can't even remember if it was a full game, but it had mode 1 maze-generation code which was of the type described above.

One day I hope to track it down :-k

User avatar
leenew
Posts: 3831
Joined: Wed Jul 04, 2012 3:27 pm
Location: Doncaster, Yorkshire
Contact:

Re: Generating mazes (BBC BASIC)

Post by leenew » Wed Apr 17, 2019 6:50 am


User avatar
Richard Russell
Posts: 699
Joined: Sun Feb 27, 2011 10:35 am
Location: Downham Market, Norfolk
Contact:

Re: Generating mazes (BBC BASIC)

Post by Richard Russell » Thu Apr 18, 2019 1:45 pm

lurkio wrote:
Tue Apr 16, 2019 11:56 pm
The program also works in BBC BASIC For Windows but fails in BBC BASIC For SDL 2.0 (MacOS version 1.02a)
The MacOS edition of BBC BASIC for SDL 2.0 is 64-bit BBC BASIC (current versions of MacOS will still run 32-bit apps, with a warning, but before too long 64-bit apps will be mandatory). That means memory addresses (pointers) must be stored in 64-bit variables, and that has significant implications for some BBC BASIC programs, notably programs which allocate memory using DIM. In the specific case of the maze program, you must change grid% to grid%%, B% to B%% and T% to T%% (alternatively omit the % which will retain compatibility with the BBC Micro). There is a reasonably comprehensive list of the potential incompatibilites here.

When the plans for a 64-bit BBC BASIC were first mooted there were all sorts of ideas for how this compatibility issue could be managed. One suggestion was for BASIC to run in a 32-bit sandbox, so that it could continue to use 32-bit addresses internally, but this caused insuperable difficulties when calling Operating System (or other external) API functions using SYS that needed true machine addresses to be passed. Another suggestion was for integer variables (% suffix) to all become 64-bits, but that broke programs using structures or which made assumptions about the size of integers - for example indexing into an array.

So the outcome was that I had to bite the bullet and incorporate true 64-bit pointers. Fortunately there are relatively few occasions when BBC BASIC programs use pointers, but allocating memory with DIM is one of them. If you are writing a program from scratch with the intention of it running on a 64-bit platform it is better to avoid this kind of memory allocation and instead declare a structure.
Last edited by Richard Russell on Thu Apr 18, 2019 1:51 pm, edited 2 times in total.

User avatar
lurkio
Posts: 1974
Joined: Tue Apr 09, 2013 11:30 pm
Location: Doomawangara
Contact:

Re: Generating mazes (BBC BASIC)

Post by lurkio » Thu Apr 18, 2019 5:13 pm

Richard Russell wrote:
Thu Apr 18, 2019 1:45 pm
In the specific case of the maze program, you must change grid% to grid%%, B% to B%% and T% to T%%
Thank you. I also had to change the "cell%" in PROCprint to "cell%%", and the names of the variables "nextI%" and "next%" had to be changed because they began with the reserved word "next".

Here's a version of the program that works in BBC BASIC For SDL 2.0 (MacOS version 1.02a):

Code: Select all

 10 REM Recursive Backtracker maze algorithm
 11 REM via Jamis Buck
 12 REM BBC BASIC version by lurkio @ Stardot, 2019
 15 REM -------------------------------------------
 20 MODE0
 40 CLEAR:VDU23,0,10,8;0;0;0:INPUT'"Size of maze? "mSize%
 45 IF mSize%<2ORmSize%>15 mSize%=1+RND(14):VDU7,11:PRINTSTRING$(14,CHR$9);mSize%;" "
 50 DIM grid%% mSize%^2
 60 FOR I%=0TOmSize%^2STEP4:I%!grid%%=0:NEXT
 70 DIM stack%(mSize%^2)
 90 VDU23,0,10,0;0;0;0
100 PROCprint(1):PRINTSTRING$(2*mSize%+1,CHR$11);:PRINTTAB(0);:H%=VPOS
105 REM -------------------
120 REM ## GENERATE MAZE ##
140 DIM buff%(3):REM cells surrounding current cell
150 sp%=0:REM stack pointer
170 cell%=RND(mSize%^2)-1:REM current cell
180 V%=1:REM number of cells visited
190 num%=0
210 REPEAT
230   stack%(sp%)=cell%:sp%=sp%+1
240   R%=cell% DIV mSize%:C%=cell%-R%*mSize%
260   IF num%>0 V%=V%+1
280   PRINTTAB(1+C%*4,H%+(mSize%-R%)*2-1);:IFV%>1PRINT" . ";ELSEPRINT" * ";
290   VDU8
300   IF cell%?grid%% AND 1 VDU8,8,11,32,32,32,8,8,8,10,9,9
310   IF cell%?grid%% AND 8 VDU8,8,8,32,9,9
320   IF cell%?grid%% AND 4 VDU9,32,8,8
330   IF cell%?grid%% AND 2 VDU8,8,10,32,32,32,8,8,8,11,9,9
350   num%=0
360   FORI%=0TO3:buff%(I%)=-1:NEXT
370   cell_n%=mSize%*(R%+1)+C%
380   IF R%<mSize%-1 AND cell_n%?grid%%=0 buff%(0)=cell_n%:num%=num%+1
390   cell_s%=mSize%*(R%-1)+C%
400   IF R%>0 AND cell_s%?grid%%=0 buff%(1)=cell_s%:num%=num%+1
410   cell_e%=mSize%*R%+C%+1
420   IF C%<mSize%-1 AND cell_e%?grid%%=0 buff%(2)=cell_e%:num%=num%+1
430   cell_w%=mSize%*R%+C%-1
440   IF C%>0 AND cell_w%?grid%%=0 buff%(3)=cell_w%:num%=num%+1
460   rand%=-1:IF num%=1 rand%=1 ELSE IF num%>1 rand%=RND(num%)
470   ni%=-1
480   FORI%=0TO3:IF buff%(I%)>-1 rand%=rand%-1
490     IF rand%=0 n%=buff%(I%):ni%=I%:rand%=-1
500   NEXT
510   IF ni%=0 cell%?grid%%=cell%?grid%% EOR 1:n%?grid%%=n%?grid%% EOR 2
520   IF ni%=1 cell%?grid%%=cell%?grid%% EOR 2:n%?grid%%=n%?grid%% EOR 1
530   IF ni%=2 cell%?grid%%=cell%?grid%% EOR 4:n%?grid%%=n%?grid%% EOR 8
540   IF ni%=3 cell%?grid%%=cell%?grid%% EOR 8:n%?grid%%=n%?grid%% EOR 4
550   IF num%>0 cell%=n%
560   IF num%=0 sp%=sp%-2:IF sp%>=0 cell%=stack%(sp%):VDU8,32
580   REMU. sp%<0:V.8,32
590 UNTILV%=mSize%^2
REM 610 FORI%=0TOmSize%^2:stack%(I%)=0:NEXT
630 REM -------------------
650 *FX15
660 SOUND1,-15,100,1
670 IFGET PRINTTAB(0,H%);:PROCprint(0)
680 *FX15
690 SOUND1,-15,100,1
700 IFGET PRINTTAB(0,H%+2*mSize%):GOTO 40
730 REM ## End ##
735 REM -------------------
750 DEFPROCprint(w%):REM blocks? 0/1
760 VDU23,255,255,255,255,255,255,255,255,255
770 DIM T%% 2+4*mSize%
780 DIM B%% 2+4*mSize%
790 PRINT "+";STRING$(mSize%,"---+");
800 FOR R%=mSize%-1 TO 0 STEP-1:REM top down
810   $T%%="|":$B%%="+"
820   FOR C%=0 TO mSize%-1
830     IF w%=0 W$="   " ELSE W$=CHR$255+CHR$255+CHR$255
840     cell%%=grid%%+C%+R%*mSize%
850     IF ?cell%% AND 4 THEN E$=" " ELSE E$="|"
860     $T%%=$T%%+W$+E$
870     IF ?cell%% AND 2 THEN S$="   " ELSE S$="---"
880     $B%%=$B%%+S$+"+"
890   NEXT:REM column
900   PRINT'$T%%'$B%%;
910 NEXT:REM row
920 ENDPROC
:idea:

User avatar
Richard Russell
Posts: 699
Joined: Sun Feb 27, 2011 10:35 am
Location: Downham Market, Norfolk
Contact:

Re: Generating mazes (BBC BASIC)

Post by Richard Russell » Thu Apr 18, 2019 5:58 pm

lurkio wrote:
Thu Apr 18, 2019 5:13 pm
the names of the variables "nextI%" and "next%" had to be changed because they began with the reserved word "next".
"next" isn't a reserved word, but "NEXT" is. There should have been no need to make that change, unless you enabled the 'Lowercase keywords' setting in the Options menu. I strongly discourage using this setting, because it introduces a major incompatibility with other versions of BBC BASIC and severely reduces the choice of variable names that you can use. It's provided only to placate users of other dialects of BASIC who have got used to using lowercase keywords and have then migrated to BBC BASIC.
Last edited by Richard Russell on Thu Apr 18, 2019 6:20 pm, edited 1 time in total.

User avatar
lurkio
Posts: 1974
Joined: Tue Apr 09, 2013 11:30 pm
Location: Doomawangara
Contact:

Re: Generating mazes (BBC BASIC)

Post by lurkio » Thu Apr 18, 2019 6:18 pm

Richard Russell wrote:
Thu Apr 18, 2019 5:58 pm
lurkio wrote:
Thu Apr 18, 2019 5:13 pm
I also had to change the "cell%" in PROCprint to "cell%%"
A better solution would have been to change cell%?grid%% to grid%%?cell%. The syntax of the diadic indirection operators is usually represented as address?offset or address!offset, not the other way around.
It was line 840 that was causing the issue. It doesn't contain any indirection operators.

Richard Russell wrote:
Thu Apr 18, 2019 5:58 pm
the names of the variables "nextI%" and "next%" had to be changed because they began with the reserved word "next".
"next" isn't a reserved word, but "NEXT" is. There should have been no need to make that change, unless you enabled the 'Lowercase keywords' setting in the Options menu.
The "Lowercase keywords" setting is enabled in my copy of BBC BASIC For SDL 2.0 (MacOS version 1.02a), but I have no memory of enabling it! It's not something I would have done deliberately or intentionally because I don't like lowercase keywords in BBC BASIC and I do remember wondering, in the past, why BBC BASIC For SDL (MacOS version) was using them!

:!:

User avatar
Richard Russell
Posts: 699
Joined: Sun Feb 27, 2011 10:35 am
Location: Downham Market, Norfolk
Contact:

Re: Generating mazes (BBC BASIC)

Post by Richard Russell » Thu Apr 18, 2019 6:24 pm

lurkio wrote:
Thu Apr 18, 2019 6:18 pm
It was line 840 that was causing the issue. It doesn't contain any indirection operators.
OK, the original program is using cell% for two quite different purposes, which is poor practice. I've edited my reply.
The "Lowercase keywords" setting is enabled in my copy of BBC BASIC For SDL 2.0 (MacOS version 1.02a), but I have no memory of enabling it!
It's disabled by default:

Code: Select all

      Lowercase% = FALSE
I'd certainly notice if it was ever enabled without me having explicitly done so!

User avatar
flaxcottage
Posts: 3518
Joined: Thu Dec 13, 2012 8:46 pm
Location: Derbyshire
Contact:

Re: Generating mazes (BBC BASIC)

Post by flaxcottage » Thu Apr 18, 2019 9:03 pm

At the risk of annoying 'BBC purists' I actually like the lower case keyword facility.

This comes from using BBCB4W on IBM-PC-compatibles in an educational environment where most of the languages we used had a lower case syntax - Python (Yuk!), VB, C, Java, Pascal, etc.

The ability to switch to uppercase and add line numbers was a great boon when transferring code to Acorn and Raspberry Pi systems.

Capital letters were also used for constants and global variables by some of our programmers and so lower case keywords made these variables stand out.
- John

Image

User avatar
Richard Russell
Posts: 699
Joined: Sun Feb 27, 2011 10:35 am
Location: Downham Market, Norfolk
Contact:

Re: Generating mazes (BBC BASIC)

Post by Richard Russell » Thu Apr 18, 2019 10:15 pm

flaxcottage wrote:
Thu Apr 18, 2019 9:03 pm
most of the languages we used had a lower case syntax - Python (Yuk!), VB, C, Java, Pascal, etc.
Yes, but I'm willing to bet that most, if not all, of those languages also require a keyword to be delimited by whitespace. For example in most BASICs PRINT is a keyword, but PRINTER is a legitimate variable name.

BBC BASIC is different: in many cases it will recognise and tokenise a keyword even if it is immediately followed by one or more alphabetic characters. So in BBC BASIC PRINTER is not usable as a variable name, because the PRINT part is still recognised as a keyword. This behaviour was of course designed to allow spaces after keywords to be omitted, and by that means make more efficient use of the limited memory in the BBC Micro.

This significantly limits the variable names you can choose, but it is mitigated by affecting only names starting with a keyword in all capitals. If you enable the Lowercase Keywords mode, not only is PRINTER not a valid variable name, but neither is printer. A significant number of 'useful' variable names become unusable, which I for one find really irritating.

Post Reply