Я пытаюсь создать алгоритм A Star и применить к игре Snake.У меня проблема в том, что я никогда ничего не рисую в окне, потому что оно никогда не достигает этого кода.Он застревает при попытке вычислить путь в методе run ().В частности, открытый набор никогда не обнуляется, и он добавляет уже существующие узлы.
Я попытался распечатать различные списки на консоли, но все, что я обнаружил, это то, что «текущий» повторяет плитки в случайных точках,и «openSet и« closedSet »продолжают увеличиваться с этими повторяющимися плитками. Я также протестировал мой объект Tile, мой метод contains и метод giveNeighbors, и все они, кажется, работают и дают ожидаемые результаты.Ссылка, я собираюсь использовать псевдокод, найденный здесь: https://en.wikipedia.org/wiki/A*_search_algorithm
import Tile
import pygame
class A_star:
def __init__(self):
self.closedSet = []
self.openSet = []
def run(self, start, goal):
self.closedSet = []
self.openSet = [start]
path = []
#THE LENGTH OF OPEN SET NEVER GOES TO ZERO!
while len(self.openSet) > 0:
#Set current to node in openSet with lowest fscore
current = self.openSet[0]
currindex = 0
for i, node in enumerate(self.openSet):
if node.fScore < current.fScore:
current = node
currindex = i
#romove from Open set and add to closed
self.openSet.pop(currindex)
self.closedSet.append(current)
#Reached the end
if current.tileEquals(goal):
print("Done")
while current != None:
path.append(current)
current = current.cameFrom
return path[::-1]
neighbors = self.giveNeighbors(current)
print("Current: " + str(current.posx) + ", " + str(current.posy))
print("Neighbors")
for i in neighbors:
print(str(i.posx) + ", " + str(i.posy))
for i in neighbors:
#if neighbor is already checked, then ignore it.
if not self.contains(self.closedSet, i):
#Distance between start adn neighbor. tenative gscore
tempGScore = current.gScore + 1
#if neighbor is not in openset. Discovered a new node!
if not self.contains(self.openSet, i):
self.openSet.append(i)
elif tempGScore < i.gScore:
i.gScore = tempGScore
i.cameFrom = current
i.fScore = i.gScore + self.heuristicCost(i, goal) #f = g + h
print("Open:")
for i in self.openSet:
print(str(i.posx) + ", " + str(i.posy))
print("Closed")
for i in self.closedSet:
print(str(i.posx) + ", " + str(i.posy))
#Calculates the estimated distance from a given tile to end
def heuristicCost(self, neighbor, goal):
#The snake never goes diagonal, therefore calculate manhatten distance
distance = abs(neighbor.posx - goal.posx) + abs(neighbor.posy - goal.posy)
return distance
def giveNeighbors(self, current):
neighbors = []
if current.posx > 0:
neighbors.append(Tile(current.posx - 10, current.posy))
if current.posx < 200:
neighbors.append(Tile(current.posx + 10, current.posy))
if current.posy > 0:
neighbors.append(Tile(current.posx, current.posy - 10))
if current.posy < 200:
neighbors.append(Tile(current.posx, current.posy + 10))
return neighbors
def contains(self, s, tile):
for i in s:
if i.tileEquals(tile):
return True
else:
return False
def testAStar():
pygame.init()
window = pygame.display.set_mode((200, 200))
pygame.display.set_caption("AStar Test")
window.fill((255,255,255))
clock = pygame.time.Clock()
start = Tile(0, 0)
end = Tile(190, 190)
astar = A_star()
path = astar.run(start, end)
run = True
while run:
for event in pygame.event.get():
if event.type == pygame.QUIT:
run = False
pygame.draw.rect(window, (0, 255, 0), (start.posx, start.posy, 10, 10))
pygame.draw.rect(window, (255, 0, 0), (end.posx, end.posy, 10, 10))
for i in path:
pygame.draw.rect(window, (0, 0, 255), (i.posx, i.posy, 10, 10))
print("drew stuff")
pygame.display.update()
window.fill((255,255,255))
clock.tick(10)
pygame.quit()
if __name__== "__main__":
testAStar()
class Tile:
def __init__(self, x, y):
self.posx = x
self.posy = y
self.fScore = 0
self.gScore = 0
self.cameFrom = None
def nextTileRight(self):
self.posx = self.posx + 10
def nextTileDown(self):
self.posy = self.posy + 10
def nextTileUp(self):
self.posy = self.posy - 10
def nextTileLeft(self):
self.posx = self.posx - 10
def tileEquals(self, t):
if self.posx == t.posx and self.posy == t.posy:
return True
else:
return False
Ожидаемый результат должен быть недиагональным путем, нарисованным в окне от начального узла до конечного узла. (Также,извините, если мои отступы отключены. Я все еще очень новичок на этом сайте)