💰

【42 Tokyo】so_longで僕が考えたこと

に公開

先日so_longという課題を提出しました。
こちらは「パックマン」のような2Dゲームを作成する課題です。

こんな感じ↓

プレイヤーは「W」「A」「S」「D」キーを使って全てのコインを集めてゴールに到達するのが目的です。

実装の処理の流れとしては、

  1. マップファイル(map.ber)を読み込みパースする
  2. マップをバリデート
  3. マップをグラフィックに表示
  4. ゲームプレイ

といった形になります。
この課題についてどのような思考で、どこにこだわりを持って作っていったのか備忘録的に書いていきます。

手始めに

まずpdfを見て最も不明瞭だったのは、windowにマップを描画したりプレイヤーを動かしたりするグラフィック周りの処理でした。ただし、コレは課題に付属しているライブラリ(MiniLibX 以下 MlX)があるのでそれでなんとかするのだろうと仮説を立てました。実際にMlXでウィンドウを開いて画像を表示する最小限のコードを書いて、本課題においてこのライブラリが担当するのはどこまでなのかざっくり見通しを立てました。
結果、マップファイルをMlXに渡すまで自分でコードを書いて、そこからの処理はライブラリ内関数で賄うのだろうと理解しました。

マップファイル読み込み → パースするまで

そこからはマップファイルをパースしてchar**gridを生成するまでの具体的な流れを考えました。

マップファイルのサンプルはこちら。

マップファイル↓
1111111111111
10010000000C1
1000011111001
1P0011E000001
1111111111111

各記号の意味↓
1 = 壁
0 = 空白
P = プレイヤー(Player)
E = 出口(Exit)
C = コイン

* このファイルを読み込んで二次元配列(char**grid)に変換し、
各セルの文字を基に適切なテクスチャを表示する必要がある。

マップを読み込んでchar**gridを生成するだけであれば、別課題でやったことを応用すれば簡単でした。
問題はバリデーションでした。
下記は有効なマップの条件です。

* マップは長方形である
* マップの全ての辺が壁に覆われている
* プレイヤーと出口はそれぞれ一つずつである
* コインは最低一つマップに存在している
* プレイヤーが全てのコインを取得してゴールまで辿り着けるパスが存在している

これらのどれか一つでも満たしてないマップの場合はそれを弾いてErrorを返さないといけないのです。

こだわった点

通常の流れだと、

  1. マップをreadしてマップの高さを取得
  2. 取得した高さを使い、mallocでマップをパースしgridを作成
  3. gridをバリデートする
  4. グラフィックを表示
  5. ゲームがプレイできる

という流れがわかりやすく自然かと思います。
ただこの工程の1~3で、実際には以下のように3回もマップ全体をループしていることになります:

  • 高さ取得のために全行を読む(1回目)
  • grid作成のために再度全行を読む(2回目)
  • バリデーションで全セルをチェック(3回目)

これだと非効率と思い、なんとかして処理回数を減らせないか考えたところマップファイルの読み込みとバリデーションを同時に行えないかと当てをつけました。
1回目のループで下記の構造体に値を挿入していく形でバリデーションを行いました。

typedef struct s_map_v
{
	int			width;                 // マップの幅
	int			height;                // マップの高さ
	int			player;                // プレイヤーの数
	int			exit;                  // 出口の数
	int			collectibles;          // コインの数
	int			is_wall;               // 全ての辺が壁になっているか
	int			is_rectangular;        // 長方形になっているか
	int			is_last_row_valid;     // 最後の行のバリデーション
	int			is_valid_characters;   // 使用可能文字(0,1,C,E,P)のチェック
}				t_map_v;

こうすることで1回目のループ終了時に下記のバリデーションが全て終わっている状態にできます。

  • マップは長方形である
  • マップの全ての辺が壁に覆われている
  • プレイヤーと出口はそれぞれ一つずつである
  • コインは最低一つマップに存在している

残すところはプレイヤーが全てのコインを取得してゴールまで辿り着けるパスが存在しているのみをチェックすれば良いので、2回目のループでgridを生成し、flood_fillを実行してパスが正しいマップかをチェックしました。

こうすることによってループの回数を一回減らし、以下の効果を得られたかと思います:

  • エラーの早期発見(無効な文字があれば1回目で即座に検出)
  • メモリ効率の向上(grid作成前にエラーを発見できればmallocが無駄にならない)
  • 処理時間の短縮(特に大きなマップで効果的)

グラフィック周り

グラフィック周りの実装については、基本的に要件に沿って作成しました。
具体的には、マップの各文字(0,1,C,E,P)に対応する画像素材を用意し、これらをMlXを使ってwindowに描画する処理を実装しました。ゲーム中は、windowにフォーカスが当たっている状態で「W」「A」「S」「D」キーが押されるたびに、プレイヤーの移動処理やコインの獲得判定を行い、状態変化に応じてマップ全体を再レンダリングするようにしました。
ゲーム終了の条件として、マップ上の全てのコインを取得した後に出口を踏むか、もしくはESCキーが押された場合にゲームが終了するよう実装しました。また、プログラム終了前には適切なメモリ管理として、MlXで生成したwindowや画像リソースをすべてdestroyして、メモリリークを防ぐ処理も含めました。

*ちなみに最初のレビューでwindowや画像リソースをdestroyし忘れており、memory still reachableと表示されてしまいました。コレがリークエラーかどうか意見が分かれるところですが、潰せるエラーではあるのできちんと忘れずdestoryしましょう^^;

まとめ

42に入って今までの課題は要件通りに作ることで精一杯で、「こうしたら改善できるかも」と考える余裕がありませんでした。しかし今回の課題では、実装中に効率化や最適化について考える余裕があり、すごく充実感を覚えました。

振り返ってみると、reallocを自前で実装できれば、ファイル読み込みのループを一回で済ませることができたかもしれません。今考えると、そちらのアプローチも試してみてもよかったなと思います。

これまでは課題を最速で終わらせることを目標にしていましたが、一つずつ理解して自分なりに改善点を見つけながら前に進んでいく感覚を大事にしていきたいと思いました。

Discussion