A * Pathfinding в 2D Sidescroller

Question

В настоящее время я пытаюсь использовать A * pathfinding в моей 2D-прокруткой-процедурно созданной мировой игре (думаю, что такая Terraaria-подобная местность).

Я использую этот ресурс: http://www.redblobgames.com/pathfinding/a-star/introduction.html

И был в основном с помощью следующего псевдокода: данного

frontier = PriorityQueue() 
frontier.put(start, 0) 
came_from = {} 
cost_so_far = {} 
came_from[start] = None 
cost_so_far[start] = 0 

while not frontier.empty(): 
    current = frontier.get() 

    if current == goal: 
     break 

    for next in graph.neighbors(current): 
     new_cost = cost_so_far[current] + graph.cost(current, next) 
     if next not in cost_so_far or new_cost < cost_so_far[next]: 
     cost_so_far[next] = new_cost 
     priority = new_cost + heuristic(goal, next) 
     frontier.put(next, priority) 
     came_from[next] = current 

Моего вопроса: в 2D-прокрутке с большим процедурно генерируемым миром , как я могу выбрать границу? Путь к определенной плите может находиться на любом расстоянии, и, очевидно, кажется неразумным перебирать всю карту.

Я стараюсь сделать это эффективно, поэтому любая помощь будет оценена!

Answer 1

Я никогда не слышал, чтобы его называли «границей», он всегда был «открытым списком», и вы помещали туда все узлы, с которыми вы можете путешествовать - соседи.

Производительность-накрест вещей я использовал:

1) Помещенного вычисление в другом потоке: (не сопрограмма) ознакомьтесь с ThreadedJob здесь http://answers.unity3d.com/questions/357033/unity3d-and-c-coroutines-vs-threading.html Это создаст отставание - результат будет несколько кадров после того, как вы его назовете: a) просто подождите; б) начать движение в общем направлении цели и изменить путь после получения результатов; c) перейти к первому узлу пути, даже остальное еще не готово.

2) кэшировать результаты: Dictionary<Vector4, List<Vector2>> pathCache; где ключ, Vector4, является startPosX, startPosY, finishPosX, finishPosY, и список значений является результатом A *. Поскольку путь является симметричным, вы также должны проверить кеш для B-> A и перевернуть путь, когда вы ищете путь от A до B.