Maze generation
» > >
»
» View previous topic :: View next topic  
I have recently made a random maze generation program, using the depth first search method, ( http://www.mazeworks.com/mazegen/mazetut/index.htm ) and it runs quite nicely, without a hitch, but is ungodly slow. Would anybody mind posting any Maze generation program you may have or anything, /me wansta know how to make mine better. Thanks Homies.
Yay you got it working! Very Happy I'll try it out.
Its been working for 3 days now. i have no idea why yours wasnt.
Mine? I didn't make one. The one you sent me didn't work though.
Edit: Oh I thought you linked to yours. Oops...
Yours as in the one I sent you.
Just a minute... let me post the code I used in my project...

here it is (note, I removed some stuff that I used only because I needed it for my 3d maze game. Also, if you wanted to, you could change this so it only uses the graph screen and no matrix, I needed that because I needed this to work for my matrix engine and also so I could convert it to string easily.)

Code:

:ClrHome
:ClrDraw
:GridOff
:AxesOff
:0→Xmin
:94→Xmax
:1→XScl
:0→Ymin
:62→YMax
:1→YScl
:Input "ATTEMPTS:",A
:Repeat H>9 and H<51
:Input "HEIGHT:",H
:End
:Repeat L>9 and L<96
:Input "LENGTH:",Str0
:If not(length(Str0)<2:Then
:sub(Str0,1,2)→Y1
:Else
:"9→Y1
:End
:Y1→L
:DelVar Y1
:End
:{H,L→dim([J]
:Fill 1,[J]
:For(X,1,L
:Line(X,61,X,62-H
:End
:randInt(2,L-1→X
:randInt(2,H-1→Z
:Pxl-Off(Z,X
:0→[J](Z,X
:DelVar PDelVar RDelVar L2DelVar SDelVar TDelVar U
:100→dim(L2
:Repeat R
:Text(55,2,P,"    ",T,"-",S,"       ",U,"     
:DelVar L1
:4→dim(L1
:If X>3:Then
:If [J](Z,X-2:1→L1(1:End
:If Z>3:Then
:If [J](Z-2,X:1→L1(2:End
:If X<L-2:Then
:If [J](Z,X+2:1→L1(3:End
:If Z<H-2:Then
:If [J](Z+2,X:1→L1(4:End
:cumSum(L1
:If Ans(4) or P:Then
:DelVar V
:Repeat V>A or L1(D
:V+1→V
:randInt(1,4→D
:End
:If L1(D:DelVar V
:If V>A and P:Then
:L2(P→D
:0→L2(P
:P-1→P
:X+2(D=1→X
:Z+2(D=2→Z
:X-2(D=3→X
:Z-2(D=4→Z
:DelVar D
:End
:If D=1 and X>3:Then
:P+1→P
:1→L2(P
:Pxl-Off(Z,X-1
:Pxl-Off(Z,X-2
:0→[J](Z,X-1
:X-2→X
:0→[J](Z,X
:End
:If D=2 and Z>3:Then
:P+1→P
:2→L2(P
:Pxl-Off(Z-1,X
:Pxl-Off(Z-2,X
:0→[J](Z-1,X
:Z-2→Z
:0→[J](Z,X
:End
:If D=3 and X<L-2:Then
:P+1→P
:3→L2(P
:Pxl-Off(Z,X+1
:Pxl-Off(Z,X+2
:0→[J](Z,X+1
:X+2→X
:0→[J](Z,X
:End
:If D=4 and Z<H-2:Then
:P+1→P
:4→L2(P
:Pxl-Off(Z+1,X
:Pxl-Off(Z+2,X
:0→[J](Z+1,X
:Z+2→Z
:0→[J](Z,X
:End
:If P>U:Then
:P→U
:X→S
:Z→T
:End
:Else
:1→R
:End
:End
:ClrDraw


If something doesn't work its because I accidentally deleted to much Laughing


IIRC, it starts out, and then chooses random directions and tries random directions for the inputed number of attemps (more = more winding passages). If it doesn't go forward in those attemps, it backtracks one and tries again. It will then continue back-tracking until it reaches the beginning and can't go anywhere. It produces pretty good mazes actually =D (No idea if this is what you used, I pretty much made it up myself Wink - although someone has probably thought of it before =D )
Any fool can use a computer. Many do.





It seems like a version of the DFS method, but with a selectable when-to-start-backtracking rate. I usually keep mine at if after 8 loops it doesnt find a way, it starts backtracking, and checking each square 8 times.

EDIT: Harq, that code wont stop asking me for the length. lol.
Pseudoprogrammer wrote:
EDIT: Harq, that code wont stop asking me for the length. 0x5.


Be sure you entered the if correctly, 9 < L < 96
Any fool can use a computer. Many do.





T'was copied n pasted foo. lol.
See this code?


Code:

:Repeat H>9 and H<51
:Input "HEIGHT:",H   ;straight forward, gets the height
:End
:Repeat L>9 and L<96  ;if to make sure the length is between 10 and 95
:Input "LENGTH:",Str0
:If not(length(Str0)<2  ;Then if the value from the last line is 2 digits
:sub(Str0,1,2)→Y1 ;store it to Y1 so I can work with it =P
:Else ;otherwise
:"9→Y1 ;store 9 to Y1 which is then stored to L which makes it false.
:End
:Y1→L
:DelVar Y1 ;clears Y1
:End ;loops back to length repeat
:{H,L→dim([J]
:Fill 1,[J]
:For(X,1,L
:Line(X,61,X,62-H
:End


I have no earthly idea what it does anymore besides bounds checking

Anyways, just enter 10 and 10 for both and tell me what happens...

EDIT: Nevermind, I have it, let me comment it for you =P
Any fool can use a computer. Many do.





It just keeps saying input length.
Pseudoprogrammer wrote:
It just keeps saying input length.


o.O There is nothing wrong with that code, I went back and commented it for you!
Any fool can use a computer. Many do.






Code:
:ClrHome
:ClrDraw
:GridOff
:AxesOff
:0→Xmin
:94→Xmax
:1→XScl
:0→Ymin
:62→YMax
:1→YScl
:Input "ATTEMPTS:",A
:Repeat H>9 and H<51
:¦ Input "HEIGHT:",H
:End
:Repeat L>9 and L<96
:¦ Input "LENGTH:",Str0
:¦ If not(length(Str0)<2:Then
:¦ ¦ sub(Str0,1,2)→Y1
:¦ ¦ Else
:¦ ¦ "9→Y1
:¦ End
:¦ Y1→L
:¦ DelVar Y1
:End
:{H,L→dim([J]
:Fill 1,[J]
:For(X,1,L
:¦ Line(X,61,X,62-H
:End
:randInt(2,L-1→X
:randInt(2,H-1→Z
:Pxl-Off(Z,X
:0→[J](Z,X
:DelVar PDelVar RDelVar L2DelVar SDelVar TDelVar U
:100→dim(L2
:Repeat R
:¦ Text(55,2,P,"    ",T,"-",S,"       ",U,"     
:¦ DelVar L1
:¦ 4→dim(L1
:¦ If X>3:Then
:¦ ¦ If [J](Z,X-2:1?L1(1:End
:¦ If Z>3:Then
:¦ ¦ If [J](Z-2,X:1?L1(2:End
:¦ If X<L-2:Then
:¦ ¦ If [J](Z,X+2:1?L1(3:End
:¦ If Z<H-2:Then
:¦ ¦ If [J](Z+2,X:1?L1(4:End
:¦ cumSum(L1
:¦ If Ans(4) or P:Then
:¦ ¦ DelVar V
:¦ ¦ Repeat V>A or L1(D
:¦ ¦ ¦ V+1→V
:¦ ¦ ¦ randInt(1,4→D
:¦ ¦ End
:¦ ¦ If L1(D:DelVar V
:¦ ¦ If V>A and P:Then
:¦ ¦ ¦ L2(P→D
:¦ ¦ ¦ 0→L2(P
:¦ ¦ ¦ P-1→P
:¦ ¦ ¦ X+2(D=1→X
:¦ ¦ ¦ Z+2(D=2→Z
:¦ ¦ ¦ X-2(D=3→X
:¦ ¦ ¦ Z-2(D=4?Z
:¦ ¦ ¦ DelVar D
:¦ ¦ End
:¦ ¦ If D=1 and X>3:Then
:¦ ¦ ¦ P+1→P
:¦ ¦ ¦ 1→L2(P
:¦ ¦ ¦ Pxl-Off(Z,X-1
:¦ ¦ ¦ Pxl-Off(Z,X-2
:¦ ¦ ¦ 0→[J](Z,X-1
:¦ ¦ ¦ X-2→X
:¦ ¦ ¦ 0→[J](Z,X
:¦ ¦ End
:¦ ¦ If D=2 and Z>3:Then
:¦ ¦ ¦ P+1→P
:¦ ¦ ¦ 2→L2(P
:¦ ¦ ¦ Pxl-Off(Z-1,X
:¦ ¦ ¦ Pxl-Off(Z-2,X
:¦ ¦ ¦ 0→[J](Z-1,X
:¦ ¦ ¦ Z-2→Z
:¦ ¦ ¦ 0→[J](Z,X
:¦ ¦ End
:¦ ¦ If D=3 and X<L-2:Then
:¦ ¦ ¦ P+1→P
:¦ ¦ ¦ 3→L2(P
:¦ ¦ ¦ Pxl-Off(Z,X+1
:¦ ¦ ¦ Pxl-Off(Z,X+2
:¦ ¦ ¦ 0→[J](Z,X+1
:¦ ¦ ¦ X+2→X
:¦ ¦ ¦ 0→[J](Z,X
:¦ ¦ End
:¦ ¦ If D=4 and Z<H-2:Then
:¦ ¦ ¦ P+1→P
:¦ ¦ ¦ 4→L2(P
:¦ ¦ ¦ Pxl-Off(Z+1,X
:¦ ¦ ¦ Pxl-Off(Z+2,X
:¦ ¦ ¦ 0?[J](Z+1,X
:¦ ¦ ¦ Z+2→Z
:¦ ¦ ¦ 0→[J](Z,X
:¦ ¦ End
:¦ ¦ If P>U:Then
:¦ ¦ ¦ P→U
:¦ ¦ ¦ X→S
:¦ ¦ ¦ Z→T
:¦ ¦ End
:¦ ¦ Else
:¦ ¦ 1→R
:¦ End
:End
I repeat... the code in that area is fine Very Happy

I can't double check it because I have lost my calc, and doubt I will find it, but it looks fine and that is what I entered...
Any fool can use a computer. Many do.





I would be interested to know how this can be adapted to old style RPG's like Rogue or Nethack. The basic idea is that you have several solution paths and remove all other cells, then place rooms so that they are adjacent to the path.
The light at the end of the tunnel is an oncoming dragon.
Give a man a fire, he'll be warm for a day; set fire to him, he'll be warm for the rest of his life.
Read the Smart Questions FAQ - they helped me!
Harq wrote:
Just a minute... let me post the code I used in my project...

here it is (note, I removed some stuff that I used only because I needed it for my 3d maze game. Also, if you wanted to, you could change this so it only uses the graph screen and no matrix, I needed that because I needed this to work for my matrix engine and also so I could convert it to string easily.)

Code:

:ClrHome
:ClrDraw
:GridOff
:AxesOff
:0→Xmin
:94→Xmax
:1→XScl
:0→Ymin
:62→YMax
:1→YScl
:Input "ATTEMPTS:",A
:Repeat H>9 and H<51
:Input "HEIGHT:",H
:End
:Repeat L>9 and L<96
:Input "LENGTH:",Str0
:If not(length(Str0)<2:Then
:sub(Str0,1,2)→Y1
:Else
:"9→Y1
:End
:Y1→L
:DelVar Y1
:End
:{H,L→dim([J]
:Fill 1,[J]
:For(X,1,L
:Line(X,61,X,62-H
:End
:randInt(2,L-1→X
:randInt(2,H-1→Z
:Pxl-Off(Z,X
:0→[J](Z,X
:DelVar PDelVar RDelVar L2DelVar SDelVar TDelVar U
:100→dim(L2
:Repeat R
:Text(55,2,P,"    ",T,"-",S,"       ",U,"     
:DelVar L1
:4→dim(L1
:If X>3:Then
:If [J](Z,X-2:1→L1(1:End
:If Z>3:Then
:If [J](Z-2,X:1→L1(2:End
:If X<L-2:Then
:If [J](Z,X+2:1→L1(3:End
:If Z<H-2:Then
:If [J](Z+2,X:1→L1(4:End
:cumSum(L1
:If Ans(4) or P:Then
:DelVar V
:Repeat V>A or L1(D
:V+1→V
:randInt(1,4→D
:End
:If L1(D:DelVar V
:If V>A and P:Then
:L2(P→D
:0→L2(P
:P-1→P
:X+2(D=1→X
:Z+2(D=2→Z
:X-2(D=3→X
:Z-2(D=4→Z
:DelVar D
:End
:If D=1 and X>3:Then
:P+1→P
:1→L2(P
:Pxl-Off(Z,X-1
:Pxl-Off(Z,X-2
:0→[J](Z,X-1
:X-2→X
:0→[J](Z,X
:End
:If D=2 and Z>3:Then
:P+1→P
:2→L2(P
:Pxl-Off(Z-1,X
:Pxl-Off(Z-2,X
:0→[J](Z-1,X
:Z-2→Z
:0→[J](Z,X
:End
:If D=3 and X<L-2:Then
:P+1→P
:3→L2(P
:Pxl-Off(Z,X+1
:Pxl-Off(Z,X+2
:0→[J](Z,X+1
:X+2→X
:0→[J](Z,X
:End
:If D=4 and Z<H-2:Then
:P+1→P
:4→L2(P
:Pxl-Off(Z+1,X
:Pxl-Off(Z+2,X
:0→[J](Z+1,X
:Z+2→Z
:0→[J](Z,X
:End
:If P>U:Then
:P→U
:X→S
:Z→T
:End
:Else
:1→R
:End
:End
:ClrDraw


If something doesn't work its because I accidentally deleted to much 0x5


IIRC, it starts out, and then chooses random directions and tries random directions for the inputed number of attemps (more = more winding passages). If it doesn't go forward in those attemps, it backtracks one and tries again. It will then continue back-tracking until it reaches the beginning and can't go anywhere. It produces pretty good mazes actually =D (No idea if this is what you used, I pretty much made it up myself Wink - although someone has probably thought of it before =D )


On the line :{H,L→dim([J] I get a syntax error at the [J] part. any help?
Epic necropost. Yes that is called a depth first search. But a more optimized version of that would check to see all squares around the current location, and pick a random one from that, instead of just picking random squares. I made a maze generator back in novemember that generates 16x16 mazes in <2 seconds.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Maze generation
»
» View previous topic :: View next topic  
Page 1 of 1
» All times are UTC - 5 Hours
 
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
You cannot vote in polls in this forum

 

Advertisement