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.
44.     if location[0] > 0 and grid[location[0] - 1][location[1]] != 1:
45.         neighbors.append([location[0] - 1, location[1]])
47.     if location[0] < rows - 1 and grid[location[0] + 1][location[1]] != 1:
48.         neighbors.append([location[0] + 1, location[1]])
50.     if location[1] > 0 and grid[location[0]][location[1] - 1] != 1:
51.         neighbors.append([location[0], location[1] - 1])
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
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
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
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