Solving a Maze

johnno56 · Oct 10, 2023, 07:23 PM

Here is an interesting BBCBasic programme that I found, on Rosettacode.org, to generate and solve a small maze. I had to add a "WAIT" statement to "show" how the programme selects the "path".

I am not all that familiar with BBCBasic but I figured, for those that are "more gifted" than myself, could modify it to work with other "Basic-like" languages.

MazeWidth% = 11
MazeHeight% = 9
MazeCell% = 50

VDU 23,22,MazeWidth%*MazeCell%/2+3;MazeHeight%*MazeCell%/2+3;8,16,16,128
VDU 23,23,3;0;0;0; : REM Line thickness 
OFF

PROCgeneratemaze(Maze&(), MazeWidth%, MazeHeight%, MazeCell%)
PROCsolvemaze(Path{()}, Maze&(), 0, MazeHeight%-1, MazeWidth%-1, 0, MazeCell%)
END

DEF PROCsolvemaze(RETURN s{()}, m&(), x%, y%, dstx%, dsty%, s%)
LOCAL h%, i%, n%, p%, q%, w%
w% = DIM(m&(),1)
h% = DIM(m&(),2)
DIM s{(w%*h%) x%,y%}
GCOL 3,14
m&(x%,y%) OR= &80
REPEAT
  FOR i% = 0 TO 3
    CASE i% OF
      WHEN 0: p% = x%-1 : q% = y%
      WHEN 1: p% = x%+1 : q% = y%
      WHEN 2: p% = x% : q% = y%-1
      WHEN 3: p% = x% : q% = y%+1
    ENDCASE
    IF p% >= 0 IF p% < w% IF q% >= 0 IF q% < h% IF m&(p%,q%) < &80 THEN
      IF p% > x% IF m&(p%,q%) AND 1 EXIT FOR
      IF q% > y% IF m&(p%,q%) AND 2 EXIT FOR
      IF x% > p% IF m&(x%,y%) AND 1 EXIT FOR
      IF y% > q% IF m&(x%,y%) AND 2 EXIT FOR
    ENDIF
  NEXT
  IF i% < 4 THEN
    m&(p%,q%) OR= &80
    s{(n%)}.x% = x%
    s{(n%)}.y% = y%
    n% += 1
  ELSE
    IF n% > 0 THEN
      n% -= 1
      p% = s{(n%)}.x%
      q% = s{(n%)}.y%
    ENDIF
  ENDIF
  LINE (x%+0.5)*s%,(y%+0.5)*s%,(p%+0.5)*s%,(q%+0.5)*s%
  x% = p%
  y% = q%
  WAIT 25
UNTIL x%=dstx% AND y%=dsty%
s{(n%)}.x% = x%
s{(n%)}.y% = y%
ENDPROC

DEF PROCgeneratemaze(RETURN m&(), w%, h%, s%)
LOCAL x%, y%
DIM m&(w%, h%)
FOR y% = 0 TO h%
  LINE 0,y%*s%,w%*s%,y%*s%
NEXT
FOR x% = 0 TO w%
  LINE x%*s%,0,x%*s%,h%*s%
NEXT
GCOL 15
PROCcell(m&(), RND(w%)-1, y% = RND(h%)-1, w%, h%, s%)
ENDPROC

DEF PROCcell(m&(), x%, y%, w%, h%, s%)
LOCAL i%, p%, q%, r%
m&(x%,y%) OR= &40 : REM Mark visited
r% = RND(4)
FOR i% = r% TO r%+3
  CASE i% MOD 4 OF
    WHEN 0: p% = x%-1 : q% = y%
    WHEN 1: p% = x%+1 : q% = y%
    WHEN 2: p% = x% : q% = y%-1
    WHEN 3: p% = x% : q% = y%+1
  ENDCASE
  IF p% >= 0 IF p% < w% IF q% >= 0 IF q% < h% IF m&(p%,q%) < &40 THEN
    IF p% > x% m&(p%,q%) OR= 1 : LINE p%*s%,y%*s%+4,p%*s%,(y%+1)*s%-4
    IF q% > y% m&(p%,q%) OR= 2 : LINE x%*s%+4,q%*s%,(x%+1)*s%-4,q%*s%
    IF x% > p% m&(x%,y%) OR= 1 : LINE x%*s%,y%*s%+4,x%*s%,(y%+1)*s%-4
    IF y% > q% m&(x%,y%) OR= 2 : LINE x%*s%+4,y%*s%,(x%+1)*s%-4,y%*s%
    PROCcell(m&(), p%, q%, w%, h%, s%)
  ENDIF
NEXT
ENDPROC

CharlieJV · Oct 10, 2023, 07:55 PM

Quote from: johnno56 on Oct 10, 2023, 07:23 PMHere is an interesting BBCBasic programme that I found, on Rosettacode.org, to generate and solve a small maze. I had to add a "WAIT" statement to "show" how the programme selects the "path".

I am not all that familiar with BBCBasic but I figured, for those that are "more gifted" than myself, could modify it to work with other "Basic-like" languages.

MazeWidth% = 11
MazeHeight% = 9
MazeCell% = 50

VDU 23,22,MazeWidth%*MazeCell%/2+3;MazeHeight%*MazeCell%/2+3;8,16,16,128
VDU 23,23,3;0;0;0; : REM Line thickness 
OFF

PROCgeneratemaze(Maze&(), MazeWidth%, MazeHeight%, MazeCell%)
PROCsolvemaze(Path{()}, Maze&(), 0, MazeHeight%-1, MazeWidth%-1, 0, MazeCell%)
END

DEF PROCsolvemaze(RETURN s{()}, m&(), x%, y%, dstx%, dsty%, s%)
LOCAL h%, i%, n%, p%, q%, w%
w% = DIM(m&(),1)
h% = DIM(m&(),2)
DIM s{(w%*h%) x%,y%}
GCOL 3,14
m&(x%,y%) OR= &80
REPEAT
  FOR i% = 0 TO 3
    CASE i% OF
      WHEN 0: p% = x%-1 : q% = y%
      WHEN 1: p% = x%+1 : q% = y%
      WHEN 2: p% = x% : q% = y%-1
      WHEN 3: p% = x% : q% = y%+1
    ENDCASE
    IF p% >= 0 IF p% < w% IF q% >= 0 IF q% < h% IF m&(p%,q%) < &80 THEN
      IF p% > x% IF m&(p%,q%) AND 1 EXIT FOR
      IF q% > y% IF m&(p%,q%) AND 2 EXIT FOR
      IF x% > p% IF m&(x%,y%) AND 1 EXIT FOR
      IF y% > q% IF m&(x%,y%) AND 2 EXIT FOR
    ENDIF
  NEXT
  IF i% < 4 THEN
    m&(p%,q%) OR= &80
    s{(n%)}.x% = x%
    s{(n%)}.y% = y%
    n% += 1
  ELSE
    IF n% > 0 THEN
      n% -= 1
      p% = s{(n%)}.x%
      q% = s{(n%)}.y%
    ENDIF
  ENDIF
  LINE (x%+0.5)*s%,(y%+0.5)*s%,(p%+0.5)*s%,(q%+0.5)*s%
  x% = p%
  y% = q%
  WAIT 25
UNTIL x%=dstx% AND y%=dsty%
s{(n%)}.x% = x%
s{(n%)}.y% = y%
ENDPROC

DEF PROCgeneratemaze(RETURN m&(), w%, h%, s%)
LOCAL x%, y%
DIM m&(w%, h%)
FOR y% = 0 TO h%
  LINE 0,y%*s%,w%*s%,y%*s%
NEXT
FOR x% = 0 TO w%
  LINE x%*s%,0,x%*s%,h%*s%
NEXT
GCOL 15
PROCcell(m&(), RND(w%)-1, y% = RND(h%)-1, w%, h%, s%)
ENDPROC

DEF PROCcell(m&(), x%, y%, w%, h%, s%)
LOCAL i%, p%, q%, r%
m&(x%,y%) OR= &40 : REM Mark visited
r% = RND(4)
FOR i% = r% TO r%+3
  CASE i% MOD 4 OF
    WHEN 0: p% = x%-1 : q% = y%
    WHEN 1: p% = x%+1 : q% = y%
    WHEN 2: p% = x% : q% = y%-1
    WHEN 3: p% = x% : q% = y%+1
  ENDCASE
  IF p% >= 0 IF p% < w% IF q% >= 0 IF q% < h% IF m&(p%,q%) < &40 THEN
    IF p% > x% m&(p%,q%) OR= 1 : LINE p%*s%,y%*s%+4,p%*s%,(y%+1)*s%-4
    IF q% > y% m&(p%,q%) OR= 2 : LINE x%*s%+4,q%*s%,(x%+1)*s%-4,q%*s%
    IF x% > p% m&(x%,y%) OR= 1 : LINE x%*s%,y%*s%+4,x%*s%,(y%+1)*s%-4
    IF y% > q% m&(x%,y%) OR= 2 : LINE x%*s%+4,y%*s%,(x%+1)*s%-4,y%*s%
    PROCcell(m&(), p%, q%, w%, h%, s%)
  ENDIF
NEXT
ENDPROC

Nice! Gotta find some time to try porting that.

johnno56 · Oct 11, 2023, 01:35 AM

Not sure on how practical this program is, but it is certainly, interesting...

News:

Solving a Maze

johnno56

CharlieJV

johnno56