Python: acelere un algoritmo Star Path Pathfinder

Question

He codificado mi primer algoritmo ligeramente complejo, una implementación del algoritmo A Star Pathfinding. Seguí algunos Python.org advice al implementar gráficos para que un diccionario contenga todos los nodos a los que está vinculado cada nodo. Ahora, dado que esto es todo por un juego, cada nodo es realmente solo un mosaico en una grilla de nodos, por lo tanto, cómo estoy resolviendo la heurística y mi referencia ocasional a ellos.

Gracias a timeit sé que puedo ejecutar esta función con éxito un poco más de cien veces por segundo. Es comprensible que esto me sienta un poco incómodo, sin otros elementos de juego, como los gráficos o el cálculo de la lógica del juego. Así que me encantaría ver si alguno de ustedes puede acelerar mi algoritmo, no estoy completamente familiarizado con Cython o su parentesco, no puedo codificar una línea de C.

Sin más divagaciones, aquí está mi A Función estrella

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

Una optimización fácil consiste en utilizar conjuntos en lugar de listas para los conjuntos abierto y cerrado.

openSet = set() 
closedSet = set() 

Esto hará que la totalidad de la in y not in pruebas O (1) en lugar de O (n ).

Answer 2

Como se sugirió anteriormente, haga closedSet en un conjunto.

Me trataron de codificación openList como un montón 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 

Sin embargo, usted todavía tiene que buscar en if tile not in openList, por lo que podría hacer esto:

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 [] 

Answer 3

me gustaría utilizar los conjuntos que tienen Se dijo, pero también usaría un montón para encontrar el elemento mínimo (el que será el próximo current). Esto requeriría mantener tanto un openSet como un openHeap, pero la memoria no debería ser realmente un problema. Además, establece insertar en O (1) y montones en O (log N) para que sean rápidos. El único problema es que el módulo heapq no está hecho para usar claves con él. Personalmente, simplemente lo modificaría para usar las teclas. No debería ser muy difícil. Alternativamente, puede usar tuplas de (mosaico.H, mosaico) en el montón.

Además, seguiría la idea de aaronasterling de usar la iteración en lugar de la recursión, pero también agregaría elementos al final de path y al reverso path al final. La razón es que insertar un artículo en el lugar 0 en una lista es muy lento, (O (N) creo), mientras que al agregarlo está O (1) si recuerdo correctamente. El código final para esa parte sería:

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

Pongo la ruta de retorno al final porque parece que debería hacerlo desde su código.

Aquí está el código final utilizando conjuntos, las escombreras y lo que no:

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 []