JUNのブログ

JUNのブログ

活動記録や技術メモ

C言語で3Dゲームを作った

42 C/C++

42の課題の1つであるcub3Dを今日クリアしたので感想を書く.

課題について

Lv2 ではCG系の課題があり, cub3Dというレイキャスティングで古典的な3Dを作るか, miniRTというレイトレーシングプログラムを作るかを選ぶのですが, 自分はcub3Dの方を選びました. なぜなら画面動かせた方が楽しそうだったから.

レイキャスティングとはなんぞやって感じだけど, 大雑把に言えば「光をシミュレートして3次元空間を2次元空間に落とし込む」という感じかな? レイキャスティングのコアとなる考え方は, 光源から放たれる全ての光(光線)をシミュレートするのではなく, 逆に目(スクリーン)から光線(のようなにか)を発射してそれを計算することで何を映すかを計算する手法って感じ?

ちょっと言語化が下手くそ過ぎたので以下の動画の冒頭部分にレイキャスティングのわかりやすい概念の説明があるのでそれ見たほうがいいかも.

www.youtube.com

cub3Dがどんな課題かというと, 完成形としては Wolfenstein 3D みたいな3DゲームをC言語で作りましょうという課題.

www.youtube.com

やらなきゃいけないこととしては以下のような感じ

  • ゲームの設定ファイル(.cubファイル)から設定情報などをパースしてそれらの情報を元にゲームを遊べるようにする.
  • レイキャスティングを用いて3Dのような表示をする
  • --save フラグが引数として提供されたら.bmpファイルを出力してプログラムを終了する

って感じ. メインはレイキャスティングのところ.

使用が許可されている関数などは決まっていて, なんでもかんでも使えるわけではない. 一応 <math.h> 内の関数は全て使用しても良いということだったので, 三角関数などは実装しなくても良い.

また, 描画に関しては, 42側からX Window Systemのラッパーライブラリが提供されるのでそれを使う必要がある.

github.com

42では課題は与えられるけど, 授業や教科書は無いので自分は以下のサイトを見ながら作った.

lodev.org

作ったもの

コード

github.com

動いている様子

youtu.be

Wolfenstein 3D のテクスチャを使うとそれっぽくなります.

youtu.be

出力されたBMPをイメージビュワーで開いた様子. (なぜかはてなブログでbmpファイルをうpするとバグったためスクショ)

f:id:JUN_NETWORKS:20210303035915p:plain

仕組み

norm_leave_comment ブランチにコメント付きのコードがあります. (ブランチ名ひどいな...)

github.com

壁の描画

github.com

プレイヤーの座標などの表し方

f:id:JUN_NETWORKS:20210304084150p:plain

プレイヤーの現在地は2次元ベクトル \vec{pos} で表されます. またプレイヤーの現在向いている方向は2次元方向ベクトル \vec{dir} で表され, これは大きさ1の単位ベクトルです.

ここからがポイントで, ここにスクリーンを表すカメラ平面ベクトル \vec{plane} を追加します. -\vec{plane} が画面左側, +\vec{plane} が画面右側を表します. またこの \vec{plane} の長さ(大きさ)によってプレイヤーの視野角が変わります.

視野角30° ( |\vec{plane}| \fallingdotseq 0.2679 )

f:id:JUN_NETWORKS:20210304085825p:plain
視野角30°

視野角66° ( |\vec{plane}| \fallingdotseq 0.6494 )

f:id:JUN_NETWORKS:20210304085928p:plain
視野角66°

視野角90° ( |\vec{plane}| \fallingdotseq 1.0000 )

f:id:JUN_NETWORKS:20210304090021p:plain
視野角90°

planeベクトルの長さの計算方法は tan(deg/2) で計算出来ます.

また, マップのデータは文字列の配列で持ちます. (0: 空白, 1: 壁, 2: スプライト(障害物))

char *MAP[] = {
        "1111111111111111111111111",
        "1000000000110000000000001",
        "1011000001110000002000001",
        "100100000000000000000000111111111",
        "111111111011000001110000000000001",
        "100000000011000001110111110111111",
        "11110111111111011100000010001",
        "11110111111111011101010010001",
        "11000000110101011100000010001",
        "10002000000000001100000010001",
        "10000000000000001101010010001",
        "11000001110101011101011010N0111",
        "11110111 1110101 101111010001",
        "11111111 1111111 111111111111",
};

光線を飛ばす

以下の図のような感じでプレイヤーの現在地から \vec{dir} - \vec{plane} から \vec{dir} + \vec{plane} までの間で光線を飛ばします. 飛ばす間隔はスクリーンの横幅のピクセル数に依存します(画面の横幅と同じ数の光線を飛ばす). (図では光線の一部を省略しています)

f:id:JUN_NETWORKS:20210304085314p:plain

で, 光線を飛ばすといっても適当に飛ばしたのではどの壁にぶつかったかわからないので, DDA(デジタル差分解析)という方法を使って光線を1マスずつ進めていき, 壁にぶつかったかどうかを都度チェックします.

f:id:JUN_NETWORKS:20210304095819p:plain

Raycasting

sideDistX, sideDistY は最初プレイヤーがいる位置がぴったりマスの端にいるとは限らないのでまず最初の1回目だけは別でマップの端に移動するための量.

deltaDistX, deltaDistY はマスの端から次のマスの端までの距離.

これらの値を使って1マスごとに壁かどうかチェックしていき, 壁だったらそこで終了する.

壁までの距離を求める

光線を飛ばして壁にぶつかれば今度は, 壁までの距離を求めることが可能になります.

ただし, プレイヤーから当たった壁までの距離をそのまま使うと魚眼のようになってしまうので, 工夫する必要があります.

具体的にはプレイヤーから壁までの距離ではなく, カメラ平面(を無限に左右に伸ばした直線)に対して垂直になるような距離(以後"垂直距離"と呼ぶ)を取ります.

f:id:JUN_NETWORKS:20210304104932p:plain

Raycasting

上の図でいうところの緑色の線が垂直距離です.

壁までの垂直距離の計算式や図を用いた導出は Raycasting でされているのでここでは割愛します.

壁を描画する

壁までの垂直距離が求まったところで, その値を使って今度は壁の高さ(height_base)を求めます.

これはただ単に 基準となる壁の高さ / 壁までの距離 で求めることが出来ます.

この基準となる壁の高さ は別にスクーン幅そのまま使ってもいいんですが, 実はそのままスクリーン幅を使うと縦横比がスクリーン幅によって変わってしまうので, 変わらないようにするために 2*|\vec{plane}| の逆数を掛けます. 式は スクリーン幅 / (2 * plane_length) です. この式の意味としては, 「視野角が広くなるということは \vec{plane} の大きさが大きくなるよね. 大きくなるということは描画された時に横の長さが一定じゃなくなるってことだから, 2 * |\vec{plane}| の逆数を掛ければ横の長さが元に戻るんじゃね?」 っていう感じ.

これで壁の高さが求められたので, あとは画面中央を基準に壁を描画すればOKです. テクスチャを描画する場合は描画している場所が壁全体の上から何%の位置にいるのかというのを求めて, それをもとにテクスチャ画像から色を取得してスクリーンに描画すればOKです.

スプライトの描画

github.com

そもそもスプライトとはなんぞやって感じなんですが, スプライトは障害物みたいな感じのやつです.

f:id:JUN_NETWORKS:20210304111022p:plain
この樽みたいなやつがスプライト

スプライトは壁の描画とは一味違ってて, よく言われる表現が「スクリーンにシールを貼った感じ」というもの. これは実際に動いている動画とかを見ないと多分わからないと思うのでこの記事の最初の方で貼った動画を見てちょ.

ただ, 正直どのようにスプライトを描画したら正解なのかがしっかりわかっている訳ではないのでもしかしたら間違ってるかもです.

というか壁の描画がプレイヤーから光線を発射し, それが壁にぶつかるまでの距離を元にどのように描画するのかを決めていたのに対し, スプライトの描画はプレイヤーとスプライトの位置関係を元に2D画像をどのような大きさでスクリーンのどこに描画するか計算するので, 壁の描画とは考え方がだいぶ違います.

技術的には 透視投影変換 というものらしいです. (42にいるゲーム開発者の方が教えてくれました)

mem-archive.com

処理の流れとしては

  1. 壁の描画フェーズにてスクリーン幅分の光線放出し, 壁までの垂直距離を求めたので, その各光線の壁までの垂直距離の情報を配列(zBuffer とする)として保持する.
  2. スプライトまでの距離(ユークリッド距離)を求めて, 距離が遠い順になるようにソート.
  3. スプライトの座標をマップ上の座標からプレイヤーからの相対座標に変換する.
  4. カメラ行列の逆行列を掛けてスクリーン上でのx座標と, プレイヤーからスプライトまでの深度(3D空間におけるZ軸)を求める.
  5. スクリーン上のx座標とスプライトまでの深度を元にスプライトを描画する幅や高さを計算する.
  6. スプライトの左端から右端にかけてスクリーンの各xに対して描画処理を行う. その際に zBuffer[x] がスプライトの深度よりも遠い (つまりスプライトが壁よりも手前にある) 場合にスプライトを描画する.

はい. むずいですね.

正直スプライトの計算に関しては元サイトの方でも説明が少なかったので理解するのが大変でした.

スプライトの描画に必要な情報の計算

スプライトの描画に必要な情報は以下の通りです.

  • スプライトの描画座標
  • プレイヤーからスプライトまでの距離

この2つです. 一応他にもスプライトの描画サイズなどもありますが, 他の情報はすべて上記の2つの値から計算されるので, この2つの値がもっとも重要なのです.

この2つの値の計算に 透視投影変換 の手法を使います.

透視投影変換は2つのフェーズに分けることができます.

https://i2.wp.com/mem-archive.com/wp-content/uploads/2018/02/%E3%82%AD%E3%83%A3%E3%83%97%E3%83%81%E3%83%A34.png

透視投影変換とは | NO MORE! 車輪の再発明

つまり以下の2つの処理に分けることが出来ます.

  • 外部パラメータ：世界座標系からカメラ座標系への変換
  • 内部パラメータ：カメラ座標系から画像座標系への変換

ちなみに...

  • カメラ: 今回の場合, プレイヤーの現在座標にあたる.
  • 世界座標系: 絶対的な位置. 今回の場合だとスプライトのMAP上での座標にあたる.
  • 外部パラメータ: カメラ行列の逆行列(後述)を掛けてカメラ座標系に変換する.
  • 内部パラメータ: カメラ座標系から画像座標系(スクリーン上での具体的な座標)に変換する

というように対応します.

世界座標系からカメラ座標系への変換

まず初めに世界座標系からカメラ座標系への変換を行います.

この変換を行うために, スプライトの座標を世界座標系(スプライトのMAP上での座標)からプレイヤーからの相対座標に変換するひつようがあるので変換します.

式は, \vec{sprite} - \vec{pos} です. シンプルですね.

次に相対座標からカメラ座標系への変換を行います.

カメラ座標系への変換には相対座標に対してカメラ行列を掛けるという操作を行います.

カメラ行列ってなんぞや? って感じですが, カメラ行列とは以下のような行列のことです.

\left[ \begin{matrix} planeX & dirX \\ planeY & dirY \end{matrix} \right]

そしてカメラ行列の逆行列は以下のような式になります.

\left[ \begin{matrix} planeX & dirX \\ planeY & dirY \end{matrix} \right]

これを先程求めたスプライトのプレイヤーからの相対座標 ( \vec{pos'} とする) に掛けます.

\frac{1}{(planeX \times dirY - dirX \times planeY)} \times \left[ \begin{matrix} planeX & -dirX \\ -planeY & dirY \end{matrix} \right] \left[ \begin{matrix} sprite'X \\ sprite'Y \end{matrix} \right] = \left[ \begin{matrix} transX \\ transY \end{matrix} \right]

この式によって求められる transX , transY は以下のような意味を持つ.

  • transX : カメラから見て左右のスプライトまでの距離. スケールはマップと同じ.
  • transY : カメラから見て前後(深度)のスプライトまでの距離. スケールはマップと同じ.

図にすると以下のような感じ.

f:id:JUN_NETWORKS:20210304123149p:plain

カメラ座標系から画像座標系へ変換する

ここではスクリーン上に描画する際に必要となる以下の値を計算します.

  • スクリーン上でのx座標
  • スプライトのスクリーン上での高さ
  • スプライトのスクリーン上での幅

まずスクリーン上でのx座標ですが, これは (int)(screenWidth / 2 * (1.0 + transX / transY)) で計算出来ます. 式の意味としては, まず transX / transY が, スプライトが画面左端にある時は -1, 中央の時は 0, 画面右端にいるときは1になります. これに1足して, 画面の横幅の半分を掛ければ具体的なスクリーン上でのスプライトの中心のx座標が求まります.

スプライトの高さと幅については壁の高さのときに使った height_base を使って height_base / transY とするれば求まります.

後はこれを描画すればOKです.

f:id:JUN_NETWORKS:20210304124246p:plain
計算過程(間違ってたら教えてください)

BMP画像の出力

www.umekkii.jp

基本的にこのサイトを見ながらファイルに各種情報を書き込んでいけばOK. Bitmapらくちん!

マップが閉じているかの判定

github.com

設定ファイルにて示されているマップが閉じていない場合はエラーを返さないといけないので, マップが閉じているかどうかの判定を行う必要があります.

"マップが閉じている"というのは具体的には, プレイヤーが歩いてマップ外部に到達不可能. つまり, 壁で覆われているということです.

この判定は floodfill というアルゴリズムを使えば可能です.

en.wikipedia.org

おまけ

アルファブレンディング

処理が重かったので関数を作っただけで使いませんでしたが, アルファブレンディングというものを実装しました.

ja.wikipedia.org

// アルファブレンディング
// dst: 背景, src: 前景
uint32_t   alpha_blend(uint32_t dst, uint32_t src)
{
    double     alpha;
    uint32_t   color;

    // 透明: 0.0, 不透明: 1.0
    alpha = -((double)(src >> 24) / (double)0xff - 1.0);
    color = 0x00000000;
    color |= (int)((src & 0xff) * alpha) + (int)((dst & 0x000000ff) * (1 - alpha));
    color |= ((int)((src >> 8 & 0xff) * alpha) + (int)((dst >> 8 & 0xff) * (1 - alpha))) << 8;
    color |= ((int)((src >> 16 & 0xff) * alpha) + (int)((dst >> 16 & 0xff) * (1 - alpha))) << 16;
    return (color);
}

やってることとしてはWikipediaの記事をそのままコードにした感じ.

f:id:JUN_NETWORKS:20210304124513p:plain
樽の背景が少し透けてる

何かに使おうと思って作ったけど, 結局使わなかったので供養.

完走した感想

完走した感想ですが, 楽しい課題でした. 3Dゲームの描画の計算のやり方(レイキャスティング)や設定ファイルをC言語でパースする方法などを知れてよかったです.

ただ, エラーハンドリングがめんどくさかった... mallocの成否の判定などを書いていると, PythonやJSの例外って便利な機能だなぁと思いました.

あと, 数学を使ったコードを久しぶりに書きましたが楽しいですね. 久しぶりに高専で使ってた線形代数のノート引っ張り出して色々思い出しました.

昨今3DゲームとかはUnityとか使えばある程度のものは簡単に作れるわけですが, 一度こうやってゲームエンジンなどを使わず, 原始的なゲームを作ってみると, かなりゲームエンジンに対する考え方なども変わりますし, ゲームエンジンってすげぇなぁ〜って思いました.

今回も記事を書く前はめんどくさいなぁ〜と思ったのですが, 記事を書く中で適当に理解して放置していた箇所を理解し直す羽目になった(特にスプライトのところ)ので良かったです. やはりアウトプットは大切. はっきりわかんだね.

本当はこの課題の前に, printf自作とかサーバー系の課題とか面白い課題が色々あったのですが, 結局書きたいなーと思って放置してしまっていますね... printfはそのうち書きます.

42, いい場所なので, プログラミングが好きな人間は来ると幸せになれると思います.

では今日はこのへんで. ではでは〜〜👋👋