'Author     : Daniel, Master Sourcerer at Kitana's Castle
'Last change: May 25, 1999
'Email      : sourcerer@kitana.org


'Labyrinth array
DIM Z%(127,127)

'Stack for branches
DIM S%(2,99)

'Initialize random number generator
RANDOMIZE TIMER

'Zone elements
G%=&H0720  'corridor (black space character)
M%=&H07DB  'wall (light grey inversed space character)
Z%=&H0458  'exit (red X character)

'Size of labyrinth (must be no larger than dimensions of array Z%())
XGR%=80:YGR%=25

'Initialize labyrinth with walls
FOR J%=0 TO YGR%-1
  FOR I%=0 TO XGR%-1
    Z%(I%,J%)=M%
  NEXT I%
NEXT J%

'Start building labyrinth from its middle
X%=XGR%/2:Y%=YGR%/2:R%=RDM%(4)-1
S%(0,0)=X%:S%(1,0)=Y%:S%(2,0)=R%:S%=1  'store starting point on stack

'Create corridors as long as there are starting points on the stack
WHILE S%>0
  S%=S%-1
  X%=S%(0,S%):Y%=S%(1,S%):R%=S%(2,S%)  'read starting point and direction
  L%=RDM%(10)+2  'get random corridor length
  CALL GETDIR(E%,F%,R%)  'get x and y movement from direction
  FOR I%=1 TO L%
    X%=X%+E%:Y%=Y%+F%  'move 1 field in the current direction
    IF X%=0 OR X%=XGR%-1 OR Y%=0 OR Y%=YGR%-1 THEN EXIT FOR  'border reached
    IF Z%(X%+E%,Y%+F%)=G% AND RDM%(2)=1 THEN EXIT FOR  'do not cross another corridor (50% chance)
    IF Z%(X%+F%,Y%+E%)=G% OR Z%(X%-F%,Y%-E%)=G% THEN  'check for adjacting corridors
      EXIT FOR  'each corridor should be 1 field in width only
    END IF
    Z%(X%,Y%)=G%  'create corridor field here
    IF RDM%(4)=1 OR I%=L% THEN  'create random branch or at end of corridor
      S%(0,S%)=X%:S%(1,S%)=Y%:S%(2,S%)=(R%+1+(RDM%(2)=1)*2) AND 3
      S%=S%+1
    END IF
  NEXT I%
WEND

'Create exit
DO
  X%=RDM%(XGR%-2):Y%=RDM%(YGR%-2)  'get random position
  IF Z%(X%,Y%)=G% THEN  'exit must be on a corridor
    N%=0
    FOR I%=0 TO 3  'and 3 adjacent fields must be walls
      CALL GETDIR(E%,F%,I%)
      IF Z%(X%+E%,Y%+F%)=M% THEN N%=N%+1
    NEXT I%
    IF N%=3 THEN Z%(X%,Y%)=Z%  'found a suitable place
  END IF
LOOP UNTIL Z%(X%,Y%)=Z%

'Show labyrinth (directly poked to video ram)
CLS
DEF SEG=&HB800
FOR J%=0 TO MIN%(24,YGR%-1)
  FOR I%=0 TO MIN%(80,XGR%-1)
    POKEI I%*2+J%*160,Z%(I%,J%)
  NEXT I%
NEXT J%
END


'Returns a random number from 1 to A
'Input : A% = number of sides of the die
'Output: random number
FUNCTION RDM%(A%)
  RDM%=INT(RND*A%)+1
END FUNCTION


'Converts a direction to x and y movement
'Input : R% = direction (0=north, 1=east, 2=south, 3=west)
'Output: X% = x movement
'        Y% = y movement
SUB GETDIR(X%,Y%,R%)
  SELECT CASE R%
  CASE 0:X%=0:Y%=-1
  CASE 1:X%=1:Y%=0
  CASE 2:X%=0:Y%=1
  CASE 3:X%=-1:Y%=0
  END SELECT
END SUB