mazeGenerator.py

# mazeGenerator.py
# ----------------
# Licensing Information:  You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
# 
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).


import random, sys

"""
maze generator code

algorithm:
start with an empty grid
draw a wall with gaps, dividing the grid in 2
repeat recursively for each sub-grid

pacman details:
players 1,3 always start in the bottom left; 2,4 in the top right
food is placed in dead ends and then randomly (though not too close to the pacmen starting positions)

notes:
the final map includes a symmetric, flipped copy
the first wall has k gaps, the next wall has k/2 gaps, etc. (min=1)

@author: Dan Gillick
@author: Jie Tang
"""

W = '%'
F = '.'
C = 'o'
E = ' '

class Maze:

  def __init__(self, rows, cols, anchor=(0, 0), root=None):
    """
    generate an empty maze
    anchor is the top left corner of this grid's position in its parent grid
    """
    self.r = rows
    self.c = cols
    self.grid = [[E for col in range(cols)] for row in range(rows)]
    self.anchor = anchor
    self.rooms = []
    self.root = root
    if not self.root: self.root = self

  def to_map(self):
    """
    add a flipped symmetric copy on the right
    add a border
    """

    ## add a flipped symmetric copy
    for row in range(self.r):
      for col in range(self.c-1, -1, -1):
        self.grid[self.r-row-1].append(self.grid[row][col])
    self.c *= 2

    ## add a border
    for row in range(self.r):
      self.grid[row] = [W] + self.grid[row] + [W]
    self.c += 2
    self.grid.insert(0, [W for c in range(self.c)])
    self.grid.append([W for c in range(self.c)])
    self.r += 2

  def __str__(self):
    s = ''
    for row in range(self.r):
      for col in range(self.c):
        s += self.grid[row][col]
      s += '\n'
    return s[:-1]

  def add_wall(self, i, gaps=1, vert=True):
    """
    add a wall with gaps
    """
    add_r, add_c = self.anchor
    if vert:
      gaps = min(self.r, gaps)
      slots = [add_r+x for x in range(self.r)]
      if not 0 in slots:
        if self.root.grid[min(slots)-1][add_c+i] == E: slots.remove(min(slots))
        if len(slots) <= gaps: return 0
      if not self.root.c-1 in slots:
        if self.root.grid[max(slots)+1][add_c+i] == E: slots.remove(max(slots))
      if len(slots) <= gaps: return 0
      random.shuffle(slots)
      for row in slots[int(round(gaps)):]:
        self.root.grid[row][add_c+i] = W
      self.rooms.append(Maze(self.r, i, (add_r,add_c), self.root))
      self.rooms.append(Maze(self.r, self.c-i-1, (add_r,add_c+i+1), self.root))
    else:
      gaps = min(self.c, gaps)
      slots = [add_c+x for x in range(self.c)]
      if not 0 in slots:
        if self.root.grid[add_r+i][min(slots)-1] == E: slots.remove(min(slots))
        if len(slots) <= gaps: return 0
      if not self.root.r-1 in slots:
        if self.root.grid[add_r+i][max(slots)+1] == E: slots.remove(max(slots))
      if len(slots) <= gaps: return 0
      random.shuffle(slots)
      for col in slots[int(round(gaps)):]:
        self.root.grid[add_r+i][col] = W
      self.rooms.append(Maze(i, self.c, (add_r,add_c), self.root))
      self.rooms.append(Maze(self.r-i-1, self.c, (add_r+i+1,add_c), self.root))

    return 1

def make_with_prison(room, depth, gaps=1, vert=True, min_width=1, gapfactor=0.5):
  """
  Build a maze with 0,1,2 layers of prison (randomly)
  """
  p = random.randint(0,2)
  proll = random.random()
  if proll < 0.5:
    p = 1
  elif proll < 0.7:
    p = 0
  elif proll < 0.9:
    p = 2
  else:
    p = 3


  add_r, add_c = room.anchor
  print p
  for j in range(p):
    cur_col = 2*(j+1)-1
    for row in range(room.r):
      room.root.grid[row][cur_col] = W
    if j % 2 == 0:
      room.root.grid[0][cur_col] = E
    else:
      room.root.grid[room.r-1][cur_col] = E

  room.rooms.append(Maze(room.r, room.c-(2*p), (add_r, add_c+(2*p)), room.root))
  for sub_room in room.rooms:
    make(sub_room, depth+1, gaps, vert, min_width, gapfactor)

  return 2*p

def make(room, depth, gaps=1, vert=True, min_width=1, gapfactor=0.5):
  """
  recursively build a maze
  TODO: randomize number of gaps?
  """

  ## extreme base case
  if room.r <= min_width and room.c <= min_width: return

  ## decide between vertical and horizontal wall
  if vert: num = room.c
  else: num = room.r
  if num < min_width + 2:
    vert = not vert
    if vert: num = room.c
    else: num = room.r

  ## add a wall to the current room
  if depth==0: wall_slots = [num-2]  ## fix the first wall
  else: wall_slots = range(1, num-1)
  if len(wall_slots) == 0: return
  choice = random.choice(wall_slots)
  if not room.add_wall(choice, gaps, vert): return

  ## recursively add walls
  # if random.random() < 0.8:
  #     vert = not vert
  for sub_room in room.rooms:
    make(sub_room, depth+1, max(1,gaps*gapfactor), not vert,
         min_width, gapfactor)
  # for sub_room in room.rooms:
  #     make(sub_room, depth+1, max(1,gaps/2), not vert, min_width)

def copy_grid(grid):
  new_grid = []
  for row in range(len(grid)):
    new_grid.append([])
    for col in range(len(grid[row])):
      new_grid[row].append(grid[row][col])
  return new_grid

def add_pacman_stuff(maze, max_food=60, max_capsules=4, toskip=0):
  """
  add pacmen starting position
  add food at dead ends plus some extra
  """

  ## parameters
  max_depth = 2

  ## add food at dead ends
  depth = 0
  total_food = 0
  while True:
    new_grid = copy_grid(maze.grid)
    depth += 1
    num_added = 0
    for row in range(1, maze.r-1):
      for col in range(1+toskip, (maze.c/2)-1):
        if (row > maze.r-6) and (col < 6): continue
        if maze.grid[row][col] != E: continue
        neighbors = (maze.grid[row-1][col]==E) + (maze.grid[row][col-1]==E) + (maze.grid[row+1][col]==E) + (maze.grid[row][col+1]==E)
        if neighbors == 1:
          new_grid[row][col] = F
          new_grid[maze.r-row-1][maze.c-(col)-1] = F
          num_added += 2
          total_food += 2
    maze.grid = new_grid
    if num_added == 0: break
    if depth >= max_depth: break

  ## starting pacmen positions
  maze.grid[maze.r-2][1] = '3'
  maze.grid[maze.r-3][1] = '1'
  maze.grid[1][maze.c-2] = '4'
  maze.grid[2][maze.c-2] = '2'

  ## add capsules
  total_capsules = 0
  while total_capsules < max_capsules:
    row = random.randint(1, maze.r-1)
    col = random.randint(1+toskip, (maze.c/2)-2)
    if (row > maze.r-6) and (col < 6): continue
    if(abs(col - maze.c/2) < 3): continue
    if maze.grid[row][col] == E:
      maze.grid[row][col] = C
      maze.grid[maze.r-row-1][maze.c-(col)-1] = C
      total_capsules += 2

  ## extra random food
  while total_food < max_food:
    row = random.randint(1, maze.r-1)
    col = random.randint(1+toskip, (maze.c/2)-1)
    if (row > maze.r-6) and (col < 6): continue
    if(abs(col - maze.c/2) < 3): continue
    if maze.grid[row][col] == E:
      maze.grid[row][col] = F
      maze.grid[maze.r-row-1][maze.c-(col)-1] = F
      total_food += 2

MAX_DIFFERENT_MAZES = 10000

def generateMaze(seed = None):
  if not seed:
    seed = random.randint(1,MAX_DIFFERENT_MAZES)
  random.seed(seed)
  maze = Maze(16,16)
  gapfactor = min(0.65,random.gauss(0.5,0.1))
  skip = make_with_prison(maze, depth=0, gaps=3, vert=True, min_width=1, gapfactor=gapfactor)
  maze.to_map()
  add_pacman_stuff(maze, 2*(maze.r*maze.c/20), 4, skip)
  return str(maze)

if __name__ == '__main__':
  seed = None
  if len(sys.argv) > 1:
    seed = int(sys.argv[1])
  print generateMaze(seed)