まず距離の見積もりだけ

経路を引く前に、ゴールがどっちにあるかの見当を持っておく。斜め移動を許さない格子では、横の差と縦の差を足したマンハッタン距離が見当になる。あるマスからゴールまで、最低でもこれだけは歩く、という下限。

各マスの見当を明度で塗る。ゴールに近いほど明るく、遠いほど暗い。同心の菱形の段が並ぶ。

塗り潰した一マスがゴール。それを中心に、菱形の段ができる。横と縦の差を足した値が等しいマスを繋ぐと、斜め45度の菱形になる。斜め移動を許す場合は、横と縦の大きい方を取るチェビシェフ距離に替わり、菱形が正方形になる。

この見当は本当の歩数より大きく見積もらない。壁があれば実際にはもっと回り道する。見当は壁を無視して直線で測るので、必ず本当の歩数以下に収まる。