_TITLE "Maze Generator to test Paint or Fills, press any to awaken from SLEEP, esc to quit" 'B+ '2019-11-23 using Maze Generator to test Steve's nice fill routine posted 2019-11-23
' 2019-09-02 isolated and updated generator code for OPTION _EXPLICIT
' from trans 2018-06-15 for Amazing Rat.bas (QB64)
' From SmallBASIC code written by Chris WS developer
' Backtracking maze generator by chrisws 2016-06-30 now found at
' https://github.com/smallbasic/smallbasic.github.io/blob/5601c8bc1d794c5b143d863555bb7c15a5966a3c/samples/node/1623.bas
'
' Chris notes:
' https://en.wikipedia.org/wiki/Maze_generation_algorithm
' - Starting from a random cell,
' - Selects a random neighbouring cell that has not been visited.
' - Remove the wall between the two cells and marks the new cell as visited,
' and adds it to the stack to facilitate backtracking.
' - Continues with a cell that has no unvisited neighbours being considered a dead-end.
' When at a dead-end it backtracks through the path until it reaches a cell with an
' unvisited neighbour, continuing the path generation by visiting this new,
' unvisited cell (creating a new junction).
' This process continues until every cell has been visited, backtracking all the
' way back to the beginning cell. We can be sure every cell is visited.
'
'B+ notes for using:
' The most important item is that the maze uses 2 arrays one for vertical walls the other for horizontal
' CONST xmax, ymax is pixel size used in maze coder, using SW, SH for screen dimensions
' Maze should mount in top left corner of screen with min border space around it at left and top at least.
' CONST W, H - number of cells Wide and High you can specify.
' CONST wallThk - adjusts thickness of walls
' CONST mazeClr - colors walls made with BF in LINE statement
' CONST border - will create a space around the maze
' SHARED cellW, cellH - are pixels sizes for cell, see calcs before SCREEN command
' SHARED h_walls(W, H) AS INTEGER, v_walls(W, H) AS INTEGER - these are your Maze, 0 no wall, 1 = wall
' When player occupies cell x, y that cell may v_wall that blocks player going left;
' a cell v_wall(x+1, y) = 1 will block a player going right;
' cell (x, y) may have an h_wall that stops player from going up;
' cell (x, y+1) may have h_wall that stops player at x, y from going down.
' Cells at (W, y) should not be occupied with W cells wide and array base 0 only W-1 can be occupied
' unless game needs something special.
' Likewise cells at (x, H) should only provide wall to stop player from going out of box.
CONST xmax
= 801, ymax
= 601, SW
= 801, SH
= 601 'maze pixels from 0,0 and screen SH, SW CONST W
= 200, H
= 150, border
= 0, wallThk
= 1 'maze cells wide and high CONST mazeClr
= &HFFFF8800
cellW = (xmax - 2 * border - wallThk) / W
cellH = (ymax - 2 * border - wallThk) / H
LINE (0, 0)-(xmax
, ymax
), &HFF000000, BF
init_walls
generate_maze
show_maze
'PSET (border + 0 * cellW + wallThk + 1, border + 0 * cellH + wallThk + 1), &HFFFFFFFF 'ok looks right
'first test with normal PAINT
'PAINT (border + 0 * cellW + wallThk + 1, border + 0 * cellH + wallThk + 1), &HFFFFFFFF, mazeClr
fill border + 0 * cellW + wallThk + 1, border + 0 * cellH + wallThk + 1, &HFFFFFFFF, &HFFFF8800
v_walls(x, y) = 1
h_walls(x, y) = 1
py = border
px = border
LINE (px
, py
)-STEP(cellW
+ wallThk
, wallThk
), mazeClr
, BF
LINE (px
, py
)-STEP(wallThk
, cellH
+ wallThk
), mazeClr
, BF
px = px + cellW
py = py + cellH
x = current.x
y = current.y
uvi = 0
uvi = uvi + 1
unvisited(uvi).x = x - 1
unvisited(uvi).y = y
uvi = uvi + 1
unvisited(uvi).x = x + 1
unvisited(uvi).y = y
uvi = uvi + 1
unvisited(uvi).x = x
unvisited(uvi).y = y - 1
uvi = uvi + 1
unvisited(uvi).x = x
unvisited(uvi).y = y + 1
DIM curr_cell
AS cell
, next_cell
AS cell
, cur_cell
AS cell
rand_cell cur_cell.x, cur_cell.y
visited(curr_cell.x, curr_cell.y) = 1
num_visited = 1
num_cells = W * H
si = 0
WHILE num_visited
< num_cells
cnt = 0
get_unvisited visited(), curr_cell, cells(), cnt
' choose randomly one of the current cell's unvisited neighbours
next_cell.x = cells(rc).x
next_cell.y = cells(rc).y
' push the current cell to the stack
si = si + 1
stack(si).x = curr_cell.x
stack(si).y = curr_cell.y
' remove the wall between the current cell and the chosen cell
IF next_cell.x
= curr_cell.x
THEN x = next_cell.x
y = max(next_cell.y, curr_cell.y)
h_walls(x, y) = 0
x = max(next_cell.x, curr_cell.x)
y = next_cell.y
v_walls(x, y) = 0
' make the chosen cell the current cell and mark it as visited
curr_cell.x = next_cell.x
curr_cell.y = next_cell.y
visited(curr_cell.x, curr_cell.y) = 1
num_visited = num_visited + 1
' pop a cell from the stack and make it the current cell
curr_cell.x = stack(si).x
curr_cell.y = stack(si).y
si = si - 1
'''$CHECKING:OFF ' <<<<<<<<<<<<<<<<< B+ mod
x = tx: y = ty
DIM Array
(fillW
, fillH
) 'AS INTEGER DIM S
(fillW
, fillH
) 'AS INTEGER IF _MEMGET(M
, M.OFFSET
+ (y1
* fillW
+ x1
) * 4, _UNSIGNED LONG) = bordercolor
THEN S
(x1
, y1
) = -1 'MRM replacement for point below 'IF POINT(x1, y1) = bordercolor THEN S(x1, y1) = -1 'This is actually Sneaky Steve Logic at its best!
'Here we're checking to see if our array matches the proper border color or not.
'If it doesn't, then it might be a spot to fill (which is 0 -- the same as our inital Array()).
MinX = x: MinY = y
MaxX = x: MaxY = y
Array
(x
, y
) = 1:
LINE (x
, y
)-STEP(0, 0), kolor
, BF
' <<<<<<<<<<<<<<<<< B+ mod pass = 1
finished = -1
np = pass + 1 'next pass
TMX = MinX: TMX2 = MaxX
TMY = MinY: TMY2 = MaxY
fill_left:
IF Array
(x
- 1, y
) = S
(x
- 1, y
) THEN Array(x - 1, y) = np
finished
= 0:
LINE (x
, y
)-STEP(0, 0), kolor
, BF
' <<<<<<<<<<<<<<<<< B+ mod x = x - 1
fill_right:
IF Array
(x
+ 1, y
) = S
(x
+ 1, y
) THEN Array(x + 1, y) = np
finished
= 0::
LINE (x
, y
)-STEP(0, 0), kolor
, BF
' <<<<<<<<<<<<<<<<< B+ mod x = x + 1
fill_up:
IF Array
(x
, y
- 1) = S
(x
, y
- 1) THEN Array(x, y - 1) = np
finished
= 0::
LINE (x
, y
)-STEP(0, 0), kolor
, BF
' <<<<<<<<<<<<<<<<< B+ mod y = y - 1
fill_down:
IF Array
(x
, y
+ 1) = S
(x
, y
+ 1) THEN Array(x, y + 1) = np
finished
= 0::
LINE (x
, y
)-STEP(0, 0), kolor
, BF
' <<<<<<<<<<<<<<<<< B+ mod y = y + 1
pass = pass + 1
IF Array
(x
, y
) THEN 'PSET (x, y), kolor IF left
THEN LINE (left
, y
)-(x
- 1, y
), kolor
, BF: left
= 0 IF left
THEN LINE (left
, y
)-(x
- 1, y
), kolor
, BF: left
= 0 '''$CHECKING:ON '<<<<<<<<<<<<<<<<< B+ mod