_TITLE "PathFinder 2, prepping maze as you read this."
'started 2018-08-11 when Colbalt asked about A* pathfinder
' He has now 2018-08-12 posted a QB64 version that is nice!
' 2018-08-11 started PathFinder 1
' 2018-08-12 almost working but buggy backtract to point A after point B is found.
' 2018-08-13 PathFinder 1a.bas I think I have a fix for buggy path BackTrack but major surgery so this new version
' 2018-08-14 Pathfinder 2: 2 parts
' Part 1: creates a map, a random Home point and backtracts all the points available to move over.
' Part 2: allows clicking variaous points of map to see if path is found.
' 2019-12-19 add Maze Generator code that converts 2 arrays for walls and ceilings to a map for PathFinder 2
'generator
DIM y
, x
, parentF
, tick
, parentx
, changes$
, ystart
, ystop
, xStart
, xStop
, xxStart
, xxStop
, yyStart
, yyStop
, cf
, xx
, yy
DIM new$
, newxy$
, newParent$
, u
, v
, mx
, my
, ps$
, parenty
'this part sets up a sample map and get's the Backtracking build into map
FOR y
= 1 TO maph
'clear and initialize map map(x, y) = " "
'maze generator
init_walls
generate_maze
fillMap 'convert walls to map and outline borders
ax = 2 * W: ay = 2 * H ' here is the target, a for anchor that all paths must go
map(ax, ay) = "A"
parentF = 1: tick = 0: parentx = 0
parentF = 0: tick = tick + 1: changes$ = ""
ystart = max(ay - tick, 1): ystop = min(ay + tick, maph)
xStart = max(ax - tick, 1): xStop = min(ax + tick, mapw)
'check out the neighbors
IF x
- 1 >= 1 THEN xxStart
= x
- 1 ELSE xxStart
= x
IF x
+ 1 <= mapw
THEN xxStop
= x
+ 1 ELSE xxStop
= x
IF y
- 1 >= 1 THEN yyStart
= y
- 1 ELSE yyStart
= y
IF y
+ 1 <= maph
THEN yyStop
= y
+ 1 ELSE yyStop
= y
cf = 0
FOR yy
= yyStart
TO yyStop
FOR xx
= xxStart
TO xxStop
parentF = 1 'so will continue looping
'update map with cells assigned parents
new$ = leftOf$(changes$, "}")
changes$ = rightOf$(changes$, "}")
newxy$ = leftOf$(new$, "{")
newParent$ = rightOf$(new$, "{")
u
= VAL(leftOf$
(newxy$
, ",")): v
= VAL(rightOf$
(newxy$
, ",")) map(u, v) = leftOf$(newParent$, ",") + "," + rightOf$(newParent$, ",")
'this parts displays the ability to find a path to blue square anywhere in the maze
_TITLE "Click maze to find a path to blue square (if any), c = clear, n = new map, esc = quit" displayM
bx = mx / sq + 1: by = my / sq + 1
LINE ((bx
- 1) * sq
+ 2, (by
- 1) * sq
+ 2)-STEP(sq
- 4, sq
- 4), &HFFFFFF000, BF
ps$ = map(bx, by)
parentx
= VAL(leftOf$
(ps$
, ",")) parenty
= VAL(rightOf$
(ps$
, ",")) IF parentx
THEN 'backtrack to A note: B could be right next to A!!! LINE ((parentx
- 1) * sq
+ 3, (parenty
- 1) * sq
+ 3)-STEP(sq
- 6, sq
- 6), &HFFFFFFFF, BF
WHILE parentx
'trace the path back ps$ = map(parentx, parenty)
parentx
= VAL(leftOf$
(ps$
, ",")) parenty
= VAL(rightOf$
(ps$
, ",")) LINE ((parentx
- 1) * sq
+ 3, (parenty
- 1) * sq
+ 3)-STEP(sq
- 6, sq
- 6), &HFFFFFFFF, BF
displayM
CASE "A": k
= &HFF0000FF 'target CASE "B": k
= &HFFFFBB00 'border CASE "O": k
= &HFF008800 'maze wall LINE ((x
- 1) * sq
, (y
- 1) * sq
)-STEP(sq
, sq
), k
, BF
rand%
= INT(RND * (hi%
- lo%
+ 1)) + lo%
posOf
= INSTR(source$
, of$
) IF posOf
> 0 THEN leftOf$
= MID$(source$
, 1, posOf
- 1)
posOf
= INSTR(source$
, of$
)
v_walls(x, y) = 1
h_walls(x, y) = 1
'this takes the generted maze and loads the Map string array
map(2 * x + 1, 2 * y + 1) = "O": map(2 * x + 2, 2 * y + 1) = "O": map(2 * x + 3, 2 * y + 1) = "O"
map(2 * x + 1, 2 * y + 1) = "O": map(2 * x + 1, 2 * y + 2) = "O": map(2 * x + 1, 2 * y + 3) = "O"
map(2 * x + 1, 1) = "B": map(2 * x + 2, 1) = "B": map(2 * x + 3, 1) = "B"
map(2 * x + 1, 2 * H + 1) = "B": map(2 * x + 2, 2 * H + 1) = "B": map(2 * x + 3, 2 * H + 1) = "B"
map(1, 2 * y + 1) = "B": map(1, 2 * y + 2) = "B": map(1, 2 * y + 3) = "B"
map(2 * W + 1, 2 * y + 1) = "B": map(2 * W + 1, 2 * y + 2) = "B": map(2 * W + 1, 2 * y + 3) = "B"
' Maze Generator Code
'
' 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.
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
