迷路探索ライブラリをRust移植するために調べたことのメモ

迷路探索ライブラリをRust移植するために調べたことのメモ

この記事の目的

個人的な備忘録です. 読んでも有用な情報はあまりないと思います.

えーと,前回の記事 を書いたおかげでブログ更新のハードルが下がりました. アホみたいな記事を書くのもいいもんですね.

どうやらRustがアツいらしい

どうやらRustがアツいらしいということはずいぶん前から見たり聞いたりしていたのですが,当時は仕様が安定していなかったり未実装の機能が多かったりと,開発しづらいイメージが先行してしまい,結局2020年に入るまでいじらずじまいでいました. ところが最近になってROS互換のフレームワークをRust実装しているらしいロボットベンチャーが現れたり,STM32をはじめとする ARM Cortex-M 系マイコン向けのサポートの整備が急速に進んだりしており,「乗るしかない!このビッグウェーブに!」と思い現在に至るわけです.

どうアツいのか

散々ほかのサイトでも解説されていると思いますが,私の知る限りのRustのアツい点を羅列すると,

  • C, C++と同様にバイナリにコンパイルする言語であること (マイコン使いには重要)
  • 標準装備のビルドシステム(cargo)やテストフレームワークが強力であること
  • オブジェクトの所有権が明確であること (moveした変数にアクセスしようとするとコンパイル時に怒られる)
  • 所有権の制約を利用してスレッド安全性をコンパイル時に担保できること (マイコンでは使わないけどすごい)
  • C++20のConceptsに相当する,Boundsが実装されていること

などなど,高度(?)なアルゴリズムをマイコンに載せたい私としては,嬉しいことが満載なのです.

移植にあたって

拙作の迷路探索ライブラリの移植を目論んでいます.

libamaze

このライブラリは,迷路やグラフの情報の格納に必要な領域をコンパイル時に計算して静的にメモリ確保することや,グラフ表現やソルバ(A*アルゴリズム,幅優先探索など)の付け替えが可能であることが特徴です. 途中まで順調に開発が進んでいたのですが,設計に致命的なミスがあったため結局完成しないまま放置されています(ひどい).

そういえばこのライブラリについての記事も書いてない(ひどい).

まずはRustの基礎の習得

まずはRustを勉強します.

The Rust Programming Language を読んで,環境の構築(1章)と基本的な文法の習得(2,3章)を行いました. こいつはとにかく書き方が冗長丁寧なので,暇なときに読む分には良いと思います. はじめはなかなか先に進まず,英語を読むスピードが遅いからかなと思っていましたが,どうやらそうではなさそうだと気づいた私は3章で脱落しました. 戦略的撤退です.

代わりに rustlings という入門例題集を一気にやりました. これを終えた頃には,なんとか調べながらRustを書けそうな気がしてきました.

効率厨の私としては,bookはさらっと眺めてからrustlingsを進めつつ読んで,最後にまたbookに戻って補強すると良いのかなと思いました. でも最初からbookを読んだほうが楽という方もいるかもしれません(私は読んだだけでは頭に入らないもので…).

上級者には Rust Quiz なるマニアックな問題集もあるらしいので,モリモリ書けるようになったらやりたいです.

ではRustでどう実現するか

Rustの基礎が身についたところで,libamazeの2つの特徴に絞って,Rustでどう実現するか考えていきます.

グラフ表現やソルバの付け替え

Rustには継承の概念がありません. その代わりに,グラフやソルバのtraitsを定義して,boundsとして使ってやればよいはずです.
(用語の使い方が怪しい… 今のところそのように理解していますが,あってるよね…?)

静的アロケーション

こちらの要件が少し厄介かもしれません. 組み込み向けのRustについては, The Embedded Rust Book に詳しくまとまっています(まだ全部読めていない…). これによると,ビルトインの固定長配列を利用するのはもちろんですが,VecやHashMapを利用したい場合は heaplessを利用するのが一般的な解決方法のように見えます.

しかし,ここで別の問題があります. stable版のRustではC++でいうテンプレート引数に定数を渡すことができないのです.

対応するものは,現状unstableなconstant genericsという機能ですが,執筆時点ではconstant genericsは指定された定数を演算して利用できないという機能の制約があります. libamazeでは,迷路のサイズから自動的にグラフのノード数を計算したり,サイズの整合性をチェックしたりする機能を実装しており,これをRustで再現するのは難しそうです.

以上を受けて移植の方針

  • マイコンでの動作を確実にするため,no_std を前提としてコードを書く
  • 迷路サイズはハードコーディングした定数とし,グラフのサイズもそこから計算する (迷路サイズはライブラリ使用側から変更できない,もしくはコンパイル時にコマンドラインやファイルで指定する)
  • (前回の反省: 結合して動作するコードよりも先に単体テストをしっかり書く)

Constant genericsで実現しようとした迷路・グラフのサイズのコンパイル時計算ですが,typenum crate を使ったり,マクロを組んだりすれば実現できるようです. しかし,いずれもハック的な解決方法でしっくり来なかったため,この機能については諦めることにし,迷路サイズは定数(幅・高さ32マス)とすることにしました. 振り返ってみれば,C++版libamazeもこの W というパラメータのせいで無駄に複雑になっていた節があるので,切り捨てて正解のような気がします.

また,libamazeでは迷路データの壁有無フラグの格納にビットフィールドを利用していましたが,これは modular-bitfield を使えば実現できそうです.

頑張るぞい

(๑•̀ㅂ•́)و✧

C++17漬けになってしまった私ですが,これでようやくモダンな言語に入門できそうです. 進捗状況はなるべく記事にしていきたいと思うので,サボってたらつついてください.

リポジトリの予定地: tokoro10g/amaze

Share Comments

麻婆豆腐を作ろう [Micro Mouse AdC 2020]

麻婆豆腐を作ろう [Micro Mouse AdC 2020]

この記事は,Micro Mouse Advent Calendar 2020の23日目の記事です.

昨日はアニキの「新・教材トレーサー」でした.

麻婆豆腐を作ろう

さて,皆さんが真面目な技術記事を書いているところ大変恐縮なのですが,私の個人的な趣味の記事を書かせていただきます. 今年はマイクロマウスについて何もやっていないのです・・・

突然ですが,あなたにとってマイクロマウスの開発に最も必要なものは何でしょうか?

― 技術への情熱
― 互いに切磋琢磨する仲間
― エンコーダ付きモータを躊躇なく買える資金力

など,様々なものが思い浮かんできそうですね.

わたしの場合はというと・・・ そう,うまい飯です. 「ロボコンダイエット」と言って,食費を削って部品代を捻出するという知り合いもいましたが,うまい飯なしにはやってられないと思いませんか? おいしいごはんのつくり方というタイトルのブログのマウサーもいるぐらいですから,これはマジです(?).

ということで(?)今回は,マイクロマウス製作に欠かせないうまい飯 麻婆豆腐 の作り方をご紹介します. (あくまでも試行回数の少ない自己流なので,この通りに作れば絶対うまい!ってわけではないです・・・)

調理中慌ただしかったので,通常のレシピ記事のように写真が豊富にないことをまずお詫びしておきます. 写真撮りながら料理できる人すげえわ.GoProほしい.

Read More

Share Comments

手が滑って光造形3Dプリンタを3万円で買ってしまった話 [rogy Advent Calendar 2019]

手が滑って光造形3Dプリンタを3万円で買ってしまった話 [rogy Advent Calendar 2019]

実に1年ぶりの更新です.みなさんお久しぶりです.

供述

同年代の社会人が,ボーナスでカメラをポチったり,CNCをポチったり,旅行に行ったりしているのを見て,わたしにもできると思った. 後悔はしていない.

即オチ3コマ.

どれを買ったか

まず,3Dプリンタには雑に大きく分けて2種類があります.

  1. 温めた樹脂を練り出すタイプ
  2. レーザーや紫外線等を当てて液体樹脂を硬化させるタイプ

いわゆる3Dプリンタとして有名なのは1つめのタイプではないでしょうか. 今回私が購入したのは,2つめの「光造形」と呼ばれる方式の3Dプリンタです.

通常,光造形方式は練り出す3Dプリンタと比較して製造コストが高く,ホビー用途としてはかなり高嶺の花[1]だったわけですが,ここ数年の間でLCD-SLAという簡易的な方式が確立されてから,かなり安価に手に入るようになりました. LCD-SLA方式は,UVレジン(ジェルネイルとかにも使うやつ)に紫外線を照射する際に,間に挟んだLCDスクリーンで積層パターンをマスクするという方式です. とはいってもお値段はだいたい5万円〜と,気軽に買える価格ではなかったのですが…

これを見て手を滑らせてしまったよ… [2]

購入したのはこちらのAnycubic Photon. 500mLのレジン付きで 262ドル !!! 定価が450ドルなのでおよそ4割引です.4割引といえばスーパーのおすしの最終値引きぐらいのお得感です.つまりめっちゃお得.

↓ 実際の出力結果とこれからどうしたいかについて書きます.

Read More

Share Comments

MATLAB芸人なら知っておきたい小ネタ関数ベスト5 [rogy Advent Calendar 2018]

MATLAB芸人なら知っておきたい小ネタ関数ベスト5 [rogy Advent Calendar 2018]

イースターエッグ

ソフトウェアにおけるイースターエッグとは, 開発者がプログラム内に仕込んだ隠し機能や隠しメッセージのことです. MATLABにも様々なイースターエッグが仕込まれていて, どれも遊び心を感じるものになっています.

この記事では, その一例を独断と偏見によるランキング形式で紹介しようと思います.

独断と偏見によるランキング

5位: fifteen, xpbombs

なんと15パズルとマインスイーパがFigureウィンドウ上で遊べます. 暇つぶしや休憩のおともにどうぞ(業務中に遊ばないでね).

コード:

fifteen

実行結果:

コード:

xpbombs

実行結果:

ちなみに, コマンドウィンドウで

>> edit xpbombs

と実行すると, ソースコードを見ることができます. GUIプログラミングをする上で参考になるので, 気になる人は読んでみると良いと思います.

4位: logo 関数

MATLAB芸人なら, 突然MATLABのロゴを出したくなったことが何度もあるはずです. そんなときに便利なのが, logo 関数です.

内部的には, membrane 関数を surf を使ってプロットし, 大きさやライトを調整しています. 詳細な手順が公式ドキュメントで示されています.

3位: spy 関数

spy 関数は本来行列のスパース性を可視化するための関数で, つぎのように使用します.

コード:

spy(bucky);

実行結果:

引数なしで実行すると, なぜか犬の顔が表示されます.

コード:

spy

実行結果:

この spy 関数は, 本来の使い方以外にも面白い使い方があります. 非ゼロの要素がある部分にドットが打たれるため, 簡単なドットマトリクスディスプレイとして使用することができます. これを応用すると, Conwayのライフゲームがこんな感じで実装・表示できます.

コード:

a = rand(128) > 0.7;
while 1
    spy(a,'r.',6); drawnow;
    a = ~fix(filter2(ones(3),a)-a/2-3);
end

実行結果:

上記のコードはここに書いてあったものをゴルフして作りました.

2位: image 関数

image 関数を引数なしで実行すると…

コード:

image

実行結果:

逆さまになった男の子の顔が表示されます. ちょっとしたホラーです.

実はこの画像にはさらに秘密があって, 各画素のdoubleの値のうち53ビットをbitrotateすると, 隠し画像が現れるらしいです. 説明が結構面倒なので, 詳細はこちらをご覧ください.

1位: why 関数

why 関数は上記に挙げた関数とは違い, 特にこれといった用途のない関数です. インパクトには欠けますが, これを知っている人は結構なMATLAB通だと思います.

why を実行すると, 予め用意された語句を組み合わせたへんちくりんな文が表示されます.

これを使った実用的なコードを何か考えられるでしょうか? 思いつく人がいたら教えてください.

まとめ

いかがでしたか? 皆さんはいくつ知っていましたか?

ほかにもバージョンごとにいろいろな隠し要素があるようなので, 探してみると面白いのではないかと思います. それでは, よいMATLAB芸人生活をお送りください.

参考

Share Comments

たのしい3次元回転の世界 (1)3次元回転の特徴 [rogy Advent Calendar 2018]

たのしい3次元回転の世界 (1)3次元回転の特徴 [rogy Advent Calendar 2018]

概要

これは rogy Advent Calendar 2018 3日目の記事です. 投稿時点で12/3の25時ですが許して.

3次元回転は, 航空機, 人工衛星, マルチコプターなどの姿勢制御や, 3DCG, VR/AR, コンピュータビジョンなど, 3次元の物体が関わるあらゆる技術に密接に関係しています. この強力なツールを習得すればできることがぐっと増えるのですが, 回転の順序を入れ替えられないことや, 回転の基準とする座標系の取り方によって結果が変わること, 数学的な表現が初学者には分かりづらいことなどを理由に, 敬遠されがちなのが実情です. 実際, わたしも特に座標系にはさんざん苦しめられながら学習してきた経緯があり, 研究で取り扱っている今でもたまに混乱することがあるほどです.

これから書いていくシリーズ「たのしい3次元回転の世界」では, 3次元の回転に関わる事実や諸注意をなるべく図的に解説し, 扱う際の混乱や誤解をなくすことを目標にしています. 特にクォータニオンに関しては, 「なぜこれで回転が表現できるのかわからない」「イメージがしづらい」という意見をよく目にしますので, そのあたりに関する解釈も書いていければと思います. 筆者は数学的な深い知識には乏しい人間ですので, あまり数学的に立ち入った内容にはせず, 読み物としてためになるものが書ければと考えています. したがって, 数学的にプロパーな解説は, ほかの方の記事や論文等を参照していただくのが良いと思います.

今回は 3次元回転の特徴 について記します. 3次元空間内の回転は, 2次元平面上での回転にない特徴を多くもっています. まずはその特徴に触れることで, 3次元の回転へのイメージを養うことからこのシリーズをはじめたいと思います.

Read More

Share Comments