Python - accélérer la recherche de chemin

Question

C'est ma fonction de recherche de chemin :

def get_distance(x1,y1,x2,y2):
    neighbors = [(-1,0),(1,0),(0,-1),(0,1)]
    old_nodes = [(square_pos[x1,y1],0)]
    new_nodes = []
    for i in range(50):
        for node in old_nodes:
            if node[0].x == x2 and node[0].y == y2:
                return node[1]
            for neighbor in neighbors:
                try:
                    square = square_pos[node[0].x+neighbor[0],node[0].y+neighbor[1]]
                    if square.lightcycle == None:
                        new_nodes.append((square,node[1]))
                except KeyError:
                    pass
        old_nodes = []
        old_nodes = list(new_nodes)
        new_nodes = []
        nodes = []
    return 50

Le problème est que l'IA met trop de temps à répondre. temps de réponse <= 100ms ) C'est juste une façon python de faire https://en.wikipedia.org/wiki/Pathfinding#Sample_algorithm

Answer 1

Vous devez remplacer votre algorithme par Recherche A* avec la distance de Manhattan comme heuristique.

Answer 2

Une solution raisonnablement rapide est d'implémenter l'algorithme de Dijkstra (que j'ai déjà implémenté dans cette question ) :

Construire la carte originale. C'est un tableau masqué où le marcheur ne peut pas marcher sur un élément masqué :

%pylab inline
map_size = (20,20)
MAP = np.ma.masked_array(np.zeros(map_size), np.random.choice([0,1], size=map_size))
matshow(MAP)

Voici l'algorithme de Dijkstra :

def dijkstra(V):
    mask = V.mask
    visit_mask = mask.copy() # mask visited cells
    m = numpy.ones_like(V) * numpy.inf
    connectivity = [(i,j) for i in [-1, 0, 1] for j in [-1, 0, 1] if (not (i == j == 0))]
    cc = unravel_index(V.argmin(), m.shape) # current_cell
    m[cc] = 0
    P = {}  # dictionary of predecessors 
    #while (~visit_mask).sum() > 0:
    for _ in range(V.size):
        #print cc
        neighbors = [tuple(e) for e in asarray(cc) - connectivity 
                     if e[0] > 0 and e[1] > 0 and e[0] < V.shape[0] and e[1] < V.shape[1]]
        neighbors = [ e for e in neighbors if not visit_mask[e] ]
        tentative_distance = [(V[e]-V[cc])**2 for e in neighbors]
        for i,e in enumerate(neighbors):
            d = tentative_distance[i] + m[cc]
            if d < m[e]:
                m[e] = d
                P[e] = cc
        visit_mask[cc] = True
        m_mask = ma.masked_array(m, visit_mask)
        cc = unravel_index(m_mask.argmin(), m.shape)
    return m, P

def shortestPath(start, end, P):
    Path = []
    step = end
    while 1:
        Path.append(step)
        if step == start: break
        if P.has_key(step):
            step = P[step]
        else:
            break
    Path.reverse()
    return asarray(Path)

Et le résultat :

start = (2,8)
stop = (17,19)
D, P = dijkstra(MAP)
path = shortestPath(start, stop, P)
imshow(MAP, interpolation='nearest')
plot(path[:,1], path[:,0], 'ro-', linewidth=2.5)

Ci-dessous, quelques statistiques de chronométrage :

%timeit dijkstra(MAP)
#10 loops, best of 3: 32.6 ms per loop

Answer 3

Le plus gros problème avec votre code est que vous ne faites rien pour éviter que les mêmes coordonnées soient visitées plusieurs fois. Cela signifie que le nombre de noeuds visités est de garanti de croître de manière exponentielle, puisqu'il peut faire de nombreux allers-retours sur les premiers nœuds.

La meilleure façon d'éviter la duplication est de maintenir une set des coordonnées que nous avons ajoutées à la file d'attente (bien que si votre node les valeurs sont hachables, vous pourriez être en mesure de les ajouter directement à l'ensemble au lieu de coordonner les tuples). Puisque nous effectuons une recherche en largeur, nous atteindrons toujours une coordonnée donnée par (l'un des) chemin(s) le(s) plus court(s), nous n'aurons donc jamais à nous soucier de trouver un meilleur chemin par la suite.

Essayez quelque chose comme ça :

def get_distance(x1,y1,x2,y2):
    neighbors = [(-1,0),(1,0),(0,-1),(0,1)]
    nodes = [(square_pos[x1,y1],0)]
    seen = set([(x1, y1)])
    for node, path_length in nodes:
        if path_length == 50:
            break
        if node.x == x2 and node.y == y2:
            return path_length
        for nx, ny in neighbors:
            try:
                square = square_pos[node.x + nx, node.y + ny]
                if square.lightcycle == None and (square.x, square.y) not in seen:
                    nodes.append((square, path_length + 1))
                    seen.add((square.x, square.y))
            except KeyError:
                pass
    return 50

J'ai également simplifié un peu la boucle. Plutôt que de changer la liste après chaque profondeur, vous pouvez simplement utiliser une boucle et ajouter à sa fin pendant que vous itérez sur les valeurs précédentes. Je m'arrête toujours si un chemin n'a pas été trouvé en moins de 50 étapes (en utilisant la distance stockée dans le 2-tuple, plutôt que le nombre de passages de la boucle externe). Une autre amélioration pourrait être d'utiliser un collections.dequeue pour la file d'attente, puisque vous pourriez efficacement pop d'une extrémité tandis que append à l'autre bout. Cela ne fera probablement pas une grande différence, mais pourrait éviter un peu d'utilisation de la mémoire.

J'ai également évité la plupart des indexations par un et par zéro en faveur d'un déballage dans des noms de variables séparés dans le fichier for boucles. Je pense que c'est beaucoup plus facile à lire, et cela évite toute confusion puisque les deux différents types de 2-tuples avaient des significations différentes (l'un est un node, distance l'autre est x, y ).