Androidの開発効率化Tips
2010/09/06追記：id:gaeさんよりXMLのファイル名はキャメルケースにできない、という指摘を頂きました。XMLのファイル名は未検証のまま書いてしまっていたのでそれに関する記述を削除させて頂きました。
Androidの開発にもだいぶ慣れてきて、スムーズに開発できるようになってはいるのですが、冷静に自分の実装プロセスを分析するとまだまだ非効率だなあと感じる点が多々あったりします。効率化のためにADTを改造するかな、とも思ったのですが、それ以前に既存のEclipse+ADTの機能を活用して効率化できる部分がまだあるのではないかと考えて調査してみました。
その中で、これは使えそうかな、というEclipse+ADTでのAndroid開発効率化の小技をいくつか紹介します。
GotoFileプラグイン
Androidで開発をしているとファイルを行ったり来たりすることが非常に多くなります。LayoutファイルとJavaソースの行ききだったり、似たような処理をしているところをコピって持ってきたり、、、。そこで使えるのが、Eclipse上で素早くファイル検索できるGotoFileプラグインです。オリジナルの配布サイトからはダウンロード出来なくなっているようですが、id:kusakariさんが表示数制限版を公開されています。
このプラグインをインストールすると、Ctrl-Alt-Nで検索窓が出てきます。Eclipse標準機能のCtrl-Shift-Tでも似たようなことができますが、GotoFileプラグインが特徴的なのは曖昧検索ができることです。
たとえば、hello_world.xmlのファイルに移動したければ「hxml」でヒットします。仮にファイルの一部分しか覚えていなくてもかなりスムーズにファイル間を移動することができます。
Extract Android String
Androidの開発で、もう一つ面倒なのがstrings.xmlファイルの存在です。
他言語化するために、基本的に文言は全てstring.xmlに抽出しますが、文言が出てくるたびにstrings.xmlを開いて編集、とやっていると非常に効率が悪いです。
あまり知られていないですが、ADTにはこれを解消するための便利な機能が用意されています。
Javaファイル、もしくはリソースXMLファイルで文言部分を選択した状態で、「Refactor->Android->Extract Android String」のメニューを選ぶと、指定された文字列をstrings.xmlに抜き出すことが出来ます。Alt-Shift-A, Sのショートカットで呼び出すとさらに便利です。
僕はこの機能で1日で1度もstrings.xmlを開かなくても開発できるようになりました。
キャメルケースを活用する
これはAndroid開発に限らないですが、Eclipseの補完機能をフル活用するために、キャメルケースで補完するのが良いです。
たとえばOnItemLongClickListenerだったらOILCと打ってCtrl-Shiftすれば、候補表示を飛ばして一発で補完できます。OnItemと打って、次に候補から選んで・・・とするよりもキーストロークを大幅に減らすことができます。
これはR.javaの各フィールドについても言えることで、R.strings.XXXXなどのXXXX部分を補完する際にも使えるので、stringsのキー名やandroid:id、layoutやdrawableのファイル名は、全てキャメルケースにしておくことをお勧めします。特にstringsのキー名とかは数が多くなってくると、必然的に長くなってくると思うので・・・
僕はいままでアンダースコアで区切っていたのですが、補完時に不便なのでキャメルケースに切り替えました。
まとめ
Eclpse+ADTにもまだまだ知らない便利機能が多いので、みんなでTipsを共有するといいと思うな！（おい
iPhone・iPad用に手書き文字認識ライブラリZinniaをビルドする
iPhone・iPad向けに手書き文字認識ライブラリ-Zinniaをビルドしてみて、結構苦労したので、そのときのメモです。Zinniaと書いてますが、Fat binary全般についての僕の理解も込みで説明してます。以下iPhoneと書いてますが、iPad用でも同様の内容があてはまります。
Fat binaryについて
まず基本的な話で、iPhone実機、Mac OSが稼働するPC、そしてiPhoneシミュレータの三者は、動作するプログラムのアーキテクチャが違う、ということを頭に置いておく必要があります。iPhoneのCPUはarm、Mac OSが稼働するCPUは（OS10.6では）x86_64、そしてiPhoneシミュレータはi386のCPUをシミュレートするようになっています。Mac OS上で普通にコンパイルするとx86_64向けのバイナリが出来てしまうので、これはiPhone実機やシミュレータでは動かないわけです。
作成されたバイナリがどのアーキテクチャ向けにビルドされているかは、otoolコマンドなどで参照することが出来て、たとえば普通にconfigureしてmakeしたZinniaのバイナリは以下のようになっています。
$ otool -vh .libs/libzinnia.a
Archive : .libs/libzinnia.a
.libs/libzinnia.a(param.o):
Mach header
magic cputype cpusubtype caps filetype ncmds sizeofcmds flags
MH_MAGIC_64 X86_64 ALL 0x00 OBJECT 3 1136 SUBSECTIONS_VIA_SYMBOLS
...こんな感じでこのライブラリにリンクされているバイナリがx86_64をターゲットにコンパイルされていることが分かります。
で、こいつをiPhoneで動かしたい、となるとシミュレータのことも考慮してarmとi386の両方で動くようにビルドしてあげる必要があるわけです。こんな風に複数CPUで動くように作られたバイナリをFat binaryとかUniversal binaryとか呼んだりします。
さて、Mac OS上でFat binaryを作るにはここに書いてあるようにいくつか方法がありますが、一番シンプルなのが、それぞれのアーキテクチャ向けに個々にコンパイルしたものを、lipoコマンドで結合してあげるやり方です。
基本的にはg++に-arch [アーキテクチャ名]のオプションが渡るようにしてあげれば、そのアーキテクチャ向けにコンパイルしてくれるはずなのですが、これがなかなか一筋縄ではいきません
armバイナリのビルド
armでビルドするときは、arm向けのライブラリやヘッダファイルなどが、Mac OSのデフォルトパス上のものとは異なるので、それらのライブラリパスやインクルードパスも全部指定し直す必要があります。arm用のファイルは、iOS SDKをインストールしたフォルダ /Developer/Platforms/iPhoneOS.platform/Developer に格納されているので、configure時にこれらを参照するように〜FLAGSなどの環境変数を設定してあげます。
export CPPFLAGS="-I$SDKROOT/usr/lib/gcc/arm-apple-darwin10/4.2.1/include/ -I$SDKROOT/usr/include/ -I$SDKROOT/usr/include/c++/4.2.1 -I$SDKROOT/usr/include/c++/4. 2.1/armv6-apple-darwin10/ -miphoneos-version-min=3.0" export CFLAGS="$CPPFLAGS -pipe -no-cpp-precomp -isysroot $SDKROOT" export CPP="$DEVROOT/usr/bin/cpp $CPPFLAGS" export CXXFLAGS="$CFLAGS" # Dynamic library location generated by the Unix package LIBPATH=$LIBFILE.dylib LIBNAME=`basename $LIBPATH` export LDFLAGS="-L$SDKROOT/usr/lib -L$SDKROOT/usr/lib/gcc/arm-apple-darwin10/4.2.1/ -Wl,-dylib_install_name,@executable_path/$LIBNAME" ./configure CXX=$DEVROOT/usr/bin/arm-apple-darwin10-g++-4.2.1 CC=$DEVROOT/usr/bin/arm-apple-darwin10-gcc-4.2.1 LD=$DEVROOT/usr/bin/ld --host=arm-apple-darwin make
これでarm用のバイナリが作られるはずです。
i386バイナリのビルド
Mac OSのライブラリ類はi386互換で作られているはずなので、armのようにインクルードパスやライブラリパスをいちいち指定し直さなくても、g++に-arch i386オプションを指定してあげれば、i386用のバイナリが作られます。
ただ一つ問題なのがZinniaのMakefileです。./configure時にCFLAGS="-arch i386"と指定してもMakefileが作られるときには、なぜかこの指定が消えてしまっているのです。恐らくはZinniaがビルドに使用しているlibtoolの問題ではないかと思うのですが（推測です）、仕方がないので無理矢理Makefileを書き換えてあげます。
./configure perl -pi -e 's@^CXXFLAGS = @CXXFLAGS = -arch i386 @g' Makefile perl -pi -e 's@^CFLAGS = @CFLAGS = -arch i386 @g' Makefile make
これでi386のバイナリもビルドできました。
まとめ
以上をまとめたZinniaのFat binaryビルドファイルです。
Mac OS 10.6.4、iOS SDK 4.0.2、Zinnia 0.0.6で動作確認しています。
build_fat.sh
#!/bin/sh LIBFILE=.libs/libzinnia export DEVROOT=/Developer/Platforms/iPhoneOS.platform/Developer export SDKROOT=$DEVROOT/SDKs/iPhoneOS4.0.sdk # build arm binary export CPPFLAGS="-I$SDKROOT/usr/lib/gcc/arm-apple-darwin10/4.2.1/include/ -I$SDKROOT/usr/include/ -I$SDKROOT/usr/include/c++/4.2.1 -I$SDKROOT/usr/include/c++/4.2.1/armv6-apple-darwin10/ -miphoneos-version-min=3.0" export CFLAGS="$CPPFLAGS -pipe -no-cpp-precomp -isysroot $SDKROOT" export CPP="$DEVROOT/usr/bin/cpp $CPPFLAGS" export CXXFLAGS="$CFLAGS" LIBPATH=$LIBFILE.dylib LIBNAME=`basename $LIBPATH` export LDFLAGS="-L$SDKROOT/usr/lib -L$SDKROOT/usr/lib/gcc/arm-apple-darwin10/4.2.1/ -Wl,-dylib_install_name,@executable_path/$LIBNAME" LIBPATH_static=$LIBFILE.a LIBNAME_static=`basename $LIBPATH_static` ./configure CXX=$DEVROOT/usr/bin/arm-apple-darwin10-g++-4.2.1 CC=$DEVROOT/usr/bin/arm-apple-darwin10-gcc-4.2.1 LD=$DEVROOT/usr/bin/ld --host=arm-apple-darwin make mkdir -p lnsout cp $LIBPATH_static lnsout/$LIBNAME_static.arm make distclean unset CPPFLAGS CFLAGS CPP LDFLAGS CXXFLAGS DEVROOT SDKROOT # build i386 binary ./configure perl -pi -e 's@^CXXFLAGS = @CXXFLAGS = -arch i386 @g' Makefile perl -pi -e 's@^CFLAGS = @CFLAGS = -arch i386 @g' Makefile make cp $LIBPATH_static lnsout/$LIBNAME_static.i386 /usr/bin/lipo -arch arm lnsout/$LIBNAME_static.arm -arch i386 lnsout/$LIBNAME_static.i386 -create -output lnsout/$LIBNAME_static unset CPPFLAGS CFLAGS CPP LDFLAGS CPP CXXFLAGS DEVROOT SDKROOT
結果
fileコマンドで本当にfat binaryができているか確認してみます。
$ file lnsout/libzinnia.a lnsout/libzinnia.a: Mach-O universal binary with 2 architectures lnsout/libzinnia.a (for architecture arm): current ar archive random library lnsout/libzinnia.a (for architecture i386): current ar archive random library
IS01専用Androidアプリ「LEDモールス」を公開しました
ものすごく久しぶりのブログになってしまいましたが生きてます。
最近は社内でスマートフォン関連の開発をやってまして、どっぷりとAndroidに浸かっています。
機種依存やら何やらに悩まされたり、Android開発の奥深さに毎度唸らされる毎日です。
で、今日はシャープとアンドロイダーが開催した「SHARP Androidアプリ開発 テクニカルセッション」というセミナーにいってきました。これはメーカーの開発者の方がいる中で、皆PC持参でひたすら実機を触るという素晴らしいイベント（※講演もありました）だったのですが、このセミナー中に１個お遊びのアプリを作ってみたので公開します。
LEDフラッシュでモールス信号を発信できるアプリです。
LEDの制御はIS01専用（というかシャープ専用）の拡張APIなので、いまのところIS01しか動きませんが、船舶間での通信、難破・遭難時の救難信号、符号理論の勉強などに是非ご活用ください！
というわけで僕はAndroid端末を持っていないので本当に公開できているか分からないのですが、「LEDモールス」という名前でマーケット公開中です。ダウンロードは（多分）↓こちらから。
【LEDモールス】（IS01専用アプリ）
http://market.android.com/search?q=org.firemobilesimulator.morse
適当なソースコードなのでさらしておきます。
package org.firemobilesimulator.morse; import java.util.Hashtable; import jp.co.sharp.android.hardware.FlashLight; import android.app.Activity; import android.os.Bundle; import android.text.Editable; import android.util.Log; import android.view.View; import android.widget.EditText; import android.widget.Toast; public class TopActivity extends Activity { private static final String TAG = "Morse"; private static final int INTERVAL = 1000; private static final int LONG = 1000; private static final int SHORT = 200; private EditText mEditText; private static Hashtable<String, String> mTable; static { mTable = new Hashtable<String, String>(); mTable.put("A", "・−"); mTable.put("B", "−・・・"); mTable.put("C", "−・−・"); mTable.put("D", "−・・"); mTable.put("E", "・"); mTable.put("F", "・・−・"); mTable.put("G", "−−・"); mTable.put("H", "・・・・"); mTable.put("I", "・・"); mTable.put("J", "・−−−"); mTable.put("K", "−・−"); mTable.put("L", "・−・・"); mTable.put("M", "−−"); mTable.put("N", "−・"); mTable.put("O", "−−−"); mTable.put("P", "・−−・"); mTable.put("Q", "−−・−"); mTable.put("R", "・−・"); mTable.put("S", "・・・"); mTable.put("T", "−"); mTable.put("U", "・・−"); mTable.put("V", "・・・−"); mTable.put("W", "・−−"); mTable.put("X", "−・・−"); mTable.put("Y", "−・−−"); mTable.put("Z", "−−・・"); mTable.put("1", "・−−−−"); mTable.put("2", "・・−−−"); mTable.put("3", "・・・−−"); mTable.put("4", "・・・・−"); mTable.put("5", "・・・・・"); mTable.put("6", "−・・・・"); mTable.put("7", "−−・・・"); mTable.put("8", "−−−・・"); mTable.put("9", "−−−−・"); mTable.put("0", "−−−−−"); } @Override public void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.main); mEditText = (EditText) findViewById(R.id.input); } public void morse(View view) { Editable edit = mEditText.getText(); String s = edit.toString(); FlashLight mFlashLight = new FlashLight(); // 通常の点灯時は、ライトの色のみ指定します int len = s.length(); for (int i = 0; i < len; i++) { String oneChar = s.substring(i, i + 1).toUpperCase(); Log.d(TAG, "morse:" + oneChar); String code = mTable.get(oneChar); if (code != null) { int codeLen = code.length(); for (int j = 0; j < codeLen; j++) { char c = code.charAt(j); int time = 0; switch (c) { case '−': time = LONG; break; case '・': time = SHORT; break; } mFlashLight.setFlashLightOn(FlashLight.LIGHT_COLOR_WHITE); try { Thread.sleep(time); mFlashLight.setFlashLightOff(); Thread.sleep(INTERVAL); } catch (InterruptedException e) { Log.e(TAG, "sleep error", e); } } } else { Log.w(TAG, "Unknown Character"); } } Toast.makeText(this, "モールス信号を発信しました", Toast.LENGTH_LONG); } }
Blenderでドミノ崩し
前回に引き続き、今度はblenderでモデルを組み立ててみます。blender上ではpythonのマクロが使えるので、手作業が大変でも、自動化で簡単に複雑なモデルを組み立てることができます。
ってなわけでblender上でドミノを配列させるスクリプトを組んでみました。
from Blender import * import math scene = Scene.GetCurrent() defRBFlags = Object.RBFlags.COLLISION | Object.RBFlags.PROP | \ Object.RBFlags.BOUNDS | Object.RBFlags.RIGIDBODY | \ Object.RBFlags.ACTOR | Object.RBFlags.DYNAMIC for n in range(18): # n周目の作成 r = 10 + 1.8 * n j = int(math.pi * r * 0.7) d = 2 * math.pi / j for i in range(j): # i個目の作成 x = r * math.cos(d*i) y = r * math.sin(d*i) objname = 'dominoobj_' + str(n) + '_' + str(i) mdat = Mesh.Primitives.Cube(1.0) mdat.name = objname m = scene.objects.new(mdat,objname) m.SizeX = 0.5 m.SizeY = 2 m.SizeZ = 3 m.LocX = x m.LocY = y m.LocZ = 1.5 s = 360*d*i/(2*math.pi) m.RotZ = d*i # 物理エンジンの計算対象にするための設定 m.rbFlags = defRBFlags m.rbMass = 0.5 m.rbShapeBoundType = Object.RBShapes.BOX Redraw()
やっていることはいたってシンプルで、半径の異なる同心円上にブロックオブジェクトを配置していっているだけです。また、rbXXXのプロパティを設定しているのは、物理エンジンの計算対象とするための設定です。
このスクリプトを実行した後は、床となるプレートオブジェクトと、ブロックを倒すためのボールオブジェクトをblender上で作ってあげます。そうすると以下のようなアニメーションが出来あがります。
うーん、面白い！
フォード・ファルカーソンのアルゴリムで最大流-最小切断問題を解く
PRMLの8.3節では、マルコフ確率場を応用した事例として画像のノイズ除去がでてきますが、PRMLで紹介されている「グラフカットアルゴリズム」を試すには最大流問題を解く必要があるのでアルゴリズムの勉強もかねて実装してみました。
最大フロー問題または最大流問題とは、各枝に容量(capacity)と流量(flow)が設定された有効グラフにおいて、ある始点（ソース）から終点（シンク）へのフローで最大となるフローを求める問題です。
この問題を解くアルゴリズムとしてフォード・ファルカーソンのアルゴリズムが一般的に良く知られていて、僕の持っているアルゴリズムC・新版—基礎・データ構造・整列・探索にも載っています。
アルゴリズムCから引用すると、フォード・ファルカーソンのアルゴリズムは「辺の流量がすべてゼロである状態から開始し、ソースからシンクに向かう道で、飽和した前向きの辺や流量ゼロの後ろ向きの辺を含まないものに沿って流量を増やし、ネットワークにそのような道がなくなるまで繰り返す」というように要約できます。「後ろ向きの辺」が何かというと、元の向きと逆向きの辺を考えて、その辺を流れるときは逆に流量を減らすというものです。この逆向きの辺を考えないと、最初に変な道の選び方をしてしまうと、もう最大フローにはたどり着かなくなってしまいます。
また、フォード・ファルカーソンのアルゴリズム自体は「ソースからシンクに向かう道で、飽和した前向きの辺や流量ゼロの後ろ向きの辺を含まないもの」を探すアルゴリズム自体を規定しているわけではないので、このアルゴリズムは自分で探索アルゴリズムを組む必要があります。アルゴリズムCでは最良優先探索を使用しています。
以下では、アルゴリズムCにならって最良優先検索で最大流および最小切断を求めてみます。
対象となる最大流問題は、アルゴリズムCの図33.2のネットワークを対象としています。
（図がダウンロードできなかったので、貼付けられず。。ご容赦。。）
#include <iostream> #include <vector> #include <math.h> using namespace std; namespace GraphCut { //NodeとEdgeで相互参照するため、あらかじめ宣言しておく。 class Node; class Edge { public: Node* s_Node_; Node* e_Node_; Edge (Node* s_Node, Node* e_Node, double size); double AddFlow (double flow); void set_reverse_edge (Edge* re); double get_flow (); void set_flow (double flow); double get_size (); private: Edge* reverse_edge_; double flow_; double size_; }; class Node { public: vector<Edge*> vecFlowPath; Node* dad_; string name_; Node (string name); void AddFlowPath (Node* e_node, double size); double get_val (); void set_val (double val); void visit (); bool get_is_visited (); Edge* dad_path_; void reset (); private: double val_; bool is_visited_; }; Edge::Edge (Node* s_Node, Node* e_Node, double size) : s_Node_(s_Node), e_Node_(e_Node), size_(size), flow_(0) {} double Edge::AddFlow (double flow) { flow_ += flow; reverse_edge_->set_flow(-flow); return flow; } double Edge::get_flow () { return flow_; } void Edge::set_flow (double flow) { flow_ = flow; } void Edge::set_reverse_edge (Edge* re) { reverse_edge_ = re; } double Edge::get_size () { return size_; } Node::Node (string name) : name_(name), val_(0), is_visited_(false) {} void Node::AddFlowPath (Node* e_node, double size) { Edge* e = new Edge(this, e_node, size); vecFlowPath.push_back(e); Edge* re = new Edge (e_node, this, -size); re->set_reverse_edge(e); e->set_reverse_edge(re); e_node->vecFlowPath.push_back(re); } double Node::get_val () { return val_; } void Node::set_val (double val) { val_ = val; } void Node::visit () { is_visited_ = true; } bool Node::get_is_visited () { return is_visited_; } void Node::reset () { is_visited_ = false; val_ = 0; } } using namespace GraphCut; //ノードnを含む最小切断を再帰的に求めてmincutに追加する void SearchMinCut (Node* n, vector<Node*>& mincut) { mincut.push_back(n); n->visit(); vector<Edge*> vecAdjEdges = n->vecFlowPath; for (int j=0; j<vecAdjEdges.size(); j++) { Edge* adjEdge = vecAdjEdges[j]; Node* adjNode = adjEdge->e_Node_; if (adjNode->get_is_visited()) continue; //飽和した前向きの辺や、流量ゼロの後ろ向きの辺ではない場合 if ((adjEdge->get_size() > 0 && adjEdge->get_flow() != adjEdge->get_size()) || (adjEdge->get_size() < 0 && adjEdge->get_flow() != 0)) { SearchMinCut(adjNode, mincut); } } } //全ノードvecNodesを順位優先で検索して、流量の増加の最も多い経路を見つける。 bool PFS (vector<Node*> vecNodes, Node* source, Node* sink) { printf("start priority-first search\n"); //初期化 for (int j=0; j<vecNodes.size(); j++) { Node* n = vecNodes[j]; n->reset(); } source->set_val(INT_MAX); Node* v = source; bool findSource2Sink = false; bool findMax = true; while (findMax) { findMax = false; v->visit(); double val = v->get_val(); //新たに訪問済になったノードvの隣接ノードのpriority（流量）の更新 vector<Edge*> vecAdjEdges = v->vecFlowPath; for (int j=0; j<vecAdjEdges.size(); j++) { Edge* adjEdge = vecAdjEdges[j]; Node* adjNode = adjEdge->e_Node_; if (adjNode->get_is_visited()) continue; //priorityの更新 //vを経由した場合の、adjNodeへの流量を求める double priority = -(adjEdge->get_flow()); double size = adjEdge->get_size(); if (size > 0) priority += size; if (priority > val) priority = val; //新たに求めたadjNodeへの流量が、既に設定された流量を上回る場合、adjNodeへの経路と流量を更新する if (adjNode->get_val() < priority) { adjNode->set_val(priority); adjNode->dad_ = v; adjNode->dad_path_ = adjEdge; } } //流量最大のノードを求める double maxval = 0; int max = -1; int nodeNum = vecNodes.size(); for (int j=0; j<nodeNum; j++) { Node* n = vecNodes[j]; if (n->get_is_visited()) continue; if (n->get_val() > maxval) { maxval = n->get_val(); max = j; } } //流量最大のノードが見つかった場合 if (max >= 0) { findMax = true; v = vecNodes[max]; if (v == sink) { //ソースからシンクまでの経路が見つかった場合 findSource2Sink = true; break; } } } return findSource2Sink; } int main (int argc, char * const argv[]) { //ノードと辺の初期化 vector<Node*> vecNodes; Node* a = new Node("a"); Node* b = new Node("b"); Node* c = new Node("c"); Node* d = new Node("d"); Node* e = new Node("e"); Node* f = new Node("f"); vecNodes.push_back(a); vecNodes.push_back(b); vecNodes.push_back(c); vecNodes.push_back(d); vecNodes.push_back(e); vecNodes.push_back(f); a->AddFlowPath(b,6); a->AddFlowPath(c,8); b->AddFlowPath(d,6); b->AddFlowPath(e,3); c->AddFlowPath(d,3); c->AddFlowPath(e,3); d->AddFlowPath(f,8); e->AddFlowPath(f,6); Node* source = a; Node* sink = f; //ソースからシンクまでの経路が尽きるまで、流量最大経路の探索を繰り返す while (PFS(vecNodes, source, sink)) { //ソースからシンクまでの流量が増加する経路が発見された場合、シンクから逆に発見された経路をたどり、流量を増加させる。 Node* n = sink; while (n != source) { Edge* e = n->dad_path_; e->AddFlow(sink->get_val()); printf("add flow to %s-%s by %f\n", e->s_Node_->name_.c_str(), e->e_Node_->name_.c_str(), sink->get_val()); n = n->dad_; } } //最小切断を求めるために全ノードを初期化 for (int j=0; j<vecNodes.size(); j++) { Node* n = vecNodes[j]; n->reset(); } //再帰的に最小切断を求める vector<Node*> mincut; SearchMinCut(source, mincut); cout << "display mincut" << endl; for (int j=0; j<mincut.size(); j++) { Node* n = mincut[j]; printf("%s\n", n->name_.c_str()); } return 0; }
実行結果
start priority-first search add flow to d-f by 6.000000 add flow to b-d by 6.000000 add flow to a-b by 6.000000 start priority-first search add flow to e-f by 3.000000 add flow to c-e by 3.000000 add flow to a-c by 3.000000 start priority-first search add flow to e-f by 3.000000 add flow to b-e by 3.000000 add flow to d-b by 3.000000 add flow to c-d by 3.000000 add flow to a-c by 3.000000 start priority-first search display mincut a c
というわけで、最小切断がa,cだということが分かりました。
PFS内で、流量最大のノードを探索している箇所をヒープソートにしたりすれば多分もっと早くなります。
ちなみにですが、石川先生のグラフカットのサーベイ論文によれば、最大流問題を解くアルゴリズムとして、フォード・ファルカーソンのアルゴリズム以外にpush-relabelアルゴリズム(PDF)が知られていて、フォード・ファルカーソンが計算量O(n^3)に対し、push-relabelはO(nmlog(n^2/m))（nは頂点の数、mは辺の数）で、push-relabelの方が速いそうです。
ですが、次回はとりあえずこのままフォード・ファルカーソンのアルゴリズムで、グラフカットによるエネルギー最小化問題を解いてみることにします。
Blender+SIO2で3D物理エンジン
すっごい間が空いてしまい、いまさらなんですが、年末年始のプチ成果まとめ第2段です。前回のBox2Dに引き続き、今度は3Dの物理エンジンをいじってみます。
Box2Dの場合、貧弱ではありますが線画機能(DebugDraw)が内蔵されていますが、3Dの場合はレンダリング（描画）は部分はそれ専用のエンジンを用いることが多いです。逆に物理エンジンの部分はそれだけに特化していて、描画機能はもたないことが多いです。
というわけでフリーで使える物理エンジンとレンダリングエンジンを分けて紹介すると、
物理エンジンでは
あたりが有名、レンダリングエンジンでは、
が有名どころだと思います。
今回はその中でも「blender」を使ってみます。blenderは物理エンジンとして、デフォルトでbullletを内蔵しており、レンダリングから物理シミュレーションまで、一つのGUI上で簡単に編集・表現することができます。
またSIO2というiPhone用の3D物理エンジンに簡単にエクスポートすることができる（SIO2にpythonで書かれたExporterスクリプトが付属してます）ので、将来iPhoneでゲームを作ってみたいという人にはうってつけ、というわけです。
blenderの入門ページとしては、藤堂+さんのblenderチュートリアルが素晴らしくまとまっています。ただSIO2のことについて触れていないので、SIO2にガンガンExportして楽しみたい人は、SIO2付属のチュートリアル（Export前のblendファイルも付いてくる）をいじってみるか、Haraさんのブログエントリー
あたりを読むと分かりやすいです。やっていることはSIO2のチュートリアルをちょこっと改造して、自作の3Dモデルに置き換えてみよう、というものです。
で、blener+SIO2にはここには書いていない落とし穴も結構あったります。
以下に書くことは、全てsio2interactive wiki-Blender and SIO2にも書いてあることで、最初からここを読んでいれば特にはまることもないのですが、日本語の文献はあまり無いようだったので、書いておきます。
- blender上で同じ計上のオブジェクトしていくと、Cube.001,Cube.002,Cube.003のように末尾に連番が付いたIDのオブジェクトが自動的に作成されていきますが、これらはblender上だと重複オブジェクトとみなされ、SIO2上で表示されないことがあります。他のIDに手動で変更が必要です。
- テクスチャはUV Mappingしなければ表示されません。UV Mappingという用語は3D素人にはなじみがないのですが、以下のエントリーが詳しいです。
- Blender.jp - フォーラム 日本語のチュートリアルがZIPで落とせる
- Blender 3D: Noob to Pro/UV Map Basics - Wikibooks, collection of open-content textbooks 英語、地球を貼付ける
- BioRUST.com :: Tutorials >> UV Mapping 英語、さいころ的なもの
- スケール値が1.0以外の値が設定されていると衝突判定されない。これはHaraさんのブログにも書いてありますね。物体の大きさを変更する場合は、Object Modeで変更するのではなく、Edit Modeで変更するか、Object Modeで変更した後に、Ctl-A -> scale and rotation to objectでscaleが1.0になるように再調整します。
とまあこんなところです。仮にiPhoneアプリ上で複雑な3Dモデルを作る場合、SIO2でモデルを組み立ててもよいのですが、blender上でpythonのマクロが使えるのでそこでモデリングしてしまうのが結構簡単です。次回はpythonでモデルを組み立てるところをやってみます。
Box2DFlashAS3でブロック崩しゲームを作る
世の中は年が開けて抱負やら振り返りやらでとてもフレッシュな香りがただよっていますが、僕は空気も読まずにとりあえず年末年始の休暇にやってたことをまとめようと思います。
まずはBox2DFlashAS3という物理エンジンのライブラリを使ってブロック崩しゲームを作りました。
やっつけで作った糞ゲーもいいところですが、せっかくなので貼付けておきます。左右でバーを動かすことができます。床に玉をついてもゲームオーバーはありません。
Box2DFlashAS3(以下Box2D)とは
ActionScriptから利用できる物理エンジン、いわゆるニュートン力学が支配する世界を手軽に表現することが出来るライブラリの一つです。これを使うことで重力による落下とか衝突とかを簡単に実装することができます。
物理エンジンには様々なライブラリがあり、たとえばNVIDIAのPHYSXなんかはよく知られています。2Dも3Dもありますが、Box2Dは2Dの物理エンジンの代表的なものです。僕は物理エンジンというもの自体になじみがなかったのですが、Web+DB PRESS vol.54の特集を読んで初めて知りました。
情報源
- Box2D（Box2DFlashAS3）によるActionScript物理シミュレーション | Flash | HapHands
- 特集：Box2DでActionScript物理プログラミング｜gihyo.jp … 技術評論社
あたりが詳しいです。僕のブロック崩しは、下の技評のサンプルプログラムを改造しています。
工夫した点など
あまり情報がないのですが、Box2Dの物体(b2Bodyオブジェクト)には作成した物体のIDや名前などのプロパティがないため、後から物体を一意に識別したい場合は、UserDataというカスタムフィールドを参照します。
以下はブロック崩しゲームにおける、ブロックの初期作成処理です。UserDataに、ブロックの連番であるindexプロパティと、ブロックであることを示すtypeプロパティをセットしています。
for (var i:int = 0; i<boxNum; i++) { //中略 var block:b2Body = world.CreateBody(blockBodyDef); var blockObj:Object = new Object(); blockObj.index = i; blockObj.type = "block"; //中略 block.SetUserData(blockObj); //中略 }
以下がUserDataを参照している部分。ContactListenerという衝突検知用のクラスの中で、UserDataのtypeプロパティを参照して、衝突した物体がブロックだったかどうかを判定しています。
public override function Add(point:b2ContactPoint):void { var body1:b2Body = point.shape1.GetBody(); var body2:b2Body = point.shape2.GetBody(); var obj1:Object = body1.GetUserData(); var obj2:Object = body2.GetUserData(); if (obj1 != null && obj1.type == "block") { //中略 } else if (obj2 != null && obj2.type == "block") { //中略 } }
全コード
BlockGame.as
package { import Box2D.Collision.b2AABB; import Box2D.Collision.b2ContactPoint; import Box2D.Collision.Shapes.b2PolygonDef; import Box2D.Collision.Shapes.b2CircleDef; import Box2D.Collision.Shapes.b2MassData; import Box2D.Common.Math.b2Vec2; import Box2D.Dynamics.b2Body; import Box2D.Dynamics.b2BodyDef; import Box2D.Dynamics.b2ContactListener; import Box2D.Dynamics.b2DebugDraw; import Box2D.Dynamics.b2World; import flash.display.Sprite; import flash.events.Event; import flash.events.MouseEvent; import flash.events.KeyboardEvent; import flash.ui.Keyboard; import flash.text.TextField; import flash.text.TextFieldAutoSize; import flash.text.TextFormat; public class BlockGame extends Sprite { private var world:b2World; private var barstate:int; private var bar:b2Body; public var blockArray:Array; public var destroyFlagArray:Array; private var destroyNum:int; private var textField:TextField; private const boxNum:int = 35; public function BlockGame():void { // イベントハンドラを登録する barstate = 0; textField = new TextField(); // テキストフィールドの準備 textField.autoSize = TextFieldAutoSize.LEFT; textField.textColor = 0xFFFFFF; textField.x = 100; textField.y = 220; textField.text = "Click to start."; var f:TextFormat = new TextFormat(); f.font="Arial"; f.size=24; textField.setTextFormat(f); addChild(textField); stage.addEventListener(MouseEvent.CLICK, clickHandler); stage.addEventListener(Event.ENTER_FRAME, enterFrameHandler); stage.addEventListener(KeyboardEvent.KEY_DOWN, keyDownHandler); stage.addEventListener(KeyboardEvent.KEY_UP, keyUpHandler); } private function clickHandler(event:MouseEvent):void { trace("start clickHandler"); destroyNum = 0; textField.text = ""; //////////////////////////////////////// // 物理エンジンのセットアップ var worldAABB:b2AABB = new b2AABB(); worldAABB.lowerBound.Set(-100, -100); worldAABB.upperBound.Set(100, 100); var gravity:b2Vec2 = new b2Vec2(0, 10); world = new b2World(worldAABB, gravity, true); //////////////////////////////////////// // 固定オブジェクトの配置 var floor:b2Body = createStaticBoxShape(2.5, 3.0, 2.3, 0.1); var top:b2Body = createStaticBoxShape(2.5, -0.1, 2.3, 0.1); var l:b2Body = createStaticBoxShape(0.1, 3.0, 0.1, 50.0); var r:b2Body = createStaticBoxShape(4.9, 3.0, 0.1, 50.0); /////////////////////////////////////// // ユーザーが動かすバーを作成する var barBodyDef:b2BodyDef = new b2BodyDef(); barBodyDef.position.Set(2.5, 2.8); var barShapeDef:b2PolygonDef = new b2PolygonDef(); barShapeDef.SetAsBox(0.5, 0.1); barShapeDef.density = 1; barShapeDef.restitution = 0; bar = world.CreateBody(barBodyDef); bar.CreateShape(barShapeDef); bar.SetMassFromShapes(); blockArray = new Array(); destroyFlagArray = new Array(); var bw:int = 7; for (var i:int = 0; i<boxNum; i++) { var x:int = i%bw; var y:int = i/bw; var xd:Number = 0.7 + x * 0.6; var yd:Number = 0.2 + y * 0.2; var blockBodyDef:b2BodyDef = new b2BodyDef(); blockBodyDef.position.Set(xd, yd); var blockShapeDef:b2PolygonDef = new b2PolygonDef(); blockShapeDef.SetAsBox(0.3, 0.1); var block:b2Body = world.CreateBody(blockBodyDef); var blockObj:Object = new Object(); blockObj.index = i; blockObj.type = "block"; blockObj.destroy = false; block.SetUserData(blockObj); block.CreateShape(blockShapeDef); blockArray.push(block); destroyFlagArray.push(false); } //////////////////////////////////////// // ボールの設置 var ballBodyDef:b2BodyDef = new b2BodyDef(); ballBodyDef.position.Set(2.5, 1.0); var ballShapeDef:b2CircleDef = new b2CircleDef(); ballShapeDef.radius = 0.05; ballShapeDef.density = 0.2; // 密度 [kg/m^2] ballShapeDef.restitution = 1; // 反発係数、通常は0〜1 var ballBody:b2Body = world.CreateBody(ballBodyDef); ballBody.CreateShape(ballShapeDef); ballBody.SetMassFromShapes(); ballBody.ApplyImpulse(new b2Vec2(0.01, 0.01), ballBody.GetWorldCenter().Copy()); var contactListener:ContactListener = new ContactListener(); world.SetContactListener(contactListener); //////////////////////////////////////// // 描画設定 var debugDraw:b2DebugDraw = new b2DebugDraw(); debugDraw.m_sprite = this; debugDraw.m_drawScale = 100; // 1mを100ピクセルにする debugDraw.m_fillAlpha = 0.3; // 不透明度 debugDraw.m_lineThickness = 1; // 線の太さ debugDraw.m_drawFlags = b2DebugDraw.e_shapeBit; world.SetDebugDraw(debugDraw); } private function keyDownHandler(event:KeyboardEvent):void { if (event.keyCode == Keyboard.LEFT) { barstate = 1; stage.addEventListener(Event.ENTER_FRAME, enterFrameHandler2); } else if (event.keyCode == Keyboard.RIGHT) { barstate = 2; stage.addEventListener(Event.ENTER_FRAME, enterFrameHandler2); } } private function keyUpHandler(event:KeyboardEvent):void { if (barstate == 1 && event.keyCode == Keyboard.LEFT) { barstate = 0; stage.removeEventListener(Event.ENTER_FRAME, enterFrameHandler2); } else if (barstate == 2 && event.keyCode == Keyboard.RIGHT) { barstate = 0; stage.removeEventListener(Event.ENTER_FRAME, enterFrameHandler2); } } private function enterFrameHandler2(event:Event):void { var c:b2Vec2 = bar.GetWorldCenter().Copy(); var f:b2Vec2; if (barstate == 1) { f = new b2Vec2(-1,0); } else if (barstate == 2) { f = new b2Vec2(1,0); } bar.ApplyForce(f, c); } private function enterFrameHandler(event:Event):void { if (world == null) { return; } if (destroyNum == boxNum) { gemeEnd(); return; } for (var i:int=0; i<boxNum; i++) { if (!destroyFlagArray[i]) { var obj:Object = blockArray[i].GetUserData(); if (obj && obj.destroy) { trace("destory:"+i); world.DestroyBody(blockArray[i]); destroyFlagArray[i] = true; ++destroyNum; } } } world.Step(1/24, 10); } private function gemeEnd():void { textField.text = "Clear! Click to restart."; world = null; } private function createStaticBoxShape(locX:Number, locY:Number, sizeX:Number, sizeY:Number):b2Body { var bbd:b2BodyDef = new b2BodyDef(); bbd.position.Set(locX, locY); var bpd:b2PolygonDef = new b2PolygonDef(); bpd.SetAsBox(sizeX, sizeY); var b:b2Body = world.CreateBody(bbd); b.CreateShape(bpd); return b; } } }
ContactListener.as
package { import Box2D.Collision.b2ContactPoint; import Box2D.Collision.Shapes.b2MassData; import Box2D.Dynamics.b2ContactListener; import Box2D.Dynamics.b2Body; import Box2D.Collision.Shapes.b2PolygonDef; public class ContactListener extends b2ContactListener { public function ContactListener() { } public override function Add(point:b2ContactPoint):void { var body1:b2Body = point.shape1.GetBody(); var body2:b2Body = point.shape2.GetBody(); var obj1:Object = body1.GetUserData(); var obj2:Object = body2.GetUserData(); if (obj1 != null && obj1.type == "block") { trace("this is obj1"); obj1.destroy = true; } else if (obj2 != null && obj2.type == "block") { trace("this is obj2"); obj2.destroy = true; } } } }
その他補足情報
コンパイルするときは、BlockGame.asとContactListener.asを同じディレクトリにおいて、
mxmlc -source-path=path_to_box2d_library BlockGame.as
traceで吐き出したログを参照する方法は
windowsやmacで、flashのtraceログが吐かれる場所 - カサヒラボ
あたりを参照。
次回は3Dの物理エンジンをいじった成果を書く予定です。
