Any ideas how to create random Labyrinths
BlitzMax Forums/BlitzMax Beginners Area/Any ideas how to create random Labyrinths
| ||
Hello my friends, I am working on my game and goes very nice so far. I would like to ask, if you have any idea about an algorithm to generate random labyrinths for my dungeons. My map is a 3D array with 40 squares horizontal and 40 squares vertical. Each square have 4 sides. My array levels contains 99 levels 40 x 40 squares of map. 4 are the sides. Four sides of walls creates one closed square. levels:String[99, 40, 40, 4] The array is string and each of square have four sides which contains the string "01" for the walls. One closed square have all sides with string "01". 'A Closed square with walls levels[99, 40, 40, 1]="01" levels[99, 40, 40, 2]="01" levels[99, 40, 40, 3]="01" levels[99, 40, 40, 4]="01" How to create a random labyrinth which fills all of those squares with closed walls? Some idea? Thank you very much. |
| ||
Is this similar to what you had in mind? http://jeremykun.com/2012/07/29/the-cellular-automaton-method-for-cave-generation/ |
| ||
I found this code , is for Quick Basic 4.5 In Quick Basic compiles and works: Quick Basic code: DECLARE SUB makemaze (map%(), maxi%, maxj%) SCREEN 13 'define the scale and sizes sc% = 8 maxi% = 20 maxj% = 20 RANDOMIZE TIMER DIM map%(20, 20) CALL makemaze(map%(), maxi%, maxj%) count% = 0 'location in cx%...point alont the path 'erase any dark blue marks FOR i% = 0 TO maxi% FOR j% = 0 TO maxj% IF map%(i%, j%) = 1 THEN map%(i%, j%) = 0 LINE (i% * sc%, j% * sc%)-(i% * sc% + sc%, j% * sc% + sc%), map%(i%, j%), BF 'LINE (i% * sc%, j% * sc%)-(i% * sc% + sc%, j% * sc% + sc%), 7, B NEXT j% NEXT i% SUB makemaze (map%(), maxi%, maxj%) 'fill with blockers FOR i% = 0 TO maxi% FOR j% = 0 TO maxj% map%(i%, j%) = 2 LINE (i% * sc%, j% * sc%)-(i% * sc% + sc%, j% * sc% + sc%), map%(i%, j%), BF LINE (i% * sc%, j% * sc%)-(i% * sc% + sc%, j% * sc% + sc%), 7, B NEXT j% NEXT i% i% = INT(RND * (maxi% / 2 - 1)) * 2 + 1 j% = INT(RND * (maxj% / 2 - 1)) * 2 + 1 nump% = 0 DO check2% = 0 count% = 0 DO count% = count% + 1 choose% = INT(RND * 4) IF choose% = 0 THEN oi% = i% + 2: oj% = j% IF choose% = 1 THEN oi% = i% - 2: oj% = j% IF choose% = 2 THEN oi% = i%: oj% = j% + 2 IF choose% = 3 THEN oi% = i%: oj% = j% - 2 IF oi% >= 1 AND oj% >= 1 AND oi% <= maxi% AND oj% <= maxj% THEN IF map%(oi%, oj%) = 3 THEN check2% = 1 END IF LOOP UNTIL check2% = 1 OR count% > 7 IF check2% = 1 THEN i% = oi% j% = oj% map%(i%, j%) = 0 IF choose% = 0 THEN map%(i% - 1, j%) = 0 IF choose% = 1 THEN map%(i% + 1, j%) = 0 IF choose% = 2 THEN map%(i%, j% - 1) = 0 IF choose% = 3 THEN map%(i%, j% + 1) = 0 'LINE (i% * sc%, j% * sc%)-(i% * sc% + sc%, j% * sc% + sc%), map%(i%, j%), BF 'LINE (i% * sc%, j% * sc%)-(i% * sc% + sc%, j% * sc% + sc%), 7, B ELSE nump% = nump% + 1 DO i% = INT(RND * (maxi% / 2 - 1)) * 2 + 1 j% = INT(RND * (maxj% / 2 - 1)) * 2 + 1 LOOP UNTIL map%(i%, j%) = 0 END IF LOOP UNTIL nump% > 10 END SUB I tried to translate it to Blitzmax with this code below but some of the code can't be translated well. Blitzmax code: Global sc:Int = 8 Global maxi:Int = 20 Global maxj:Int = 20 Global choose:Int, oi:Int, i:Int, oj:Int, j:Int, check2:Int, count:Int sct = 8 maxi = 20 maxj = 20 Function Create_Maze(maxi, maxj) For i = 0 To maxi For j = 0 To maxj DrawRect(i, j, i * sc + sc, j * sc + sc) Next Next i = Rnd(maxi / 2 - 1 * 2, maxi / 2 - 1 * 2 + 1) j = Rnd(maxj / 2 - 1 * 2, maxj / 2 - 1 * 2 + 1) nump = 0 Repeat check2:Int = 0 count:Int = 0 Repeat count = count + 1 choose = Rnd(1, 4) If choose = 0 Then oi = i + 2 oj = j If choose = 1 Then oi = i - 2 oj = j If choose = 2 Then oi = i oj = j + 2 If choose = 3 Then oi = i oj = j - 2 If oi >= 1 And oj >= 1 And oi <= maxi And oj <= maxj Then If maze_map[oi, oj] = 3 Then check2 = 1 End If Until check2 = 1 Or count > 7 If check2 = 1 Then i = oi j = oj maze_map[i, j] = 0 If choose = 0 Then maze_map[i - 1, j] = 0 If choose = 1 Then maze_map[i + 1, j] = 0 If choose = 2 Then maze_map[i, j - 1] = 0 If choose = 3 Then maze_map[i, j + 1] = 0 Else nump = nump + 1 Repeat i = Rnd(maxi / 2 - 1 * 2, maxi / 2 - 1 * 2 + 1) j = Rnd(maxj / 2 - 1 * 2, maxj / 2 - 1 * 2 + 1) Until maze_map[i, j] = 0 EndIf Until nump > 10 End Function I tried to translate this from Quick Basic i = Int(Rnd * (maxi / 2 - 1)) * 2 + 1 j = Int(Rnd * (maxj / 2 - 1)) * 2 + 1 To this to Blitzmax i = Rnd(maxi / 2 - 1 * 2, maxi / 2 - 1 * 2 + 1) j = Rnd(maxj / 2 - 1 * 2, maxj / 2 - 1 * 2 + 1) But it doesn't work. Also the variables are not descriptive. In Quick basic code they pass an empty array to a function DIM map%(20, 20) DECLARE SUB makemaze (map%(),maxi%, maxj%) In blitzmax this can't be translated like this Global map:Int[20,20] Function makemaze(map[],maxi,maxj) Any Idea how to translate the quick basic code to blitzmax? |
| ||
I found this by Curtastic in codearcs http://www.blitzbasic.com/codearcs/codearcs.php?code=981 It's a lot easier to convert it to BMX. Looks like this is what you have in mind.. |
| ||
Yes there is a ported code from blitz basic to blitzmax and the second example is the example I want. I will try to put it in my game. Thank you very much for the link. I will try the code and I will tell if I manage something. |
| ||
you're welcome. oh yeah that's great, I missed that one. Hope you can get this thing sorted out. good day. |
| ||
There's summaries of a variety of maze algorithms at http://www.astrolog.org/labyrnth/algrithm.htm . You'll probably have to google the terms involved for more info. I'm currently working on a Blitz3D implementation of Wilson's algorithm which I'll be putting in the code archives (it's done, I've just got to test it and make a demo). My research links for that are are below. Wilson’s algorithm http://bl.ocks.org/mbostock/11357811 http://www.pixieland.org.uk/2014/wilsons-algorithm/ (a good summary) https://eventuallyalmosteverywhere.wordpress.com/tag/wilsons-algorithm/ http://en.wikipedia.org/wiki/Loop-erased_random_walk Minimum spanning tree (with decent definitions and summary) (BlitzMax code) http://www.blitzbasic.com/codearcs/codearcs.php?code=2870 |
| ||
I made it with the link from the code of blitzmax about. I will see and the other algorithms to see if they are working. |
| ||
I've finished my code for the maze generator using Wilson's algorithm and put it into the code archives. Link is below. http://www.blitzbasic.com/codearcs/codearcs.php?code=3178 |
| ||
The link above is in blitz basic and it needs to be translated. For now I will use me current algorithm which does the job perfectly. |