サークルに関数を適用するためのトリックがありますか？

Question

A *アルゴリズムを使用して、限られたハードウェア（CPU：Vortex86,256MB）上のポイントAからポイントBまでの良好なパスを見つけたいと考えています。私は固定された障害を持つ300x200のセルのグリッドを持っています。障害物を避けるためのヒットボックスはディスクです。

私はヒットボックスがA *で非常に頻繁に行われるように障害物と衝突しているかどうかをチェックする最適な方法を探しています。

最も明白な方法は次のようにディスクの全領域をチェックすることでした：

radiusは、ディスクおよびディスクの中央の center座標の半径である

bool check(std::function<bool(const Coordinates &)> collide) 
{ 
    const std::uint32_t RADIUS2 = radius * radius; 
    Coordinates cell(-radius, -radius); 

    for (; cell.x <= radius; cell.x++) 
    { 
     for (cell.y = -radius; cell.y <= radius; cell.y++) 
     { 
      if (cell.x * cell.x + cell.y * cell.y <= RADIUS2 && !collide(center + cell)) 
      { 
       return false; 
      } 
     } 
    } 

    return true; 
} 

。

もっと良い解決策は、ディスクの外周をチェックすることだけかもしれません。しかし、両方のソリューションは2 forのループを使用する必要があり、時間の大部分を占めるディスク領域には適合しません。

あなたはそれを賢明なやり方で解決する方法はありますか？

Answer 1

ネストされたループ内では、std::function::operator()を呼び出しています。これは間接的な呼び出しであり、抽象的な抽象的なペナルティはありません。今すぐ近代 CPUは、最初のいくつかの呼び出しの後にその分岐を正常に予測する分岐予測を持つでしょう。しかし、あなたの古いチップはすぐそこに苦しむでしょう。

だから、本当にこれを避ける必要があります。幸いにも、最初のコメントはすでに頭の爪に当たっています。障害物を回避するためのゾーンを計算することで、ヒットテストを効率的に事前計算することができます。

また、障害が移動しないと仮定すると、ヒットテストの結果を各セルにキャッシュすることができます。これは、最初に小さな部品しか必要としない大きなグリッドを使用している場合に特に効果的です。