Python – Acelera un algoritmo de búsqueda de estrellas A

He codificado mi primer algoritmo ligeramente complejo, una implementación del algoritmo A Star Pathfinding . Seguí algunos consejos de Python.org sobre la implementación de gráficos para que un diccionario contenga todos los nodos a los que también está vinculado cada nodo. Ahora, ya que esto es todo para un juego, cada nodo es en realidad un mosaico en una cuadrícula de nodos, por lo tanto, cómo trabajo 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 haga sentir un poco incómodo, esto es sin que haya otras “cosas del 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 familiarizado con Cython o es familiar, no puedo codificar una línea de C.

Sin más divagaciones, aquí está mi función A Star.

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 

Una optimización fácil es usar conjuntos en lugar de listas para los conjuntos abiertos y cerrados.

 openSet = set() closedSet = set() 

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

Yo usaría los conjuntos como se ha dicho, pero también usaría un montón para encontrar el elemento mínimo (el que será la próxima current ). Esto requeriría mantener un openSet y un openHeap, pero la memoria no debería ser realmente un problema. Además, los conjuntos se insertan en O (1) y los montones en O (registro N) para que sean rápidos. El único problema es que el módulo heapq no está realmente hecho para usar claves con él. Personalmente, simplemente lo modificaría para usar claves. No debería ser muy difícil. Alternativamente, puedes usar tuplas de (tile.H, tile) 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 la path y la path inversa al final. La razón es que la inserción de un elemento en el lugar 0 en una lista es muy lenta, (O (N), creo), mientras que añadir O (1) es si recuerdo bien. 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 

Puse ruta de retorno al final porque parecía que debería desde su código.

Aquí está el código final usando conjuntos, montones 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 [] 

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

Intenté codificar openList como un montón de import heapq montón:

 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, aún debe buscar en el if tile not in openList , así que haría 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 []