マイクロマウスロボット制作に関わるヒントを記録
2024年度はマイクロマウス20年目｡
（2024-03-10)
斜め・回転を考えず、単純な歩数を幅優先探索で求めるだけなら、192byteでいけるよ！探査or未探査=1bit*32*32=128byte探索ノードが保持すべき親ノードを示す情報：2bit同時にあらわれる探索ノードの最悪個数:（32-1）*4=124マス128+124*2/4=192byte
まあもちろん何かをあきらめれば小さくできますが．．．ちなみに50kByteの内訳は，迷路の壁，既探索か未探索かの情報・・・4k枝情報・・・1.6k上記迷路情報の退避用配列・・・(4+1.6)*2k簡易最短経路計算用配列・・・8k経路計算高速化用配列・・・8k最短経路計算用配列・・・8k経路計算高速化用配列・・・8k経路格納用配列・・・1k現在はざっと削って25kくらいになっています
2 件のコメント:
斜め・回転を考えず、単純な歩数を幅優先探索で求めるだけなら、192byteでいけるよ！
探査or未探査=1bit*32*32=128byte
探索ノードが保持すべき親ノードを示す情報：2bit
同時にあらわれる探索ノードの最悪個数:（32-1）*4=124マス
128+124*2/4=192byte
まあもちろん何かをあきらめれば小さくできますが．．．
ちなみに50kByteの内訳は，
迷路の壁，既探索か未探索かの情報・・・4k
枝情報・・・1.6k
上記迷路情報の退避用配列・・・(4+1.6)*2k
簡易最短経路計算用配列・・・8k
経路計算高速化用配列・・・8k
最短経路計算用配列・・・8k
経路計算高速化用配列・・・8k
経路格納用配列・・・1k
現在はざっと削って25kくらいになっています
コメントを投稿