*由json文件iphone构成的单层寻径算法

Question

我正在尝试实现一个*寻路算法。我刚接触iphone开发，尤其是游戏方面。我想问一下，我有一个从json文件读取的平铺映射数组m。在NSArray中获取平铺地图的所有值。现在我想在上面实现一个*寻路算法。我是否必须自己创建A*寻路算法，并将输入作为NSArray，或者我们也有它的任何教程。我已经尝试了互联网，但得到了有关tmx文件的教程。有没有人可以给我发一些很好的教程或者示例代码，或者至少给我指引一个正确的方向。你们真是太好了。谢谢。

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