srli · March 9, 2018 05:20 · Mar 9, 2018 · Mar 9, 2018
diff --git a/astar_pseudo.py b/astar_pseudo.py
@@ -68,7 +68,7 @@ def solve(self):
 
 def answer(maze):
     astar = AStar(maze)
-    return astar.solve_all_paths()
+    return astar.solve()
 
 maze = [[0, 0, 0, 0, 0, 0],
         [1, 1, 1, 1, 1, 0],

diff --git a/astar_pseudo.py b/astar_pseudo.py
@@ -0,0 +1,80 @@
+#!/usr/bin/python
+
+import heapq
+
+class Cell(object):
+    def __init__(self, x, y, is_wall):
+        self.reachable = not is_wall
+        self.x = x
+        self.y = y
+        self.parent = None
+        # G, H, F are current costs
+        self.g = 0 # cost to get to end pos
+        self.h = 0 # cost to get to from start pos
+        self.f = 0 # g + h
+
+class AStar(object):
+    def __init__(self, maze):
+        # Open cells to still visit
+        self.opened = []
+        heapq.heapify(self.opened)
+
+        # Visited cells list
+        self.closed = set()
+
+        # Initialize all cells
+        self.init_grid()
+
+    def init_grid(self):
+        # Create cells by looping through the input maze
+        for x in range(self.grid_width):
+            for y in range(self.grid_height):
+                if self.maze[y][x] == 1:
+                    is_wall = True
+                else:
+                    is_wall  = False
+                self.cells.append(Cell(x, y, is_wall))
+
+    def solve(self):
+        # Add starting cell to open heap queue
+        heapq.heappush(self.opened, (self.start.f, self.start))
+        while len(self.opened):
+            # Pop cell from heap queue
+            f, cell = heapq.heappop(self.opened)
+
+            # Add cell to closed list so we don't process it twice
+            self.closed.add(cell)
+
+            # If ending cell, return found path
+            if cell is self.end:
+                return self.get_path()
+
+            # Get adjacent cells for the current cell
+            adj_cells = self.get_adjacent_cells(cell)
+            for adj_cell in adj_cells:
+                # If the adj_cell is not a wall and hasn't been visited
+                if adj_cell.reachable and adj_cell not in self.closed:
+                    # If adj_cell in open list from another cell, check if current path is
+                    # better than the one previously found for this cell
+                    if (adj_cell.f, adj_cell) in self.opened:
+                        if adj_cell.g > cell.g + 10:
+                            # If so, update its cost and parent with the current cell
+                            self.update_cell(adj_cell, cell)
+                    else:
+                        # If adj_cell has never been visited before, update it with its
+                        # cost and parent cell. Add to heap for use
+                        self.update_cell(adj_cell, cell)
+                        heapq.heappush(self.opened, (adj_cell.f, adj_cell))
+
+def answer(maze):
+    astar = AStar(maze)
+    return astar.solve_all_paths()
+
+maze = [[0, 0, 0, 0, 0, 0],
+        [1, 1, 1, 1, 1, 0],
+        [0, 0, 0, 0, 0, 0],
+        [0, 1, 1, 1, 1, 1],
+        [0, 1, 1, 1, 1, 1],
+        [0, 0, 0, 0, 0, 0]]
+
+print answer(maze)
No results found