It is currently Wed Jun 20, 2018 6:19 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 9 posts ] 
Author Message
 Post subject: Maze generator (randomized Depth-first search)
PostPosted: Sat Mar 03, 2018 1:27 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Thu Apr 30, 2009 5:23 pm
Posts: 249
Location: Côtes d'Azur, France
Read https://en.wikipedia.org/wiki/Maze_gene ... rst_search

Edit: change #Delay constant to make it faster or slower.

Code:
#delay=70 ;milliseconds: reduce this value to make it faster
#mapsize=60
#size=10
;colors
#Black0=$000000
#White0=$FFFFFF
#Red0=$0000FF
#Blue0=$FF0000
If InitSprite() = 0 Or InitKeyboard() = 0 Or InitMouse() = 0 Or OpenWindow(0, 0, 0, #mapsize*#size, #mapsize*#size, "Maze generator", #PB_Window_SystemMenu | #PB_Window_ScreenCentered)=0 Or OpenWindowedScreen(WindowID(0),0,0,#mapsize*#size,#mapsize*#size,0,0,0,#PB_Screen_NoSynchronization)=0
   MessageRequester("Error", "Can't open the sprite system", 0)
   End
EndIf
Structure stack
   x.i
   y.i
EndStructure
Dim carte.b(#mapsize,#mapsize)
NewList stack.stack()
Dim dir.stack(3)
Dim dir2.b(3,1)
CreateSprite(0,#mapsize*#size,#mapsize*#size)
StartDrawing(SpriteOutput(0))
FillArea(10,10,#White)
StopDrawing()
CreateSprite(1,#size-2,#size-2)
StartDrawing(SpriteOutput(1))
Box(0,0,#size-2,#size-2,#Red)
StopDrawing()
dir(0)\x=0:dir(0)\y=-1:dir(1)\x=1:dir(1)\y=0
dir(2)\x=0:dir(2)\y=1:dir(3)\x=-1:dir(3)\y=0
dir2(0,0)=%0111:dir2(1,0)=%1011:dir2(2,0)=%1101:dir2(3,0)=%1110
dir2(0,1)=%1101:dir2(1,1)=%1110:dir2(2,1)=%0111:dir2(3,1)=%1011
For j.i=0 To #mapsize-1
   For i.i=0 To #mapsize-1
      xx.i=i*#size:yy.i=j*#size
      carte(i,j)=%1111
      If i=0 Or j=0 Or i=#mapsize-1 Or j=#mapsize-1:carte(i,j)=0:EndIf
   Next i
Next j
x.i=1:y.i=1:color.i=#Red0
Repeat
   Repeat:Until WindowEvent()=0
   Delay(#delay)
   FlipBuffers()
   ClearScreen(#Black0)
   ExamineKeyboard():If KeyboardPushed(#PB_Key_Escape):End:EndIf
   ;draw maze
   StartDrawing(SpriteOutput(0))
   xx=x*#size:yy=y*#size
   If carte(x,y) & %1000
      LineXY(xx,yy,xx+#size,yy,#Black0)
   Else
      LineXY(xx+1,yy,xx+#size-1,yy,#White0)
   EndIf   
   If carte(x,y) & %0100
      LineXY(xx+#size,yy,xx+#size,yy+#size,#Black0)
   Else
      LineXY(xx+#size,yy+1,xx+#size,yy+#size-1,#White0)
   EndIf   
   If carte(x,y) & %0010
      LineXY(xx+#size,yy+#size,xx,yy+#size,#Black0)
   Else
      LineXY(xx+#size-1,yy+#size,xx+1,yy+#size,#White0)
   EndIf   
   If carte(x,y) & %0001
      LineXY(xx,yy+#size,xx,yy,#Black0)
   Else
      LineXY(xx,yy+#size-1,xx,yy+1,#White0)
   EndIf
   StopDrawing()   
   DisplaySprite(0,0,0)
   DisplayTransparentSprite(1,x*#size+1,y*#size+1,255,color)
   color=#Red0
   ;test 4 directions
   If carte(x,y-1)<%1111 And carte(x+1,y)<%1111 And carte(x,y+1)<%1111 And carte(x-1,y)<%1111
      ;regression in stack
      x=stack()\x:y=stack()\y
      DeleteElement(stack())
      ;save picture when maze is completed
      If ListSize(stack())=0:SaveSprite(0,"maze.bmp"):End:EndIf
      color=#Blue0
      Continue
   EndIf
   ;choose a direction
   Repeat
      direction.i=Random(3)
   Until x+dir(direction)\x>0 And x+dir(direction)\x<#mapsize-1 And y+dir(direction)\y>0 And y+dir(direction)\y<#mapsize-1 And carte(x+dir(direction)\x,y+dir(direction)\y)=%1111
   ;delete previous wall
   carte(x,y)=carte(x,y) & dir2(direction,0)
   ;add to the stack
   AddElement(stack())
   stack()\x=x:stack()\y=y
   x=x+dir(direction)\x:y=y+dir(direction)\y
   ;delete wall
   carte(x,y)=carte(x,y) & dir2(direction,1)
ForEver

_________________
There are 2 methods to program bugless.
But only the third works fine.


Last edited by Fig on Sat Mar 03, 2018 7:39 pm, edited 3 times in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: Maze generator (randomized Depth-first search)
PostPosted: Sat Mar 03, 2018 1:46 pm 
Offline
Addict
Addict

Joined: Mon Feb 16, 2015 2:49 pm
Posts: 1418
It's very mesmerising to watch. :) Good stuff.

Fig wrote:
It's slow on purpose.

Can it be made faster? I see no delays in the code to change.


Top
 Profile  
Reply with quote  
 Post subject: Re: Maze generator (randomized Depth-first search)
PostPosted: Sat Mar 03, 2018 2:11 pm 
Offline
Addict
Addict

Joined: Fri Nov 09, 2012 11:04 pm
Posts: 1575
Location: Uttoxeter, UK
@Fig,
Interesting. Thank you.
It would be nice if the speed could be controlled by the user: I would like to see it even slower to fully appreciate what is going on.

_________________
DE AA EB


Top
 Profile  
Reply with quote  
 Post subject: Re: Maze generator (randomized Depth-first search)
PostPosted: Sat Mar 03, 2018 5:02 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Wed Sep 22, 2010 1:17 pm
Posts: 261
Location: United Kingdom
davido wrote:
@Fig,
It would be nice if the speed could be controlled by the user: I would like to see it even slower to fully appreciate what is going on.

Add this after the escape key test.
Code:
If KeyboardPushed(#PB_Key_Up) And z > 0:z - 1:EndIf
If KeyboardPushed(#PB_Key_Down):z + 1:EndIf

And this before ForEver.
Code:
Delay(z)

Down to slow down, up to speed up.


Top
 Profile  
Reply with quote  
 Post subject: Re: Maze generator (randomized Depth-first search)
PostPosted: Sat Mar 03, 2018 7:25 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Thu Apr 30, 2009 5:23 pm
Posts: 249
Location: Côtes d'Azur, France
It was slow by design: I displayed all cells each loop.
I changed the code. Now, only one cell each loop is updated.
#Delay constant makes it faster or slower.

When the cursor gets back, it changes its color to blue.
It's easyer to understand what's going on this way.

When completed, the maze picture is saved.

Thank you for your comments.

_________________
There are 2 methods to program bugless.
But only the third works fine.


Top
 Profile  
Reply with quote  
 Post subject: Re: Maze generator (randomized Depth-first search)
PostPosted: Sat Mar 03, 2018 10:54 pm 
Offline
Addict
Addict

Joined: Fri Nov 09, 2012 11:04 pm
Posts: 1575
Location: Uttoxeter, UK
@spikey,
@Fig,

Thank you, both, very much. :D

_________________
DE AA EB


Top
 Profile  
Reply with quote  
 Post subject: Re: Maze generator (randomized Depth-first search)
PostPosted: Sun Mar 04, 2018 5:16 am 
Offline
Enthusiast
Enthusiast

Joined: Mon May 10, 2010 4:02 pm
Posts: 136
Thank you


Top
 Profile  
Reply with quote  
 Post subject: Re: Maze generator (randomized Depth-first search)
PostPosted: Sun Mar 04, 2018 9:38 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Thu Apr 30, 2009 5:23 pm
Posts: 249
Location: Côtes d'Azur, France
Dude wrote:
It's very mesmerising to watch.

I guess you was looking for a...maze..ing ? :mrgreen:

_________________
There are 2 methods to program bugless.
But only the third works fine.


Top
 Profile  
Reply with quote  
 Post subject: Re: Maze generator (randomized Depth-first search)
PostPosted: Tue Mar 06, 2018 11:55 am 
Offline
Moderator
Moderator
User avatar

Joined: Thu Dec 31, 2009 11:05 pm
Posts: 558
Location: Berlin and Ibiza
Very nice. Image

_________________
ImageImageImageImage


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 9 posts ] 

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye