1

它返回值（21、2、0、-1、-1 等），而实际上它应该只返回原点和目标，因为两者之间有一条清晰的路径。我无法理解我做错了什么。注意：代码似乎只是返回最接近原点（寻路对象）的节点，然后是目标 (0)，而不管原点的位置。更新：新代码（现在显示在下面代替其他代码）只是将目标节点作为序列中的下一个返回，而不管该特定路径是否被阻塞。

def Dijkstra(NodeDistanceApart, Target):
    #finds the shortest path according to node distances


    #0 - Initializes values for pathfinding
    NodeDistanceFromOrigin = [10000.0] * NUMBEROFNODES
    NodeSolved = [False] * NUMBEROFNODES
    NodeArcSet = [[-1] * NUMBEROFNODES for x in range(NUMBEROFNODES)]
    ClosestNode = 0
    PreviousNode = 0

    #1 - Sets the origin node (the NPC node) and the target node (the player node) values
    NodeSolved[NUMBEROFNODES2] = True
    NodeDistanceFromOrigin[NUMBEROFNODES2] = 0
    NodeArcSet[NUMBEROFNODES2][0] = NUMBEROFNODES2

    #2 - finds the shortest path
    while NodeSolved[0] == False:
        ClosestNode = 0
        for n in range(NUMBEROFNODES):
            if NodeSolved[n] == True:#loops through nodes, if a node is solved, find connected nodes
                for i in range(NUMBEROFNODES):
                    if NodeSolved[i] == False and NodeDistanceApart[n][i] < 10000:#loops through nodes, if a node is solved or unconnected, then ignore it
                        if (NodeDistanceFromOrigin[n] + NodeDistanceApart[n][i]) < NodeDistanceFromOrigin[i]:
                            NodeDistanceFromOrigin[i] = NodeDistanceFromOrigin[n] + NodeDistanceApart[n][i]
                        if NodeDistanceFromOrigin[i] < NodeDistanceFromOrigin[ClosestNode]:
                            ClosestNode = i
                            PreviousNode = n
        NextInArray = -1
        n = 0
        while NextInArray == -1:#finds the next unused index in the array for a nodes arc set
            if NodeArcSet[ClosestNode][n] == -1:
                NextInArray = n
            n = n + 1
        NodeSolved[ClosestNode] = True
        NodeArcSet[ClosestNode] = NodeArcSet[PreviousNode]
        NodeArcSet[ClosestNode][NextInArray] = ClosestNode
    print(NodeArcSet[0])
    return NodeArcSet
4

1 回答 1

1

我没有阅读整个算法，因为实现存在严重错误。

问题是这条线

NodeArcSet = [[-1] * NUMBEROFNODES] * NUMBEROFNODES

这将创建指向同一数组 [[-1]*NUMBEROFNODES] 的 NUMBEROFNODES 指针。

>>> a=[[0]*2]*2
>>> a
[[0, 0], [0, 0]]
>>> a[0][0]=1
>>> a
[[1, 0], [1, 0]]

我为解决此问题所做的事情类似于

NodeArcSet = [[-1] * NUMBEROFNODES for x in xrange(NUMBEROFNODES)] 
                     # In python 3 you should use range instead of xrange.
于 2012-12-03T11:50:29.997 回答