Results 1 to 7 of 7

Thread: Attn: DaltonSpence - Maze Generation Code (Screensaver)

  1. #1
      Arcana is offline
    Administrator Facebook Connected Arcana's Avatar
    Join Date
    Mar 2006
    Location
    Fairborn, OH
    Posts
    2,775
    Blog Entries
    5

    Post Attn: DaltonSpence - Maze Generation Code (Screensaver)

    A LONG time ago back in the VB6 days I wrote a screensaver that utilized the Mazegen code from some website that sprobably long gone now. It originally was a Java applet that used three different algorithms to generate and solve perfect mazes.

    The algorithms were Prim, Kruskal, and the ever popular Depth First Search. All the solutions are generated using Depth First Search.

    I have the code for those algorithms Dalton if you would like to peruse and implement into your Mazegen script? I'm not sure what algorithm you're using, but the three algorithms I have each produce totally different styles of mazes, some more open and some more convoluted, but all perfect.

    I'll attach the actual screensaver...the email addresses in there are useless, so don't try to email me at that address...and I don't think the screensaver is properly coded for use with XP...I couldn't get it to do anything except generate mazes full screen...no configure window, but you may be luckier.
    Attached Files Attached Files
    Robbie Powell - Site Admin

  2. #2
      Arcana is offline
    Administrator Facebook Connected Arcana's Avatar
    Join Date
    Mar 2006
    Location
    Fairborn, OH
    Posts
    2,775
    Blog Entries
    5

    Post

    I think I'm going to update this while I'm in Orlando at a convention next week....we'll see.
    Robbie Powell - Site Admin

  3. #3
    Guild Apprentice
    Join Date
    Jun 2006
    Location
    Hamilton, Ontario, CANADA
    Posts
    47

    Post An aMazing macro

    Here is my maze generating macro. Basically it's variant of the Hunt and Kill algorithm, using GE (Get Entity) to test intersection points inside the maze for existing walls. It's a bit slow, but the only way I can do it in the macro language. I managed to get LTP to work by making sure it's only executed at the end of a line chain. This is the first step to a macro dungeon generator.

    Some ideas I use to regularize my code:
    1. Except for the core macro of the project, all subsidiary macro names begin with a project prefix (in this case "MZ") followed by an underscore.
    2. All labels within subsidiary macros begin with the project prefix, followed immediately by a macro specific prefix, followed by an underscore. Labels within core macros do not require the project prefix, just the macro specific one. (Example: macro MZ_InVars contains labels starting with "MZI_", while DrawMaze contains labels starting with "DM_".)
    3. All variable names begin with a single letter denoting the value type: "n" for integer values, "v" for real values, "p" for points values (real x/y components of a point use the appropriate letter) and "s" for string values.
    Code:
    MACRO MZ_INVARS
    :MZI_CellSize
    gv vCellSize 5
    gv vCellSize ^DEnter size of maze cell [5]:
    ifp vCellSize MZI_Wall
    askbox Invalid Cell Size
    The cell size entered must
    be greater than zero. Do
    you want to re-enter it?
    
    iferr MZI_Exit
    goto MZI_CellSize
    :MZI_Wall
    gv vMazeWall 1
    gv vMazeWall ^DEnter thickness of the maze wall [1]:
    ifn vCellSize-2*vMazeWall MZI_Wall2
    ifp vMazeWall MZI_Border
    :MZI_Wall2
    askbox Invalid Maze Wall Thickness
    The maze wall thickness must
    be greater than zero but less
    than half the cell width. Do
    you want to re-enter it?
    
    iferr MZI_Exit
    
    goto MZI_Wall
    :MZI_Border
    gp pMzCorner ^DSelect the lower left corner of the maze:
    iferr MZI_Exit
    sset WALLS
    lwidth vMazeWall
    agrid pMzCorner
    gridv vCellSize
    snapv 1
    snapon
    box pMzCorner ^DSelect the upper right corner of the maze:
    iferr MZI_Exit
    gp pNxtPt @0,0
    getx xMazeL pMzCorner
    getx xMazeH pNxtPt
    ifp xMazeH-xMazeL MZI_Width
    getx xMazeL pNxtPt
    getx xMazeH pMzCorner
    :MZI_Width
    gn nMazeWd (xMazeH-xMazeL)/vCellSize
    ifp nMazeWd-1 MZI_CheckHt
    askbox Invalid Maze Width
    The maze must be greater
    than one cell wide. Do
    you want to redraw it?
    
    iferr MZI_Exit
    undo
    goto MZI_Border
    :MZI_CheckHt
    gety yMazeL pMzCorner
    gety yMazeH pNxtPt
    ifp yMazeH-yMazeL MZI_Height
    gety yMazeL pNxtPt
    gety yMazeH pMzCorner
    :MZI_Height
    gn nMazeHt (yMazeH-yMazeL)/vCellSize
    ifp nMazeHt-1 MZI_Finish
    askbox Invalid Maze Height
    The maze must be greater
    than one cell high. Do
    you want to redraw it?
    
    iferr MZI_Exit
    goto MZI_Border
    :MZI_Finish
    gn nUnvisited (nMazeWd-1)*(nMazeHt-1)
    exitm
    :MZI_Exit
    exitam
    ENDM
    This macro inputs the maze cell and wall widths and draws the outer wall of the maze. Note that to do the latter, the currently active grid is aligned to the lower left corner of the maze, and the grid distance and snap setting are changed to the cell width. This changes the properties of the selected named grid setting, which will have to e corrected manually after the maze is drawn.
    Code:
    MACRO MZ_1STWALL
    random vRand
    gn nRand vRand*(nMazeHt+nMazeWd-2)*2
    ifn nRand-(nMazeWd-1) MZFW_S
    gn nRand nRand-(nMazeWd-1)
    ifn nRand-(nMazeHt-1) MZFW_E
    gn nRand nRand-(nMazeHt-1)
    ifn nRand-(nMazeWd-1) MZFW_N
    gn nRand nRand-(nMazeWd-1)
    gn nX1 0
    gn nX2 1
    goto MZFW_Y
    :MZFW_S
    gn nY1 0
    gn nY2 1
    goto MZFW_X
    :MZFW_E
    gn nX1 nMazeWd
    gn nX2 nMazeWd-1
    :MZFW_Y
    gn nY1 nRand+1
    gn nY2 nY1
    goto MZFW_Exit
    :MZFW_N
    gn nY1 nMazeHt
    gn nY2 nMazeHt-1
    :MZFW_X
    gn nX1 nRand+1
    gn nX2 nX1
    :MZFW_Exit
    gp pCurPt xMazeL+vCellSize*nX1,yMazeL+vCellSize*nY1
    gn nSegments 0
    ENDM
    The first wall segment is always anchored to the edge of the outer wall and ends one cell width inward.
    Code:
    MACRO MZ_TESTPT
    gn nVisited 0
    ge pNxtPt xMazeL+vCellSize*nX2,yMazeL+vCellSize*nY2
    iferr MZTP_Exit
    gn nVisited 1
    :MZTP_Exit
    ENDM
    
    MACRO MZ_TESTE
    gn nVisited 1
    gn nX2 nX1+1
    gn nY2 nY1
    ifp nX2-nMazeWd+1 MZTE_Exit
    MZ_TESTPT
    :MZTE_Exit
    gn nValid nValid-nVisited
    gn nEmptyE 1-nVisited
    ENDM
    
    MACRO MZ_TESTW
    gn nVisited 1
    gn nX2 nX1-1
    gn nY2 nY1
    ifn nX2-1 MZTW_Exit
    MZ_TESTPT
    
    :MZTW_Exit
    gn nValid nValid-nVisited
    gn nEmptyW 1-nVisited
    ENDM
    
    MACRO MZ_TESTN
    gn nVisited 1
    gn nX2 nX1
    gn nY2 nY1+1
    ifp nY2-nMazeHt+1 MZTN_Exit
    MZ_TESTPT
    :MZTN_Exit
    gn nValid nValid-nVisited
    gn nEmptyN 1-nVisited
    ENDM
    
    MACRO MZ_TESTS
    gn nVisited 1
    gn nX2 nX1
    gn nY2 nY1-1
    ifn nY2-1 MZTS_Exit
    MZ_TESTPT
    :MZTS_Exit
    gn nValid nValid-nVisited
    gn nEmptyS 1-nVisited
    ENDM
    The above macros test the points surrounding the last point chosen (either the end of a wall segment or a new starting point)

    The macro below is the core one, and is broken into sections for ease of expanation.
    1. The first section of the core macro saves the current settings and sheet name, inputs the variables, draws the outer wall and gets the coordinates for the first wall segment and goes to draw that.
      Code:
      MACRO DRAWMAZE
      ecoff
      savesettings
      sgetname sShtName
      MZ_InVars
      MZ_1STWALL
      goto DM_DRAWWALL
    2. Find a point on an existing wall to start a new section.
      Code:
      :DM_LOOP1
      random vRand
      gn nX1 vRand*(nMazeWd+1)
      random vRand
      gn nY1 vRand*(nMazeHt+1)
      ge pCurPt xMazeL+vCellSize*nX1,yMazeL+vCellSize*nY1
      iferr DM_LOOP1
    3. If the point selected is on the outer wall, test only the point one cell inward from it. If there is no wall passing through that point, draw one from the outer wall to it. Otherwise, repeat from step 2.
      Code:
      gn nValid 1
      ifp nX1 DM_NOTWEST
      MZ_TESTE
      ifp nEmptyE DM_DRAWWALL
      goto DM_LOOP1
      :DM_NOTWEST
      ifn nX1-nMazeWd DM_NOTEAST
      MZ_TESTW
      ifp nEmptyW DM_DRAWWALL
      goto DM_LOOP1
      :DM_NOTEAST
      ifp nY1 DM_NOTSOUTH
      MZ_TESTN
      ifp nEmptyN DM_DRAWWALL
      goto DM_LOOP1
      :DM_NOTSOUTH
      ifn nY1-nMazeHt DM_LOOP2
      MZ_TESTS
      ifp nEmptyS DM_DRAWWALL
      goto DM_LOOP1
    4. Test all of the possible end points surrounding the current wall segment starting point. If none are valid (ie. they all have walls running through or to them) and at least one possible endpoint in the maze is unvisited, return to step 2*. (*NOTE: if at least one wall segment has been drawn since the last time that happened, convert the line chain into a path before doing so.)
      Code:
      :DM_LOOP2
      gn nValid 4
      MZ_TESTE
      MZ_TESTW
      MZ_TESTN
      MZ_TESTS
      ifz nValid-1 DM_GETPT
      ifp nValid-1 DM_RNDPT
      ifz nSegments DM_NoSegments
      gn nSegments 0
      ltp pCurPt pCurPt
      :DM_NoSegments
      ifp nUnvisited DM_LOOP1
      goto DM_EXIT
    5. If only one end point is valid, select it to draw. If more than one is valid, select a valid endpoint at random. (EDIT: I just modified this section to increase its speed.)
      Code:
      :DM_GETPT
      gn nRand 0
      goto DM_TESTE
      :DM_RNDPT
      random vRand
      gn nRand vRand*nValid
      :DM_TESTE
      ifz nEmptyE DM_TESTW
      gn nX2 nX1+1
      gn nY2 nY1
      ifz nRand DM_DRAWWALL
      gn nRand nRand-1
      :DM_TESTW
      ifz nEmptyW DM_TESTN
      gn nX2 nX1-1
      gn nY2 nY1
      ifz nRand DM_DRAWWALL
      gn nRand nRand-1
      :DM_TESTN
      ifz nEmptyN DM_TESTS
      gn nX2 nX1
      gn nY2 nY1+1
      ifz nRand DM_DRAWWALL
      gn nRand nRand-1
      :DM_TESTS
      ifz nEmptyS DM_TESTE
      gn nX2 nX1
      gn nY2 nY1-1
    6. Draw the wall segment, make the current endpoint the next starting point, increment the wall segment counter and decrement the number of unvisited endpoints remaining. If the latter is greater than zero, go to step 4. Otherwise, convert the line chain into a path.
      Code:
      :DM_DRAWWALL
      gp pNxtPt xMazeL+vCellSize*nX2,yMazeL+vCellSize*nY2
      line pCurPt pNxtPt;
      gp pCurPt pNxtPt
      gn nX1 nX2
      gn nY1 nY2
      gn nUnvisited nUnvisited-1
      gn nSegments nSegments+1
      ifp nUnvisited DM_LOOP2
      ltp pCurPt pCurPt
    7. Restore the old sheet name and settings.
      Code:
      :DM_EXIT
      sset sShtName
      getsettings
      econ
      ENDM


    Attached is a maze generated by this macro.

    --

    Dalton "who is amazed he finally got the thing to work" Spence
    Attached Thumbnails Attached Thumbnails Attn: DaltonSpence - Maze Generation Code (Screensaver)-sample2a_149.png  

  4. #4
    Guild Apprentice
    Join Date
    Jun 2006
    Location
    Hamilton, Ontario, CANADA
    Posts
    47

    Post

    Here's another much larger maze created with the same macro. It took several minutes to complete. I really don't know how to make it faster and still keep it perfect. Now to work on the dungeon builder macros.

    --

    Dalton "who's still waiting for some comments about my code" Spence
    Attached Thumbnails Attached Thumbnails Attn: DaltonSpence - Maze Generation Code (Screensaver)-sample2b_423.png  

  5. #5
      RPMiller is offline
    Community Leader RPMiller's Avatar
    Join Date
    Apr 2006
    Location
    Watching you from in here
    Posts
    3,231

    Post

    This is just too cool! My son loves mazes, and I may just use this to make some mazes just for the purpose of giving him something to play with. Thanks!

  6. #6
    Guild Apprentice
    Join Date
    Jun 2006
    Location
    Hamilton, Ontario, CANADA
    Posts
    47

    Post

    Just remember to cut a couple of doors in the outer wall. It doesn't really matter where (although there should be at least one outer corridor wall between them) since any cell in a perfect maze can be reached from any other.

    --

    Dalton "who's fresh out of pithy quips right now" Spence

  7. #7
    Guild Apprentice
    Join Date
    Jun 2006
    Location
    Hamilton, Ontario, CANADA
    Posts
    47

    Post

    Here is a slightly friendlier input macro. Instead of asking for a cell size, it asks for a corridor width, which it adds to the wall thickness to get the cell size. I've set minimum corridor width at 2', which is slightly larger than the minimum crawlway width of 22" recommended by Architectural Graphic Standards.
    Code:
    MACRO MZ_INVARS
    :MZI_CorrWid
    gv vCorrWid 4
    gv vCorrWid ^DEnter width of maze corridor (min. 2') [4]:
    ifp vCorrWid-2 MZI_Wall
    ifz vCorrWid-2 MZI_Wall
    askbox Invalid Corridor Width
    The maze corridor width entered
    must be a minimum of two feet. Do
    you want to re-enter it?
    
    iferr MZI_Exit
    goto MZI_CorrWid
    :MZI_Wall
    gv vMazeWall 1
    gv vMazeWall ^DEnter thickness of the maze wall [1]:
    ifp vMazeWall MZI_Border
    askbox Invalid Maze Wall Thickness
    The maze wall thickness must
    be greater than zero. Do
    you want to re-enter it?
    
    iferr MZI_Exit
    goto MZI_Wall
    :MZI_Border
    gv vCellSize vCorrWid+vMazeWall
    gp pMzCorner ^DSelect the lower left corner of the maze:
    iferr MZI_Exit
    sset WALLS
    lwidth vMazeWall
    agrid pMzCorner
    gridv vCellSize
    snapv 1
    snapon
    csnapon
    box pMzCorner ^DSelect the upper right corner of the maze:
    iferr MZI_Exit
    gp pNxtPt @0,0
    getx xMazeL pMzCorner
    getx xMazeH pNxtPt
    ifp xMazeH-xMazeL MZI_Width
    getx xMazeL pNxtPt
    getx xMazeH pMzCorner
    :MZI_Width
    gn nMazeWd (xMazeH-xMazeL)/vCellSize
    ifp nMazeWd-1 MZI_CheckHt
    askbox Invalid Maze Width
    The maze must be greater
    than one cell wide. Do
    you want to redraw it?
    
    iferr MZI_Exit
    undo
    goto MZI_Border
    :MZI_CheckHt
    gety yMazeL pMzCorner
    gety yMazeH pNxtPt
    ifp yMazeH-yMazeL MZI_Height
    gety yMazeL pNxtPt
    gety yMazeH pMzCorner
    :MZI_Height
    gn nMazeHt (yMazeH-yMazeL)/vCellSize
    ifp nMazeHt-1 MZI_Finish
    askbox Invalid Maze Height
    The maze must be greater
    than one cell high. Do
    you want to redraw it?
    
    iferr MZI_Exit
    goto MZI_Border
    :MZI_Finish
    gn nUnvisited (nMazeWd-1)*(nMazeHt-1)
    exitm
    :MZI_Exit
    exitam
    ENDM
    --

    Dalton "who hopes this makes using the macro easier." Spence

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •