Text Only | Text with Attachments

QB64.org Forum

Active Forums => Programs => Topic started by: SierraKen on September 22, 2020, 06:34:50 pm

Title: Maze Generator 7
Post by: SierraKen on September 22, 2020, 06:34:50 pm
Maze Generator 7 by SierraKen
Sept. 22, 2020
Every maze is not solvable but most are. You can squeeze through some tiny gaps in the wall corners.
Start from the bottom and go to the top. You can enter and exit on any of the blank doors.
To print on printer, press P, to Copy to Clipboard, press C. Esc to Quit.
On this new version, every horizontal wall is evenly spaced and the same for every maze (except its blank doors).
Press the Space Bar to make a new maze.

This is a very simple maze generator, nothing like the true mazes B+ and others have made in the past. This might be as close as I can get to
just using randomness to make a challenging maze.

Code: QB64: [Select]
  1. 'Maze Generator 7 by SierraKen
  2. 'Sept. 22, 2020
  3. 'Every maze is not solvable but most are. You can squeeze through tiny gaps in the wall corners.
  4. 'Start from the bottom and go to the top. You can enter and exit on any of the blank doors.
  5. 'To print on printer, press P, to Copy to Clipboard, press C. Esc to Quit.
  6. 'On this new version, every horizontal wall is evenly spaced and the same for every maze (except its blank doors).
  7. 'Press the Space Bar to make a new maze.
  8. start:
  11. picture& = _NEWIMAGE(600, 600, 32)
  12. SCREEN picture&
  13. PAINT (2, 2), _RGB32(255, 255, 255)
  14. 'Border Box
  15. LINE (50, 50)-(550, 550), _RGB32(0, 0, 0), B
  16. 'Horizontal Walls
  17. FOR ly = 50 TO 550 STEP 10
  18.     LINE (50, ly)-(550, ly), _RGB32(0, 0, 0)
  19. NEXT ly
  21. 'Starts and Finshes
  22. FOR outs = 1 TO 5
  23.     xx = INT(RND * 490) + 50
  24.     LINE (xx, 550)-(xx + 10, 550), _RGB32(255, 255, 255)
  25.     xx = INT(RND * 490) + 50
  26.     LINE (xx, 50)-(xx + 10, 50), _RGB32(255, 255, 255)
  27. NEXT outs
  28. 'Walls
  29. FOR l = 1 TO 300
  30.     x = INT(RND * 500) + 50
  31.     walls:
  32.     y = INT(RND * 500) + 50
  33.     IF y / 10 <> INT(y / 10) THEN GOTO walls:
  34.     LINE (x, y)-(x, y + 10), _RGB32(0, 0, 0)
  36. 'Blank Doors
  37. FOR ll = 1 TO 500
  38.     x = INT(RND * 500) + 50
  39.     doors:
  40.     y = INT(RND * 490) + 60
  41.     IF y / 10 <> INT(y / 10) THEN GOTO doors:
  42.     LINE (x, y)-(x + 10, y), _RGB32(255, 255, 255)
  43. NEXT ll
  45.     _LIMIT 10
  46.     _TITLE "Press Space Bar for another one, P to Print, C to copy to Clipboard, or Esc to Quit."
  47.     a$ = INKEY$
  48.     IF a$ = " " THEN GOTO start:
  49.     IF a$ = CHR$(27) THEN END
  50.     IF a$ = "p" OR a$ = "P" THEN GOSUB printing:
  51.     IF a$ = "c" OR a$ = "C" THEN _CLIPBOARDIMAGE = picture&
  53. printing:
  54. picture2& = _COPYIMAGE(0)
  55. _PRINTIMAGE picture2&
  57. _FREEIMAGE picture2&
  59.  
Title: Re: Maze Generator 7
Post by: SpriggsySpriggs on September 22, 2020, 06:58:27 pm
Pretty cool!
Title: Re: Maze Generator 7
Post by: SierraKen on September 22, 2020, 07:19:39 pm
Thanks SpriggsySpriggs :)
Title: Re: Maze Generator 7
Post by: bplus on September 22, 2020, 10:10:36 pm
I thought it might be interesting to study MasterGy's maze generator that he did not invent. I started reformating code and explaining to myself what the inventor was up to.

Look at this! how he has setup the start of a grid:
Code: QB64: [Select]
  1. ' masterGy algo not inventer by me 2020-06-21
  2. 'https://www.qb64.org/forum/index.php?topic=2735.new#new
  3. ' 2020-09-22  bplus mod to my way of code structure  and comment code (where I understand it.
  4.  
  6.  
  7. maze_x = 75 'maze size X
  8. maze_y = 25 'maze size Y
  9.  
  10. 'preparation -------------------------------------------------------------------------------------------------------------------------------------------
  11. IF maze_x / 2 = INT(maze_x / 2) THEN maze_x = maze_x + 1 ' make maze_x an odd number
  12. IF maze_y / 2 = INT(maze_y / 2) THEN maze_y = maze_y + 1 ' make maze_y an odd number
  13.  
  14. monx = (maze_x + 10) * 8: mony = (maze_y + 5) * 16 'finding pixel sizes for screen
  15. '                                                   with offsets x = 10*8 = 80  and y = 5*16 = 80
  16. '                                                   so 40 pixel frame then?
  17.  
  18. kep = _NEWIMAGE(monx, mony, 32)
  19. SCREEN kep
  20.  
  21. ' these are directions  but is x or y listed first I would list x first y 2nd
  22. d(0, 0) = 0: d(0, 1) = -1 ' North ?    ? = needs to be confirmed
  23. d(1, 0) = 0: d(1, 1) = 1 ' South ?
  24. d(2, 0) = -1: d(2, 1) = 0 ' West ?
  25. d(3, 0) = 1: d(3, 1) = 0 ' East ?
  26.  
  27. ' key codes or map code  looks like we end with just k$(0), k$(3) or k$(4) = k$(5)
  28. k$(0) = "±" 'fal / adjustable wall
  29. k$(1) = " " 'nem bejart ureg / non walked road
  30. k$(2) = "W" 'lehetoseg / possible way
  31. k$(3) = "U" 'szilard fal / standard wall  = border
  32. k$(4) = "!" 'bejart ureg  / walked road   = passage
  33. k$(5) = "." 'belepesi pont  / entry point  = start or exit?
  34.  
  35.  
  36. DIM maze(maze_x - 1, maze_y - 1) AS _BYTE '0-fal 1-ureg 2-lehetoseg
  37.  
  38.  
  39. 'create empty maze -------------------------------------------------------------------
  40. FOR tx = 0 TO maze_x - 1
  41.     FOR ty = 0 TO maze_y - 1
  42.         k = 0
  43.         IF tx = 0 OR ty = 0 OR tx = maze_x - 1 OR ty = maze_y - 1 THEN k = 3 ' border
  44.         IF tx AND 1 AND ty AND 1 THEN k = 1 ' dang bit math
  45.         maze(tx, ty) = k
  46.     NEXT
  48. 'see what we made
  49. GOSUB drawing ' ah so the bit math went and poked holes and made a grid
  51.  
  52.  
  53. 'start position ----------------------------------------------------------------------
  55.     sx = INT(maze_x * RND(1)): sy = INT(maze_y * RND(1))
  56. LOOP WHILE maze(sx, sy) <> 1
  57. maze(sx, sy) = 4 'the start of the way
  58. 'see what we made
  59. GOSUB drawing ' ah so the bit math went and poked holes and made a grid
  61.  
  62. 'way searching -----------------------------------------------------------------------
  63. DO: REDIM way(9999, 2): wdb = 0
  64.     FOR tx = 0 TO maze_x - 1: FOR ty = 0 TO maze_y - 1
  65.             IF maze(tx, ty) = 4 THEN
  66.                 van = 0
  67.                 FOR t = 0 TO 3
  68.                     vpx1 = tx + d(t, 0): vpy1 = ty + d(t, 1): vpx2 = tx + d(t, 0) * 2: vpy2 = ty + d(t, 1) * 2
  69.                     f = (vpx2 > maze_x - 1 OR vpx2 < 0) OR (vpy2 > maze_y - 1 OR vpy2 < 0)
  70.                     IF NOT f THEN
  71.                         IF maze(vpx1, vpy1) = 0 AND maze(vpx2, vpy2) = 1 THEN
  72.                             FOR t2 = 0 TO 3: vpx3 = vpx2 + d(t2, 0): vpy3 = vpy2 + d(t2, 1): IF maze(vpx3, vpy3) = 4 THEN GOTO kovi
  73.                             NEXT t2
  74.                             maze(vpx1, vpy1) = 2: way(wdb, 0) = tx: way(wdb, 1) = ty: way(wdb, 2) = t: wdb = wdb + 1
  75.                             kovi:
  76.                         END IF
  77.                     END IF
  78.                 NEXT t
  79.             END IF
  80.     NEXT ty, tx
  81.  
  82.     IF wdb THEN
  83.         aw = INT(wdb * RND(1))
  84.         FOR t = 0 TO 2
  85.             hovax = way(aw, 0) + d(way(aw, 2), 0) * t: hovay = way(aw, 1) + d(way(aw, 2), 1) * t
  86.             IF (maze(hovax, hovay) = 2) OR (maze(hovax, hovay) = 1) THEN maze(hovax, hovay) = 4
  87.         NEXT t
  88.  
  89.         FOR tx = 0 TO maze_x - 1: FOR ty = 0 TO maze_y - 1: IF maze(tx, ty) = 2 THEN maze(tx, ty) = 0
  90.         NEXT ty, tx
  91.     END IF
  92.  
  94.  
  95. 'entry point 1
  96. sx = 0: sy = 3: IF maze(sx + 1, sy) <> 4 THEN sy = sy + 1
  97. maze(sx, sy) = 4
  98.  
  99. 'entry point 2
  100. sx = maze_x - 1: sy = maze_y - 3: IF maze(sx - 1, sy) <> 4 THEN sy = sy - 1
  101. maze(sx, sy) = 4
  102.  
  103. ' it has taken so far to build the maze. contained in the maze array ------------------------------------------------------------------------------------------------
  104. GOSUB drawing
  105.  
  107. drawing:
  108. ' making offsets to fit inside screen pretty
  109. sy = INT((mony / 16 - maze_y) / 2) + 1: sx = INT((monx / 8 - maze_x) / 2) + 1
  110. FOR tx = 0 TO maze_x - 1
  111.     FOR ty = 0 TO maze_y - 1
  112.         LOCATE sy + ty, sx + tx: PRINT k$(maze(tx, ty))
  113.     NEXT
  116.  
  117.  

I haven't gotten to "way searching" yet but I made a GOSUB out of drawing to examine various stages of the developing grid.
Title: Re: Maze Generator 7
Post by: SMcNeill on September 23, 2020, 01:57:11 am
        IF tx AND 1 AND ty AND 1 THEN k = 1 ' dang bit math

It’s not a complex bit to figure out.  ;)

In this case, IF the first bit of tx is set, AND the first bit of ty is set, THEN k = 1.

In this case, it seems to me that it’s basically a case of:

IF tx is odd AND ty is odd THEN k = 1.

Maze(1,1) = 1
Maze(1,3) = 1
Maze(1,5) = 1
ect...
Title: Re: Maze Generator 7
Post by: bplus on September 23, 2020, 11:53:21 am
Yaaaa figured that out by the grid drawn, the bit math gets way more interesting when f is set with the direction array involved :)

I was pointing this out because Ken might want to try his maze making with the same kind of start, holes everywhere.
Then you just have to stay odd (or is it even?) when you make tunnels or remove walls to make paths.

Odd or even?
Odd, AND 1 means odd, make a space, a place you can walk = 1, k$(1) = space fitting choice of number.

Can't knock down a wall if it is (even, even) or if on a border. That rule alone should prevent parking lots from being created at least ones lacking a center stripe.

BTW van = 0 is never used.

Title: Re: Maze Generator 7
Post by: SierraKen on September 23, 2020, 01:39:30 pm
Thanks B+. I looked a little bit at it yesterday and was lost as usual. I'll look at it again soon. There's a Wiki site explaining the different ways people make mazes. One way is you make a grid and remove walls as you go. But in doing so you use every single block on the grid as the maze. You go right or left a couple blocks (or up, or down), then turn and keep doing so until your path can't go anywhere else that you haven't been before. Then you keep backing up to where you were before until you can delete a wall to a block you haven't been before. Some day I'll figure it out I hope.

Here is the Wiki site. I don't recall which maze algorithm that I described above is on this page:
https://en.wikipedia.org/wiki/Maze_generation_algorithm
Title: Re: Maze Generator 7
Post by: bplus on September 23, 2020, 01:58:19 pm
Quote from: SierraKen on September 23, 2020, 01:39:30 pm
Thanks B+. I looked a little bit at it yesterday and was lost as usual. I'll look at it again soon. There's a Wiki site explaining the different ways people make mazes. One way is you make a grid and remove walls as you go. But in doing so you use every single block on the grid as the maze. You go right or left a couple blocks (or up, or down), then turn and keep doing so until your path can't go anywhere else that you haven't been before. Then you keep backing up to where you were before until you can delete a wall to a block you haven't been before. Some day I'll figure it out I hope.

Here is the Wiki site. I don't recall which maze algorithm that I described above is on this page:
https://en.wikipedia.org/wiki/Maze_generation_algorithm

You've described it pretty well, Ken. An array is used to track which cells have been visited or not and usually a stack is involved when there is choices to go one way or another. One choice is taken and the other(s) saved to come back to when a route is exhausted of options. A stack is an array that holds items until you're ready to process them the last item put in the stack is usually the first item handled when ready to check another route. Using different codes to mark the array is a way to avoid using more arrays which I thought you might find appealing.

I am not expecting you to get all this, but I thought starting the way the Inventor did might help the mazes you make look more maze like. Then I figured you might work out on your own how to finish out empty cells without access to path, getting them hooked in.
Text Only | Text with Attachments