OpenEuphoria

To: Evan Marshall (Maze Maker)

• Posted by Don Phillips <Graebel at hotmail.com> Jun 06, 2002
• 518 views

Thanks for the algo!

Very interesting way to create a maze.  I cant think of any reason to need 
one at the moment, but I thought just for fun I would take a stab at 
improving its speed.  This is what I came up with.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

without warning
include Win32Lib.ew

-- register controls with win32lib
constant
MainWin = create( Window, "Maze", NULL, 0.1, 0.1, 0.8, 0.8, 0 ),
Canvas = create( Window, "", MainWin, 0, 0, 1, 1, 
{WS_CHILD,WS_VISIBLE,WS_DLGFRAME} ),
MaxXLbl = createEx( EditText, "", Canvas, 14, 7, 50, 15, 
{WS_CHILD,WS_VISIBLE,WS_DISABLED}, {0} ),
MaxYLbl = createEx( EditText, "", Canvas, 74, 7, 50, 15, 
{WS_CHILD,WS_VISIBLE,WS_DISABLED}, {0} ),
EditX = create( EditText, "20", Canvas, 10, 22, 50, 20, ES_NUMBER ),
EditY = create( EditText, "20", Canvas, 70, 22, 50, 20, ES_NUMBER ),
RunMaze = create( DefPushButton, "Make Maze", Canvas, 131, 18, 140, 29, 0 
),
Status = create( ProgressBar, "", Canvas, 0, 0, 1, 1, 0 )

-- define variables
integer RoomsX
integer RoomsY
integer UsedRooms
sequence Grid
sequence Path
sequence Slice
sequence NewPos
sequence Mask Mask = { 0, 1, 0, 2, 0, 3, 0, 4, 0}
sequence Move Move = { {0,-1}, {-1,0}, {1,0}, {0,1} }

-- remove a wall in specified direction
procedure RemoveWall( integer Direction )
if Direction = 1 then
drawLine( MainWin, (NewPos[1]-1)*10+1, (NewPos[2]-1)*10, 
(NewPos[1]-1)*10+10, (NewPos[2]-1)*10 )
elsif Direction = 2 then
drawLine( MainWin, (NewPos[1]-1)*10, (NewPos[2]-1)*10+1, (NewPos[1]-1)*10, 
(NewPos[2]-1)*10+10 )
elsif Direction = 3 then
drawLine( MainWin, (NewPos[1]-1)*10+10, (NewPos[2]-1)*10+1, 
(NewPos[1]-1)*10+10, (NewPos[2]-1)*10+10 )
else
drawLine( MainWin, (NewPos[1]-1)*10+1, (NewPos[2]-1)*10+10, 
(NewPos[1]-1)*10+10, (NewPos[2]-1)*10+10 )
end if
end procedure

-- make the maze
function makeMaze()
integer PosX
integer PosY
integer Direction
integer NewMove
integer Index
sequence Size

-- clear screen
repaintWindow( MainWin )

-- get size of grid
Size = value( getText(EditX) )
if Size[1] = GET_SUCCESS then
RoomsX = Size[ 2 ]
else
return( -1 )
end if

Size = value( getText(EditY) )
if Size[1] = GET_SUCCESS then
RoomsY = Size[ 2 ]
else
return( -1 )
end if

-- enforce maximums
Size = getClientRect( MainWin )
if RoomsX > floor((Size[3] - 20) / 10) then
setText( EditX, sprintf( "%d", {floor((Size[3] - 20) / 10)} ))
RoomsX = floor((Size[3] - 20) / 10)
end if
if RoomsY > floor((Size[4] - 80) / 10) then
RoomsY = floor((Size[4] - 80) / 10)
setText( EditY, sprintf( "%d", {floor((Size[4] - 80) / 10)} ))
end if

-- set status indicator range to maximum
UsedRooms = 0
setScrollRange( Status, 0, RoomsX * RoomsY )

-- initialize grid
Grid = {}
Grid &= { repeat( 0, RoomsX+2 ) }
Grid &= repeat( 0 & repeat( 1, RoomsX ) & 0, RoomsY )
Grid &= { repeat( 0, RoomsX+2 ) }

-- draw initial grid on screen
setPenColor( MainWin, Yellow )
for IterY = 0 to RoomsY do
drawLine( MainWin, 10, IterY*10+10, RoomsX*10+10, IterY*10+10 )
end for
for IterX = 0 to RoomsX do
drawLine( MainWin, IterX*10+10, 10, IterX*10+10, RoomsY*10+10 )
end for
setPenColor( MainWin, Black )

-- set random initial position
PosX = rand( RoomsX ) + 1
PosY = rand( RoomsY ) + 1
Grid[ PosY ][ PosX ] = 0

Index = 1
NewPos = { PosX, PosY }
Path = { NewPos }
NewMove = 1

while length(Path) do
-- update the indicator
setScrollPos( Status, UsedRooms )

-- while processing let win32lib handle other events
doEvents( 0 )

-- get movement grid slice
Slice = {}
for SliceIter = -1 to 1 do
Slice &= Grid[ NewPos[2]+SliceIter ][ NewPos[1]-1..NewPos[1]+1 ]
end for

-- mask to find valid move positions
Slice = reverse( sort( (Slice and Mask) * Mask ))

if not Slice[1] then -- no valid moves, remove from path
Path = Path[ 1..Index-1 ] & Path[ Index+1..length(Path) ]
if length(Path) then
Index = rand( length(Path) )
NewPos = Path[ Index ]
NewMove = 1
end if
else
if NewMove then -- On first move after jump always move to open room
Direction = Slice[ rand(find(0,Slice)-1) ]
RemoveWall( Direction )
NewPos += Move[ Direction ]
Path = append( Path, NewPos )
NewMove = 0
UsedRooms += 1
Grid[ NewPos[2] ][ NewPos[1] ] = 0
else -- After first move chance to move anywhere
Direction = Slice[ rand(4) ]
if Direction then
RemoveWall( Direction )
NewPos += Move[ Direction ]
Path = append( Path, NewPos )
UsedRooms += 1
Grid[ NewPos[2] ][ NewPos[1] ] = 0
else
-- hit another room, random jump to new position in path
Index = rand( length(Path) )
NewPos = Path[ Index ]
NewMove = 1
end if
end if
end if
end while

-- maze done, cut out random top and bottom piece
PosX = rand( RoomsX ) + 1
drawLine( MainWin, (NewPos[1]-1)*10+1, 10, (NewPos[1]-1)*10+10, 10 )
PosX = rand( RoomsX ) + 1
drawLine( MainWin, (NewPos[1]-1)*10+1, RoomsY*10+10, (NewPos[1]-1)*10+10, 
RoomsY*10+10 )

-- clear status indicator
setScrollPos( Status, 0 )

return( 1 )
end function

-- run the maze algorithm
procedure onClick_RunMaze()
integer RetVal
RetVal = makeMaze()
end procedure
onClick[ RunMaze ] = routine_id( "onClick_RunMaze" )

-- resize controls to parent
procedure onResize_MainWin( integer Style, integer CX, integer CY )
setRect( Canvas, 0, CY-60, CX, 60, True )
setRect( Status, 283, 23, CX-300, 18, True )

setText( MaxXLbl, sprintf( "Max %d", {floor((CX - 20) / 10)} ))
setText( MaxYLbl, sprintf( "Max %d", {floor((CY - 80) / 10)} ))
end procedure
onResize[ MainWin ] = routine_id( "onResize_MainWin" )

-- initialize
procedure onOpen_MainWin()
setWindowBackColor( MainWin, Black )
setWindowBackColor( MaxXLbl, getSysColor(COLOR_BTNFACE) )
setWindowBackColor( MaxYLbl, getSysColor(COLOR_BTNFACE) )
setFocus( EditX )
end procedure
onOpen[ MainWin ] = routine_id( "onOpen_MainWin" )

-- event loop
WinMain( MainWin, Maximize )

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-