今年も残り僅かとなりましたが、皆様いかがお過ごしでしょうか。「拙作iOSアプリ『馬場タクシー3D』の中で競技プログラミングがどのように生かされているか」を書いてみます。いつも寝不足になりながらコドフォをやってる人も、競技プログラミングって何の役に立つのん?って人も、ぜひ読んで頂けたら嬉しいです。馬場タクシー3Dとは?いきなり宣伝ですいませんが、これは趣味で作っているiOSアプリでして、東京でタクシー業務やレースを楽しめるドライビング・シミュレータです。「新宿や銀座でクレタクやグランツーリスモをやりたいなぁと思って作ったゲーム」と言った方がピンと来る方も多いかもしれません。プレイ動画にある通り、Twitterのフォロワーがお客さんとして乗ってくるのでタクシー業務に勤しみます。してるとお客さんが怒り出すので頑張りましょう。おまけ機能としてお客さんの最新のツイートが画面に表示されるので、遊びながら友達の近況がゆるやかに伝わってきたりもします。タクシーの他にレースモードもありまして、いくつかの市街地コースでレースをすることができます。「前を走ってる車はこういうライン取りをするだろうからこのタイミングでこっちに出るとぶつからずにジェントルに美しく抜けるかな」などと考えながらタイムアタックするのが大好きなんですね(笑)。そのなんというか物理法則と世界の成り立ちとライバル車が何を考えているかをより正確に理解することが速いタイムにつながるみたいな仕組みが好きなんだと思います。このゲームでもそういう世界を再現すべく、アイテムを使うと爆速になるとかそういうのじゃなくてできるだけ物理法則に沿った動きになるように頑張っています。丸投げしており、ちゃんとブレーキを踏んで十分に速度を落とさないとタイヤが滑ってまともに曲がれなくなるようになってるとかその程度ではありますが。出だしかもしれませんがもっともっと面白くして多くの方に楽しんで頂きたいと思っています。ちなみに、アンギラはスペイン語やフランス語で競プロ界に時おり出てくるウナギの意味で、島の形がウナギに似ていることから命名されたそうです。wikipediaによると。地図データを元にしています。ポリゴンデータや道路グラフを自動生成して、それをアプリから使っています。馬場タクシー3D内で競技プログラミングが生かされている所というわけで早速競プロに関連する部分に行きます。コードの大部分はいたって普通のコードなんですが、マップデータがそれなりに大きいので、マップに関連するところでは計算量を落とす工夫をしたり、ちょっとしたグラフのアルゴリズムを使ったりしています。つをピックアップして紹介します。道路グラフとは何かと言うと、道の要所要所の座標や接続関係を表した有向グラフです。データを元に作ります。}いたって普通の隣接リスト表現です。図にするとこんなんです。しそうな香りがします。実はこの道路グラフ、馬場タク内のいろんな所で使われています。ビルの看板、ジャンプ台、客の初期位置、AI車の初期位置など、各種データを道路グラフを元に生成するなどなど。データを元にしているので、素性の良さを検証したいと思います。次の図のように交差点が別々の頂点に分かれていると、例えば目的地までの経路を計算する時に「下から来て左折するルート」を導出できなかったりするかもしれません。頂点にまとめることにします。以内に他の頂点があるかどうか」を計算したいですよね!さてそこで問題です。誕生日に平面上の点の集合をプレゼントされました。以内に他の点があるかどうか」を調べるゲームをしていましたが、途中で気持ちよくなって寝てしまいました。代わりに最初から調べてください。start3...2...1...おわり回答例では実際に採用した方法を紹介します。data;空間を正方形のセルに分割したと思って、点は「その点を含むセル」が持つリストに登録します。点リストを格納します。セルの幅/2)を引いた地点のセルと、その右、上、右上の計4セルに含まれる全ての点に対して距離チェックをします。円がセルからはみ出るかもしれないので周辺のセルも見るというわけです。個を見るとかでもいいと思います。以内の領域は必ずこの4セルに含まれるので、それらをチェックすれば十分です。点の密度に上限があるので、リストに点がたくさん入ってて結局全探索に近くなるといったこともありません。実際は定数項が大事とはいえ、まぁいい感じだと思います。秒で終わるようになりました。他にもこんな所で使っています。輪郭をポリゴン化するとガードレールの出来上がりです。以内に候補点があればそこにジャンプ台を設置します。繁華街のビルの角に看板を設置する処理。看板がよく見えるように道に一番近いビルの角に取り付けます。間隔で点を設置して、あるビルに含まれるすべての頂点に対して5m以内の点を探す→一番道上の点に近いビルの角に看板を設置します。以内に車がいる場合はブレーキを踏みます。歩道沿いの候補点をたくさん生成しておいて、プレイヤー近くの候補点を探して客を配置します。以上遠くの候補点だけ選びます。台走らせるようにしています。回収され、何事もなかったかのようにプレイヤーの近くに配置されます。候補点を探して車を配置します。以上遠くの点だけを選びます。いいところは、単純でスケールアウトしやすい所だと思います。データ構造もそのまま分割できますし、プレイヤーの移動に合わせてサーバから新たなタイルデータをダウンロードするとか、そもそもマップデータの生成を並列実行するとかも自然にできそうです。長いので飽きてきましたが、もうちょいやります。プレイヤーが動ける範囲はガードレールの内側(道路側)に限られています。道路グラフ上で行き止まりがあるとそこに入ったプレイヤーも行き止まりになってしまいます。一本道を行ったら実は行き止まりで戻るしかない、という状況はつまんないのでなくしたいですね!そこで、道路グラフ上で行き止まりに通ずる一本道の道路を消すという前処理をしておきます。普通は道路の行き止まりってあんまりないものですが、マップデータの端の方とかはどうしても行き止まりになってしまうんで、やります。森で見つけた無向グラフをたどるゲームを始めるところです。行き止まりが嫌いなので、行き止まりにくると泣いてしまいます。泣かせないように、与えられたグラフから最低限の頂点と辺を取り除いて、行き止まりを含まないグラフを作ってください。start3...2...1...おわり回答例(面倒なので擬似コード)これはアルゴリズム的な工夫というよりは実装問題かなと思います。グラフと仲良くなろうみたいな。行き止まりを見つけたら、そこから戻って1本道である間消すフラグを立てていくみたいな感じです。新頂点に入れるべきなので辺を追加する。実際には道路グラフでの行き止まりはそんなに多くないし、サクサク軽快に動いています。ほか詳細は省きますが、アルゴリズムっぽい部分は他にこんなものがありました。画像合成まとめ長々書きましたがいかがでしたでしょうか。おれならこうするとか、質問とか、ここ間違ってるとか気づいたら遠慮なくお知らせください。自分としては、ふつうのアプリにしては結構アルゴリズムっぽいことをしてるな〜という印象ですね。作ってても楽しかったです。いうわけで競技プログラミングの先にこんな応用例もありますよという記事でした。@akenshoさんです。センター試験英語(第5問)(過去に作ったものを紹介するだけです。そのゲームを作ってみました。