Код: Выделить всё
import numpy as np
import random
blocked = set() #Stores the coordinates of all the found obstacles
expanded = 0 #Stores the number of expanded nodes
class Node:
def __init__(self, index, prev, g, h):
self.index = index #The pair that stores the indices of the area of the grid
self.prev = prev #Another Node that stores the previous node
self.g = g
self.h = h
def get_f(self):
return (self.g + self.h)
def set_prev(self, node):
self.prev = node
class BinHeap:
def __init__(self):
self.heap = []
def isEmpty(self):
if len(self.heap) == 0:
return True
return False
def insert(self, node):
self.heap.append(node)
self.sortUp(len(self.heap) - 1)
def getMin(self):
return self.heap[0]
def delMin(self):
self.heap[0] = self.heap[-1]
self.heap.pop()
if not self.isEmpty():
self.sortDown(0)
def sortUp(self, index):
parent = (index - 1) // 2
while parent >=0 and (self.heap[parent].get_f() > self.heap[index].get_f() or (self.heap[parent].get_f() == self.heap[index].get_f() and self.heap[parent].g = self.heap[minimal].g))):
minimal = child1
if(child2 < len(self.heap) and (self.heap[child2].get_f() < self.heap[minimal].get_f() or (self.heap[child2].get_f() == self.heap[minimal].get_f() and self.heap[child2].g >= self.heap[minimal].g))):
minimal = child2
if minimal != currentIndex:
self.heap[minimal], self.heap[currentIndex] = self.heap[currentIndex], self.heap[minimal]
isSmaller = True
currentIndex = minimal
child1, child2 = 2 * currentIndex + 1, 2 * currentIndex + 2
def generateWorld(): #Maze generation method: recursive backtracking.
world = np.zeros((101, 101))
directions = [(-2, 0), (2, 0), (0, -2), (0, 2)] #We jump by 2s to take into account the fact we first intialized everything as a wall(with values of 0) hence this creates a clear path
#backtracking stack
track = []
#Check if in bounds
def inBounds(x, y):
return 0 < x < 100 and 0 < y < 100 #Notice we never access the areas on the border. Those will always remain as walls in this algorithm
startX, startY = 1, 1
world[startY][startX] = 1 #Start is marked as visited
track.append((startX, startY))
while len(track) != 0:
x, y = track[-1]
neighbors = []
for dirx, diry in directions:
adjx, adjy = x + dirx, y + diry
if inBounds(adjx, adjy) and world[adjy][adjx] == 0:
neighbors.append((adjx, adjy))
if len(neighbors) != 0: #If we have unvisited neighbors, choose a random one to create a path to
newX, newY = random.choice(neighbors)
#Get the wall separating the current position and the neighbor and remove it
wallX, wallY = (x + newX) // 2, (y + newY) // 2
world[wallY][wallX] = 1
world[newY][newX] = 1
track.append((newX, newY)) #Add the neigbor onto the stack
else: #If we hit a dead-end we backtrack
track.pop()
# New code to output the world to a text file
with open('generated_world.txt', 'w') as f:
for row in world:
f.write(''.join(['#' if cell == 0 else '.' for cell in row]) + '\n')
print("World generated and saved to 'generated_world.txt'", flush=True)
return world
def forwardA(start, goal, backwards): #This function does a single A* search. To be implemented within the main code for repeated A* search
global expanded
global blocked
openlist = BinHeap()
closedlist = set()
startH = sum(abs(a - b) for a, b in zip(start, goal)) #Calculates manhattan distance. sum() returns the sum of all elements in an iterable, which here is our generator expression. Zip pairs the corresponding elements in each tuple as their own tuples
startNode = Node(start, None, 0, startH)
openlist.insert(startNode) #Adds start node to the open list
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
#check if in bounds
def isBounded(x, y):
return 0
Подробнее здесь: [url]https://stackoverflow.com/questions/79041616/issue-with-regards-to-speed-of-repeated-backwards-a[/url]