jsonファイルから作成された単層のための*経路探索アルゴリズムiphone

Question

私はA * pathfinding algoを実装しようとしています。 iPhone開発と特にゲーム面での新しいもの。私は、jsonファイルからタイルマップ配列を読み込んでいます。 NSArrayのタイルマップのすべての値を取得します。今私はそれにA * pathfinding algoを実装したいと思います。 A * pathfinding algoをNSArrayとして入力して作成する必要がありますか、それともチュートリアルもありますか？私はインターネットを試みたが、tmxファイルを含むチュートリアルを手に入れた。誰か私に素晴らしいチュートリアルやサンプルコードを載せてもらえますか？それはあなたの人の本当にいいだろう。ありがとうございました。

Answer 1

A *は、そのコアがグラフに適用されているアルゴリズムです。あなたの場合、グラフ上のすべてのノードはマップ内の1つのタイルに対応します。

グラフの各辺は、2つのタイルの間の隣接関係に対応しています。

A *の実装は困難ではありませんが、使用するには過度の可能性があります。優先度キューの使用、ヒューリスティックのサポートなどを心配する必要があります。

場合によっては、エッジに重みがない限り、単純なbreadth-first-searchがこのトリックを行う可能性があります。

ラフアルゴリズムスケッチ：

ShortestPath(start, goal): 
    let queue = new Queue 
    queue.Enqueue(start) 
    while (queue is not empty): 
     let node = queue.Dequeue() 
     if (node == goal) 
      break; 
     else 
      for each adjacent node, aNode: 
       // only add unvisited nodes 
       if (aNode.previous == null) 
        aNode.previous = node 
        queue.Enqueue(previous) 

    if (node != goal) return failure // we never found the goal, so there's no path 

    // trace back your path into a list structure   
    let path = new List 

    while (node != null): 
     path.Add(node) 
     node = node.previous 

    // it's in a backwards order, so reverse it 
    return path.Reverse()