1 #!/usr/bin/env python
   2 #-*- coding:utf-8 -*-
   3 """
   4 use map depth first search to create a maze.
   5 """
   6 import random
   7 import numpy as np
   8 
   9 DIRS = ((0, +1),
  10         (0, -1),
  11         (-1, 0),
  12         (+1, 0))
  13 
  14 def create_maze(mw, mh):
  15     """
  16     assume maze is a map,
  17     use depth first search to connect the map,
  18     and so is a maze.
  19     """
  20     path = [(0,0)] #the search path
  21     vector_link = [] #links between vectors, for draw maze
  22     visited = np.zeros((mw,mh)) #for O(1) search
  23     visited[0,0] = 1
  24 
  25     while True:
  26         #get next vector
  27         nextp = get_next(path, visited, mw, mh)
  28         #check if this vector is the end
  29         if not nextp:
  30             # if so, pop to previous head
  31             path.pop()
  32             # if path is empty, search is finished
  33             if path == []:
  34                 #finish search
  35                 break
  36             continue
  37         #store data, move to next head
  38         vector_link.append((path[-1],nextp))
  39         visited[nextp] = 1
  40         path.append(nextp)
  41 
  42     #create maze
  43     maze = np.ones((mw*2-1, mh*2-1), dtype=np.int)
  44     for start, end in vector_link:
  45         #print start, end
  46         d1 = start[0]*2, start[1]*2
  47         d2 = end[0]*2, end[1]*2
  48         middle = ((start[0] + end[0]),
  49                   (start[1] + end[1]))
  50         maze[d1] = 0
  51         maze[d2] = 0
  52         maze[middle] = 0
  53     return maze
  54 
  55 def get_next(path, visited, mw, mh):
  56     """
  57     get what is the next vector?
  58     """
  59     head = path[-1]
  60     nextps = [] #store next vectors
  61     for mod in DIRS:
  62         newp = head[0] + mod[0], head[1] + mod[1]
  63         #out of the scope
  64         if ((0 > newp[0]) or (mw <= newp[0]) or
  65             (0 > newp[1]) or (mh <= newp[1])
  66             ):
  67             continue
  68         #have visited
  69         if visited[newp] == 1:
  70             continue
  71         nextps.append(newp)
  72     if nextps == []:
  73         return None
  74     #random choose a vector
  75     return nextps[random.randint(0, len(nextps)-1)]
  76 
  77 def show_maze(maze):
  78     """
  79     print maze to command line.
  80     """
  81     for row in maze:
  82         print "".join(["%d"%i for i in row])
  83 
  84 def draw_maze(maze):
  85     """
  86     use pygame to render a png file.
  87     """
  88     try:
  89         import pygame
  90     except:
  91         print "looks like you don't have pygame,"
  92         print "install pygame for rending a image file."
  93     pygame.init()
  94 
  95     DOT = 8
  96     size = maze.shape
  97     sw, sh = size
  98 
  99     surface = pygame.Surface((sw*DOT, sh*DOT))
 100     for i in range(sw):
 101         for j in range(sh):
 102             if maze[i][j] == 0:
 103                 surface.fill((200,200,200), 
 104                              pygame.Rect(i*DOT, j*DOT, DOT, DOT))
 105     pygame.image.save(surface, "test.png")
 106 
 107 def main():
 108     maze = create_maze(20,20)
 109     show_maze(maze)
 110     draw_maze(maze)
 111 
 112 if __name__=="__main__":
 113     main()

   1 #!/usr/bin/env python
   2 #-*- coding:utf-8 -*-
   3 """
   4 use map depth first search to create a maze.
   5 this map is multi dimension!
   6 """
   7 import random
   8 import numpy as np
   9 
  10 def create_maze(*size):
  11     """
  12     assume maze is a map,
  13     use depth first search to connect the map,
  14     and so is a maze.
  15     """
  16     dim = len(size) #dimension
  17     start = np.zeros(dim, dtype=np.int)
  18     path = [start] #the search path
  19     vector_link = [] #links between vectors, for draw maze
  20     visited = np.zeros(size, dtype=np.bool) #for O(1) search
  21     visited[tuple(start.tolist())] = True
  22     #directions
  23     DIRS = []
  24     for i in range(dim):
  25         z = np.zeros(dim, dtype=np.int)
  26         z[i] += 1
  27         DIRS.append(z)
  28         z = np.zeros(dim, dtype=np.int)
  29         z[i] -= 1
  30         DIRS.append(z)
  31 
  32     while True:
  33         #get next vector
  34         nextp = get_next(path, visited, size, DIRS)
  35         #check if this vector is the end
  36         if nextp is None:
  37             # if so, pop to previous head
  38             path.pop()
  39             # if path is empty, search is finished
  40             if path == []:
  41                 #finish search
  42                 break
  43             continue
  44         #store data, move to next head
  45         vector_link.append((path[-1],nextp))
  46         visited[tuple(nextp.tolist())] = 1
  47         path.append(nextp)
  48 
  49     #create maze
  50     maze_size = np.array(size)*2 -1
  51     maze = np.zeros(maze_size, dtype=np.bool)
  52     for start, end in vector_link:
  53         #print start, end
  54         d1 = start*2
  55         d2 = end*2
  56         middle = start + end
  57         maze[tuple(d1.tolist())] = True
  58         maze[tuple(d2.tolist())] = True
  59         maze[tuple(middle.tolist())] = True
  60     return maze
  61 
  62 def get_next(path, visited, size, DIRS):
  63     """
  64     get what is the next vector?
  65     """
  66     head = path[-1]
  67     #print "head:",head
  68     nextps = [] #store next vectors
  69     for mod in DIRS:
  70         newp = head + mod
  71         #print 'newp:',newp
  72         #out of the scope
  73         out_scope = False
  74         for i, v in enumerate(newp):
  75             if (v<0) or (v>=size[i]): 
  76                 #print newp, v, size[i], size
  77                 out_scope = True
  78                 break
  79         if out_scope:
  80             continue
  81         #have visited
  82         if visited[tuple(newp.tolist())] == True:
  83             # print "visited:",newp
  84             # print visited
  85             continue
  86         nextps.append(newp)
  87     if nextps == []:
  88         return None
  89     #random choose a vector
  90     nextp = nextps[random.randint(0, len(nextps)-1)]
  91     #print "nextps:",nextps
  92     #print "nextp:  ",nextp
  93     return nextp
  94 
  95 def show_maze(maze):
  96     """
  97     print maze to command line.
  98     """
  99     if maze.ndim == 3:
 100         for map in maze:
 101             print
 102             for row in map:
 103                 print "".join(['_'if i else '#' for i in row])
 104     elif maze.ndim == 2:
 105         for row in maze:
 106             print "".join(['_'if i else '#' for i in row])
 107 
 108 def draw_maze(maze):
 109     """
 110     use pygame to render a png file.
 111     """
 112     if maze.ndim != 2: return
 113     try:
 114         import pygame
 115     except:
 116         print "looks like you don't have pygame,"
 117         print "install pygame for rending a image file."
 118     pygame.init()
 119 
 120     DOT = 8
 121     size = maze.shape
 122     sw, sh = size
 123 
 124     surface = pygame.Surface((sw*DOT, sh*DOT))
 125     for i in range(sw):
 126         for j in range(sh):
 127             if maze[i][j] == True:
 128                 surface.fill((200,200,200), 
 129                              pygame.Rect(i*DOT, j*DOT, DOT, DOT))
 130     pygame.image.save(surface, "test.png")
 131 
 132 def main():
 133     maze = create_maze(30, 30, 30)
 134     show_maze(maze)
 135     draw_maze(maze)
 136 
 137 if __name__=="__main__":
 138     main()