« previous next »
Pages: [1]   Go Down

Author Topic: Recursively maze creation  (Read 4134 times)

0 Members and 1 Guest are viewing this topic.

Offline MasterGy

  • Seasoned Forum Regular
  • Posts: 327
  • people lie, math never lies
    • View Profile
Recursively maze creation
« on: June 21, 2020, 03:26:37 pm »
Hi !

I was looking at maze solutions lately.
He started to get interested and I wanted something that has a beginning and an end and can only be walked through in 1 way.

The algorithm was not invented by me, I found it online, its name is recursively maze creation.

Code: QB64: [Select]
  2.  
  3. maze_x = 50 'maze size X
  4. maze_y = 25 'maze size Y
  5.  
  6. 'preparation -------------------------------------------------------------------------------------------------------------------------------------------
  7. IF maze_x / 2 = INT(maze_x / 2) THEN maze_x = maze_x + 1
  8. IF maze_y / 2 = INT(maze_y / 2) THEN maze_y = maze_y + 1
  9. monx = (maze_x + 10) * 8: mony = (maze_y + 5) * 16: kep = _NEWIMAGE(monx, mony, 32): SCREEN kep
  10. d(0, 0) = 0: d(0, 1) = -1: d(1, 0) = 0: d(1, 1) = 1: d(2, 0) = -1: d(2, 1) = 0: d(3, 0) = 1: d(3, 1) = 0
  11. k$(0) = "±" 'fal / adjustable wall
  12. k$(1) = " " 'nem bejart ureg / non walked road
  13. k$(2) = "W" 'lehetoseg / possible way
  14. k$(3) = "Ű" 'szilard fal / standard wall
  15. k$(4) = "." 'bejart ureg  / walked road
  16. k$(5) = "." 'belepesi pont  / entry point
  17. DIM maze(maze_x - 1, maze_y - 1) AS _BYTE '0-fal 1-ureg 2-lehetoseg
  18.  
  19.  
  20. 'create empty maze --------------------------------------------------------------------------------------------------------------------------------------
  21. FOR tx = 0 TO maze_x - 1: FOR ty = 0 TO maze_y - 1: k = 0
  22.         IF tx = 0 OR ty = 0 OR tx = maze_x - 1 OR ty = maze_y - 1 THEN k = 3
  23.         IF tx AND 1 AND ty AND 1 THEN k = 1
  24. maze(tx, ty) = k: NEXT ty, tx
  25.  
  26. 'start position -----------------------------------------------------------------------------------------------------------------------------------------
  27. DO: sx = INT(maze_x * RND(1)): sy = INT(maze_y * RND(1)): LOOP WHILE maze(sx, sy) <> 1: maze(sx, sy) = 4
  28.  
  29.  
  30. 'way searching ------------------------------------------------------------------------------------------------------------------------------------------
  31. DO: REDIM way(9999, 2): wdb = 0
  32.     FOR tx = 0 TO maze_x - 1: FOR ty = 0 TO maze_y - 1
  33.             IF maze(tx, ty) = 4 THEN
  34.                 van = 0
  35.                 FOR t = 0 TO 3
  36.                     vpx1 = tx + d(t, 0): vpy1 = ty + d(t, 1): vpx2 = tx + d(t, 0) * 2: vpy2 = ty + d(t, 1) * 2
  37.                     f = (vpx2 > maze_x - 1 OR vpx2 < 0) OR (vpy2 > maze_y - 1 OR vpy2 < 0)
  38.                     IF NOT f THEN
  39.                         IF maze(vpx1, vpy1) = 0 AND maze(vpx2, vpy2) = 1 THEN
  40.                             FOR t2 = 0 TO 3: vpx3 = vpx2 + d(t2, 0): vpy3 = vpy2 + d(t2, 1): IF maze(vpx3, vpy3) = 4 THEN GOTO kovi
  41.                             NEXT t2
  42.                             maze(vpx1, vpy1) = 2: way(wdb, 0) = tx: way(wdb, 1) = ty: way(wdb, 2) = t: wdb = wdb + 1
  43.                             kovi:
  44.                         END IF
  45.                     END IF
  46.                 NEXT t
  47.             END IF
  48.     NEXT ty, tx
  49.  
  50.     IF wdb THEN
  51.         aw = INT(wdb * RND(1))
  52.         FOR t = 0 TO 2
  53.             hovax = way(aw, 0) + d(way(aw, 2), 0) * t: hovay = way(aw, 1) + d(way(aw, 2), 1) * t
  54.             IF (maze(hovax, hovay) = 2) OR (maze(hovax, hovay) = 1) THEN maze(hovax, hovay) = 4
  55.         NEXT t
  56.  
  57.         FOR tx = 0 TO maze_x - 1: FOR ty = 0 TO maze_y - 1: IF maze(tx, ty) = 2 THEN maze(tx, ty) = 0
  58.         NEXT ty, tx
  59.     END IF
  60.  
  62.  
  63. 'entry point 1
  64. sx = 0: sy = 3: IF maze(sx + 1, sy) <> 4 THEN sy = sy + 1
  65. maze(sx, sy) = 4
  66.  
  67. 'entry point 2
  68. sx = maze_x - 1: sy = maze_y - 3: IF maze(sx - 1, sy) <> 4 THEN sy = sy - 1
  69. maze(sx, sy) = 4
  70.  
  71. ' it has taken so far to build the maze. contained in the maze array ------------------------------------------------------------------------------------------------
  72.  
  73. 'drawing
  74. sy = INT((mony / 16 - maze_y) / 2) + 1: sx = INT((monx / 8 - maze_x) / 2) + 1
  75. FOR tx = 0 TO maze_x - 1: FOR ty = 0 TO maze_y - 1: LOCATE sy + ty, sx + tx: PRINT k$(maze(tx, ty)): NEXT ty, tx
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  [attachment=1]
Logged

Offline MasterGy

  • Seasoned Forum Regular
  • Posts: 327
  • people lie, math never lies
    • View Profile
Re: Recursively maze creation
« Reply #1 on: June 21, 2020, 05:24:10 pm »
I made a mini-game out of it in my boredom

Code: QB64: [Select]
  2. settings$ = "maze.set": GOSUB re
  3.  
  4. 'preparation -------------------------------------------------------------------------------------------------------------------------------------------
  5. IF maze_x / 2 = INT(maze_x / 2) THEN maze_x = maze_x + 1
  6. IF maze_y / 2 = INT(maze_y / 2) THEN maze_y = maze_y + 1
  7. monx = (maze_x + 10) * 8: mony = (maze_y + 9) * 16: kep = _NEWIMAGE(monx, mony, 32): SCREEN kep
  8. d(0, 0) = 0: d(0, 1) = -1: d(1, 0) = 0: d(1, 1) = 1: d(2, 0) = -1: d(2, 1) = 0: d(3, 0) = 1: d(3, 1) = 0
  9. k$(0) = "±" 'fal / adjustable wall
  10. k$(1) = " " 'nem bejart ureg / non walked road
  11. k$(2) = "W" 'lehetoseg / possible way
  12. k$(3) = "Ű" 'szilard fal / standard wall
  13. k$(4) = " " 'bejart ureg  / walked road
  14. k$(5) = " " 'belepesi pont  / entry point
  15. k$(6) = "X" 'enemies
  16. k$(7) = "<" 'me left
  17. k$(8) = ">" 'me right
  18. mea = 8
  19. DIM maze(maze_x - 1, maze_y - 1) AS _BYTE '0-fal 1-ureg 2-lehetoseg
  20. DIM en(enemies - 1, 2) '0-x 1-y 2-vector (d-array)
  21.  
  22. 'create empty maze --------------------------------------------------------------------------------------------------------------------------------------
  23. FOR tx = 0 TO maze_x - 1: FOR ty = 0 TO maze_y - 1: k = 0
  24.         IF tx = 0 OR ty = 0 OR tx = maze_x - 1 OR ty = maze_y - 1 THEN k = 3
  25.         IF tx AND 1 AND ty AND 1 THEN k = 1
  26. maze(tx, ty) = k: NEXT ty, tx
  27.  
  28. 'start position -----------------------------------------------------------------------------------------------------------------------------------------
  29. DO: sx = INT(maze_x * RND(1)): sy = INT(maze_y * RND(1)): LOOP WHILE maze(sx, sy) <> 1: maze(sx, sy) = 4
  30.  
  31.  
  32. 'way searching ------------------------------------------------------------------------------------------------------------------------------------------
  33. DO: REDIM way(9999, 2): wdb = 0
  34.     FOR tx = 0 TO maze_x - 1: FOR ty = 0 TO maze_y - 1
  35.             IF maze(tx, ty) = 4 THEN
  36.                 van = 0
  37.                 FOR t = 0 TO 3
  38.                     vpx1 = tx + d(t, 0): vpy1 = ty + d(t, 1): vpx2 = tx + d(t, 0) * 2: vpy2 = ty + d(t, 1) * 2
  39.                     f = (vpx2 > maze_x - 1 OR vpx2 < 0) OR (vpy2 > maze_y - 1 OR vpy2 < 0)
  40.                     IF NOT f THEN
  41.                         IF maze(vpx1, vpy1) = 0 AND maze(vpx2, vpy2) = 1 THEN
  42.                             FOR t2 = 0 TO 3: vpx3 = vpx2 + d(t2, 0): vpy3 = vpy2 + d(t2, 1): IF maze(vpx3, vpy3) = 4 THEN GOTO kovi
  43.                             NEXT t2
  44.                             maze(vpx1, vpy1) = 2: way(wdb, 0) = tx: way(wdb, 1) = ty: way(wdb, 2) = t: wdb = wdb + 1
  45.                             kovi:
  46.                         END IF
  47.                     END IF
  48.                 NEXT t
  49.             END IF
  50.     NEXT ty, tx
  51.  
  52.     IF wdb THEN
  53.         aw = INT(wdb * RND(1))
  54.         FOR t = 0 TO 2
  55.             hovax = way(aw, 0) + d(way(aw, 2), 0) * t: hovay = way(aw, 1) + d(way(aw, 2), 1) * t
  56.             IF (maze(hovax, hovay) = 2) OR (maze(hovax, hovay) = 1) THEN maze(hovax, hovay) = 4
  57.         NEXT t
  58.  
  59.         FOR tx = 0 TO maze_x - 1: FOR ty = 0 TO maze_y - 1: IF maze(tx, ty) = 2 THEN maze(tx, ty) = 0
  60.         NEXT ty, tx
  61.     END IF
  62.  
  64. 'entry point 1
  65. sx = 0: sy = 3: IF maze(sx + 1, sy) <> 4 THEN sy = sy + 1
  66. maze(sx, sy) = 5
  67. mex = sx: mey = sy 'my start position
  68.  
  69.  
  70. 'entry point 2
  71. sx = maze_x - 1: sy = maze_y - 3: IF maze(sx - 1, sy) <> 4 THEN sy = sy - 1
  72. maze(sx, sy) = 5
  73. endx = sx: endy = sy
  74.  
  75. ' it has taken so far to build the maze. contained in the maze array ------------------------------------------------------------------------------------------------
  76.  
  77. 'create enemies
  78. FOR t = 0 TO enemies - 1: DO: sx = INT(maze_x * RND(1)): sy = INT(maze_y * RND(1)): LOOP WHILE maze(sx, sy) <> 4
  79. en(t, 0) = sx: en(t, 1) = sy: en(t, 2) = INT(4 * RND(1)): maze(sx, sy) = 6: NEXT t
  80.  
  81.  
  82. DO: _LIMIT speed
  83.     'inkey-commands
  85.     CASE "n": RUN: CASE "r": KILL settings$: RUN
  86.     CASE "a": maze_x = maze_x - 2: GOTO wr: CASE "s": maze_x = maze_x + 2: GOTO wr
  87.     CASE "y": maze_y = maze_y - 2: GOTO wr: CASE "x": maze_y = maze_y + 2: GOTO wr
  88.     CASE "q": enemies = enemies - 1: GOTO wr: CASE "w": enemies = enemies + 1: GOTO wr
  89.     CASE "-": speed = speed - 1: GOTO wr: CASE "+": speed = speed + 1: GOTO wr
  90.     END SELECT
  91.  
  92.     'moving enemies
  93.     FOR t = 0 TO enemies - 1
  94.        10: IF uj THEN en(t, 2) = INT(4 * RND(1))
  95.         vpx = en(t, 0) + d(en(t, 2), 0): vpy = en(t, 1) + d(en(t, 2), 1): f1 = (vpx > maze_x - 2 OR vpx < 1) OR (vpy > maze_y - 2 OR vpy < 1)
  96.         IF f1 THEN uj = 1: GOTO 10
  97.         f2 = (maze(vpx, vpy) = 0 OR maze(vpx, vpy) = 3) OR INT(5 * RND(1)) = 0
  98.         'f2 = (maze(vpx, vpy) <> 4) AND (maze(vpx, vpy) <> 6)
  99.         IF f2 THEN uj = 1: GOTO 10
  100.         maze(en(t, 0), en(t, 1)) = 4: en(t, 0) = en(t, 0) + d(en(t, 2), 0): en(t, 1) = en(t, 1) + d(en(t, 2), 1): maze(en(t, 0), en(t, 1)) = 6
  101.     NEXT t
  102.     GOSUB death
  103.     'moving me
  104.     t = 4 't is my array vector
  105.     IF _KEYDOWN(CVI(CHR$(0) + "P")) THEN t = 1 '_KEYDOWN(20480)
  106.     IF _KEYDOWN(CVI(CHR$(0) + "H")) THEN t = 0 '_KEYDOWN(18432)
  107.     IF _KEYDOWN(CVI(CHR$(0) + "K")) THEN t = 2: mea = 7 '_KEYDOWN(19200)
  108.     IF _KEYDOWN(CVI(CHR$(0) + "M")) THEN t = 3: mea = 8 '_KEYDOWN(19712)
  109.  
  110.     vpx = mex + d(t, 0): vpy = mey + d(t, 1)
  111.     IF (vpx > maze_x - 1 OR vpx < 0) OR (vpy > maze_y - 1 OR vpy < 0) THEN GOTO 12
  112.     IF maze(vpx, vpy) = 0 OR (maze(vpx, vpy) = 3) THEN GOTO 12
  113.     maze(mex, mey) = 4: mex = mex + d(t, 0): mey = mey + d(t, 1): maze(mex, mey) = mea
  114.    12:
  115.  
  116.     GOSUB drawing
  117.     IF mex = endx AND mey = endy THEN LOCATE 10, 5: PRINT "YOU WIN !": _DISPLAY: END
  118.     GOSUB death
  119.  
  121.  
  122.  
  123. drawing: 'drawing
  124. sx = INT((monx / 8 - maze_x) / 2) + 1: sy = 2
  125. FOR tx = 0 TO maze_x - 1: FOR ty = 0 TO maze_y - 1: LOCATE sy + ty, sx + tx: PRINT k$(maze(tx, ty)): NEXT ty, tx
  126. LOCATE 1, 1: PRINT " Go through the maze !"
  127. LOCATE maze_y + sy, 1
  128. PRINT "N   - new track": PRINT "Q/W - pieces of enemies"; enemies: PRINT "A/S - maze X"; maze_x
  129. PRINT "Y/X - maze Y"; maze_y: PRINT "+/- - speed"; speed: PRINT "R   - reset settings"
  131.  
  132. death: FOR t = 0 TO enemies - 1: IF en(t, 0) = mex AND en(t, 1) = mey THEN LOCATE 10, 5: PRINT "YOU DEATH !": _DISPLAY: END
  134.  
  135. wr:
  136. IF maze_x < 17 THEN maze_x = 17
  137. IF maze_y < 5 THEN maze_y = 5
  138. IF enemies < 0 THEN enemies = 0
  139. IF speed < 5 THEN speed = 5
  140. OPEN settings$ FOR OUTPUT AS 1: PRINT #1, maze_x, maze_y, enemies, speed: CLOSE 1: RUN
  141.  
  142. re: IF _FILEEXISTS(settings$) = 0 THEN maze_x = 30: maze_y = 12: enemies = 3: speed = 10: GOTO wr
  143. OPEN settings$ FOR INPUT AS 1: INPUT #1, maze_x, maze_y, enemies, speed: CLOSE 1: RETURN
  144.  
  145.  

Logged

FellippeHeitor

  • Guest
Re: Recursively maze creation
« Reply #2 on: June 21, 2020, 05:25:57 pm »
Looks cool! I'm sure @Virtusoroca will like looking at this piece too.
Logged

Offline Virtusoroca

  • Newbie
  • Posts: 24
    • View Profile
Re: Recursively maze creation
« Reply #3 on: June 21, 2020, 05:50:51 pm »
@MasterGy thanks for this one! And thanks @FellippeHeitor for pointing it out. I was trying to implement the backtrack algorithm but had to stop because of work. Hope to come back to the forum in a couple of weeks. Very excited to run and explore this code! Looks very nice! <3
Logged

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Recursively maze creation
« Reply #4 on: June 21, 2020, 06:06:08 pm »
Wow allot less to it than what I was using, nice!
Logged

Offline MasterGy

  • Seasoned Forum Regular
  • Posts: 327
  • people lie, math never lies
    • View Profile
Re: Recursively maze creation
« Reply #5 on: June 23, 2020, 04:58:37 pm »
I couldn’t wait to have time to integrate the maze into 3D space.
The maze is closed, but only 1 road leads from one place to another.
I had to resolve to skip the location of the towers but leave 1 entrance.
Since the smallest unit in the 3d game is the rectangle, and to save space by filling the maze, I solved it to lay it out with as few rectangles (or rectangles) of different sizes as possible.



Try it
https://drive.google.com/file/d/1bKiKYf_tXS0lkj_zxPycvmN3F-2v-mYe/view?usp=sharing
« Last Edit: June 23, 2020, 05:09:35 pm by MasterGy »
Logged

Offline Ashish

  • Forum Resident
  • Posts: 630
  • Never Give Up!
    • View Profile
Re: Recursively maze creation
« Reply #6 on: June 24, 2020, 01:25:01 am »
WOW! Beautiful 3D Version!! :D +1
Logged
if (Me.success) {Me.improve()} else {Me.tryAgain()}


My Projects - https://github.com/AshishKingdom?tab=repositories
OpenGL tutorials - https://ashishkingdom.github.io/OpenGL-Tutorials

Offline MasterGy

  • Seasoned Forum Regular
  • Posts: 327
  • people lie, math never lies
    • View Profile
Re: Recursively maze creation
« Reply #7 on: June 24, 2020, 05:06:34 pm »
thank you very much ! i still have a few ideas i want to try. eg in 2d, if I like 2-3 mazes in 1 space that are separated from each other and connect them with a bridge. Obsession ! so that scheme is supplemented by a 3rd dimension. So theoretically there would be 1 cube with two entrances. and then inside there would be paths like that. like a cave.
Logged
Pages: [1]   Go Up
« previous next »