python - 我的 A Star 实现不会返回到达目的地的步骤列表

Question

我会尽量简短。我正在尝试在 Python 上实现 A Star，但显然我做错了什么，因为当我测试它时，它没有返回到达目的地的步骤列表。

基本上，上下文是:我有一张 map ，表示为由节点形成的图形。我有一个 Player 类、一个 Node 类和一个 Graph 类。这无关紧要，但可能是必要的。玩家必须到达最近的有硬币的节点，这也是一个类。

我的实现基于维基百科伪代码，但由于某些原因它无法工作。我几乎完全确定我的错误在 A* 星上，但我找不到它。在这里，我将放上我为 A Star 制作的两个功能。希望它不会太乱，我刚开始编程，我很喜欢评论。

如果能帮我找到问题，我将不胜感激:)

注意:我不会说英语，所以我为我的错误感到抱歉。希望几年后，我能更好地沟通。

def A_Star(player,graph,array_of_available_coins):
    # Define the initial position and the last position, where the coin is
    initial_position=player.position # Player is a class. Position is of type Node 
    final_position=closest_cpin(player,graph,array_of_available_coins)

    # Define the open_set, closed_set, and work with a Heap.
    open_set=[initial_position] # Open_set will be initialized with the current position of the player
    closed_set=[]
    heapq.heapify(open_set) # Converts the open_set into a Python Heap (or Priority Queue)
    came_from={} # It's a dictionary where each key is the a node, and the value is the previous node in the path

    # Modify G and H, and therefore F, of the initial position. G of the inicial position is 0.
    #And H of the initial position is the pitagoric distance.
    initial_position.modify_g_and_h(0,initial_position.distance(final_position))


    while open_set!=[]: 
        square=heapq.heappop(open_set) # Gets the least value of the open_set
        if square.is_wall(): # If it's a Wall, the player can't move over it.
            continue
        if square==final_position:
            movements=[] # Creates a empty array to save the movements 
            rebuild_path(came_from,square,movements) # Calls the function to rebuild the path
            player.add_movements_array(movements) # Copies the movements into the movements array of the player
            return

        # In this point, the square is not a wall and it's not the final_position

        closed_set.append(square) # Add the square into the closed_set

        neighbours=graph.see_neighbours(square) # Checks all the neighbours of the current square

        for neigh in neighbours:
            if neigh.is_wall()==True:
                continue
            if neigh in closed_set:
                continue

            # Calculates the new G, H and F values
            g_aux=square.see_g()+square.get_cost(neigh) # Current g + the cost to get from current to neighbour
            h_aux=neigh.distance(final_position) # Pitagoric distance between the neighbour and the last position
            f_aux=g_aux+h_aux # F=G+H

            if neigh not in open_set:
                heapq.heappush(open_set,neigh) # Adds the neigh into the open_set
                is_better=True 
            elif f_aux<neigh.see_f():
                is_better=True
            else: 
                is_better=False

            if is_better==True:
                came_from[neigh]=square # The actual neigh came from the actual square
                neigh.modify_g_and_h(g_aux,h_aux) #Modifies the g and h values of the actual neighbour

    return None

def rebuild_path(came_from,square,array_of_movements):
    array_of_movements.insert(0,square) # Adds, in the first position of the array, the square it gets by parameter

    if not square in came_from: # if there is no key "square" in the came_from dictionary, then it's the first position
        array_of_movements.remove(array_of_movements[0]) # Gets the first element of the array out (because i need it to be that way later)
        return array_of_movements

    rebuild_path(came_from,came_from[square],array_of_movements)
    return

问题是，我必须实现该算法，因为它是练习的一部分(更大，有 Pygame 和所有东西)，这是唯一让我紧张的事情。如果我用了一个库，它会算作我没有用过，所以我必须重新交付它:(

Answer 1

我会推荐networkx

import networkx 

这可以做这样的事情:

#!/usr/bin/env python
# encoding: utf-8
"""
Example of creating a block model using the blockmodel function in NX.  Data used is the Hartford, CT drug users network:

@article{,
title = {Social Networks of Drug Users in {High-Risk} Sites: Finding the Connections},
volume = {6},
shorttitle = {Social Networks of Drug Users in {High-Risk} Sites},
url = {http://dx.doi.org/10.1023/A:1015457400897},
doi = {10.1023/A:1015457400897},
number = {2},
journal = {{AIDS} and Behavior},
author = {Margaret R. Weeks and Scott Clair and Stephen P. Borgatti and Kim Radda and Jean J. Schensul},
month = jun,
year = {2002},
pages = {193--206}
}

"""

__author__ = """\n""".join(['Drew Conway <drew.conway@nyu.edu>',
                          'Aric Hagberg <hagberg@lanl.gov>'])

from collections import defaultdict
import networkx as nx
import numpy
from scipy.cluster import hierarchy
from scipy.spatial import distance
import matplotlib.pyplot as plt


def create_hc(G):
"""Creates hierarchical cluster of graph G from distance matrix"""
path_length=nx.all_pairs_shortest_path_length(G)
distances=numpy.zeros((len(G),len(G)))
for u,p in path_length.items():
    for v,d in p.items():
        distances[u][v]=d
# Create hierarchical cluster
Y=distance.squareform(distances)
Z=hierarchy.complete(Y)  # Creates HC using farthest point linkage
# This partition selection is arbitrary, for illustrive purposes
membership=list(hierarchy.fcluster(Z,t=1.15))
# Create collection of lists for blockmodel
partition=defaultdict(list)
for n,p in zip(list(range(len(G))),membership):
    partition[p].append(n)
return list(partition.values())

if __name__ == '__main__':
G=nx.read_edgelist("hartford_drug.edgelist")

# Extract largest connected component into graph H
H=nx.connected_component_subgraphs(G)[0]
# Makes life easier to have consecutively labeled integer nodes
H=nx.convert_node_labels_to_integers(H)
# Create parititions with hierarchical clustering
partitions=create_hc(H)
# Build blockmodel graph
BM=nx.blockmodel(H,partitions)


# Draw original graph
pos=nx.spring_layout(H,iterations=100)
fig=plt.figure(1,figsize=(6,10))
ax=fig.add_subplot(211)
nx.draw(H,pos,with_labels=False,node_size=10)
plt.xlim(0,1)
plt.ylim(0,1)

# Draw block model with weighted edges and nodes sized by number of internal nodes
node_size=[BM.node[x]['nnodes']*10 for x in BM.nodes()]
edge_width=[(2*d['weight']) for (u,v,d) in BM.edges(data=True)]
# Set positions to mean of positions of internal nodes from original graph
posBM={}
for n in BM:
    xy=numpy.array([pos[u] for u in BM.node[n]['graph']])
    posBM[n]=xy.mean(axis=0)
ax=fig.add_subplot(212)
nx.draw(BM,posBM,node_size=node_size,width=edge_width,with_labels=False)
plt.xlim(0,1)
plt.ylim(0,1)
plt.axis('off')
plt.savefig('hartford_drug_block_model.png')