Как вернуть путь наиболее эффективно в алгоритме A * - PullRequest
Новая
       64

Как вернуть путь наиболее эффективно в алгоритме A *

0 голосов
/ 28 января 2019

Я работаю над поиском кратчайшего пути в лабиринте и хотел бы, чтобы кто-то просмотрел мой код и прокомментировал, как его улучшить, а также сказал, что было бы наиболее эффективным способом вернуть путь. 

def aStarSearch(currentNode, endNode):
    openList = []
    closedList = []
    currentNode.set_g(0) #cost so far
    currentNode.set_h(endNode.return_y(), endNode.return_x()) #estimated euclidean distance
    currentNode.set_f((currentNode.get_g() + currentNode.get_h())) #total cost
    openList.append(currentNode)
    closedList.append(currentNode)

    while openList != []:
        for node in openList:
            if node.get_f() <= currentNode.get_f(): #node with smaller total cost becomes current node
                currentNode = node
                currentNode.set_h(endNode.return_y(), endNode.return_x()) #estimated euclidean distance
                currentNode.set_f((currentNode.get_g() + currentNode.get_h())) #total cost
        draw_maze(endNode)
        neighbours = return_Neighbours(currentNode)
        for neighbour in neighbours:
            neighbour.set_f(neighbour.get_g() + neighbour.get_h()) #calculate the f cost     
            if neighbour.get_g() <= currentNode.get_g() and neighbour in closedList: #if the neighbours cost is smaller and in closed list mean already visited,should backtrack
                openList.append(neighbour)
                closedList.remove(neighbour)
                neighbour.set_colour((255,0,255))
            elif currentNode.get_g() <= neighbour.get_g() and neighbour in openList: #it has not been already visited but seen so g is smaller
                neighbour.set_g(currentNode.get_g()) #change g because g is previous cost
                closedList.append(neighbour)
                neighbour.set_colour((255,255,0))
            elif neighbour not in openList or closedList: #not visited yet, needs to be appended, calculate h because cannot find another place to do that
                openList.append(neighbour)
                neighbour.set_h(endNode.return_x(), endNode.return_y())
                neighbour.set_colour((0,255,255))
        if currentNode.get_vector() == endNode.get_vector():
            return closedList
...