Python - Accélérez un algorithme A Star Pathfinding

Question

J'ai codé mon premier légèrement-algorithme complexe, une mise en œuvre de l' Une Étoile Pathfinding de l'algorithme. J'ai suivi certains Python.org des conseils sur la mise en œuvre des schémas d'un dictionnaire contient tous les nœuds chaque nœud est lié aussi. Maintenant, puisque c'est pour un jeu, chaque nœud est vraiment juste une tuile dans une grille de nœuds, donc comment je fais l'heuristique et ma référence à eux.

Grâce à timeit je sais que je peux exécuter cette fonction avec succès un peu plus d'une centaine de fois par seconde. C'est compréhensible ce qui me rend un peu mal à l'aise, c'est sans aucun autre jeu trucs " en cours, comme le graphisme ou le calcul de la logique de jeu. Alors, j'aimerais voir si vous pouvez augmenter la vitesse de mon algorithme, je suis complètement familier avec Cython, ou de ses parents, je ne peux pas le code d'une ligne de C.

Sans plus de la randonnée, voici mon Une Star de la fonction.

def aStar(self, graph, current, end):
    openList = []
    closedList = []
    path = []

    def retracePath(c):
        path.insert(0,c)
        if c.parent == None:
            return
        retracePath(c.parent)

    openList.append(current)
    while len(openList) is not 0:
        current = min(openList, key=lambda inst:inst.H)
        if current == end:
            return retracePath(current)
        openList.remove(current)
        closedList.append(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                if tile not in openList:
                    openList.append(tile)
                tile.parent = current
    return path

Answer 1

Une optimisation facile consiste à utiliser des ensembles au lieu de listes pour les ensembles ouverts et fermés.

 openSet   = set()
closedSet = set()
 

Cela fera tous les tests in et not in O (1) au lieu de O ( n ).

Answer 2

Je voudrais utiliser les jeux comme il a été dit, mais je voudrais aussi utiliser un tas pour trouver le minimum de l'élément (celui qui sera le prochain current). Cela nécessiterait de garder à la fois un openSet et un openHeap, mais la mémoire ne devrait pas vraiment être un problème. Aussi, ensembles insérer en O(1) et des tas en O(log N), de sorte qu'ils seront vite. Le seul problème est que le heapq module n'est pas vraiment fait pour utiliser les touches avec elle. Personnellement, je voudrais juste modifier pour utiliser les touches. Il ne devrait pas être très dur. Alternativement, vous pouvez simplement utiliser des tuples de (tuile.H,tuile) dans le tas.

Aussi, je voudrais suivre aaronasterling l'idée de l'utilisation de l'itération de la place de la récursivité, mais aussi, je voudrais ajouter des éléments à la fin de l' path et de inverser la path à la fin. La raison en est que l'insertion d'un élément à l'0e place dans une liste est très lente, (O(N), je crois), tout en ajoutant est O(1) si je me souviens bien. Le code final pour la partie serait:

def retracePath(c):
    path = [c]
    while c.parent is not None:
        c = c.parent
        path.append(c)
    path.reverse()
    return path

J'ai mis le chemin de retour à la fin, car il semble qu'il devrait partir de votre code.

Voici le code final à l'aide des ensembles, des tas et ce n'est pas:

import heapq


def aStar(graph, current, end):
    openSet = set()
    openHeap = []
    closedSet = set()

    def retracePath(c):
        path = [c]
        while c.parent is not None:
            c = c.parent
            path.append(c)
        path.reverse()
        return path

    openSet.add(current)
    openHeap.append((0, current))
    while openSet:
        current = heapq.heappop(openHeap)[1]
        if current == end:
            return retracePath(current)
        openSet.remove(current)
        closedSet.add(current)
        for tile in graph[current]:
            if tile not in closedSet:
                tile.H = (abs(end.x - tile.x)+abs(end.y-tile.y))*10
                if tile not in openSet:
                    openSet.add(tile)
                    heapq.heappush(openHeap, (tile.H, tile))
                tile.parent = current
    return []

Answer 3

Comme suggéré ci-dessus, faites de closedSet un ensemble.

J'ai essayé de coder openList comme un tas import heapq :

 import heapq

def aStar(self, graph, current, end):
    closedList = set()
    path = []

    def retracePath(c):
        path.insert(0,c)
        if c.parent == None:
            return
        retracePath(c.parent)

    openList = [(-1, current)]
    heapq.heapify(openList)
    while openList:
        score, current = openList.heappop()
        if current == end:
            return retracePath(current)
        closedList.add(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                if tile not in openList:
                    openList.heappush((tile.H, tile))
                tile.parent = current
    return path
 

Cependant, vous devez toujours rechercher if tile not in openList , donc je ferais ceci:

 def aStar(self, graph, current, end):
    openList = set()
    closedList = set()

    def retracePath(c):
        def parentgen(c):
             while c:
                 yield c
                 c = c.parent
        result = [element for element in parentgen(c)]
        result.reverse()
        return result

    openList.add(current)
    while openList:
        current = sorted(openList, key=lambda inst:inst.H)[0]
        if current == end:
            return retracePath(current)
        openList.remove(current)
        closedList.add(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                openList.add(tile)
                tile.parent = current
    return []