ここでは通常の歩数マップ(1マス1歩)を理解していることを前提に話を進めていきます。
通常の歩数マップでは、区画の中心にノードを置いてあるものとして考えられています。
よって、ノードとノードの間には常に一定の距離(常に1)であるため、1歩=1マスとなります。
今回考える歩数マップでは、ノードを別の位置に定義します。
上の図は前述の歩数Mapの考え方によって、生成される歩数マップと、予想される経路です。
2つの経路が生成されています。 斜め走行が可能な場合、この迷路では斜めを選択した方が速いと思います。
この時、 『目の前に同じ歩数を持つ区画が2つ以上存在する場合、それらを適切に選択するプログラムが必要になる』 ことが問題になります。
この歩数Mapを基準に良い経路を求めるためには、ここから独自のアルゴリズムを用いることになると思います。
次に、拡張歩数Mapの考え方によって、生成される歩数マップと、予想される経路です。
この歩数Mapの生成には以下の考え方を用いています。
1:各区画の境界をノードとする。
⇒壁の中は最大値int方の最大値等、十分大きい数を与えておきます。
2:壁の長さを7とし、直角二等辺三角形(1:1.4142… ≒ 5:7)を用いて、
直進=7、曲がる=5とする。
⇒歩数を具体的な距離としています。最短経路=最速経路とは限らないが、十分に近くなることが見込める。
上記に紹介した理論は、全て一定の速度で移動するならば、最短の経路=最速の経路を導出できたと言えます。
しかし、実際にマウスが走る際には、加速と減速を繰り返すことから、このままでは不十分となります。
このとき、以下の考えを導入します。
これにより、マップ上に『加速度』が考慮された歩数マップが生成され、より最速経路に近い経路導出が可能になると言えます。
一方で、
に対して、基準値よりも大きい値を与えるという工夫も有効である考えられます。