attachment:multi_maze.py of MiscItems/2010-04-16

   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()