差分
この文書の現在のバージョンと選択したバージョンの差分を表示します。
|
拡張歩数mapでの経路導出 [2015/02/04 20:13] member |
拡張歩数mapでの経路導出 [2015/03/01 15:25] (現在) member |
||
|---|---|---|---|
| ライン 7: | ライン 7: | ||
| よって、ノードとノードの間には常に一定の距離(常に１)であるため、１歩＝１マスとなります。 | よって、ノードとノードの間には常に一定の距離(常に１)であるため、１歩＝１マスとなります。 | ||
| - | 今回考える歩数マップでは、ノードの位置を別のところに置くものとします。 | + | 今回考える歩数マップでは、ノードを別の位置に定義します。 |
| - | ====== ノードの付けかた ====== | + | ====== ノードの付け方による違い ====== |
| - | 随時、執筆します。 | + | {{:map1.jpg|}} |
| + | |||
| + | 上の図は前述の歩数Mapの考え方によって、生成される歩数マップと、予想される経路です。 | ||
| + | |||
| + | ２つの経路が生成されています。 | ||
| + | 斜め走行が可能な場合、この迷路では斜めを選択した方が速いと思います。 | ||
| + | |||
| + | この時、 | ||
| + | 『目の前に同じ歩数を持つ区画が２つ以上存在する場合、それらを適切に選択するプログラムが必要になる』 | ||
| + | ことが問題になります。 | ||
| + | |||
| + | この歩数Mapを基準に良い経路を求めるためには、ここから独自のアルゴリズムを用いることになると思います。 | ||
| + | |||
| + | 次に、拡張歩数Mapの考え方によって、生成される歩数マップと、予想される経路です。 | ||
| + | |||
| + | {{:map2.jpg|}} | ||
| + | |||
| + | この歩数Mapの生成には以下の考え方を用いています。 | ||
| + | |||
| + | １：各区画の境界をノードとする。 | ||
| + | |||
| + | ⇒壁の中は最大値int方の最大値等、十分大きい数を与えておきます。 | ||
| + | |||
| + | ２：壁の長さを７とし、直角二等辺三角形（1:1.4142... ≒ 5:7）を用いて、 | ||
| + | |||
| + | 直進＝７、曲がる＝５とする。 | ||
| + | |||
| + | ⇒歩数を具体的な距離としています。最短経路＝最速経路とは限らないが、十分に近くなることが見込める。 | ||
| + | |||
| + | ====== 重み付け拡張歩数Map ====== | ||
| + | 上記に紹介した理論は、全て一定の速度で移動するならば、最短の経路＝最速の経路を導出できたと言えます。 | ||
| + | |||
| + | しかし、実際にマウスが走る際には、加速と減速を繰り返すことから、このままでは不十分となります。 | ||
| + | |||
| + | このとき、以下の考えを導入します。 | ||
| + | * 歩数Mapの生成を行う際、『一定以上』直進が続くならば、基準値(5or7)よりも小さい値を用いその区画を更新する。 | ||
| + | これにより、マップ上に『加速度』が考慮された歩数マップが生成され、より最速経路に近い経路導出が可能になると言えます。 | ||
| + | |||
| + | 一方で、 | ||
| + | * マウスの動作上タイムロスに繋がるような動き（ターン） | ||
| + | * ターンの難易度（リスク）が高いもの | ||
| + | に対して、基準値よりも大きい値を与えるという工夫も有効である考えられます。 | ||
