json 파일로 만든 단일 레이어에 대한 경로 찾기 * iphone

Question

A * 길 찾기 알고리즘을 구현하려고합니다. 새로운 iPhone 개발 및 특히 게임 측면에 새로운. 내가 물어보고 싶은 것은, json 파일로부터 타일 맵 배열을 읽는 것이다. NSArray에 타일 맵의 모든 값을 가져 왔습니다. 이제는 A * 길 찾기 알 고를 구현하고 싶습니다. NSArray와 같은 입력을 사용하여 A * pathfinding algo를 직접 생성해야합니까? 아니면 자습서가 있습니까? 나는 인터넷을 시도했지만 tmx 파일을 포함하는 튜토리얼을 가지고있다. 누구든지 나에게 좋은 자습서 나 샘플 코드 또는 atleast를 올바른 방향으로 직접 게시 할 수 있습니까? 너희들 정말 좋을거야. 고맙습니다.

Answer 1

A *는 그래프에 적용되는 핵심 알고리즘입니다. 귀하의 경우 그래프의 모든 노드는지도의 단일 타일에 해당합니다.

그래프의 모든 가장자리는 두 타일 간의 인접한에 해당합니다.

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()