PyCon 2013 チュートリアル 迷路問題その2 隣接マップで書き換えたもの

maze2.py

#! /usr/bin/env python
# coding:utf-8 

class Maze(object):
  def __init__(self, maze_map):
    self.neighbor_node_map = dict()
    self.build_neighbor_node_map(maze_map)

  def is_floor(self, maze_map, x, y):
    return True if maze_map[y][x]==0 else False

  def build_neighbor_node_map(self, maze_map):
    for j in range(1,7):
      for i in range(1,7):
        result = list()
        for (dx, dy) in ((-1, 0), (0, -1), (1, 0), (0, 1)):
          (mx, my) = (i + dx, j + dy)
          if self.is_floor(maze_map, mx, my):
            result.append((mx, my))
        self.neighbor_node_map[(i, j)] = result
    print(self.neighbor_node_map)

  def get_neighbors(self, x, y):
    return self.neighbor_node_map[(x, y)]


class Walker(object):
  def __init__(self, maze, x, y, goal_x, goal_y):
    self.maze = maze
    self.x = x
    self.y = y
    self.goal_x = goal_x
    self.goal_y = goal_y
    self.passed_positions = set()
    self.trail_log = list()

  def get_to_goal(self):
    return (self.x == self.goal_x) and (self.y == self.goal_y)

  def get_movable_positions(self):
    for next_pos in self.maze.get_neighbors(self.x, self.y):
      if next_pos not in self.passed_positions:
        return next_pos
    return None

  def move_to(self, x, y):
    print("Move from (%d, %d) to (%d, %d)" % (self.x, self.y, x, y))
    self.x = x
    self.y = y

  def solve(self):
    while not self.get_to_goal():
      next_pos = self.get_movable_positions()
      if next_pos != None:
        self.passed_positions.add((self.x, self.y))
        self.trail_log.append((self.x, self.y))
        self.move_to(*next_pos)
      else:
        self.passed_positions.add((self.x, self.y))
        next_pos = self.trail_log.pop()
        self.move_to(*next_pos)

    print("I got goal!")


class Borad(object):
  def __init__(self):
      width = 0
      height = 0
      unit_xy = 0

  def calculation_unit(self):
    lf = self.lifeboard
    unitx = int(self.width / lf.xmax())
    unity = int(self.height / lf.ymax())
    self.unit_xy = unitx if unitx <= unity else unity


def main():
  maze_map = (
  (1,1,1,1,1,1,1,1),
  (1,0,1,0,1,1,0,1),
  (1,0,1,0,1,0,0,1),
  (1,0,0,0,1,1,0,1),
  (1,1,1,0,0,0,0,1),
  (1,0,1,0,1,1,0,1),
  (1,0,0,0,0,1,0,1),
  (1,1,1,1,1,1,1,1))
  maze = Maze(maze_map)

  walker = Walker(maze, 1, 1, 6, 6)
  walker.solve()

if __name__ == "__main__":
  main()