A * Производительность на больших картах

Question

Мне нужна помощь для поиска алгоритма AStar, который берет с моей точки зрения далеко в длину. Несмотря на то, что моя карта с 500 * 400 координатами (объективно мой график плитки немного меньше, так как я не взял стены в TileGraph.) Большой, я хотел бы ожидать результата через несколько секунд. Мир выглядит так, несмотря на задачу не будучи шахтной

Я хочу, чтобы найти отмеченных координат «Старт» (120 | 180) к «Зил» (320 | 220), который в настоящее время занимает 48 минут. И жаль всех, кто не говорит по-немецки, но текст на картинке не важен.

Сначала я хочу показать вам, что я запрограммировал для A *. В целом адаптировал себя к псевдокоду в https://en.wikipedia.org/wiki/A * _search_algorithm.

bool AStarPath::Processing(Node* Start, Node* End) 
m_Start = Start; 
m_End = End; 
for (Node* n : m_SearchRoom->GetAllNodes()) 
{ 
    DistanceToStart[n] = std::numeric_limits<float>::infinity(); 
    CameFrom[n] = nullptr; 
} 
DistanceToStart[m_Start] = 0; 
NotEvaluatedNodes.AddElement(0, m_Start); 
while (NotEvaluatedNodes.IsEmpty() == false) 
{ 
    Node* currentNode = NotEvaluatedNodes.GetElement(); 
    NotEvaluatedNodes.DeleteElement(); 
    if (currentNode == m_End) 
    { 
     ReconstructPath(); 
     return true; 
    } 
    EvaluatedNodes.insert(currentNode); 
    ExamineNeighbours(currentNode); 
} 
return false; 
//End Processing 

void AStarPath::ExamineNeighbours(Node* current) 
for (Node* neighbour : m_SearchRoom->GetNeighbours(current)) 
{ 

    if (std::find(EvaluatedNodes.begin(), EvaluatedNodes.end(), neighbour) != EvaluatedNodes.end()) 
    { 
     continue; 
    } 

    bool InOpenSet = NotEvaluatedNodes.ContainsElement(neighbour); 

    float tentative_g_score = DistanceToStart[current] + DistanceBetween(current, neighbour); 

    if (InOpenSet == true && tentative_g_score >= DistanceToStart[neighbour]) 
    { 
     continue; 
    } 

    CameFrom[neighbour] = current; 

    DistanceToStart[neighbour] = tentative_g_score; 

    float Valuation = tentative_g_score + DistanceBetween(neighbour, m_End); 

    if (InOpenSet == false) 
    { 
     NotEvaluatedNodes.AddElement(Valuation, neighbour); 
    } 
    else 
    { 
     NotEvaluatedNodes.UpdatePriority(neighbour, Valuation); 
    } 
} 

// END ExamineNeighbours

double AStarPath::DistanceBetween(Node* a, Node* b) 

return sqrt(pow(m_SearchRoom->GetNodeX(a) - m_SearchRoom->GetNodeX(b), 2) 
    + pow(m_SearchRoom->GetNodeY(a) - m_SearchRoom->GetNodeY(b), 2)); 
//END DistanceBetween 

Я извиняюсь за плохое форматирование, но я не знаю, как работать с кодовыми блоками здесь.

класс AStarPath

частные:

std::unordered_set<Node*> EvaluatedNodes; 


Binary_Heap NotEvaluatedNodes; 


std::unordered_map<Node*, float> DistanceToStart; 


std::unordered_map<Node*, Node*> CameFrom; 

std::vector<Node*> m_path; 

TileGraph* m_SearchRoom; 

// END класса AStarPath

Во всяком случае, я думал сам над моей проблемой уже и изменил некоторые вещи. Во-первых, я реализовал двоичную кучу вместо std :: priority_queue. Я использовал страницу в policyalmanac для этого, но мне не разрешено добавлять другую ссылку, поэтому я не могу дать вам адрес. Это улучшило производительность, но по-прежнему занимает довольно много времени, как я сказал в начале. Во-вторых, я использовал неупорядоченные контейнеры (если есть два варианта), чтобы контейнеры не сортировались после изменений. Для моих EvaluatedNodes я взял std :: unordered_set, поскольку, насколько мне известно, это самый быстрый способ для std :: find, который я использую для проверок сдерживания. Использование std :: unordered_map вызвано необходимостью иметь отдельные ключи и значения. В-третьих, я думал о том, чтобы разбить мою карту на узлы, которые представляют собой несколько координат (вместо того, где теперь один узел представляет одну координату), но я не уверен, как их выбирать. Я думал о настройке точек в позиции, что алгоритм децилирует на основе длины и ширины карты и добавляет соседние координаты, если на базовом узле/координате нет определенного расстояния или больше, и я могу достичь их только из предыдущие добавленные координаты. Чтобы проверить, есть ли возможность ходить, я бы использовал обычный A *, только с координатами (преобразованными в узлы A *), которые находятся в этих больших узлах. Несмотря на это, я не уверен, какие координаты я должен взять для начала и конца этого пути. Это, вероятно, уменьшит количество узлов/координат, которые проверяются, если я использую только координаты/узлы, которые были частью больших узлов. (Так что используются только узлы, где часть более крупных узлов на верхнем уровень)

Прошу прощения за мой английский, но надеюсь, что все будет понятно. Я с нетерпением жду ваших ответов и изучая новые методы и способы решения проблем, а также узнаю обо всех сотнях ошибок глупостей, которые я произвел. Если какой-либо важный аспект неясен или я должен добавить больше кода/информации, не стесняйтесь спрашивать.

EDIT: Binary_Heap

class Binary_Heap 

private: 

std::vector<int> Index; 
std::vector<int> m_Valuation; 
std::vector<Node*> elements; 

int NodesChecked; 

int m_NumberOfHeapItems; 

void TryToMoveElementUp(int i_pos); 

void TryToMoveElementDown(int i_pos); 

public: 

Binary_Heap(int i_numberOfElements); 


void AddElement(int Valuation, Node* element); 


void DeleteElement(); 


Node* GetElement(); 

bool IsEmpty(); 

bool ContainsElement(Node* i_node); 

void UpdatePriority(Node* i_node, float newValuation); 


Binary_Heap::Binary_Heap(int i_numberOfElements) 

Index.resize(i_numberOfElements); 
elements.resize(i_numberOfElements); 
m_Valuation.resize(i_numberOfElements); 

NodesChecked = 0; 

m_NumberOfHeapItems = 0; 

аннулируются Binary_Heap :: AddElement (интермедиат оценка, Node * элемент)

++NodesChecked; 
++m_NumberOfHeapItems; 

Index[m_NumberOfHeapItems] = NodesChecked; 

m_Valuation[NodesChecked] = valuation; 

elements[NodesChecked] = element; 

TryToMoveElementUp(m_NumberOfHeapItems); 

аннулируются Binary_Heap :: DeleteElement()

elements[Index[1]] = nullptr; 
m_Valuation[Index[1]] = 0; 

Index[1] = Index[m_NumberOfHeapItems]; 
--m_NumberOfHeapItems; 

TryToMoveElementDown(1); 

BOOL Binary_Heap :: IsEmpty()

return m_NumberOfHeapItems == 0; 

Node * Binary_Heap :: GetElement()

return elements[Index[1]]; 

BOOL Binary_Heap :: ContainsElement (Node * i_element)

return std::find(elements.begin(), elements.end(), i_element) != elements.end(); 

аннулируются Binary_Heap :: UpdatePriority (Node * i_node, поплавок newValuation)

if (ContainsElement(i_node) == false) 
{ 
    AddElement(newValuation, i_node); 
} 
else 
{ 
    int treePosition; 

    for (int i = 1; i < Index.size(); i++) 
    { 
     if (elements[Index[i]] == i_node) 
     { 
      treePosition = i; 

      break; 
     } 
    } 

    //Won't influence each other, since only one of them will change the position 
    TryToMoveElementUp(treePosition); 
    TryToMoveElementDown(treePosition); 
} 

аннулируются Binary_Heap :: TryToMoveElementDown (INT i_pos)

int nextPosition = i_pos; 

while (true) 
{ 
    int currentPosition = nextPosition; 

    if (2 * currentPosition + 1 <= m_NumberOfHeapItems) 
    { 
     if (m_Valuation[Index[currentPosition]] >= m_Valuation[Index[2 * currentPosition]]) 
     { 
      nextPosition = 2 * currentPosition; 
     } 
     if (m_Valuation[Index[currentPosition]] >= m_Valuation[Index[2 * currentPosition + 1]]) 
     { 
      nextPosition = 2 * currentPosition + 1; 
     } 
    } 
    else 
    { 
     if (2 * currentPosition <= m_NumberOfHeapItems) 
     { 
      if (m_Valuation[Index[currentPosition]] >= m_Valuation[Index[2 * currentPosition]]) 
      { 
       nextPosition = 2 * currentPosition; 
      } 
     } 
    } 

    if (currentPosition != nextPosition) 
    { 
     int tmp = Index[currentPosition]; 
     Index[currentPosition] = Index[nextPosition]; 
     Index[nextPosition] = tmp; 
    } 
    else 
    { 
     break; 
    } 
} 

аннулируются Binary_Heap :: TryToMoveElementUp (INT i_pos)

int treePosition = i_pos; 

while (treePosition != 1) 
{ 
    if (m_Valuation[Index[treePosition]] <= m_Valuation[Index[treePosition/2]]) 
    { 
     int tmp = Index[treePosition/2]; 

     Index[treePosition/2] = Index[treePosition]; 

     Index[treePosition] = tmp; 

     treePosition = treePosition/2; 
    } 
    else 
    { 
     break; 
    } 
} 

Answer 1

Эта линия представляет большую неэффективность, так как он должен перебрать все узлы в очереди, в каждой итерации.

bool InOpenSet = NotEvaluatedNodes.ContainsElement(neighbour); 

Попробуйте использовать более эффективную структуру данных, например. unordered_set, который вы используете для EvaluatedNodes. Всякий раз, когда вы нажимаете или выталкиваете узел из кучи, модифицируйте набор, чтобы всегда содержать только узлы в куче.