マイクロマウス迷路探索シミュレータの製作

マイクロマウス迷路探索シミュレータの製作

6438150af1c6caa04bed27d5e04e668f.png

レポジトリ

  • このプロジェクトはまたしてもBitbucketでバージョン管理しています.
    https://bitbucket.org/tokoro10g/mousesim-revb

目標

  • GUIベースのシミュレータにするため,Qtを使用してみる
  • 斜め走行などの実装を行うため,グラフ生成部分を大幅に変更する
  • 前回同様最短経路探索は \(A^\ast\) algorithm
  • 迷路探索部分とシミュレータの表示部分を分離することで,移植を簡単にする

方針

迷路に対して下の図のようなグラフを生成すれば斜め走行も簡単に考えられるのでは・・・?
ノード数は \(2n(n-1)\) ,エッジ数は \(6n^2-12n+4\ (n\geq 2)\)

Bc7nKjqCUAA43Sa.png

ギャラリー

結果

  • どれだけ頑張っても計算量が多く,マシンに積むとギリギリだった
  • 今後は単純なアルゴリズム(歩数マップなど)と併用して,ハイブリッドに解くものを考えていきたい
  • 同時に,直線や斜めなどの重み付けが容易にできるようにしたい
Share Comments