Алгоритм поиска пути для одного слоя из файла json для iphone

Question

Я пытаюсь реализовать алгоритм поиска пути A *.M новичок в разработке для iPhone и особенно в игровой части.Хотел спросить, у меня есть массив мозаичных карт, который я читаю из файла json.Получил все значения мозаичной карты в NSArray.Теперь я хочу реализовать алгоритм поиска пути *.Нужно ли мне создавать алгоритм поиска пути A * с помощью input как NSArray, или у нас тоже есть какое-то руководство по нему?Я пробовал Интернет, но получил учебники с участием файлов TMX.Может кто-нибудь опубликовать мне хорошие уроки или пример кода, или, по крайней мере, направить меня в правильном направлении.Это будет очень мило с вашей стороны, ребята.Спасибо.

Answer 1

A * - это алгоритм, который по своей сути применяется к графу. В вашем случае каждый узел на графике соответствует одной плитке на вашей карте.

Каждое ребро на графике соответствует смежности между двумя тайлами.

Внедрение A * не сложно, но это может быть излишним для вашего использования. Вам нужно беспокоиться об использовании приоритетной очереди, поддержке эвристики и т. Д.

В вашем случае простой поиск в ширину может помочь, если на ваших краях нет веса.

Эскиз грубого алгоритма:

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