' WarSOFT Maze Generator v1
' by Jesse Warford
' (c) 2023 WarSOFT Apps
'
' This is version 1 that just creates an integer array in memory and displays
'  a maze on the screen. A future version may allow traversing the maze from
'  the inside using crude 3D
'
Option Explicit
Option Base 0
Option Default Integer
Randomize Timer
MODE 1      'will also work with mode 2 as-is with no other alterations

' general purpose
Dim i, n

' directions
Dim dx(3) = (0, 1, 0, -1), dy(3) = (-1, 0, 1, 0)

' screen resolution cut into cells
Dim csiz = 10, hsiz = 5                 '8x8px cell plus 1px border, half size
Dim hr = MM.HRes / csiz, vr = MM.VRes / csiz  '#cells horiz & vert

' def & init maze area
' ---------------------
' bits: 0 (001-01) - from dir lo bit
'       1 (002-02) - from dir hi bit
'       2 (004-04) - up     this cell is open going up
'       3 (008-08) - right  "
'       4 (016-10) - down   "
'       5 (032-20) - left   "
'       6 (064-40) - visited - already visited during maze generation
'       7 (128-80) - (reserved)
' --------------------
' mask    - const &hff or 255, used for clearing bits
' bs.fdir - the direction taken to get to this cell, ie. "from" dir
' bs()    - Bit Set (from) direction array
' bz()    - bit set (to) direction array
' br.fdir - used for clearing direction bit. not used yet...
' br()    - Bit Reset (or bit clear) direction array
' --------------------

Dim mask = &hff             'used for clearing bits, but not used yet...
' def bit SET vars - <OR>
Dim bs.fdir = &h03
Dim bs(3) = (&h04, &h08, &h10, &h20)
Dim bz(3) = (bs(2), bs(3), bs(0), bs(1))
Dim bs.visited = &h40
' def bit RESET vars - <AND>
Dim br.fdir = mask - bs.fdir
Dim br(3) = (mask - bs(0), mask - bs(1), mask - bs(2), mask - bs(3))
Dim br.visited = mask - bs.visited

Dim maze(hr, vr)
For i = 0 To hr - 1
 For n = 0 To vr - 1
   maze(i, n) = 0  'init all cells as unvisited and untested
 Next n
Next i

' maze generation init
Dim sx = Fix(Rnd * hr), sy = Fix(Rnd * vr)  'starting position
Dim x = sx, y = sy                          'set current position
Dim nx, ny                                  'new position to test
Dim d, od, dd                               'current and old direction
maze(x, y) = bs.visited                     'set starting cell as visited
Box x * csiz, y * csiz, csiz, csiz          'draw starting cell empty

' test border cells of current cell for unvisited
Do
 d = Fix(Rnd * 4)                          'choose random direction
 od = d                                    'remember starting dir
 dd = Fix(Rnd * 2)                         'dd = test dir: clockwise
 If dd = 0 Then dd = -1                    ' or counter-clockwise
 Do
   nx = x + dx(d)                          'new cell coords based on
   ny = y + dy(d)                          ' current direction
   If nx >= 0 And nx < hr And ny >= 0 And ny < vr Then   'ck for out of bounds
     If (maze(nx, ny) And bs.visited) = 0 Then 'ck visited flag
       maze(x, y) = maze(x, y) Or bs(d)        'set move to dir in from cell
       x = nx:y = ny                           'update current pos
       maze(x, y) = maze(x, y) Or d            'set dir used to get here
       maze(x, y) = maze(x, y) Or bz(d)        'set move from dir in to cell
       maze(x, y) = maze(x, y) Or bs.visited   'set visited flag
       Box x * csiz, y * csiz, csiz, csiz      'draw current cell empty
       d = -1                                  'so backup doesn't trip
       Exit                                    'exit test new dir loop
     EndIf
   EndIf
   d = d + dd            'if the last test dir cell was visited, try next dir
   If d = 4 Then         'increment or decrement direction
     d = 0               'using round-robin
   ElseIf d = -1 Then    'try both clockwise and counter-clockwise to keep
     d = 3               ' the maze from always drawing around the edge
   EndIf
 Loop Until d = od       'keep going till all directions have been tried

 If d = od Then          'if all are visited, it's a dead end, so backup
   d = maze(x, y) And bs.fdir          'get direction to go backwards (from)
   x = x - dx(d):y = y - dy(d)         'set new cell coords w/new dir's
   nx = x * csiz + hsiz * dx(d) + 1        'erase breadcrumb by drawing an
   ny = y * csiz + hsiz * dy(d) + 1        ' empty box w/no borders, erasing
   Box nx, ny, csiz - 2, csiz - 2, 1, 0, 0 ' the cells merged borders
 EndIf
Loop Until x = sx And y = sy                      'keep going and backing up
                                                 ' till returned to start
Dim a$
Do While a$=""
 a$=Inkey$
Loop
Run