2015/10/14

馬場タクシー2をリリースしました このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

ドライバーの皆さん、こんにちは!

初代馬場タクシー3Dのリリースから早2年が経とうとしています。
その間、1万DL突破、AppStoreレーシングカテゴリ7位獲得など、まぁまぁご好評頂いており、あざま〜す。

そして今日、大きなバージョンアップがようやくリリースとなりました。
グラフィックがきれいに、より面白くなった馬場タクシー2へようこそ。



↓もうちょっと長いゲーム紹介動画↓


▼主な変更点
- ドライブ可能エリア拡大(山手線内上半分対応)
- ミッションをクリアするとドライブ可能範囲が広がる「エリアレベル」システムを導入
- 車の各種消耗をシミュレート
- 画面デザイン、グラフィック、キャラクタアクション、表現の改善
- 効果音、BGM を多数追加
- バッジを多数追加
- 「馬場コイン」を導入(消耗品の回復を早めることができます。毎日プレゼント。)
- いくつかのバグ修正
- がんばってアプリ配布サイズを 100MB 以下にしました
- 今までの走行データは引き継がれます




↓一応、宣伝ぽいもの↓

▼世界初の東京エリア対応iOSドライビングシミュレータ
▼1万DL突破!
▼レーシングカテゴリ7位獲得
▼たった1分。無性にドライブしたくなったらこのアプリ。

▼ユーザの声
「競争ではなく、自由に走れる車ゲームが欲しかった!」
「ゴチャゴチャした道路とゆるい感じに好感が持てます」
「こーゆーの待ってた!」

▼こんな人にオススメ
運転が好きな方
タクシー業務を通じお客様を満足させ、圧倒的成長! したい方

▼こんなゲームです
山手線内上半分をドライブできます
タクシー業務モード ... Twitterでフォローしている人が客として登場
レースモード ... 早稲田グランプリ、裏馬場耐久レース、新宿三丁目チャレンジ、鶴巻カップ、新宿周遊カップ



>> もっと詳しいゲーム紹介はこちらからどうぞ。 <<

ではでは、Enjoy driving!

2014/12/04

Happy 2015 このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

そろそろ年末ということで、拙作iOSアプリ「分身カメラ」でキラキラした動画を作ってみましたよ。

 

仕組みはどうなってるかというと、東京タワーを背にペンライトで空中に "2015" と描く様子を動画で撮影しておいて、 キラキラした部分を「分身カメラ」を使って分身させると冒頭の動画になる、という感じです。

身の回りに適当なペンライトがなかったので、以前使っていた iPhone5 で http://pa-n.com/light/ を表示させてペンライトとしてみました。

ちなみに、Safari でそのまま表示すると白いアドレスバーが動画に映り込んでしまいますが、「ホーム画面に追加」して出来たアイコンを起動すると全画面モードになりタイトルバーもナビゲーション部分も表示されなくなるのでGOODです。

鏡文字を一定のペースでゆっくり描かないといけない所が結構難しく、何回か練習が必要でした。

というわけで、キミもイルミネーションをバックにキラキラ動画を作ってみよう!三脚は必須だぞー!!


(こっそりおまけ)
Apple本社に行った時に撮影した、Infinite Loop 看板の周りをぐるぐる走る分身動画も載せておきます。手持ち撮影なのでうまく分身できていないです... 手ぶれ補正とか課題。

2013/12/18

馬場タクシー3Dと競技プログラミング このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

はじめに


これは Competitive Programming Advent Calendar Div2013 の 18 日目の記事です。

今年も残り僅かとなりましたが、皆様いかがお過ごしでしょうか。
今日は、@nodchip さんから始まった

「拙作○○○(作品名)の中で競技プログラミングがどのように生かされているか」シリーズ

の続編として、

「拙作iOSアプリ『馬場タクシー3D』の中で競技プログラミングがどのように生かされているか」

を書いてみます。いつも寝不足になりながらコドフォをやってる人も、競技プログラミングって何の役に立つのん?って人も、ぜひ読んで頂けたら嬉しいです。



馬場タクシー3Dとは?


いきなり宣伝ですいませんが、これは趣味で作っているiOSアプリでして、東京でタクシー業務やレースを楽しめるドライビング・シミュレータです。

「新宿や銀座でクレタクやグランツーリスモをやりたいなぁと思って作ったゲーム」

と言った方がピンと来る方も多いかもしれません。

プレイ動画にある通り、Twitterのフォロワーがお客さんとして乗ってくるのでタクシー業務に勤しみます。もたもたしてるとお客さんが怒り出すので頑張りましょう。おまけ機能としてお客さんの最新のツイートが画面に表示されるので、遊びながら友達の近況がゆるやかに伝わってきたりもします。

タクシーの他にレースモードもありまして、いくつかの市街地コースでレースをすることができます。 カートを運転したことがある方はより分かってもらえるかもしれませんが、 作者は
  • 「次のコーナーをタイヤのグリップぎりぎりまで使ってスリップせずに曲がるにはどんなライン取りでいつフルブレーキすればいいのか?」
  • 「コーナーの前にある起伏でちょっと浮く時に荷重が減ってグリップも弱くなるのでちょっとスピードを落とさないと」
  • 「前を走ってる車はこういうライン取りをするだろうからこのタイミングでこっちに出るとぶつからずにジェントルに美しく抜けるかな」
などと考えながらタイムアタックするのが大好きなんですね(笑)。 そのなんというか物理法則と世界の成り立ちとライバル車が何を考えているかをより正確に理解することが速いタイムにつながるみたいな仕組みが好きなんだと思います。 なので、このゲームでもそういう世界を再現すべく、アイテムを使うと爆速になるとかそういうのじゃなくてできるだけ物理法則に沿った動きになるように頑張っています。といっても実態はすべて物理エンジンの Bullet に丸投げしており、ちゃんとブレーキを踏んで十分に速度を落とさないとタイヤが滑ってまともに曲がれなくなるようになってるとかその程度ではありますが。


で、市場の反応はというと、日本の AppStore の「iPad→ゲーム→レーシング→無料」カテゴリで最高 25 位になったほか、 海外ではカリブ海に浮かぶ人口 1.5 万人のアンギラ(Anguilla)という国のiPhone版同カテゴリでなぜか 10 位になるなど、 まずまずの出だしかもしれませんがもっともっと面白くして多くの方に楽しんで頂きたいと思っています。

ちなみに、アンギラはスペイン語やフランス語で競プロ界に時おり出てくるウナギの意味で、島の形がウナギに似ていることから命名されたそうです。wikipediaによると。

ゲームで使うマップデータは Open Database License という緩めのライセンスの元に使用できる OpenStreetMap の地図データを元にしています。 元データは XML になっているので、それを python スクリプトで読み込んでビルや街路樹などの 3D ポリゴンデータや道路グラフを自動生成して、それをアプリから使っています。



馬場タクシー3D内で競技プログラミングが生かされている所


というわけで早速競プロに関連する部分に行きます。

まぁコードの大部分はいたって普通のコードなんですが、マップデータがそれなりに大きいので、マップに関連するところでは計算量を落とす工夫をしたり、ちょっとしたグラフのアルゴリズムを使ったりしています。

今日はそんな処理 2 つをピックアップして紹介します。
  • 道路グラフを検証する処理
  • 道路グラフの行き止まりをなくす処理


競プロっぽい所その(1) - 道路グラフを検証する処理


道路グラフとは何かと言うと、道の要所要所の座標や接続関係を表した有向グラフです。OSM(OpenStreetMap) データを元に作ります。

 // 道路グラフ
 struct RoadGraph {
  vector<Vector3> 頂点配列
  vector<vector<int> > 隣接リスト
 }

いたって普通の隣接リスト表現です。

で、山手線をまるごと含むエリアの道路グラフは頂点数 82,474、辺数 115,738 で、図にするとこんなんです。

結構濃ゆいですね。いかにも TLE しそうな香りがします。

実はこの道路グラフ、馬場タク内のいろんな所で使われています。例えば:
  • AI車がそれっぽい動きをするように道路グラフ上をランダムウォークさせる
  • タクシーモードのとき、プレイヤーの現在地から目的地までの最短経路を A* で計算して表示する
  • ガードレール、街路樹、放置自転車、ビルの看板、ジャンプ台、客の初期位置、AI車の初期位置など、各種データを道路グラフを元に生成する

などなど。

さてこの道路グラフですが、何しろ手動で入力された OSM データを元にしているので、素性の良さを検証したいと思います。

例えば、交差点は中央の頂点が図のように周囲の4頂点とつながっていることが期待されますが、



次の図のように交差点が別々の頂点に分かれていると、例えば目的地までの経路を計算する時に「下から来て左折するルート」を導出できなかったりするかもしれません。


というわけで、もし 2m 以内に点が複数ある場合はそこは交差点とみなして 1 頂点にまとめることにします。 まとめる処理は後でやるとして、ひとまず全ての頂点について「2m 以内に他の頂点があるかどうか」を計算したいですよね!

さてそこで問題です。

Problem (Div1 250)

time limit: 2s

Little Petya は誕生日に平面上の点の集合をプレゼントされました。
Petya は、すべての点について「2m 以内に他の点があるかどうか」を調べるゲームをしていましたが、途中で気持ちよくなって寝てしまいました。
点の座標が与えられるので、あなたが Petya の代わりに最初から調べてください。

Input

vector<pair<double, double> > points

1≦points.size()≦100,000
-10,000≦points[i].first (x座標)≦10,000
-10,000≦points[i].second (y座標)≦10,000
単位は m
任意の半径 5m の円に含まれるの点の個数 ≦ 10

Output

vector<bool> result
result[i] ... points[i] の周囲 2m 以内に他の点(points[j], i≠j)があるかどうか
result.size() should be equals to points.size()


Coding phase start


3...


2...



1...


おわり



回答例

では実際に採用した方法を紹介します。(いろんな方法があると思うので一例です)
空間データ構造としては kd tree, BSP, BVH みたいなのとかいろいろあると思いますが、シンプルで書きやすそうな 2D bucket を使いました。

// データ構造
const double grid_size = 5; // 2m * 2 以上
map<pair<int, int>, vector<pair<double, double> > > data;

空間を正方形のセルに分割したと思って、点は「その点を含むセル」が持つリストに登録します。 具体的にはセルの左下の整数点 pair<int, int> をキーとして map に点リストを格納します。(右上が X+, Y+ とします)

// grid_size==5 で
// (2.5, 0.0), (5.1, 101.5), (4.0, 4.0) を登録したところ
data = {
 (0, 0) -> [ (2.5, 0.0), (4.0, 4.0) ],
 (1, 20) -> [ (5.1, 101.5) ],
}

クエリは、点の座標から(セルの幅/2, セルの幅/2)を引いた地点のセルと、その右、上、右上の計4セルに含まれる全ての点に対して距離チェックをします。円がセルからはみ出るかもしれないので周辺のセルも見るというわけです。


はみ出る対策は、面倒なら無条件に点の座標のセルの周囲 8 個を見るとかでもいいと思います。

セルの 1 辺の長さが 4m 以上であれば、点から 2m 以内の領域は必ずこの4セルに含まれるので、それらをチェックすれば十分です。 また、点の密度に上限があるので、リストに点がたくさん入ってて結局全探索に近くなるといったこともありません。

// クエリ
bool query(double x, double y) {
 const double within = 2.0;
 pair<int, int> base_key(floor(x/grid_size - 0.5), floor(y/grid_size - 0.5));
 int dx[] = {0, 1, 0, 1};
 int dy[] = {0, 0, 1, 1};
 int count = 0;
 for(int i=0;i<4;i++) {
  pair<int, int> key(base_key.first+dx[i], base_key.second+dy[i]);
  if(!data.count(key)) continue;
  for(size_t j=0;j<data[key].size();j++) {
   double lx = x - data[key][j].first;
   double ly = y - data[key][j].second;
   if(lx*lx+ly*ly <= within * within) count++;
  }
 }
 return count > 1; // 自分の点はカウントしない
}

計算量は、点の数を N, 1セルに入るデータ数の平均を M とすると map を引くところが O(log(N/M)), リストを全部見るところが O(M) なのでクエリ全体は O(Mlog(N/M)), 点の密度の上限があるので M を小さな定数とすると O(logN), 実際は定数項が大事とはいえ、まぁいい感じだと思います。

// データ構造の構築
void build(const vector<pair<double, double> >& points) {
 data.clear();
 for(size_t i=0;i<points.size();i++) {
  pair<int, int> key(floor(points[i].first/grid_size), floor(points[i].second/grid_size));
  data[key].push_back(points[i]);
 }
}

// 本体
void solve() {
 build(points);
 for(size_t i=0;i<points.size();i++) {
  result[i] = query(points[i].first, points[i].second);
 }
}

実際のマップデータの処理は python でやっています。さきほどの山手線を含むグラフの場合、総当りで O(N^2) だと終わらなかったのが 2D bucket を使うことで 2.8 秒で終わるようになりました。

2D bucket は他にもこんな所で使っています。大活躍です。
  • (マップデータ生成時) ガードレールの生成
    アルゴリズム: 道路グラフの辺それぞれについて辺を太くしたような長方形を作って、それらの union の輪郭をポリゴン化するとガードレールの出来上がりです。union を計算するために Clipper を使っています。

  • (マップデータ生成時) ジャンプ台を大きな道路のガードレール沿いに設置する処理
    アルゴリズム: 細い道のも含むすべてのガードレール沿いに 20m 間隔で候補点を生成して、その後大きな道路上を 50m 間隔で見ていって 20m 以内に候補点があればそこにジャンプ台を設置します。

  • (マップデータ生成時) 繁華街のビルの角に看板を設置する処理。看板がよく見えるように道に一番近いビルの角に取り付けます。
    ジャンプ台と看板

    アルゴリズム: すべての道上に 10m 間隔で点を設置して、あるビルに含まれるすべての頂点に対して5m以内の点を探す→一番道上の点に近いビルの角に看板を設置します。

  • (アプリ実行時) AI車の前方に車がいるかどうか判定する処理
    アルゴリズム: AI車は基本的に道路グラフ上をランダムウォークしますが、自車の前方 2m, 4m, 6m, 15m の地点から半径 3m 以内に車がいる場合はブレーキを踏みます。車の位置を適宜更新しつつ、2D bucket のクエリで判定します。

  • (アプリ実行時) プレイヤーとの距離が 30m〜100m の歩道上に客を配置して待機させる処理
    アルゴリズム: 歩道沿いの候補点をたくさん生成しておいて、プレイヤー近くの候補点を探して客を配置します。プレイヤーに近すぎるといきなり現れたように見えるので 30m 以上遠くの候補点だけ選びます。

  • (アプリ実行時) プレイヤーとの距離が 100m〜200m の道路上に AI 車を配置する処理
    マップ全体を数千台の車が走っているとすると物理シミュレーションが終わらないので、プレイヤーから 200m くらいの範囲内で車を最大 75 台走らせるようにしています。遠くなった車は GC で回収され、何事もなかったかのようにプレイヤーの近くに配置されます。
    アルゴリズム: 道路沿いの候補点をたくさん生成しておいて、プレイヤーからの距離が 100m〜200m の候補点を探して車を配置します。これも近すぎるといきなり現れたように見えるので 100m 以上遠くの点だけを選びます。

  • (アプリ実行時) プレイヤーに最も近い場所(駅, 信号機, 店とか)の名前を表示する処理
2D bucket のいいところは、単純でスケールアウトしやすい所だと思います。局所的で場所ごとに独立なデータ構造になってるので、将来もっと広いエリアをサポートする時にマップデータを分割したら 2D bucket のデータ構造もそのまま分割できますし、プレイヤーの移動に合わせてサーバから新たなタイルデータをダウンロードするとか、そもそもマップデータの生成を並列実行するとかも自然にできそうです。



競プロっぽい所その(2) - 道路グラフの行き止まりをなくす処理


長いので飽きてきましたが、もうちょいやります。。

プレイヤーが動ける範囲はガードレールの内側(道路側)に限られています。 そのガードレールは前述の通り道路グラフの輪郭なので、 道路グラフ上で行き止まりがあるとそこに入ったプレイヤーも行き止まりになってしまいます。 しばらく一本道を行ったら実は行き止まりで戻るしかない、という状況はつまんないのでなくしたいですね!

そこで、道路グラフ上で行き止まりに通ずる一本道の道路を消すという前処理をしておきます。 普通は道路の行き止まりってあんまりないものですが、マップデータの端の方とかはどうしても行き止まりになってしまうんで、やります。

というわけで問題です。

Problem (Div2 475)

time limit: 20s

Fox Ciel は森で見つけた無向グラフをたどるゲームを始めるところです。
Ciel は行き止まりが嫌いなので、行き止まりにくると泣いてしまいます。
Ciel を泣かせないように、与えられたグラフから最低限の頂点と辺を取り除いて、行き止まりを含まないグラフを作ってください。

|V|≦80,000
|E|≦120,000
行き止まりの数≦1000


Coding phase start


3...


2...


1...


おわり



回答例(面倒なので擬似コード)

これはアルゴリズム的な工夫というよりは実装問題かなと思います。グラフと仲良くなろうみたいな。

行き止まりを見つけたら、そこから戻って1本道である間消すフラグを立てていくみたいな感じです。

# alive[v] な頂点だけからなるグラフは行き止まりを含まない
alive ← [True for i in range(len(g))]

# alive なサブグラフ上で次数 1 の頂点がないように alive[i] を False にしていく
changed ← True
while changed:
 changed ← False
 for v in すべての頂点番号:
  while alive[v] かつ v から出る辺のうち、向こう側が live な頂点の個数が 1 なら:
   alive[v] ← False
   changed ← True
   v ← その向こう側の頂点

# alive[v] の頂点だけからなるグラフを構築
old_new_map ← [-1 for i in range(頂点数)]
new_v ← []
new_e ← []
for v in すべての頂点:
 if alive[v]:
  old_new_map[new_v.length] = v
  new_v.append(v)
  new_e.append([])
 for v2 in v から出るすべての頂点:
  if old_new_map[v2] != -1:
   # 新頂点に入れるべきなので辺を追加する。
   new_e[-1].append(old_new_map[v2])


O(|V|+|E|) くらいだと思います。実際には道路グラフでの行き止まりはそんなに多くないし、サクサク軽快に動いています。



ほか


詳細は省きますが、アルゴリズムっぽい部分は他にこんなものがありました。
  • 目的: ガードレールや白線を複雑な凹凸のある地表にぴったり配置する
    アルゴリズム: 白線を表す線分をグリッド(直線 X=500N, 直線 Y=500N)との交点で分割する→グリッドの各地点での高さにセット

  • 目的: 現在地から目的地までの最短経路を表示する
    アルゴリズム: 2D 距離をヒューリスティックとする A* 探索

  • 目的: Draw call を抑えるために、複数のビルや看板のテクスチャを1つにまとめる
    アルゴリズム: 長方形を大きな正方形の中に効率よく敷き詰める(マラソンぽいですね)→その座標を元に Imagemagick で画像合成



まとめ


長々書きましたがいかがでしたでしょうか。おれならこうするとか、質問とか、ここ間違ってるとか気づいたら遠慮なくお知らせください。

自分としては、ふつうのアプリにしては結構アルゴリズムっぽいことをしてるな〜という印象ですね。作ってても楽しかったです。

というわけで競技プログラミングの先にこんな応用例もありますよという記事でした。
明日 12/19 は @tatuyan_edsonさん, @akenshoさんです。お楽しみに!

2011/10/02

Xcode でシェーダーをコンパイルさせないようにする このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

シェーダーがコンパイルされてしまう

OpenGL ES のプログラマブルシェーダーはアプリ実行時にコンパイルされるものなので、アプリビルドの際は何もせずにファイルとしてパッケージングしたいわけですが、Xcode 4.0.2 で拡張子が .vsh や .fsh のシェーダーファイルを追加してアプリをビルドするとシェーダーまでコンパイルされてしまい、シェーダーの独自構文が Objective C コンパイラで通らなくてビルドエラーになったりします。



Xcode 4.0.2 でシェーダーをコンパイルしないようにする方法

  1. 左側ペインのProject navigatorでプロジェクトを選択
  2. 右側ペインの左側部分でTARGETSを選択
  3. 右側ペインの右側部分で Build Phases タブを選択
  4. Compile Sources を開くとシェーダーファイルが表示されるので、ドラッグ&ドロップでCopy Bundle Resources のところに移動


スクリーンショット


2011/09/23

Blender 2.5 をコマンドラインツールとして使う このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

Blender をコマンドラインツールとして使う

以下のようにすると Blender をコマンドラインから起動して指定した Python スクリプトを実行することができます。

$ blender --background --python test.py

--background オプションを付けると Blender の UI を出さないモードで起動します。 コマンドラインツールとして大量のレンダリングを実行したり、モデルを自動生成するのに使えます。

blender コマンドにはパスを通すなどしてシェルから実行できるようにしておく必要があります。当方では以下のように alias を設定しています。

alias blender='/Applications/blender-2.59-OSX_10.5_i386/blender.app/Contents/MacOS/blender'


視点をスクリプトから設定したい

で、当方ではモデルを自動生成するのに使っているんですが、その blend ファイルを開いて確認する際、毎回決まった視点で表示したいと思ったので調べました。以下のようなスクリプトで設定できます。(ついでにテクスチャ付きで描画するようにしてあります)

# -*- coding: utf-8 -*-

import bpy
from mathutils import Quaternion


for a in bpy.context.window.screen.areas:
    for s in a.spaces:
        if s.type == "VIEW_3D":
            # テクスチャ付きで描画する設定
            s.viewport_shade = "TEXTURED"
            
            # ビューの設定
            s.region_3d.view_rotation = Quaternion((1,0,0),-1.57)
            s.region_3d.view_distance = 5
# 保存
bpy.ops.wm.save_as_mainfile(filepath="sample.blend", relative_remap=True)

Quaternion を使ってビューを設定します。
Blender の座標系は右手系なので、Quaternion((1,0,0), -1.57) は「X軸の方向を向いて反時計回りに-90度の回転」を表します。

何も回転しないと「X 軸が右、Y 軸が上、 Z 軸が手前」のビューになるので、上記の回転を施すと「X 軸が右、Y 軸が手前、Z 軸が下」になります。



スクリーンショット
生成された sample.blend を開いたところです。確かに X 軸が右、Y 軸が手前、Z 軸が下になっています。