Maze Generator 7

[SierraKen]

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:
9. _LIMIT 50
10. CLS
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
20. RANDOMIZE TIMER
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)
35. NEXT l
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
44. DO
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&
52. LOOP
53. printing:
54. picture2& = _COPYIMAGE(0)
55. _PRINTIMAGE picture2&
56. _DELAY 2
57. _FREEIMAGE picture2&
58. RETURN
59.  

[SpriggsySpriggs]

Pretty cool!

[SierraKen]

Thanks SpriggsySpriggs :)

[bplus]

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.  
5. RANDOMIZE TIMER
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
47. NEXT
48. 'see what we made
49. GOSUB drawing ' ah so the bit math went and poked holes and made a grid
50. SLEEP
51.  
52.  
53. 'start position ----------------------------------------------------------------------
54. DO
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
60. SLEEP
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.  
93. LOOP WHILE wdb
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.  
106. END
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
114. NEXT
115. RETURN
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.

[SMcNeill]

        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...

[bplus]

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.

[SierraKen]

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

[bplus]

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.