phillip1882 Posted April 9, 2009 Report Share Posted April 9, 2009 so i was reading this programming challenges website and i came across an interesting one. write an algorithm that generates mazes. now that was a good challenge. sufficiently difficult for me, but not overly difficult that i couldn't code it.here's the approach i took. mark each cell in the maze as unvisited, and surrounded by walls.start on the left side, and look for any unvisited neighbours. if 1 or more exist randomly go to one of the neighbours, destroying the wall between them. mark the the cell you were just at as a possible backtrack node. continue going from the new cell untill you block yourself in. then go to the nearest backtrack cell with 1 or more unvisited neighbours, and continue from there. keep doing this until you backtrack all the way to the start node with 0 unvisited neighbours. the maze is compete, just set any cell on the right side to the exit.here is the code. import random import sys def mazecreator(hor,ver): visit = [[0]*hor for i in range(ver)] wall = [[15]*hor for i in range(ver)] start = random.randint(0,ver-1) visit[start][0] = 1 backtrack = [[start,0]] wall[start][0] = 7 posy = start posx = 0 nieghbors = getnieghbors(visit,start,0) while posy != start or posx != 0 or len(nieghbors) >0: prevx = posx prevy = posy if posx <0 or posy<0: break if len(nieghbors) >0: direction = random.randint(0,len(nieghbors)-1) posx = nieghbors[direction][1] posy = nieghbors[direction][0] visit[posy][posx] = 1 if prevx <posx: wall[prevy][prevx] = wall[prevy][prevx] -4 wall[posy][posx] = wall[posy][posx] -8 elif prevx>posx: wall[prevy][prevx] = wall[prevy][prevx]-8 wall[posy][posx] = wall[posy][posx]-4 elif prevy<posy: wall[prevy][prevx] = wall[prevy][prevx]-1 wall[posy][posx] = wall[posy][posx] -2 else: wall[prevy][prevx] = wall[prevy][prevx] -2 wall[posy][posx] = wall[posy][posx] -1 nieghbors = getnieghbors(visit,posy,posx) if len(nieghbors) >1: backtrack = backtrack +[[posy,posx]] if len(nieghbors) == 0: while len(nieghbors) == 0 and len(backtrack) >0: posx = backtrack[len(backtrack)-1][1] posy = backtrack[len(backtrack)-1][0] del backtrack[len(backtrack)-1] nieghbors = getnieghbors(visit,posy,posx) for i in range(0,len(wall[0])): print " _", ; sys.stdout.softspace=0 print " " exit = len(wall)-start for i in range(0,len(wall)): for j in range(0,len(wall[0])): if wall[i][j] >= 8: if wall[i][j]%2 == 1: print "|_", ; sys.stdout.softspace=0 else: print "| ", ; sys.stdout.softspace=0 if wall[i][j] < 8: if wall[i][j] %2 == 0: print " ", ; sys.stdout.softspace=0 else: print " _", ; sys.stdout.softspace=0 if i != exit: print "|" else: print "" def getnieghbors(visit,posver,poshor): around = [] if posver > 0 and visit[posver-1][poshor] == 0: around = [[posver-1,poshor]] if posver < len(visit)-1 and visit[posver+1][poshor] ==0: around = around +[[posver+1,poshor]] if poshor >0 and visit[posver][poshor-1] == 0: around = around +[[posver,poshor-1]] if poshor <len(visit[0])-1 and visit[posver][poshor+1] == 0: around = around +[[posver,poshor+1]] return around horizontal = int(raw_input("how wide would you like the maze? ")) vertical = int(raw_input("how high would you like the maze? ")) mazecreator(horizontal,vertical) CraigD 1 Quote Link to comment Share on other sites More sharing options...
CraigD Posted April 10, 2009 Report Share Posted April 10, 2009 Maze generator programs are very cool! :confused: I’m glad to see programmers still writing them. I got acquainted with them around 1980, when a commercial version of one – a pretty version that let you wander around the interior of a “garden maze” - appeared for the Apple II computers that filled the lab I worked in appeared. As with most commercial Apple software of that day, it was in the form of AppleSoft BASIC, allowing you to read the code and figure out how it worked, so I never had your experience, Phillip, of inventing my first maze algorithm on my own – though I came up with lots of variations on the theme then and over the years to come, on various languages and platforms. The kind of maze you’ve described and coded for is a kind I first called “single branch”, and later learned is more commonly called “simply connected” or just “simple”. It’s defining characteristics areThere’s only one shortest path between any to points in it. It’s “loop free”.You can find the path between any two points by “hugging the right (or left) wall”, what’s sometimes know as the “right wall rule”, or “right’s the rule”, a well-known folk algorithm among maze puzzle enthusiast dating back centuries, and more recently, among FRPGer, who on occasion need to systematically explore mazes in the course of a game.You can easily make a simply connected maze complexly connected by making a few random connections (wall removals) to the completed maze. Here’s my currently on-hand one, a collection of little library entries of MUMPS xecute code. This is the code that actually generates a maze:n (XSBMIS,R,C) k C x XSBMIS(1),XSBMIS(2) s C=R ;XSBMIS: create random square connection space of dimension R=d1,d2[,d3 ...] s P=$l(R,","),$p(C,"1,",P)=1,C(0,C)="" f s I=$p(C,",",P)+1,F=I>$p(R,",",P) s:'F $p(C,",",P)=I,C(0,C)="",P=$l(R,",") i F s $p(C,",",P)=1,P=P-1 q:'P ;XSBMIS(1) s C="" f s C=$o(C(0,C)) q:C="" k C(0,C) f D=-1,1 f P=1:1:$l(R,",") s C2=C,$p(C2,",",P)=$p(C,",",P)+D s:$d(C(0,C2)) C(0,C,C2)="" ;XSBMIS(2) n (XSBM1,C) k C(1),C(2) m C(1)=C(0) f x XSBM1(2),XSBM1(1):$d(C(1,C)) i '$d(C(1,C)) x XSBM1(2) s CI=C,C=$g(C(3,CI)) k C(3,CI) q:C="" ;XSBM1: fill space C(2) per C(1) & single branch maze rule s C2="" f I=-1,$r(T) f T=0:1 s C2=$o(C(1,C,C2)) q:'C2 i T=I k C(1,C,C2),C(1,C2,C) s (C(2,C,C2),C(2,C2,C))="",C(3,C2)=C,C=C2 q ;XSBM1(1): find and connect C to random C2 s CI="" f s CI=$o(C(0,C,CI)) q:CI="" k C(1,CI,C) ;XSBM1(2): remove connections to C s R="38,11" x XSBMIS,XSBM1This example generates a 38x11 2-dimensional square maze (regular triangle or hexagon-tiled mazes are also fun, and can be generated with a small change to the only the XSBMIS part of this code). 38x11 is a nice size, as draws with ASCII characters, it just fits on a 80x24 screen with room for labels. The code can generate mazes in any number of dimensions (eg: R=”9,9,9” for 3-D, or R=”9,9,9,5,5” for 5-D), though drawing mazes in more than 3 dimensions requires some trickery. Here’s MUMPS code that draws the generated 2-D maze:n (XMB2S,C) w " " x XMB2S(1),XMB2S(2) w !," ",$tr($j("",C9*2+1)," ","X") f C2=1:1:$p(C9,",",2) f M=0,1 w !,$s(M:" ",1:C2#10)," X" f C1=1:1:C9 w $s(M:$s($d(C(2,C1_","_C2,C1_","_(C2+1))):" ",1:"X")_"X",1:" "_$s($d(C(2,C1_","_C2,C1+1_","_C2)):" ",1:"X")) ;XMB2S: output 2-d square XSBM-type maze s (C1,C9)="" f s C1=$o(C(0,C1)) q:C1="" zt:$l(C1,",")-2 s:C1>C9 $p(C9,",")=+C1 s:$p(C1,",",2)>$p(C9,",",2) $p(C9,",",2)=$p(C1,",",2) ;XMB2S(1) f C1=1:1:C9 w $j(C1#10,2) ;XMB2S(2) x XMB2Sand its output[font="Fixedsys"][noparse] 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 1 X X X X X X X X X X X X X X X XXX X XXXXXXX X XXXXX X XXX X XXXXX X XXXXX XXX XXX X XXXXX XXXXXXX X 2 X X X X X X X X X X X X X X X X X X X X X XXX XXX X X XXX X XXXXXXXXXXXXXXX XXX X XXX XXX XXX XXX XXXXXXX XXXXX X X X 3 X X X X X X X X X X X X X X X X X X X X X X X XXX X X X X X X X X X XXX XXX X X X XXXXXXX XXXXX XXX XXXXXXXXXXXXXXXXX X 4 X X X X X X X X X X X X X X X X X X X X X X XXXXXXXXX X X XXX X XXXXXXXXX XXX X X X X X XXXXX XXX XXX X XXXXXXX X XXX X 5 X X X X X X X X X X X X X X X X X X X X X X XXXXX X X XXX X XXXXX X X XXX XXX XXXXXXXXXXX XXX X X XXXXX XXX XXXXX XXX 6 X X X X X X X X X X X X X X X X X X X X X X X X XXXXXXXXXXX XXX X XXX XXX XXXXX X X XXX XXX X XXXXXXXXX XXX X XXX X X X 7 X X X X X X X X X X X X X X X X X X X X XXX XXX X X X XXXXX XXXXXXX X XXX X X XXXXXXXXX XXXXX X X X XXXXXXXXX X XXX X 8 X X X X X X X X X X X X X X X X X X X X XXX X XXX X XXXXX X XXXXXXXXXXXXX XXX X XXXXXXXXX X XXX X XXXXXXX X X XXXXX 9 X X X X X X X X X X X X X X X X X X X X X XXXXXXXXXXX X X XXX X XXX X X XXXXX X X X XXX X XXX X XXXXXXXXX X X XXXXX X 0 X X X X X X X X X X X X X X X X X X X X X XXXXXXXXX XXX XXX XXXXX XXXXX X XXXXXXXXXXX X XXXXXXXXX X XXX XXX XXX XXXXX 1 X X X X X X X X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX[/noparse][/font]As a homage to that Apple program I discovered back in the 1980s, here’s code that shows the maze from the inside and lets you move around with arrow keys (in a DEC VT-equivalent terminal):n (XME2S,C) s:'$g(C) C="1,1" s:'$g(C(4.1)) C(4.1)="1,2",C(4.2)="-1,1" f x XME2S(1),XME2S(2),XME2S(2.1),XME2S(3) q:R=13 ;XME2S: explore interior of 2d square maze S P1=C(4.1),P2=$p(P1,",",2),I1=C(4.2),I2=$p(I1,",",2),C1=C,$p(C1,",",P1)=$p(C,",",P1)-I1,DL=$d(C(2,C,C1)),$p(C1,",",P1)=$p(C,",",P1)+I1,DR=$d(C(2,C,C1)),C1=C,$p(C1,",",P2)=$p(C,",",P2)+I2,D1=$d(C(2,C,C1)),(D1L,D1R,D2,D2L,D2R,D3)=0 i D1 s C2=C1,$p(C2,",",P1)=$p(C1,",",P1)-I1,D1L=$d(C(2,C1,C2)),$p(C2,",",P1)=$p(C1,",",P1)+I1,D1R=$d(C(2,C1,C2)),C2=C1,$p(C2,",",P2)=$p(C2,",",P2)+I2,D2=$d(C(2,C1,C2)) i D2 s C1=C2,$p(C2,",",P1)=$p(C1,",",P1)-I1,D2L=$d(C(2,C1,C2)),$p(C2,",",P1)=$p(C1,",",P1)+I1,D2R=$d(C(2,C1,C2)),C2=C1,$p(C2,",",P2)=$p(C2,",",P2)+I2,D3=$d(C(2,C1,C2)) ;XME2S(1): get connections k W s (W(0),W(1))="XXX",$e(W(0),2)="+" ;XME2S(1,-2) s C1=C,$p(C1,",",C(4.1))=$p(C,",",C(4.1))-C(4.2) i $d(C(2,C,C1)) s $e(W(0))=" " ;XME2S(1,-1) s C1=C,$p(C1,",",$p(C(4.1),",",2))=$p(C,",",$p(C(4.1),",",2))+$p(C(4.2),",",2) i $d(C(2,C,C1)) s $e(W(1),2)=" ",(W(2),W(3))="XXX",$e(W(2),2)=" " x XME2S(1,0,-1),XME2S(1,0,0),XME2S(1,0,1) ;XME2S(1,0) s C2=C1,$p(C2,",",C(4.1))=$p(C1,",",C(4.1))-C(4.2) i $d(C(2,C1,C2)) s $e(W(2))=" " ;XME2S(1,0,-1) s C2=C1,$p(C2,",",$p(C(4.1),",",2))=$p(C1,",",$p(C(4.1),",",2))+$p(C(4.2),",",2) i $d(C(2,C1,C2)) s $e(W(3),2)=" " ;XME2S(1,0,0) s C2=C1,$p(C2,",",C(4.1))=$p(C1,",",C(4.1))+C(4.2) i $d(C(2,C1,C2)) s $e(W(2),3)=" " ;XME2S(1,0,1) s C1=C,$p(C1,",",C(4.1))=$p(C,",",C(4.1))+C(4.2) i $d(C(2,C,C1)) s $e(W(0),3)=" " ;XME2S(1,1) k W s (NC,Y)=0 f s NC=$o(XME2S(2,NC)) q:'NC i @$e(NC,2,99) f s Y=$o(XME2S(2,NC,Y)) q:'Y s V=$p(XME2S(2,NC,Y)," ;") f X=1:1:$l(V) s E=$e(V,X) s:E'=" " $e(W(Y),X)=E ;XME2S(2): build W _______________________ ;XME2S(2,"5'D1",2) _______________________ ;XME2S(2,"5'D1",22) ;XME2S(2,"5'D1L&D1",6) ;XME2S(2,"5'D1L&D1",7) ;XME2S(2,"5'D1L&D1",8) / ;XME2S(2,"5'D1L&D1",17) / ;XME2S(2,"5'D1L&D1",18) / ;XME2S(2,"5'D1L&D1",19) / ;XME2S(2,"5'D1R&D1",6) / ;XME2S(2,"5'D1R&D1",7) / ;XME2S(2,"5'D1R&D1",8) ;XME2S(2,"5'D1R&D1",17) ;XME2S(2,"5'D1R&D1",18) ;XME2S(2,"5'D1R&D1",19) __________ ;XME2S(2,"5'D2&D1",8) ____________ ;XME2S(2,"5'D2&D1",16) ;XME2S(2,"5'D2L&D2",10) / ;XME2S(2,"5'D2L&D2",15) / ;XME2S(2,"5'D2R&D2",10) ;XME2S(2,"5'D2R&D2",15) ______ ;XME2S(2,"5'D3&D2",10) ______ ;XME2S(2,"5'D3&D2",14) ;XME2S(2,"5'DL",1) ;XME2S(2,"5'DL",2) / ;XME2S(2,"5'DL",23) / ;XME2S(2,"5'DL",24) / ;XME2S(2,"5'DR",1) / ;XME2S(2,"5'DR",2) ;XME2S(2,"5'DR",23) ;XME2S(2,"5'DR",24) / ;XME2S(2,"5D1",3) / ;XME2S(2,"5D1",4) / ;XME2S(2,"5D1",5) / ;XME2S(2,"5D1",20) / ;XME2S(2,"5D1",21) / ;XME2S(2,"5D1",22) | ;XME2S(2,"5D1L",6): D1L | ;XME2S(2,"5D1L",7) |___ ;XME2S(2,"5D1L",8) | ;XME2S(2,"5D1L",9) | ;XME2S(2,"5D1L",10) | ;XME2S(2,"5D1L",11) | ;XME2S(2,"5D1L",12) | ;XME2S(2,"5D1L",13) | ;XME2S(2,"5D1L",14) | ;XME2S(2,"5D1L",15) |__ ;XME2S(2,"5D1L",16) | ;XME2S(2,"5D1L",17) | ;XME2S(2,"5D1L",18) | ;XME2S(2,"5D1L",19) | ;XME2S(2,"5D1L=D2&D1",9) | ;XME2S(2,"5D1L=D2&D1",10) | ;XME2S(2,"5D1L=D2&D1",11) | ;XME2S(2,"5D1L=D2&D1",12) | ;XME2S(2,"5D1L=D2&D1",13) | ;XME2S(2,"5D1L=D2&D1",14) | ;XME2S(2,"5D1L=D2&D1",15) | ;XME2S(2,"5D1L=D2&D1",16) | ;XME2S(2,"5D1R",6): D1R | ;XME2S(2,"5D1R",7) ___| ;XME2S(2,"5D1R",8) | ;XME2S(2,"5D1R",9) | ;XME2S(2,"5D1R",10) | ;XME2S(2,"5D1R",11) | ;XME2S(2,"5D1R",12) | ;XME2S(2,"5D1R",13) | ;XME2S(2,"5D1R",14) | ;XME2S(2,"5D1R",15) __| ;XME2S(2,"5D1R",16) | ;XME2S(2,"5D1R",17) | ;XME2S(2,"5D1R",18) | ;XME2S(2,"5D1R",19) | ;XME2S(2,"5D1R=D2&D1",9) | ;XME2S(2,"5D1R=D2&D1",10) | ;XME2S(2,"5D1R=D2&D1",11) | ;XME2S(2,"5D1R=D2&D1",12) | ;XME2S(2,"5D1R=D2&D1",13) | ;XME2S(2,"5D1R=D2&D1",14) | ;XME2S(2,"5D1R=D2&D1",15) | ;XME2S(2,"5D1R=D2&D1",16) / ;XME2S(2,"5D2",9) / ;XME2S(2,"5D2",16) |__ ;XME2S(2,"5D2L",10) | ;XME2S(2,"5D2L",11) | ;XME2S(2,"5D2L",12) | ;XME2S(2,"5D2L",13) |_ ;XME2S(2,"5D2L",14) | ;XME2S(2,"5D2L",15) | ;XME2S(2,"5D2L=D3&D2",11) | ;XME2S(2,"5D2L=D3&D2",12) | ;XME2S(2,"5D2L=D3&D2",13) | ;XME2S(2,"5D2L=D3&D2",14) __| ;XME2S(2,"5D2R",10) | ;XME2S(2,"5D2R",11) | ;XME2S(2,"5D2R",12) | ;XME2S(2,"5D2R",13) _| ;XME2S(2,"5D2R",14) | ;XME2S(2,"5D2R",15) | ;XME2S(2,"5D2R=D3&D2",11) | ;XME2S(2,"5D2R=D3&D2",12) | ;XME2S(2,"5D2R=D3&D2",13) | ;XME2S(2,"5D2R=D3&D2",14) ___ ;XME2S(2,"5DL",2) ___ ;XME2S(2,"5DL",22) | ;XME2S(2,"5DL=D1",3) | ;XME2S(2,"5DL=D1",4) | ;XME2S(2,"5DL=D1",5) | ;XME2S(2,"5DL=D1",6) | ;XME2S(2,"5DL=D1",7) | ;XME2S(2,"5DL=D1",8) | ;XME2S(2,"5DL=D1",9) | ;XME2S(2,"5DL=D1",10) | ;XME2S(2,"5DL=D1",11) | ;XME2S(2,"5DL=D1",12) | ;XME2S(2,"5DL=D1",13) | ;XME2S(2,"5DL=D1",14) | ;XME2S(2,"5DL=D1",15) | ;XME2S(2,"5DL=D1",16) | ;XME2S(2,"5DL=D1",17) | ;XME2S(2,"5DL=D1",18) | ;XME2S(2,"5DL=D1",19) | ;XME2S(2,"5DL=D1",20) | ;XME2S(2,"5DL=D1",21) | ;XME2S(2,"5DL=D1",22) ___ ;XME2S(2,"5DR",2) ___ ;XME2S(2,"5DR",22) | ;XME2S(2,"5DR=D1",3) | ;XME2S(2,"5DR=D1",4) | ;XME2S(2,"5DR=D1",5) | ;XME2S(2,"5DR=D1",6) | ;XME2S(2,"5DR=D1",7) | ;XME2S(2,"5DR=D1",8) | ;XME2S(2,"5DR=D1",9) | ;XME2S(2,"5DR=D1",10) | ;XME2S(2,"5DR=D1",11) | ;XME2S(2,"5DR=D1",12) | ;XME2S(2,"5DR=D1",13) | ;XME2S(2,"5DR=D1",14) | ;XME2S(2,"5DR=D1",15) | ;XME2S(2,"5DR=D1",16) | ;XME2S(2,"5DR=D1",17) | ;XME2S(2,"5DR=D1",18) | ;XME2S(2,"5DR=D1",19) | ;XME2S(2,"5DR=D1",20) | ;XME2S(2,"5DR=D1",21) | ;XME2S(2,"5DR=D1",22) f Y=$o(W("")):1:$o(W(""),-1) w $g(W(Y)),! ;XME2S(2.1) r *R,! q:R=13 s:$e($zb,1,2)=$c(27,91) R=$e($zb,3) x XME2S(3,$f("ABCD",R)) ;XME2S(3): get input ;XME2S(3,0) s C1=C,$p(C1,",",$p(C(4.1),",",2))=$p(C,",",$p(C(4.1),",",2))+$p(C(4.2),",",2) i $d(C(2,C,C1)) s C=C1 ;XME2S(3,2): backward s C1=C,$p(C1,",",$p(C(4.1),",",2))=$p(C,",",$p(C(4.1),",",2))-$p(C(4.2),",",2) i $d(C(2,C,C1)) s C=C1 ;XME2S(3,3): forward s C(4.1)=$p(C(4.1),",",2)_","_$p(C(4.1),","),C(4.2)=-$p(C(4.2),",",2)_","_$p(C(4.2),",") ;XME2S(3,4): right s C(4.1)=$p(C(4.1),",",2)_","_$p(C(4.1),","),C(4.2)=$p(C(4.2),",",2)_","_-$p(C(4.2),",") ;XME2S(3,5): leftand its output (from some randomly wandered-to place):[font="Fixedsys"][noparse]___ / | / | / | / | / | / | / | / | |________| | | | | | | | | | | |________| | | | | / | / | / | / | / | / __|/ [/noparse][/font]Despite all the years and uses to which I’ve put simply connected mazes, I still have unanswered questions about them, my favorite being:how can you generalize the right wall rule into 3 or more directions? Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.