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 に答える