Spring Challenge 2020の感想および方針
最近CodinGameにはまり始めたけせらせらです。
今回実は参加自体は2回目ですが、前回(OceanOfCode)はツイッターのFFの方々が次々とGoldに行く中自分だけSilver19位で止まってしまった上に、ただのルールベースのコードだったので、別にブログを書かなくてもよいか…という気分でした。
では、今回はすごいコードを書いたのかというとそうではありません。書いたものはdfs、bfs、と少し工夫した貪欲ぐらいだったと思います。
しかし、今回違うのは結果です。
なんと今回Gold96位でした!
ということで今回はそんなに難しいアルゴリズムを書かなくてもGoldに行けるよ!という意味合いも込めて記事を書きました。 ということで、
今回の概略
不確定情報には手を出さず(出せず…)確定情報だけでやりました。
一番リソースを割いたのが経路探索の部分で他はルールベースで書きました。
方針
・前計算
1. 各点間の距離
2. 各点の次数
3. 袋小路の検出
4. スーパーペレットの割り当て
1.2.はいろいろ使います。
3.についてですが、袋小路の場所と出入口を計算しました。これは主に敵のキルに使いました。
4.ですが、これはちゃんとやるとちょっと難しそうなのでやめ。妥協します。
最初は各パックからの最短距離を測って割り当てていたのですが、
それだとスーパーペレットの間に挟まれたパックが右往左往してペレットを取りに行くことになり効率が悪いです。なので、最短距離を測って一番短いパックを割り当てたペレットに移動、再びその場所からスーパーペレットの距離を測り一番短いパックを割り当てたペレットに移動、というように割り当てました。(恐らく最適ではないが最初よりはまし)
・経路探索
経路の評価は別で盤面を評価し、辿ったマスの合計で判定しました
経路探索はdfsで全探索しました。ですが、これはさすがに計算量がかかるので、深さは6-7位です。これでもGoldには行けました。
ただ、さすがに改善の余地があるので次の枝刈りを行いました。
1. 同じ点を3回以上通る場合はカット
2. その時点での最大値を取りこの先絶対にこの値を超えることがなければカット
これで探索の深さは10まで行くようになりました。
・盤面の評価
これはいろいろ試行錯誤した結果すごく簡素なものになりました。
1. 相手より近い場所は1.1倍
2. 終盤においてペレットが連結してる個数に沿って少し加点
3. 自分のパックの行き先周辺は減点
としました。
・敵のキル
これは前計算3.を用いて敵が袋小路に侵入したのを確認し次第 、袋小路の出入り口にどちらが先にたどり着くかで判定しました。
敵味方共に袋小路に入っている場合が心配になりそうですが、味方パックのゴールを相手の位置に設定しているので問題ないです。
曲がり角があっても見失うのは必ず曲がり角なので1回までなら必ず見つけてくれます。
しかし、袋小路に2回曲がり角があると見失ってしまう場合があります。その場合は、袋小路の先端に行くようにすれば取り敢えずおっけーです。(していませんでしたが…)
やりたかったこと
- 視界外のペレットの推測
- 敵位置推定
- 経路探索をビームサーチや焼きなましで探索
上の二つはやれば必ず強くなるのでスキルが追い付けばやりたかったです。さらに、この2つは関係性が強いので片方ができれば片方にも役立ちます。 やるとすれば、次数が3の点(T字路)においてTの横棒の部分に自分のパックがいれば見えなくなった瞬間に下に言ったことを判定できるみたいな感じ。 3つ目も練習すればできるものだと思うので、細々と練習していきます。
他の方の話を聞いて
- パックの経路探索を2フェーズに分けて味方の経路を邪魔しないようにする。
- SPEED中にペレットの状況を確認するため交差点で止まる
特に2つ目は実装が簡単なのでできたなーとおもいました。さらに、驚いたのが本質情報として交差点が2マス置きに設置されているためSPEEDのタイミングを調整すれば必ず交差点を確認できるという事実です。すごい…
感想
正直、自分の順位にびっくりしている状況です。
そして、自分の発想力でもそんなに悪い作戦ではなかったと感じたので自分の力でも通用する可能性は十分あるのかなと思いました。
ただ、実装したかったのにできなかったことがあるのは事実なのでこれからも精進したいです…
そして、CodinGameを始めようか迷ってる方!難しいアルゴリズムが書けなくてもGoldに行くチャンスはあるので参加してみましょう!!
取り敢えず一段落かな...
今回の成果
- HP, MP,制限時間の実装
- ロックオン機能の実装
- フロントエンドの実装
- 超簡単な敵AIの実装
1・バトルゲームの経験があればわかると思います。例のあれです。
2・敵を正面にとらえている状態をロックオン状態と呼び、その状態の時のみ弾が誘導弾になるという仕様です。ロックオンしている相手の上には逆三角形が表示されます。
3・ここでいうフロントエンドとは、下の画像の左上のHP,MP表示などのゲームの状況を示す表示を指しています。
4・相手をロックオンしていなければジャンプしロックオンする。弾は打ちっぱなしという雑なAIです。
今回の反省
今回は割とスムーズに進んだ印象です。
これまでを振り返って
絵を抜きにしても、誘導弾の誘導性がまだ高すぎますし、敵AIも雑すぎますが、そういうことを言い始めると永遠に完成しなさそうなのでここでいったん完成とします。(著者もそうおっしゃっているので良いのです! )
プログラミング自体を趣味で始めてから1年ほどたちますけど、この経験を通してだいぶゲーム開発へのイメージが湧いたと思います。そして(これは大体のことに言えますが)もっと早く始めていればよかったとしみじみ思います。就活に追われながらするプログラミングはなかなか心理的にきついものがあります。
またnullptrだよ...
少し間が空いてしまいましたが取り敢えずの進捗報告をします。
今回の成果
- 簡単なシーケンス遷移の実装
- ジャンプの高さ、時間制限
- ジャンプすると自動的に一度相手をロックする
- 弾の発射、またその弾が一定時間たつ、又は相手に当たると消える
- Imageクラスの実装
という感じです。
シーケンス遷移の階層は簡単のため1段階にし、タイトル、ゲーム開始前、ゲーム、ゲーム結果画面を実装しました。*1
ジャンプに関しては書いてある通りで、弾の当たり判定は「弾の座標がロボの直方体の中に入るかどうか」というシンプルな実装になっています。
Image
クラスに関しては画像をただ表示するクラスです。これは、以前制作したボンバーマンクラスにもありましたが*2、今回はハードウェアの力を借りて三角形に分割して表示しようという方針ですので別で作る必要がありました。前回に比べ、かなりすっきりしたコードになりハードウェアの力を実感しております...
今回の失敗
- シーケンス遷移の作り方を完全に忘れていた(一番時間を食いました...)
- この本では画像ファイルを2冪×2冪で取ることをすっかり忘れていた
- ジャンプ時に相手と反対方向を向き、空中浮遊したまま地面に戻らない
またもう一つ以下のような失敗をしました。簡単に言うとnullptr
です。
ロボ(プレイヤー)の位置、角度、カメラの初期位置から、現在のカメラの位置を設定する以下の部分を関数化してupdate
関数の見た目をすっきりさせようと試みたところ画面が真っ黒になってしまいました…
Child* Game::update(Parent* parent) { //ここから Matrix34 w; w.setTranslation(mRobo[mPlayerId]->position()); w.rotateY(mRobo[mPlayerId]->angleY()); Vector3 cameraPos, cameraTarget; w.multiply(&cameraPos, mRobo[mPlayerId]->cameraPosition()); w.multiply(&cameraTarget, mRobo[mPlayerId]->cameraTarget()); mCamera->setPosition(cameraPos); mCamera->setTarget(cameraTarget); //ここまでを関数化 }
本当に関数化以外は何もしていなかったので大パニック!
実際に悪さをしていたのはsetPosition
とsetTarget
の2つの関数だと判明。
// Cameraクラス内 void Camera::setPosition(Vector3& pos) { mPosition = &pos; } void Camera::setTarget(Vector3& target) { mTarget = ⌖ }
という定義だったので、update
内で定義していた変数cameraPos
,cameraTarget
を新しい関数内で定義すると、新しい関数の実行後にその2つの変数は消され、mPosition
,mTarget
は既に存在しない参照を見ることになります。(同じようなミスを前にもしたような…)
// Cameraクラス内 void Camera::setPosition(Vector3& pos) { *mPosition = pos; } void Camera::setTarget(Vector3& target) { *mTarget = target; }
へ訂正すると、mPosition
,mTarget
の(事前に確保されている)参照先にcameraPos
,cameraTarget
の値を代入できるので、解決。(mPosition,mTarget == 0
の時に*mPosition
を見てよいのか気になりますが、これはCameraクラスのコンストラクタ内でnew
によりメモリを確保しているので大丈夫です。)
関数化だけでもバグの原因になってしまうという良い教訓でした。
これからもぼちぼち頑張っていきます。
見た目は大事。構造も大事。
今回は15章!前回の内容から以下の点が変わりました!
- テクスチャを張った
- VertexBuufer, IndexBuffer, Batch, Model, Cameraクラスを追加し、Configクラスを削除。
一つ目は以下の画像の通りです。
二つ目ですが、それぞれ頂点バッファ、インデックスバッファ、バッチ、描画インスタンス、カメラのクラスです。Configクラスですが、今までCameraクラスとほとんど同じ働きをしていたので今回でサヨナラ。二つ目の変更のおかげで頂点バッファとインデックスバッファとテクスチャをコンストラクタに設定すれば、変換行列を生成する過程をかなり自動化できました。
今回のやらかしとしては、アクセスしてはいけないメモリの参照を出したことですね。 恐らく簡単に言うと以下のようなことをしてしまいました。
void test(int* x){ int z = 10; x = &z; } int main(void){ int* y = new int; test(y); cout << *y << endl; }
今後本書ではXMLもどきのファイル形式を定めて、それの字句解析用のプログラムを作ることによって、「頂点バッファとインデックスバッファのXMLもどきのファイル」と「テクスチャの画像ファイル」を用意すればコード内でファイルをロードするだけでロボやらステージがポンと出すことができるところまでもっていくそうです。
ゲーム開発再開!
最近就活が本格化してきている現状に憂鬱なけせらせらです。
さあ、今までサボりにサボっていたゲーム開発を再開しました。(前の記事を見たら200日以上前でした…)
前回は2Dで今回は3Dのゲームを作ってみます。内容は14章です。
現状報告
- 意味不明な緑色の直方体(プレイヤー)が謎の平面の上を前後左右に移動する。
- (等速の)ジャンプができる。
- それと共にカメラが移動する。また、左右にカメラを旋回させられる。
ということができたところです。
具体的なコードはこちら
こんなお粗末なプレイ画像ですが、途中はなぜか、
- カメラが思った方向に旋回しない
- 2つの直方体が同じ場所に表示されてしまう
- そもそも床の上に直方体が出てきてくれない
と災難だったので、希望通りに動いたときは雄叫びを上げてしまいました。もうここ最近で一番うれしかったです。
また、久しぶりだったので、Visual Studioの使い方を大分忘れていましたが、これは過去の自分の記事により案外早めに解決しました。 やっぱり記録を残すのは大事ですね。
ここまでの経験によって、プレイ画面を出すまでのおおまかな流れを学ぶことができましたが、案外線形代数を忘れていることもわかりました。時間があるときに学部時代の教科書を読みなおそうと思います。
爆弾人が取り敢えず完成
取り敢えず殆どオリジナルで作ったボンバーマン(爆弾人)が完成しました(第7章~8章に当たる部分)。期間にして大体1週間ちょいですかね。
ソースコードはこちら。
ということで本書の7章~8章を(ここで初めて)読んだうえでの感想を書いていきます。
反省点
- エラーが残っている
- プレイヤーの座標の取り方
- ステージのパラメータ
・1について
この反省点がある時点で完成しているとは言い難い状況なのは重々承知ですが、明確に原因を究明するのが現時点で厳しそうなので保留にしました。
今現在わかっていることは、長期間残っているエラーはSAFE_DELETEの使い方(または、それ自体)に問題がありそうだということです。この推論に至った理由は、残っているログの使用されている関数を見ると必ずSAFE_DELETEを使っている関数で終わっているという点、また実際にSAFE_DELETEを消すことにより解消した例外が存在したという2点です。後者はソースコード内のSequence::Game::Parent内のsetStateという関数において観測されました。
・2について
座標の値を実際の画素の1000倍の値をとることにより細かなスピードの調整が(intにおいて)できるというものです。僕のコードでは画素単位の座標をそのまま持ってしまっているのでそのようなことができません。
・3について
ステージのパラメータをもって、それを基にステージの自動生成を行うというものです。僕が書いたコードにも似たようなものはありますが、特定の数の敵を必ず配置するなど実現できていない部分があるので書き直す必要がありそうです。
工夫した点
- 連続した操作の確率
- ボムの当たり判定
だけです()
正確に言うと、壁に当たっても滑る処理など工夫した点はほかにもあるのですが、本書に書いてあるものは割愛しました。
・1について
先に言っておくと、この工夫は別に必要ありませんでした。悲しい。
そのうえで興味のある人は読んでください。
これの目的は、選択肢が与えられたときに等確率でその選択肢を選ぶことです。
この工夫が必要な理由ですが、大まかに言うと、与えられた選択肢を同時に選ぶ場合(以下でいうp_0,p_1,…)と順番に選ぶ場合(以下でいうhoge(0),hoge(1),…を実行すること)で特定の選択肢を選ぶ確率が異なるからです。
今、選択肢に0,1,2,…と番号を付けます。p_0を0を選ぶ確率、f_0を確率p_0でtrueを返す関数とした時、選択肢をif (f_0) hoge(0); else if (f_1) hoge(1); else if …
のようにつないだ時に互いの選択肢を選ぶという事象が独立ではなくなってしまうので、p_0== p_1 == …
となるようにしても、厳密には(hoge(0)を実行する確率)>=(hoge(1)を実行する確率)>=…となってしまいます。
今それぞれを選ぶ確率は p_0, (1-p_0)p_1, (1-p_0)(1-p_1)p_2,… となっているので、これらが等しくなるようにすればよいです。具体的に等式を解いてみると、p_(i+1) = p_i / (1 - p_i) (i = 0,1,…)という漸化式が成り立ち、p_i = p_0 / (1 - i * p_0) (i = 0,1,…)という式が成り立ちそうなのがわかります。
実際にこの式が正しいことは数学的帰納法により証明できます。
あとはこのように定めたp_iに対してf_iを本書内のpercentのように定義してあげればよいだけです。
あとから気づいたのですが、最初に言った通りこんなことしなくてもできます。
選択肢に0,1,2,…とラベル付けをしてgetRandom(選択肢の数-1)としてあげてから、その値によってif文で分けるほうが簡単で分かりやすいです……
・2について
これは本書とは違う実装になったので解説しておきます。
まず今回の問題点は、ボムを置いた直後「移動後にボムに触れる場合は動かない」という判定により動けなくなってしまいそのままボムの餌食になってしまうことでした。
本書の解決法では一度ボムから離れたら先ほどの当たり判定を用いるというものです。
僕の場合ですが、「今現在ボムに触れていない かつ 移動先でボムに触れている」の場合のみを当たり判定に用いました。そうすれば問題点は解消できますし、壁やブロックに対して同じ判定を用いても問題ないのでこっちのほうが便利です(きっと)。
感想
結構時間がかかり、普通に疲れました。
一番反省が必要なのはやはりエラーが残ってしまったことですね。これでも頑張って減らしたほうだと思っていますが…
この点に関して軽く調べてみるとスマートポインタなるものが存在するらしいです。
後で調べてみます(きっと…)
また、作業中の笑ってしまうようなバグには結構癒されました。
本書で紹介されている「爆弾の上でただひたすら死を待つだけのバグ」は僕もやりましたし、他に覚えているのは「敵を1体倒すと他の敵が透明化するバグ」とか「開始直後に死ぬバグ」とか「動いたら死ぬバグ」ですかね。
なんか、死んでばっかだな。
こんな感じで色々ありましたが一応それっぽいものは完成したので結構楽しかったです。
またこの調子で続きも勉強していきます。
C++ エラー備忘録
この記事は僕の個人的なエラーのメモ帳代わりの記事です。
僕が今までに苦戦したエラーを中心に、大体の内容と実践した解決法を記載していきます。
ちなみに、僕はC++をVisual Studio 2019で書いています。
また、この記事はエラーに苦戦する度(かつ、ブログを書く気になったとき)に更新する予定です。
"CL.exe"はコード2を伴って終了しました
今のところ一番苦戦していて、かつ、何度も会っているエラーです。
・内容
本質的なことは正直よくわかってないです…
が、その時の原因を書きます。
- 返り値が
void
ではない関数においてreturn
忘れがある。 include
されていないファイルがある。- 初期化されていない変数を使う
・解決法
- 適切な返り値を書く。
- 出力(?)を見てインクルードされていないファイルを特定し、インクルードできるように適当に治す。(僕の場合は、途中でソースコードのファイルを削除してしまったため正常にファイルが
include
されていなかったので、プロジェクトから除外してあげたら治りました) - 変数の初期化を行う。あとから代入するからいいやとポインタを初期化せずそのまま使おうとした時に起こりました。取り敢えず、(別の予期しないバグを起こさないためにも)ポインタは使わないときは0を代入しておきましょう。
未解決の外部シンボル~~が関数~~で参照されています
・内容
所謂、宣言されているが、定義はされていない状況です。
・解決法
その関数が使われているファイル内に直接定義を書く。
または、定義が書いてあるファイルを#include
してあげる。