Generating Mazes

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|574\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> Off Topic -> Generating Mazes
Wed, 05 Feb 2014, 15:18
rockford	That's a cloe-up of a brain, isn't it?
Wed, 05 Feb 2014, 15:18
spinal	why is it so impossible to find any information at all for generating this kind of maze?! -- -=-=- Check out my excellent homepage!
Wed, 05 Feb 2014, 16:47
Jayenkai	Tried and failed! hurray! BlitzMax : Exceedingly messy, and not at all good! Global MapWide=320 Global MapHigh=240 Graphics MapWide,MapHigh,0 Global Map[(MapWide+2)(MapHigh+2)] Global sx,sy,ex,ey Global ratx,raty,targetx,targety Global travelled ' Step One. Everything is wall.. For x=0 To MapWide For y=0 To MapHigh ID=yMapWide+x Map[ID]=1 Next Next ' Step Two. Find a start and end point. Repeat sx=Rand(0,MapWide) sy=Rand(0,MapHigh) Until sx=0 Or sx=MapWide Or sy=0 Or sy=MapHigh Repeat ex=Rand(0,MapWide) ey=Rand(0,MapHigh) Until ex=0 Or ex=MapWide Or ey=0 Or ey=MapHigh sx=0;sy=0 ex=MapWide;ey=MapHigh travelled=0 NewRoute() ratdir=0 Repeat Cls DrawMap() For s=0 To 320 x=ratx+Rand(-6,6) y=raty+Rand(-6,6) ID=(yMapWide)+x If x>0 And y>0 And x<MapWide And y<MapHigh Then Map[ID]=0 x=ratx+Rand(-4,4) y=raty+Rand(-4,4) ID=(yMapWide)+x If x>0 And y>0 And x<MapWide And y<MapHigh Then Map[ID]=1 For x=ratx-1 To ratx+1 For y=raty-1 To raty+1 ID=(yMapWide)+x If x>0 And y>0 And x<MapWide And y<MapHigh Then Map[ID]=0 Next Next If ratdir=1 And Rand(0,3)=1 Then raty=raty-1 If ratdir=2 And Rand(0,3)=1 Then ratx=ratx+1 If ratdir=3 And Rand(0,3)=1 Then raty=raty+1 If ratdir=4 And Rand(0,3)=1 Then ratx=ratx-1 If ratx<1 Then ratx=1;ratdir=0 If raty<1 Then raty=1;ratdir=0 If ratx>MapWide-1 Then ratx=MapWide-1;ratdir=0 If raty>MapHigh-1 Then raty=MapHigh-1;ratdir=0 If ratdir>0 And Rand(0,20)=1 Then ratdir=0 If ratdir=0 c=8;If raty>targety Then c=3 If Rand(0,c)=1 Then ratdir=1 c=8;If ratx<targetx Then c=3 If Rand(0,c)=1 Then ratdir=2 c=8;If raty<targety Then c=3 If Rand(0,c)=1 Then ratdir=3 c=8;If ratx>targetx Then c=3 If Rand(0,c)=1 Then ratdir=4 EndIf If Abs(ratx-targetx)<8 And Abs(raty-targety)<8 NewRoute() EndIf Next Flip fin=0 If (KeyDown(KEY_F4) And (KeyDown(KEY_LALT) Or KeyDown(Key_RALT))) Or AppTerminate() Or KeyDown(KEY_ESCAPE) Then fin=1 Until fin=1 End Function DrawMap() Cls For x=0 To MapWide-1 For y=0 To MapHigh-1 ID=(yMapWide)+x d=0 ' If Map[ID]=1 Then SetColor(0,0,0) If Map[ID]=0 Then SetColor(255,255,255);d=1 If Abs(x-sx)<4 And Abs(y-sy)<4 Then SetColor(255,0,0);d=1 If Abs(x-ex)<4 And Abs(y-ey)<4 Then SetColor(0,255,0);d=1 If d=1 Then Plot x,y Next Next Flip End Function Function NewRoute() 'Repeat ratx=Rand(0,MapWide) raty=Rand(0,MapHigh) 'Until ratx=0 Or ratx=MapWide Or raty=0 Or raty=MapHigh targetx=Rand(0,MapWide) targety=Rand(0,MapHigh) If Rand(0,4)=1 Then ratx=sx;raty=sy If Rand(0,4)=1 Then ratx=ex;raty=ey If Rand(0,4)=1 Then targetx=sx;targety=sy If Rand(0,4)=1 Then targetx=ex;targety=ey If (travelled Mod 4)=1 Then ratx=sx;raty=sy;targetx=ex;targety=ey travelled=travelled+1 End Function --v -=-=- ''Load, Next List!''
Thu, 06 Feb 2014, 01:54
spinal	If I have to resort to hand-drawn levels, I wont be happy! -=-=- Check out my excellent homepage!
Thu, 06 Feb 2014, 14:14
dna	Here's Something that might help solve the problem: #Include "vbcompat.bi" #include "fbgfx.bi" const False = 0 const True = Not False const fbGray = RGB (150, 150, 150) const fbBlack = RGB (0, 0, 0) const fbYellow = RGB (255, 255, 0) const fbWhite = RGB(255, 255, 255) const mazew = 100 const mazeh = 70 enum terrain floor = 0 wall dot end enum enum gdir north = 1 east south west end enum 'Cell type type cell north as integer south as integer east as integer west as integer visit as integer terr as terrain end type 'Player type ptype x as integer y as integer end type dim shared maze(1 to mazeh, 1 to mazew) as cell dim shared player as ptype dim as integer done = False Dim e As fb.EVENT 'get a random number between low and high Function Rand(lowerbound As Integer, upperbound As Integer) As Integer Return Int((upperbound - lowerbound + 1) * Rnd + lowerbound) End Function sub DrawMaze dim as integer x, y screenlock cls for y = 1 to mazeh for x = 1 to mazew locate y, x if maze(y, x).terr = wall then color fbGray, fbBlack print chr(219); elseif maze(y, x).terr = floor then color fbGray, fbBlack print chr(32); elseif maze(y, x).terr = dot then color fbWhite, fbBlack print chr(249); end if next next locate player.y, player.x color fbYellow, fbBlack print chr(2); screenunlock end sub sub FillMaze dim as integer x, y cls for y = 1 to mazeh for x = 1 to mazew maze(y, x).terr = wall maze(y, x).visit = False maze(y, x).visit = False maze(y, x).north = False maze(y, x).south = False maze(y, x).east = False maze(y, x).west = False next next end sub function CheckLoc(y as integer, x as integer, cdir as integer) as integer dim as integer nx, ny, ret = False if cdir = north then nx = x ny = y - 1 if ny > 2 then if maze(ny, nx).visit = False then if (maze(ny, nx - 1).terr = wall) and (maze(ny, nx + 1).terr = wall) and (maze(ny - 1, nx).terr = wall) then if (maze(ny - 1, nx - 1).terr = wall) and (maze(ny - 1, nx + 1).terr = wall) then ret = True end if end if end if end if elseif cdir = east then nx = x + 1 ny = y if nx <= mazew - 2 then if maze(ny, nx).visit = False then if (maze(ny - 1, nx).terr = wall) and (maze(ny + 1, nx).terr = wall) and (maze(ny, nx + 1).terr = wall) then if (maze(ny - 1, nx + 1).terr = wall) and (maze(ny + 1, nx + 1).terr = wall) then ret = True end if end if end if end if elseif cdir = south then nx = x ny = y + 1 if ny <= mazeh - 2 then if maze(ny, nx).visit = False then if (maze(ny, nx - 1).terr = wall) and (maze(ny, nx + 1).terr = wall) and (maze(ny + 1, nx).terr = wall) then if (maze(ny + 1, nx - 1).terr = wall) and (maze(ny + 1, nx + 1).terr = wall) then ret = True end if end if end if end if elseif cdir = west then nx = x - 1 ny = y if nx > 2 then if maze(ny, nx).visit = False then if (maze(ny - 1, nx).terr = wall) and (maze(ny + 1, nx).terr = wall) and (maze(ny, nx - 1).terr = wall) then if (maze(ny - 1, nx - 1).terr = wall) and (maze(ny - 1, nx - 1).terr = wall) then ret = True end if end if end if end if end if return ret end function function GetNewDir(y as integer, x as integer) as integer dim as integer cdir, nx, ny cdir = Rand(north, west) if CheckLoc(y, x, cdir) then return cdir end if cdir += 1 if cdir > west then cdir = north if CheckLoc(y, x, cdir) then return cdir end if cdir += 1 if cdir > west then cdir = north if CheckLoc(y, x, cdir) then return cdir end if cdir += 1 if cdir > west then cdir = north if CheckLoc(y, x, cdir) then return cdir end if return 0 end function sub BuildMaze(y as integer, x as integer) dim as integer nx, ny, cdir maze(y, x).terr = floor maze(y, x).visit = True cdir = GetNewDir(y, x) if cdir = 0 then exit sub if cdir = north then 'Try north direction nx = x ny = y - 1 maze(y, x).north = True maze(ny, nx).south = True maze(ny, nx).visit = True BuildMaze ny, nx end if if cdir = east then 'Try east direction nx = x + 1 ny = y maze(y, x).east = True maze(ny, nx).west = True maze(ny, nx).visit = True BuildMaze ny, nx end if if cdir = south then 'Try south direction nx = x ny = y + 1 maze(y, x).south = True maze(ny, nx).north = True maze(ny, nx).visit = True BuildMaze ny, nx end if if cdir = west then 'Try west direction nx = x - 1 ny = y maze(y, x).west = True maze(ny, nx).east = True maze(ny, nx).visit = True BuildMaze ny, nx end if BuildMaze y, x end sub sub DoMaze dim as integer mx, my FillMaze my = Rand(2, mazeh - 2) mx = 3 player.x = mx player.y = my maze(my, mx).visit = True maze(my, mx).terr = dot BuildMaze my, mx DrawMaze end sub sub MovePlayer(sc as integer) dim as integer x, y if sc = FB.SC_LEFT then x = player.x - 1 y = player.y if x < 2 then x = 1 if maze(y, x).terr <> wall then maze(y, x).terr = dot player.x = x player.y = y DrawMaze end if end if if sc = FB.SC_RIGHT then x = player.x + 1 y = player.y if x > mazew then x = mazew if maze(y, x).terr <> wall then maze(y, x).terr = dot player.x = x player.y = y DrawMaze end if end if if sc = FB.SC_UP then x = player.x y = player.y - 1 if y < 1 then y = 1 if maze(y, x).terr <> wall then maze(y, x).terr = dot player.x = x player.y = y DrawMaze end if end if if sc = FB.SC_DOWN then x = player.x y = player.y + 1 if y > mazeh then y = mazeh if maze(y, x).terr <> wall then maze(y, x).terr = dot player.x = x player.y = y DrawMaze end if end if end sub Screen 19, 32 width 100, 75 Randomize Timer WindowTitle "Maze Runner" DoMaze Do 'Get next screen event. If (ScreenEvent(@e)) Then Select Case e.Type 'Check for escape key press Case fb.EVENT_KEY_PRESS If e.scancode = fb.SC_ESCAPE Then done = True else MovePlayer e.scancode End If case fb.EVENT_KEY_REPEAT MovePlayer e.scancode 'Check for window close Case fb.EVENT_WINDOW_CLOSE done = True End Select End If Sleep 10, 1 Loop until (done = True) --v -=-=- DNA
Fri, 07 Feb 2014, 02:11
spinal	I can generate a regular maze with walls and paths being the same size, which is much better looking than the walls being just lines between the tiles. But that's not really what I want for my game, I need something like a cave system, also, I need it to be 2 layers deep, which adds another layer of tricky. -=-=- Check out my excellent homepage!
Fri, 07 Feb 2014, 04:54
Krakatomato	Possibly not what you want, but I did knock something up on PMC yonks ago: [pmc]krakatomato/tiled-procedural-caves[/pmc] Based off an approach by Noel Berry. Pretty crap demo, but you should get the idea. //Andy
Fri, 07 Feb 2014, 05:03
Jayenkai	"Most Excellent!"
Fri, 07 Feb 2014, 05:21
spinal	Thats very much the sort of thing I'm after! I've been experimenting with random wall thickness in my normal maze generator, trying to make the resulting maze look a little more organic... [pmc]spinal/maze-generator-random-walls[/pmc] I was going to attempt random step sizes before I read the above replay. Now I think I'll look into that instead! -=-=- Check out my excellent homepage!
Fri, 07 Feb 2014, 05:54
Krakatomato	To be honest, it was incredibly easy to knock up. There's a lot of improvements that can (and should) be made - not least because it can generate very small maps (so stick some limits in there!). Can't wait to see what you come up with now //Andy
Fri, 07 Feb 2014, 20:17
dna	That's a great generator Spinal
Thu, 13 Feb 2014, 13:38
spinal	I've came up with what seems to be a good compromise. I took the above maze generator, plonked it over some randomly generated caves from some online thingumy, and wollop! The maze gives my a direction to take the player from each screen, the random caves gives it a bit of, um, caveness. -=-=- Check out my excellent homepage!
Thu, 13 Feb 2014, 14:11
Jayenkai	Kewly! Looking forward to seeing the end result!
Thu, 13 Feb 2014, 15:21
spinal	I'm currently running around the front map, making sure you can actually get round most of it. then a day or so drawing the back map then testing again. -=-=- Check out my excellent homepage!
Thu, 13 Feb 2014, 16:06
rockford	Sounds interesting. Is this for a new game or something you're just playing with?
Fri, 14 Feb 2014, 01:40
spinal	Yes, yes it is
Fri, 14 Feb 2014, 15:40
dna	Is this Map a cave system or did you opt for the traditional? -=-=- DNA
Mon, 17 Feb 2014, 13:01
Andy_A	This will generate the type of maze you want. https://blitzmax.com/codearcs/codearcs.php?code=981 Just fiddle with the setting a bit.