A* (A-star) python implementation

Original implementation from: http://www.laurentluce.com/posts/solving-mazes-using-python-simple-recursivity-and-a-search/

This is just modified for my test cases.
class Cell:
          def __init__(self,x, y, wall):
                    self.x = x
                    self.y = y
                    self.wall = wall
                    self.h = 0
                    self.g = 0
                    self.f = 0
class Astar:
          def __init__(self):
                    self.cells = []
                    self.open_list = []
                    self.closed_list = []
          def make_maze(self, maze):
                    self.__init__()
                    self.maze_width = len(maze[0])
                    self.maze_height = len(maze)
                    for i in range(self.maze_height):
                              for j in range(self.maze_width):
                                        wall = False
                                        if maze[i][j] == ‘#’:
                                                  wall = True
                                        if maze[i][j] == ‘X’:
                                                  end = (i, j)
                                        if maze[i][j] == ‘T’:
                                                  start = (i, j)
                                        self.cells.append(Cell(i, j, wall))
                    self.start = self.get_cell(start[0], start[1])
                    self.end = self.get_cell(end[0], end[1])
                    self.process()
                    self.show()
          def get_cell(self, x, y):
                    return self.cells[x * self.maze_width + y]
          def get_adjc(self, cell):
                    cells = []
                    if cell.x > 0:
                              cells.append(self.get_cell(cell.x-1,cell.y))
                    if cell.y > 0:
                              cells.append(self.get_cell(cell.x,cell.y-1))
                    if cell.x < self.maze_height – 1:
                              cells.append(self.get_cell(cell.x+1,cell.y))
                    if cell.y < self.maze_height – 1:
                              cells.append(self.get_cell(cell.x,cell.y+1))
                    return cells
          def update_cell(self, adjc, cell):
                    adjc.parent = cell
                    adjc.g = cell.g + 10
                    adjc.h = self.heur(adjc)
                    adjc.f = adjc.h + adjc.g
          def heur(self, cell):
                    return 10 * (abs(cell.x – self.end.x) + abs(cell.y – self.end.y))
          def process(self):
                    self.open_list.append((self.start.f, self.start))
                    while self.open_list:
                              f, cell = min(self.open_list)
                              self.open_list.remove((f, cell))
                              if cell is self.end:
                                        break
                              self.closed_list.append(cell)
                              adjc = self.get_adjc(cell)
                              for c in adjc:
                                        if not c.wall and c not in self.closed_list:
                                                  if (c.f, c) in self.open_list:
                                                            if c.g > cell.g + 10:
                                                                      self.update_cell(c, cell)
                                                            else:
                                                                      self.update_cell(c, cell)
                                                                      self.open_list.append((c.f, c))
          def show(self):
                    print
                    for i in range(self.maze_height):
                              for j in range(self.maze_width):
                                        cell = self.get_cell(i, j)
                                        if cell.x == self.start.x and cell.y == self.start.y:
                                                  print ‘T’,
                                        else:
                                                  if cell.x == self.end.x and cell.y == self.end.y:
                                                            print ‘X’,
                                                  else:
                                                            if cell.wall:
                                                                      print ‘#’,
                                                            else:
                                                                      if cell.g:
                                                                                print ‘!’,
                                                                      else:
                                                                                print ‘.’,
                    print
a = Astar()
a.make_maze([“X……..”,”.#…….”,”………”,”……..#”,”.##..##..”,”.#..#….”,”.#.###…”,”##..#..#.”,”.T.#..#..”]) # 8
a.make_maze([“……….”,”#.##…##.”,”..###.#…”,”.#.#.#..##”,”.#…..#..”,”..##.#..#.”,”#..T#.#.#.”,”..#X#…#.”,”..#.#..##.”,”…#……”]) # 1
a.make_maze([“#..#…#..”,”..#.X#..#.”,”.#…T#.#.”,”…##.#.#.”,”.##…#…”,”.#..#..##.”,”….##….”]) # 2
a.make_maze([“#…..”,”..##.#”,”.#….”,”..#T..”,”.#..#X”,”.###..”,”…#.#”,”.#….”]) # 3
a.make_maze([“#………”,”..###…#.”,”.#…###T.”,”…#.X….”,”.###..#…”,”.#..###.##”,”…#……”]) # 4
a.make_maze([“…#…#.”,”.##..#…”,”…#….#”,”.#.###..#”,”.#.T..#..”,”.####..X.”,”……#..”,”.#.#….#”]) # 5
a.make_maze([“…..#”,”.#.#..”,”..#.#.”,”#.#…”,”…##X”,”.#.#..”,”#..#..”,”..T…”,”.#.##.”,”……”]) # 6
a.make_maze([“#.#……”,”..#.###.#”,”.#..#..X.”,”…#.#…”,”.##….#.”,”.#.#.#…”,”….T..#.”,”###…##.”,”….#….”]) # 7
a.make_maze([“##…”,”#T.#.”,”..#..”,”.#…”,”..X#.”,”.##..”]) # -1
a.make_maze([“…..#.”,”.##.#..”,”#T….#”,”..##…”,”.#…#.”,”.#.#.#.”,”…#X.#”]) # -1
#a.display_path()
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: