Author Topic: Maze Generator 7  (Read 3721 times)

0 Members and 1 Guest are viewing this topic.

Offline SierraKen

  • Forum Resident
  • Posts: 1454
    • View Profile
Maze Generator 7
« 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:
  9. picture& = _NEWIMAGE(600, 600, 32)
  10. SCREEN picture&
  11. PAINT (2, 2), _RGB32(255, 255, 255)
  12. 'Border Box
  13. LINE (50, 50)-(550, 550), _RGB32(0, 0, 0), B
  14. 'Horizontal Walls
  15. FOR ly = 50 TO 550 STEP 10
  16.     LINE (50, ly)-(550, ly), _RGB32(0, 0, 0)
  17. NEXT ly
  18. 'Starts and Finshes
  19. FOR outs = 1 TO 5
  20.     xx = INT(RND * 490) + 50
  21.     LINE (xx, 550)-(xx + 10, 550), _RGB32(255, 255, 255)
  22.     xx = INT(RND * 490) + 50
  23.     LINE (xx, 50)-(xx + 10, 50), _RGB32(255, 255, 255)
  24. NEXT outs
  25. 'Walls
  26. FOR l = 1 TO 300
  27.     x = INT(RND * 500) + 50
  28.     walls:
  29.     y = INT(RND * 500) + 50
  30.     IF y / 10 <> INT(y / 10) THEN GOTO walls:
  31.     LINE (x, y)-(x, y + 10), _RGB32(0, 0, 0)
  32. 'Blank Doors
  33. FOR ll = 1 TO 500
  34.     x = INT(RND * 500) + 50
  35.     doors:
  36.     y = INT(RND * 490) + 60
  37.     IF y / 10 <> INT(y / 10) THEN GOTO doors:
  38.     LINE (x, y)-(x + 10, y), _RGB32(255, 255, 255)
  39. NEXT ll
  40.     _LIMIT 10
  41.     _TITLE "Press Space Bar for another one, P to Print, C to copy to Clipboard, or Esc to Quit."
  42.     a$ = INKEY$
  43.     IF a$ = " " THEN GOTO start:
  44.     IF a$ = CHR$(27) THEN END
  45.     IF a$ = "p" OR a$ = "P" THEN GOSUB printing:
  46.     IF a$ = "c" OR a$ = "C" THEN _CLIPBOARDIMAGE = picture&
  47. printing:
  48. picture2& = _COPYIMAGE(0)
  49. _PRINTIMAGE picture2&
  50. _FREEIMAGE picture2&
  51.  
Maze Generator 7 Example.jpg
* Maze Generator 7 Example.jpg (Filesize: 114.1 KB, Dimensions: 600x600, Views: 222)
« Last Edit: September 22, 2020, 06:41:43 pm by SierraKen »

Offline SpriggsySpriggs

  • Forum Resident
  • Posts: 1145
  • Larger than life
    • View Profile
    • GitHub
Re: Maze Generator 7
« Reply #1 on: September 22, 2020, 06:58:27 pm »
Pretty cool!
Shuwatch!

Offline SierraKen

  • Forum Resident
  • Posts: 1454
    • View Profile
Re: Maze Generator 7
« Reply #2 on: September 22, 2020, 07:19:39 pm »
Thanks SpriggsySpriggs :)

Offline bplus

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

I haven't gotten to "way searching" yet but I made a GOSUB out of drawing to examine various stages of the developing grid.
« Last Edit: September 22, 2020, 10:16:46 pm by bplus »

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Maze Generator 7
« Reply #4 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...
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Maze Generator 7
« Reply #5 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.

« Last Edit: September 23, 2020, 12:08:56 pm by bplus »

Offline SierraKen

  • Forum Resident
  • Posts: 1454
    • View Profile
Re: Maze Generator 7
« Reply #6 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

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Maze Generator 7
« Reply #7 on: September 23, 2020, 01:58:19 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.
« Last Edit: September 23, 2020, 02:03:17 pm by bplus »