document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. import svg
  2. import random
  3.  
  4. \'\'\' Adds a colored box to SVG file class \'\'\'
  5. def addBox(x, y, w, h, clr):
  6.     global svg_scene
  7.     svg_scene.add(svg.Rectangle([x,y],w,h,clr))
  8.  
  9. \'\'\' Maze box node - stores index, parent & path(=True if node belongs to a path) \'\'\'
  10. class node:
  11.     def __init__(self, i, j, parent=None):
  12.         self.i = i
  13.         self.j = j
  14.         self.p = parent
  15.         self.isPath = False
  16.  
  17. \'\'\' Global settings - can modify \'\'\'
  18. MAX_CORRIDOR_LENGTH = 20 # limits the length of fake corridors
  19. BLOCK_SIZE = 20 # base block size in pixels
  20.  
  21. \'\'\' Global settings - dont modify! \'\'\'
  22. svg_scene = None # svg class
  23. maxTreeSize = MAX_CORRIDOR_LENGTH # limit
  24. treeSize = 0 # counts the lengthon corridors
  25. N = 0 # num of cells in row/col
  26. table = [] # NxN maze table
  27. finish = [] # finishing cell position
  28. path = [] # array of nodes that belong to the maze path from start to finish
  29.  
  30. \'\'\' Picks item randomly from array & removes the value from array. \'\'\'
  31. def pickdel(arr):
  32.     indx = random.randint(0,len(arr)-1)
  33.     data = arr[indx]
  34.     del arr[indx]
  35.     return data
  36.  
  37. \'\'\' Validates indexes to maze table size. Returns False if indexes are valid. \'\'\'
  38. def badRange(i, j):
  39.     global N
  40.     if i < 0 or j < 0: return True
  41.     if i >= N or j >= N: return True
  42.     return False
  43.  
  44. \'\'\' Use DFS to find path from Start to Finish. Found path is placed in path array. \'\'\'
  45. def depthwalk(pos, parent=None):
  46.    
  47.     global table
  48.     global finish
  49.     global path
  50.  
  51.     # set as visited
  52.     i, j = pos
  53.     table[i][j] = node(i, j, parent)
  54.  
  55.     # reached end
  56.     if pos == finish:
  57.         path.append(table[i][j])
  58.         table[i][j].isPath = True
  59.         return True
  60.  
  61.     # move in cross - dx, dy, flag_dir, flag_forward
  62.     #   flag_dir => neighbour check flag (horiz == True)
  63.     #   flag_forward => movement direction flag (forward == True)
  64.     next = [[i+1, j, True], [i-1, j, True], [i, j-1, False], [i, j+1, False]]
  65.    
  66.     while len(next) > 0:
  67.         # visit randomly
  68.         dest = pickdel(next)
  69.  
  70.         # new tile to check
  71.         ni, nj, flag = dest
  72.        
  73.         # check range
  74.         if badRange(ni, nj): continue
  75.         if table[ni][nj]: continue # already visited
  76.  
  77.         # check neighbours - cant touch their walls (no loops in maze!)
  78.         if flag:
  79.             # moving: up/down, neighbour check - horizontal
  80.             j_left = nj-1
  81.             j_right = nj+1
  82.             if j_left >= 0 and table[ni][j_left]: continue;
  83.             if j_right < N and table[ni][j_right]: continue;
  84.  
  85.             # cant touch wall by moving in the desired direction
  86.             if ni-i < 0:
  87.                 next_up = ni-1 # check one more tile up
  88.                 if next_up >= 0 and table[next_up][nj]: continue;
  89.             else:
  90.                 next_down = ni+1 # check one more tile down
  91.                 if next_down < N and table[next_down][nj]: continue;
  92.         else:
  93.             # moving: left/right, neighbour check - vertical
  94.             i_up = ni-1
  95.             i_down = ni+1
  96.             if i_up >= 0 and table[i_up][nj]: continue;
  97.             if i_down < N and table[i_down][nj]: continue;
  98.  
  99.             # cant touch wall by moving in the desired direction
  100.             if nj-j < 0:
  101.                 next_left = nj-1 # check one more tile left
  102.                 if next_left >= 0 and table[ni][next_left]: continue;
  103.             else:
  104.                 next_right = nj+1 # check one more tile right
  105.                 if next_right < N and table[ni][next_right]: continue;
  106.  
  107.  
  108.         if depthwalk([ni, nj], table[i][j]): #check deeper
  109.             path.append(table[i][j]) #path found
  110.             table[i][j].isPath = True
  111.             return True
  112.  
  113.     return False
  114.  
  115. \'\'\' Use BFS to generate dead-end corridors in the maze \'\'\'
  116. def growTree(i, j, pi = -1, pj = -1):
  117.     global table
  118.     global N
  119.     global treeSize
  120.     global maxTreeSize
  121.  
  122.     if table[i][j]:
  123.         print \'ERROR: invalid tile passed!\'
  124.         return
  125.    
  126.     # check if this tile can be made empty
  127.     next = [[i+1, j], [i-1, j], [i, j-1], [i, j+1]]
  128.     for tile in next:
  129.         if tile == [pi, pj]: continue # dont check parent
  130.         ni, nj = tile
  131.         if badRange(ni, nj): continue
  132.         # cant use as corridor - dont make loops to other paths or corridors
  133.         if table[ni][nj]: return
  134.  
  135.     # tests passed - make node as a corridor
  136.     table[i][j] = node(i, j)
  137.     treeSize += 1
  138.  
  139.     # generate further
  140.     while len(next) > 0 and treeSize < maxTreeSize:
  141.         # visit randomly
  142.         dest = pickdel(next)
  143.         ni, nj = dest
  144.         if dest == [pi, pj]: continue # dont check parent
  145.         if badRange(ni, nj): continue
  146.         if table[ni][nj]: continue # dont check paths & corridors
  147.        
  148.         growTree(ni, nj, i, j)
  149.    
  150. \'\'\' Generate dead-end corridors starting from current path nodes \'\'\'
  151. def makeWalls():
  152.     global path
  153.     global table
  154.     global N
  155.     global treeSize
  156.     global MAX_CORRIDOR_LENGTH
  157.     global maxTreeSize
  158.  
  159.     maxTreeSize = MAX_CORRIDOR_LENGTH
  160.    
  161.     for p in path:
  162.         x, y = p.i, p.j
  163.         treeSize = 0
  164.        
  165.         # move in cross
  166.         next = [[x+1, y], [x-1, y], [x, y-1], [x, y+1]]
  167.         while len(next) > 0:
  168.             # visit directions randomly
  169.             ni, nj = pickdel(next)
  170.             if badRange(ni, nj): continue
  171.             if table[ni][nj]: continue # cant start from other path or corridor
  172.  
  173.             # grow other paths from the path nodes
  174.             growTree(ni, nj, x, y)
  175.  
  176.     #double check empty places
  177.     maxTreeSize = 99999999 # dont count
  178.    
  179.     for i in range(0, N):
  180.         for j in range(0, N):
  181.             if not table[i][j]: growTree(i, j)
  182.        
  183. \'\'\' Generates a maze & builds a SVG file from the data \'\'\'
  184. def buildMaze(scene, size, block):
  185.     global svg_scene
  186.     global finish
  187.     global BLOCK_SIZE
  188.     global N
  189.     global table
  190.     global path
  191.  
  192.     BLOCK_SIZE = block
  193.  
  194.     # setup scene(the svg file class)
  195.     svg_scene = scene
  196.     svg_scene.setDims(size, size) # pixels
  197.     addBox(0,0,size,size,[0,0,0]) # background
  198.     N = size / BLOCK_SIZE
  199.  
  200.     # clear table
  201.     table = [[None for i in range(0, N)] for j in range(0, N)]
  202.     path = [] # clear old path
  203.    
  204.     # create path from Start to Finish
  205.     finish = [N-1, N-1]
  206.     start = [0, 0]
  207.     depthwalk(start)
  208.  
  209.     print "path length = %d" % len(path)
  210.     if len(path) == 0:
  211.         print "could not create maze, retry!"
  212.  
  213.     # clear junk
  214.     for i in range(0, N):
  215.         for j in range(0, N):
  216.             if table[i][j] and table[i][j].isPath == False:
  217.                 table[i][j] = None
  218.  
  219.     # generate dead-end corridors
  220.     makeWalls()
  221.  
  222.     pathColor = [255,128,0]
  223.     corridorColor = [255,255,255]
  224.     startColor = [0,0,255]
  225.     finishColor = [255,0,0]
  226.  
  227.     # paint - show corridors
  228.     for i in range(0, N):
  229.         for j in range(0, N):
  230.             if table[i][j] and table[i][j].isPath == False:
  231.                 addBox(i*BLOCK_SIZE, j*BLOCK_SIZE, BLOCK_SIZE, BLOCK_SIZE, corridorColor)
  232.  
  233.     # paint - mark path
  234.     for p in path:
  235.         addBox(p.i*BLOCK_SIZE, p.j*BLOCK_SIZE, BLOCK_SIZE, BLOCK_SIZE, pathColor)
  236.  
  237.     # show start/finish
  238.     addBox(start[0]*BLOCK_SIZE, start[1]*BLOCK_SIZE, BLOCK_SIZE, BLOCK_SIZE, startColor)
  239.     addBox(finish[0]*BLOCK_SIZE, finish[1]*BLOCK_SIZE, BLOCK_SIZE, BLOCK_SIZE, finishColor)
');