Guest User

Untitled

a guest
Feb 21st, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.08 KB | None | 0 0
  1. class Node(object):
  2.     def __init__(self, row, col):
  3.         """
  4.        Initialize a new node
  5.        """
  6.         self.row = row
  7.         self.col = col
  8.         self.passable = passable
  9.         self.parent = None
  10.         self.g = 0
  11.         self.h = 0
  12.         self.f = 0
  13.  
  14. class AStar(object):
  15.     def __init__(self):
  16.         """
  17.        Stuff for A* Pathfinding
  18.        """
  19.         self.open = []
  20.         heapq.heapify(self.open)
  21.         self.closed = set()
  22.         self.nodes = []
  23.  
  24.     def init_grid(self, ant_loc, target):
  25.         """
  26.        Initialize node list
  27.        """
  28.         for row in range(ants.rows):
  29.             for col in range(ants.cols):
  30.                 if ants.passable((row, col)):
  31.                     passable = True
  32.                 else:
  33.                     passable = False
  34.                 self.nodes.append(Node(
  35.                         row, col, passable))
  36.         self.start = ant_loc
  37.         self.end = target
  38.  
  39.     def get_node(self, row, col):
  40.         """
  41.        Return node from self.nodes based on row, col
  42.        """
  43.         return self.nodes[row * ants.rows + col]
  44.  
  45.     def get_adj_nodes(self, node):
  46.         """
  47.        Retrieve adjacent nodes
  48.        """
  49.         nodes = []
  50.         if col < ants.cols - 1:
  51.             nodes.append(get_node(
  52.                     node.row,
  53.                     node.col + 1))
  54.         if col == ants.cols - 1:
  55.             nodes.append(get_node(
  56.                     node.row,
  57.                     1))
  58.         if row < ants.rows - 1:
  59.             nodes.append(get_node(
  60.                     node.row + 1,
  61.                     node.col))
  62.         if row == ants.rows - 1:
  63.             nodes.append(get_node(
  64.                     1,
  65.                     node.col))
  66.         if col > 0:
  67.             nodes.append(get_node(
  68.                     node.row,
  69.                     node.col - 1))
  70.         if col == 0:
  71.             nodes.append(get_node(
  72.                     node.row,
  73.                     ants.cols - 1))
  74.         if row > 0:
  75.             nodes.append(get_node(
  76.                     node.row - 1,
  77.                     node.col))
  78.         if col == 0:
  79.             nodes.append(get_node(
  80.                     ants.rows - 1,
  81.                     node.col))
  82.         return nodes
  83.  
  84.     def create_path(self):
  85.         """
  86.        Create list with path
  87.        """
  88.         path = []
  89.         node = self.end
  90.         while node.parent is not self.start:
  91.             node = node.parent
  92.             path.insert(0, (node.row, node.col))
  93.  
  94.     def score_node(self, adj, node):
  95.         """
  96.        Score g, h and set parent node
  97.        """
  98.         adj.g = node.g + 1
  99.         # heuristic score: ants.distance()
  100.         adj.h = ants.distance(adj.g, self.end)
  101.         adj.parent = node
  102.         adj.f = adj.g + adj.h
  103.  
  104.     def find_path(self):
  105.         """
  106.        The big, bad
  107.        A Star Pathfinding Algorithm
  108.        """
  109.         heapq.heappush(self.open,
  110.                        (self.start.f, self.start))
  111.         # as long as there's stuff in
  112.         # open list, process it
  113.         while len(self.open):
  114.             # get cell from heapq and
  115.             # put it in closed list
  116.             h, node = heapq.heappop(self.open)
  117.             self.closed.add(node)
  118.             # at target node, create path
  119.             if node is self.end:
  120.                 self.create_path()
  121.                 break
  122.             # otherwise, get_adj_nodes
  123.             adj_nodes = self.get_adj_nodes(node)
  124.             # check if adj_node is better
  125.             # than previously found
  126.             for adj in adj_nodes:
  127.                 if adj.passable and adj not in self.closed:
  128.                     if adj in self.open:
  129.                         if adj.g > node.g + 1:
  130.                             # score_node and be done with it
  131.                             self.score_node(adj, node)
  132.                         else:
  133.                             # score_node and add to open list
  134.                             self.score_node(adj, node)
  135.                             heapq.heappush(self.open,
  136.                                            (adj.f, adj))
Add Comment
Please, Sign In to add comment