Python - Accelera un Algoritmo Pathfinding A Star

Question

Ho codificato il mio primo algoritmo leggermente complesso, un'implementazione dell'algoritmo A Star Pathfinding. Ho seguito alcuni Python.org advice sull'implementazione dei grafici, quindi un dizionario contiene tutti i nodi a cui è collegato anche ciascun nodo. Ora, dato che questo è tutto per un gioco, ogni nodo è in realtà solo una tessera in una griglia di nodi, quindi come sto elaborando l'euristica e il mio riferimento occasionale a loro.

Grazie a timeit, so che posso eseguire questa funzione con successo un po 'più di cento volte al secondo. Comprensibilmente questo mi rende un po 'a disagio, questo è senza alcun' roba di gioco 'in corso, come grafica o calcolo della logica di gioco. Quindi mi piacerebbe vedere se qualcuno di voi può accelerare il mio algoritmo, sono completamente estraneo a Cython o è parente, non riesco a codificare una riga di C.

Senza altro vagante, ecco il mio A Funzione stella.

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

Un'ottimizzazione semplice è utilizzare set anziché elenchi per i set aperti e chiusi.

openSet = set() 
closedSet = set() 

Questo renderà tutto il in e not in test O (1) invece di O (n ).

Answer 2

Come suggerito sopra, impostare in un set.

ho cercato di codifica openList come un mucchio 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 

Tuttavia, è ancora bisogno di cercare al if tile not in openList, quindi vorrei fare questo:

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

Vorrei utilizzare il set come hanno fatto stato detto, ma vorrei anche usare un mucchio per trovare l'elemento minimo (quello che sarà il prossimo current). Ciò richiederebbe mantenere sia un openSet che un openHeap, ma la memoria non dovrebbe essere davvero un problema. Inoltre, imposta insert in O (1) e heap in O (log N) in modo che siano veloci. L'unico problema è che il modulo heapq non è fatto apposta per usare le chiavi con esso. Personalmente, vorrei solo modificarlo per usare le chiavi. Non dovrebbe essere molto difficile. In alternativa, puoi semplicemente usare tuple di (tile.H, tile) nell'heap.

Inoltre, vorrei seguire l'idea di aaronasterling di utilizzare l'iterazione anziché la ricorsione, ma anche, aggiungerei elementi alla fine di path e invertire path alla fine. Il motivo è che l'inserimento di un elemento al 0 ° posto in una lista è molto lento, (O (N) credo), mentre l'aggiunta è O (1) se ricordo correttamente. Il codice finale per quella parte sarebbe:

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

Ho messo il percorso di ritorno alla fine perché sembrava che fosse dal tuo codice.

Ecco il codice finale utilizzando set, i cumuli ei cosa 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 []