3Dゲームを作る課題の振り返り

42

42 TokyoでFPSっぽい3Dゲームを作る課題をクリアしたので振り返り記事を書きます。

課題の概要

2Dのマップを元にしてcub3Dという名前の3DゲームをC言語で作成します。

プログラムの実行に必要な情報（テクスチャー、色、2Dマップ）は以下のように記述した設定ファイル（以降、cubファイルと呼びます）を引数として渡すことで指定します。

NO ./textures/north_61.xpm
SO ./textures/south_61.xpm
WE ./textures/west_61.xpm
EA ./textures/east_61.xpm

F 46,139,87
C 135,206,235


        1111111111111111111111111
        1000000000110000000000001
        1011000001110000000000001
        1001000000000000000000001
111111111011000001110000000000001
100000000011000001110111110111111
11110111111111011100000010001
11110111111111011101010010001
11000000110101011100000010001
10000000000000001100000010001
10000000000000001101010010001
11000001110101011111011110N0111
11110111 1110101 101111010001
11111111 1111111 111111111111
指定子　 意味
NO 壁の北側テクスチャー
SO 壁の南側テクスチャー
WE 壁の西側テクスチャー
EA 壁の東側テクスチャー
F 床の色
C 天井の色
マップ上の文字 意味
1 壁
0 床
N プレイヤー（北向き）
S プレイヤー（南向き）
W プレイヤー（西向き）
E プレイヤー（東向き）

プログラムは大まかに以下の3点を行う必要があります。

  • cubファイルを正しく解釈する。
  • 解釈した情報をもとに3D空間をウィンドウにレンダリングする。
  • WASDキーでプレイヤー位置の移動、左右の矢印キーで視点移動ができるようにする。

また、画面への描画はMinilibXというX Window Systemのラッパー関数のライブラリを使用するという指定があります。MinilibXではウィンドウの表示、xpm形式の画像ファイルの読み込み、ピクセル単位での画面への描画、キーボード・マウス操作のフックができます。

MinilibXのリポジトリはこちら

github.com

成果物

デモ動画

streamable.com

コード

github.com

課題の進め方

42 Tokyoの学生のnyokotaさん と組んで取り組みました。 最初は何をしたらいいか分からない状態だったので、

  1. ペアプロ形式でなんとなく動くものを作る
  2. 役割分担してリファクタリング、機能追加

という2段階で実装しました。

ペアプロ形式でなんとなく動くものを作る

適当なブランチを切って以下の順番で実装しました。

  1. テクスチャーなしで描画する
  2. プレイヤー移動、視点移動できるようにする
  3. テクスチャーを実装する
  4. cubファイルを読み込む

役割分担してリファクタリング、機能追加

ここから、機能ごとにブランチを切って取り組みました。 ブランチの運用はGitHub Flowを参考にしました。 以下のように役割分担して取り組みました。
rsudo 　: ファイルの読み込み、バリデート
nyokota : 画面への描画

実装について

ファイル読み込み

ファイルに記述されている内容をバリデートしながら読み取って行きます。 ファイルの内容のうち、mapは閉じている必要があるのですが、この判定方法としてペイントプログラムの図形塗りつぶしで用いられるflood fillというアルゴリズムを使ってバリデートしました。

flood fillを可視化した様子

streamable.com

flood fillについて詳しくはこちら en.wikipedia.org

画面への描画

画面への描画にはレイキャスティングという手法を使いました。レイキャスティングはこんなイメージです。

f:id:rio_1:20220215142902p:plain

レイキャスティングの背後にある考え方は、ピクセルごとに1つずつ目から光線をトレースし、その光線の経路をブロックしている最も近いオブジェクトを見つけることです。

Ray casting - Wikipedia

計算部分のロジックはこちらのサイトを参考にしました。

lodev.org

下のような流れで計算を行いました。

  1. 以下の図のように、プレイヤーの視野（ウィンドウ幅）の範囲にrayを飛ばし、壁にぶつかるまでの距離を計測する
  2. rayがぶつかった位置からカメラ平面に対して垂直な線の長さを求める
  3. 2で計測した長さに応じて描画する壁の高さを決定する

一つずつ考えていきます。

rayの長さを計算する

rayが壁のx方向の面に当たるかy方向に当たるかによって異なる値を使う必要があるのですが、簡略化のためにx方向に当たるrayを想定します。 rayの長さを求めるためにsideDistX、deltaDistXという変数を使います。定義はそれぞれ以下のようになります。

sideDistX:  開始位置からxの少数部が0になる点まで増加したときのrayの長さの増加分。図のP-A

deltaDistX: xを1増加したときのrayの長さの増加分。図のA-B、B-C、C-Wall

図の場合だとrayの長さはsideDistX + deltaDistX + deltaDistX + deltaDistXで求めることができます。

f:id:rio_1:20220215173624p:plain

垂直距離を求める

rayの長さをそのまま使用すると壁を描画すると視界の端が歪んで見えてしまいます。

下の画像が分かりやすい例なのでもう一度持ってきました。

この場合、視界の中心のrayより視界の端のrayの方が長いので、魚眼レンズを通したように描画されてしまうのですが、ゲーム的にはこの壁は水平に描画された方が自然です。

f:id:rio_1:20220215142902p:plain

そこで、rayが壁に衝突した点からカメラ平面に対して垂直な線の長さを求めます。

個人的にこの値の導出が少し混乱したので、備忘録として残しておきます。 下図のperpWallDistが今回求めたい値です。

また、今回はrayが壁のy方向に衝突した場合を想定しています。

（さっきはx方向だったやんと思った方、ごめんなさい）

f:id:rio_1:20220215191157p:plain

それぞれの値の定義を整理します。 便宜上、図の点WallをWと表記します。

dir: プレイヤーの向きを表す単位ベクトル。長さは常に1
rayDir: rayの方向ベクトル。PD
rayDirY:  rayDirベクトルのy方向の成分。
euclidean: 先ほど求めたrayの長さ。rayを伸ばしていく過程でsideDistYをインクリメントしていき sideDistY- deltaDistYがこの値になる。PW
カメラ平面: dirに対して垂直な線
perpWallDist: Wからカメラ平面に対して垂直な線分
yDist: euclidianに対するy方向の長さ。BW

  1. dirは単位ベクトルなので、perpWallDistとdirの比が分かれば描画する壁の高さを求めることができる

  2. △APW と△EPDは相似なので

      perpWallDist : dir = euclidian : rayDir

  3. △PBW と △PCDは相似なので

     euclidean : rayDir = yDist : rayDiyY

  4.   yDist = euclidean / deltaDistY 
   　　    = (sideDistY - deltaDistY) / deltaDistY

  5. deltaDistY = 1 / rayDirYなので

     (sideDistY - deltaDistY) / deltaDistY = (sideDistY - deltaDistY) * rayDirY

  6.  (sideDistY - deltaDistY) * rayDirY : rayDirY = (sideDistY - deltaDistY) : 1

計算を端折った部分もありますが、perpWallDistの値としてsideDistY - deltaDistYを使用すればいいことが分かりました。

描画する壁の高さを決定する

あとはスクリーンの高さに応じて描画する壁の高さを決めればいいだけです。

screenHeight / perpWallDist

これをウィンドウの横幅の分繰り返すと、3Dゲームっぽい描画ができます。

テスト

ファイルのバリデート

エラーのcubファイルを実行ファイルに渡すシェルスクリプトを作成しました。

使用関数

42 Tokyoの課題では使用可能な関数が指定されており、その確認方法としてnm -uコマンドを実行ファイルに対して使用して、未定義シンボルを表示させるという方法が主流となっています。しかし、今回の課題ではminilibXの関数が様々な外部関数を使用しており、自分でどの関数を使用したかが分かりづらいという問題がありました。そこで、他の生徒の助言を参考にワンライナーをMakefileに書きました。

ifeq ($(shell uname), Darwin)
nm:
  nm -u cub3D | grep -E "^_" | grep -Ev "^_X" | grep -Ev "^__" | cut -b 2- | grep -Ev "^(open|close|read|write|printf|malloc|free|perror|strerror|exit|sin|cos)" | xargs -I{} bash -c "echo '[[' {} ']]'; grep {} src/*/* src/main.c"
else
nm:
  nm -u cub3D | awk '{print $$2}' | grep -Ev "^_" | grep -v "X" | grep -Ev "(open|close|read|write|printf|malloc|free|perror|strerror|exit|sin|cos)" | awk -F'@' '{print $$1}' | xargs -I{} bash -c "echo '[[' {} ']]'; grep {} src/*/* src/main.c"
endif

nm -uで出力される関数のうち、Xで始まるX window Systemの関数や、使用可能な関数をgrep -vで取り除き、使用可能関数ではないが実行ファイルで使用されている関数を求めてます。そして、その結果でソースファイルをgrepすることで、それを自分のソースコードでは使用していないことを示しています。 macOSとubuntuでnmコマンドの出力形式が異なっていたので、それぞれに対応しました。

まとめ

開始から完成までおよそ３週間程度かかりました。自分は数学の素養がないことが不安だったのですが、予想より短期間でクリアすることができたと思います。（ベクトルの基礎、三角関数の基礎からやり直しました）ペアのnyokotaさんは実装力がある方で、一緒にコードを書くと勉強になることが多かったです。ファイル構成や関数の命名など、可読性の観点で提出直前まで議論できたのが印象的でした。