attachment:mapmaze.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 """
   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()