iphone - 由 json 文件 iphone 制作的单层的 A* 寻路算法

Question

我正在尝试实现 A* 寻路算法。我是 iPhone 开发新手，尤其是游戏方面的新手。想问一下，我有一个从 json 文件中读取的平铺 map 数组 m。在 NSArray 中获取平铺 map 的所有值。现在我想在上面实现 A* 寻路算法。我是否必须自己创建输入为 NSArray 的 A* 寻路算法，或者我们是否也有它的任何教程。我试过互联网，但得到了涉及 tmx 文件的教程。谁能给我发一些不错的教程或示例代码，或者至少指导我正确的方向。你们真的很好。谢谢。

Answer 1

A* 是一种算法，其核心是应用于图形。在您的例子中，图表上的每个节点都对应于 map 中的一个图 block 。

图中的每条边都对应于两个图 block 之间的一个邻接。

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