1. To: Evan Marshall (Maze Maker)
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 )
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
2. Re: To: Evan Marshall (Maze Maker)
I'm glad you found it interesting. I was thinking about making a 3D
maze and decided a 2D one would be easier to start with.
I found an algorithm very similar to yours somewhere on the net (I can't
remember where :( ) and decided to go for simplicity(?) over speed for
the first draft. I plan on going back to increase the speed later, as
right now I have more time to wait for a program to run than I do to
develop it!
I am also going to make the maze printable and am working on a print
preview routine. (That should take me quite awhile!)
Don Phillips wrote:
>
> 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 ) }
<snip>
>
>
>
3. Re: To: Evan Marshall (Maze Maker)
I'm going to try to go through my original and speed it up before I look
at yours. Then I'll look at this code and see how (if at all) similar
the two are.
Don Phillips wrote:
>
>>I'm glad you found it interesting. I was thinking about making a 3D
>>maze and decided a 2D one would be easier to start with.
>>I found an algorithm very similar to yours somewhere on the net (I can't
>>
>>remember where :( ) and decided to go for simplicity(?) over speed for
>>
>>the first draft. I plan on going back to increase the speed later, as
>>right now I have more time to wait for a program to run than I do to
>>develop it!
>>I am also going to make the maze printable and am working on a print
>>preview routine. (That should take me quite awhile!)
>>
>>Don Phillips wrote:
>>
>
>Yes, I found it very interesting. Its good to try something new every
>once in a while and optimizing this code was alot of fun. I was able to
>speed it up even further and reduce the code in the main loop quite a
>bit from the one I posted last. Also I was able to make the status
>indicator consistant in movement.
>
>I think I like this version the best. Not only is it faster, shorter,
>and easier to understand, I believe it makes better overall (and harder)
>mazes to solve.
>
>-=-=-=-=-=-=-=-=-=-
>
>without warning
>include Win32Lib.ew
>
>-- register controls with win32lib
>constant
>MainWin = create( Window, "Maze", NULL, 0.1, 0.1, 0.8, 0.8,
>or_all({WS_CLIPCHILDREN,WS_CLIPSIBLINGS}) ),
>Canvas = create( Window, "", MainWin, 0, 0, 1, 1,
>{WS_CHILD,WS_VISIBLE,WS_DLGFRAME,WS_CLIPCHILDREN,WS_CLIPSIBLINGS} ),
>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 globals
>sequence NewPos
>
>-- 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
>procedure makeMaze()
> integer Direction
> integer Index
> integer PosX
> integer PosY
> integer RoomsX
> integer RoomsY
> integer UsedRooms
> sequence Grid
> sequence Mask
> sequence Move
> sequence Path
> sequence Size
> sequence Slice
>
> -- clear screen
> repaintWindow( MainWin )
>
> -- get size of grid
> Size = value( getText(EditX) )
> RoomsX = Size[ 2 ]
> Size = value( getText(EditY) )
> RoomsY = Size[ 2 ]
>
> -- 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)} ))
<snip>
>
>
>
4. Re: To: Evan Marshall (Maze Maker)
- Posted by jluethje at gmx.de
Jun 07, 2002
Hello Don,
you wrote:
>> I'm glad you found it interesting. I was thinking about making a 3D
>> maze and decided a 2D one would be easier to start with.
>> I found an algorithm very similar to yours somewhere on the net (I can't
>>
>> remember where :( ) and decided to go for simplicity(?) over speed for
>>
>> the first draft. I plan on going back to increase the speed later, as
>> right now I have more time to wait for a program to run than I do to
>> develop it!
>> I am also going to make the maze printable and am working on a print
>> preview routine. (That should take me quite awhile!)
>>
>> Don Phillips wrote:
> Yes, I found it very interesting. Its good to try something new every
> once in a while and optimizing this code was alot of fun. I was able to
> speed it up even further and reduce the code in the main loop quite a
> bit from the one I posted last. Also I was able to make the status
> indicator consistant in movement.
> I think I like this version the best. Not only is it faster, shorter,
> and easier to understand, I believe it makes better overall (and harder)
> mazes to solve.
<snip>
Very nice program!
But I have a problem (under Windows 98):
When "Maze" has drawn a maze, and I then activate another program, so
that it's window lies (partly) over the drawing, and I switch back to
"Maze", the drawing is (partly) destroyed.
It looks, as if your program cannot "remember" the maze that it has
drawn.
Best regards,
Juergen
5. Re: To: Evan Marshall (Maze Maker)
>Very nice program!
>
>But I have a problem (under Windows 98):
>When "Maze" has drawn a maze, and I then activate another program, so
>that it's window lies (partly) over the drawing, and I switch back to
>"Maze", the drawing is (partly) destroyed.
>
>It looks, as if your program cannot "remember" the maze that it has
>drawn.
>
>Best regards,
> Juergen
Tis true, I just threw it out there kinda bare bones to show the enhanced
algorithm. It is drawing directly to the main window, but not on a paint
event so its not smart enough to redraw itself. It only draws when you
click the button. This of course is an easy enough fix if you need it.
Just make the calls (like the original) to a pixmap and on a paint event
bitblt it to the screen.
6. Re: To: Evan Marshall (Maze Maker)
Hello Don,
you wrote:
<snip>
> Tis true, I just threw it out there kinda bare bones to show the
> enhanced algorithm. It is drawing directly to the main window, but
> not on a paint event so its not smart enough to redraw itself. It
> only draws when you click the button. This of course is an easy
> enough fix if you need it.
> Just make the calls (like the original) to a pixmap and on a paint
> event bitblt it to the screen.
Thanks.
Best regards,
Juergen
7. Re: To: Evan Marshall (Maze Maker)
<html>
<head>
</head>
<body>
Oops. I forgot to redraw it. I will put that in next version.<br>
<br>
<br>
<br>
<a class="moz-txt-link-abbreviated" href="mailto:jluethje at gmx.de">jluethje at
gmx.de</a> wrote:<br>
<blockquote type="cite" cite="mid:0.1700008810.1346263749-1463792382-1023466229
at topica.com">
<blockquote type="cite">
<pre wrap="">I'm glad you found it interesting. I was thinking about
making a 3D<br>maze and decided a 2D one would be easier to start with.<br>I
found an algorithm very similar to yours somewhere on the net (I can't
<br><br>remember where :( ) and decided to go for simplicity(?) over speed for
<br><br>the first draft. I plan on going back to increase the speed later, as
<br>right now I have more time to wait for a program to run than I do to
<br>develop it!<br>I am also going to make the maze printable and am working on a
print <br>preview routine. (That should take me quite awhile!)<br><br>Don
Phillips wrote:<br></pre>
</blockquote>
</blockquote>
<pre wrap=""><!----><br></pre>
<blockquote type="cite">
<pre wrap="">Yes, I found it very interesting. Its good to try
something new every <br>once in a while and optimizing this code was alot of fun.
I was able to <br>speed it up even further and reduce the code in the main loop
quite a <br>bit from the one I posted last. Also I was able to make the status
<br>indicator consistant in movement.<br></pre>
</blockquote>
<pre wrap=""><!----><br></pre>
<blockquote type="cite">
<pre wrap="">I think I like this version the best. Not only is it
faster, shorter, <br>and easier to understand, I believe it makes better overall
(and harder) <br>mazes to solve.<br></pre>
</blockquote>
