cjburkey01

Untitled

Mar 8th, 2021
762
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # A node within the space to search
  2. class Node:
  3.     # Initialize values in constructor
  4.     def __init__(self, value, parent):
  5.         self.value = value
  6.         self.parent = parent
  7.  
  8.     # Determine if this node is the same as another
  9.     # (If we don't do this, python will count two different objects as
  10.     # different nodes even if they share the same location; this breaks our
  11.     # checks for whether a node has already been visited)
  12.     def __eq__(self, other):
  13.         if other.value is not None and len(other.value) == 2:
  14.             return other.value[0] == self.value[0] and other.value[1] == self.value[1]
  15.  
  16.  
  17. def getNeighbors(location, grid):
  18.     # Get row count
  19.     rows = len(grid)
  20.  
  21.     # If there are no rows, return an empty list
  22.     if rows < 1:
  23.         return []
  24.  
  25.     # Get the columns count
  26.     cols = len(grid[0])
  27.  
  28.     # If there are no columns, return an empty list
  29.     if cols < 1:
  30.         return []
  31.  
  32.     # Make sure the position is valid and within the provided grid
  33.     if len(location) != 2\
  34.             or location[0] < 0\
  35.             or location[0] >= rows\
  36.             or location[1] < 0\
  37.             or location[1] >= cols:
  38.         return []
  39.  
  40.     # Define neighbors list
  41.     neighbors = []
  42.  
  43.     # Add up neighbor
  44.     if location[0] > 0 and grid[location[0] - 1][location[1]] != 1:
  45.         neighbors.append([location[0] - 1, location[1]])
  46.     # Add down neighbor
  47.     if location[0] < rows - 1 and grid[location[0] + 1][location[1]] != 1:
  48.         neighbors.append([location[0] + 1, location[1]])
  49.     # Add left neighbor
  50.     if location[1] > 0 and grid[location[0]][location[1] - 1] != 1:
  51.         neighbors.append([location[0], location[1] - 1])
  52.     # Add right neighbor
  53.     if location[1] < cols - 1 and grid[location[0]][location[1] + 1] != 1:
  54.         neighbors.append([location[0], location[1] + 1])
  55.  
  56.     # Return neighbors list
  57.     return neighbors
  58.  
  59.  
  60. # Expand a node into its neighbors, put them into the frontier, and mark the
  61. # node as visited
  62. def expandNode(node, grid, closed_list, open_list):
  63.     # Make sure this node isn't visited or queued to be visited already
  64.     if node in closed_list:
  65.         return
  66.  
  67.     # Add this node to the visited list
  68.     closed_list.append(node)
  69.  
  70.     if node in open_list:
  71.         return
  72.  
  73.     # Get possible neighbors for this node's position
  74.     for neighbor in getNeighbors(node.value, grid):
  75.         # Make sure the neighbor isn't already visited or scheduled to be visited
  76.         for n in closed_list:
  77.             if n.value == neighbor:
  78.                 continue
  79.         for n in open_list:
  80.             if n.value == neighbor:
  81.                 continue
  82.  
  83.         # Mark accessible neighbors as to-be-visited
  84.         open_list.append(Node(neighbor, node))
  85.  
  86.  
  87. # The grid values must be separated by spaces, e.g.
  88. # 1 1 1 1 1
  89. # 1 0 0 0 1
  90. # 1 0 0 0 1
  91. # 1 1 1 1 1
  92. # Returns a 2D list of 1s and 0s
  93. def readGrid(filename):
  94.     # Initialize grid to empty list
  95.     grid = []
  96.  
  97.     # Open the file
  98.     with open(filename) as f:
  99.         # Read each line of the file
  100.         for line in f.readlines():
  101.             # Split each line into its individual values and add them to the
  102.             # grid
  103.             grid.append([int(x) for x in line.split()])
  104.  
  105.     # No need to close file using `with` syntax
  106.  
  107.     # Return the grid
  108.     return grid
  109.  
  110.  
  111. # Writes a 2D list of 1s and 0s with spaces in between each character
  112. # 1 1 1 1 1
  113. # 1 0 0 0 1
  114. # 1 0 0 0 1
  115. # 1 1 1 1 1
  116. def outputGrid(filename_str, grid, start, goal, path):
  117.     # Open file
  118.     with open(filename_str, 'w') as f:
  119.         print(
  120.             'Goal: ' + str(goal[0]) + ', ' + str(goal[1]) + ' | Grid size: ' + str(len(grid)) + 'x' + str(len(grid[0])))
  121.  
  122.         # Mark the start and goal points
  123.         grid[start[0]][start[1]] = 'S'
  124.         grid[goal[0]][goal[1]] = 'G'
  125.  
  126.         # Mark intermediate points with *
  127.         for i, p in enumerate(path):
  128.             if 0 < i < len(path) - 1:
  129.                 grid[p[0]][p[1]] = '*'
  130.  
  131.         # Write the grid to a file
  132.         for r, row in enumerate(grid):
  133.             for c, col in enumerate(row):
  134.                 # Don't add a ' ' at the end of a line
  135.                 if c < len(row) - 1:
  136.                     f.write(str(col) + ' ')
  137.                 else:
  138.                     f.write(str(col))
  139.  
  140.             # Don't add a '\n' after the last line
  141.             if r < len(grid) - 1:
  142.                 f.write("\n")
  143.  
  144.  
  145. def setPath(current, path):
  146.     # Keep track of current looping node
  147.     node = current
  148.  
  149.     # Loop through parents to beginning
  150.     while node is not None:
  151.         # Add this node to the path
  152.         path.append(node.value)
  153.  
  154.         # Assign current node to parent
  155.         node = node.parent
  156.  
  157.     # Flip the path around so the first element is the beginning
  158.     path.reverse()
  159.  
  160.  
  161. # Perform a search using breadth-first if `dfs` is false, or depth-first if `dfs` is True
  162. def uninformedSearch(grid, start, goal, dfs=False):
  163.     # Initialize search
  164.     open_list = [Node(start, None)]
  165.     closed_list = []
  166.  
  167.     # Loop until we reach the goal
  168.     while len(open_list) > 0:
  169.         # Pull new node from open_list
  170.         if dfs:
  171.             # DFS is LIFO so we use `pop()` to remove last element
  172.             current = open_list.pop()
  173.         else:
  174.             # BFS is FIFO so we use `pop(0)` to remove first element
  175.             current = open_list.pop(0)
  176.  
  177.         # Check if we're at the goal position
  178.         if current.value == goal:
  179.             # Create path
  180.             path = []
  181.             setPath(current, path)
  182.  
  183.             # Return path
  184.             return path
  185.  
  186.         # Add traversable neighbors to `open_list` and current node to
  187.         # `closed_list`
  188.         expandNode(current, grid, closed_list, open_list)
  189.  
  190.     # No path was found!
  191.     return []
  192.  
  193.  
  194. # Determine which algorithm to use
  195. getting_input = True
  196. algo_type = None
  197. while getting_input:
  198.     algo_type = input('Please enter the algorithm type (DFS/BFS): ')
  199.     if algo_type == 'DFS':
  200.         algo_type = True
  201.     elif algo_type == 'BFS':
  202.         algo_type = False
  203.     else:
  204.         print('Please enter \"DFS\" or \"BFS\"')
  205.         continue
  206.  
  207.     getting_input = False
  208.  
  209. start = [1, 1]
  210. goal = [5, 8]
  211.  
  212. # Read the grid in, perform the search, and output the path
  213. grid = readGrid('maze_in.txt')
  214. print(grid)
  215. solved_path = uninformedSearch(grid, start, goal, algo_type)
  216. outputGrid("maze_out.txt", grid, start, goal, solved_path)
  217.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×