PDA

View Full Version : Attn: DaltonSpence - Maze Generation Code (Screensaver)



Arcana
11-28-2006, 10:01 AM
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.

Arcana
11-29-2006, 10:05 AM
I think I'm going to update this while I'm in Orlando at a convention next week....we'll see.

DaltonSpence
12-03-2006, 04:52 PM
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: 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.
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_".)
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.
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.

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.

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.

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.

MACRO DRAWMAZE
ecoff
savesettings
sgetname sShtName
MZ_InVars
MZ_1STWALL
goto DM_DRAWWALL

Find a point on an existing wall to start a new section.

: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

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.

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

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

: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

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

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

: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

Restore the old sheet name and settings.

: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

DaltonSpence
12-06-2006, 09:44 AM
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

RPMiller
12-06-2006, 11:17 AM
This is just too cool! 8) 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!

DaltonSpence
12-06-2006, 04:03 PM
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

DaltonSpence
12-16-2006, 01:06 PM
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. (http://ca.wiley.com/WileyCDA/Brand/id-1.html)
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