2次元配列の距離を効率よく計算する

Question

私はボンバーマン型のゲームを作っています。 2点間の距離を計算したい。プレーヤーは4方向に移動できます。私が（0,0）にいて、（5,5）に行きたい場合は、タクシーの距離の式（（5-0）+（5-0））を使って距離を計算できます。垂直。

しかし、今では、プレーヤーが移動できない壁をゲームに実装したいと考えています。

タクシーブックの式を使用する距離の私の現在の実装。

int distanceTo(Position Pos) 
{ 
    return (abs(this->x - Pos.x) + abs(this->y - Pos.y)); 
} 

は、どのように私はその間に来る不動ボックス/壁を考慮すると、二つの点（x1、y1）と（x2、y2）との間の距離を見つけるのですか？

Answer 1

障害がある場合は、簡単なタクシーの距離計算式をより洗練された経路探索アルゴリズムに置き換える必要があります。

グリッドはどのくらいですか？ Dijkstraのアルゴリズムは小さなグリッドで、A *（Dijkstraの修正）は大きなものに対しては機能します。

Amit PatelにはDijkstra'sとA *とそれぞれの実装の詳細を記述する優れたリソースがあります。あなたはそれを表示することがありますhere。