[42Tokyo] C言語で一人称視点のゲームを作った

42Tokyoの課題「**Cub3D**」についての記事です。

# 42Tokyoの「Cub3D」課題解説

Cub3Dは、一人称視点の3Dゲームを作成するためにRaycasting技術を活用する課題です。

## Raycastingとは

Raycastingは、リアルタイムの3Dグラフィックレンダリングにおいて重要な技術です。私たちが物体を認識するのは、光源から発せられた光線が物体に反射し、私たちの目に届くことによって可能になります。
<img width="600" alt="image.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/cf9888b2-c75c-138f-fad1-78625da0d1e0.png">
引用: [The Textbook of RayTracing @TDU](https://knzw.tech/raytracing/?page_id=1154)

全ての光線を計算すると膨大な処理が必要になりますが、Raycastingではカメラから見える範囲内の光線のみを計算し、それ以外の光線は無視します。これにより、グラフィックレンダリングの計算処理が大幅に軽減されます。
<img width="600" alt="image.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/bc674f92-9928-304e-f508-7e250ec0a4a7.png">
引用: [The Textbook of RayTracing @TDU](https://knzw.tech/raytracing/?page_id=1154)

Raytracing技術は、Raycastingに加えて光の屈折や影などの詳細な処理を含みます。

Raycastingの概念については、以下の動画で分かりやすく説明されています。

https://youtu.be/Mtf4rz9UEQo

## 課題内容
このプロジェクトでは以下の実装が求められます。

**Mandatory:**
・床と壁は2種類の色を設定可能
・←→キーで左右の視界移動
・WASDキーで移動
・ESCキーまたはXボタンでプログラム終了
・地図は「0」（空間）、「1」（壁）、及び「NSWE」（プレイヤーのスポーン地点と向き）で構成
・地図が壁で囲まれていない場合、エラー表示
・地図内のスペースで区切り可能
・東西南北でテクスチャ指定
・床と天井の色指定

**Bonus:**
・壁の衝突判定
・ミニマップ
・マウスによる視点移動
・ドアの開閉（未実装）
・スプライト表示（未実装）

42Tokyoの課題では、使用可能な関数が限られており、この制約の下での実装が求められます。三角関数のライブラリ「math.h」は使用可能です。

描画には、42が開発したグラフィックライブラリ「minilibx」を使用します。minilibxのmacOS版は非公開ですが、Linux版は以下のリンクからアクセス可能です。

https://github.com/42Paris/minilibx-linux

**チーム開発**
この課題は2人1組でのチーム開発形式で進められ、GitHubを使用してバージョン管理とタスク管理を行いました。

# 実動するゲームの動画

以下は、実際に動作するCub3Dゲームの動画です。

<iframe width="560" height="315" src="https://www.youtube.com/embed/eS35y5QXnsA" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>
<iframe width="560" height="315" src="https://www.youtube.com/embed/RdUJbgnzIEk" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>

<br>
<br>

## プロジェクトのGitHubリポジトリ
プロジェクトのソースコードは以下のGitHubリポジトリで公開しています。

https://github.com/subarunrun0812/42-Cub3D

# ゲームファイルの読み取り
ゲームを実行する際には、実行ファイルとマップファイルを指定します。
```sh
./cub3D <.cubファイルのパス>
```
ゲーム設定ファイル（.cubファイル）は、テクスチャ、床と天井の色、ステージのマップの3つの要素で構成されており、これらをパースしてステージが形成されます。以下はその一例です。
```cub
NO textures/no.xpm
SO textures/so.xpm
WE textures/we.xpm
EA textures/ea.xpm

F 220,100,0
C 225,30,0

111111111
100000001
100000001
1000N0001
100000001
100000001
111111111
```

## 有効なマップの判定
Cub3Dのゲームマップは、特定の文字で表現され、それぞれに特別な意味があります。

**マップの構成**
・マップは次の6つの文字で構成されます：
`0`: 何もない空間
`1`: 壁
`N`,`S`,`W`,`E`: プレイヤーのスポーン地点と向き


**無効なマップの条件**
以下の条件を満たさない場合、エラーを出力します：

・　マップが`1`で囲まれていない場合
・　`0`,`1`以外の文字を含む空間の描画、またはプレイヤーがそこに移動する場合
・　`N`,`S`,`W`,`E`が複数存在する場合（プレイヤーのスポーン地点は1つのみ）

## マップの実装詳細
マップ情報はchar型の2次元配列に格納され、以下のポイントでチェックされます：

1. mapdata の1行目と最後の行が`1`または`<space>`で構成されていること。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/6feacfbe-e978-c3cb-0a37-df95fda40aa4.png)
2. 各行の左右の端が`1`であること。
3. `0`およびプレイヤーのスポーン地点 (`N`,`S`,`W`,`E`) の周囲8方向に`space`と`tab`が存在しないこと。この際、対象行の n 番目の文字が前後の行より大きい場合、壁に囲まれていないとみなし、エラーを出力します。

## 床と天井の色指定
床と天井の色は、課題の要件に基づき特定の色で指定されますが、テクスチャでの描画も可能です。解析時に、床と天井が色指定かテクスチャパス指定かを識別します`F`と`C`の後の文字列が数字で構成されている場合、色指定とみなし、RGBの3つの値を構造体に代入します。テクスチャ指定の場合は`N`,`S`,`W`,`E`の指定と同様の処理を行います。


# RayCastingの実装

## 基本的な考え方
この課題では、壁の高さが統一されており、Z軸が固定されているため、3次元空間を2次元ベクトルで表現します。プレーヤーの現在位置は2次元ベクトル`pos`で示され、向きは大きさ1の単位ベクトル`dir`で示されます。さらに、視野を形成するためのカメラ平面ベクトル`Plane`を追加します。`Plane`の左端を`-1`、右端を`1`として、その大きさにより視野角（FOV）が決定されます。

<img width="400" alt="image.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/c00504a9-9c90-981c-5e12-7245cd85ac73.png">



## 壁との衝突判定
プレーヤーの視線方向を基準に、ウィンドウのX座標に依存する方向でレイを送出します。レイが2Dマップ上の壁（正方形）に当たるまで前進させ、DDA（ディジタル微分解析器）アルゴリズムを使用して壁との当たり判定を行います。DDAは、正方形のグリッド上で線がどの正方形に当たるかを高速に判断します。レイがX軸やY軸の整数座標に到達するたびに壁との接触を確認します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/45d1ff63-9a1b-455a-6c09-0df9614794b1.png)

次に、DDAを用いてプレイヤーと壁までの距離を計算します。下記の図では、side_Dist が壁に当たるまでの距離を示し、delta_dist はレイが1ユニット移動する際にX方向とY方向にそれぞれどれだけ移動するかを示しています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/2b3ac827-ffc3-7b2d-b8b4-8a9df5a998d4.png)

### DDA記法と壁の衝突判定

DDA記法を使用して、レイがマップのどの壁（X軸またはY軸）に当たるかを判定します。以下は、この処理の実装コードです。

```c
static void	set_ray_data(t_ray *ray, t_vars *vars, int x)
{
	double	x_current_cam;

	x_current_cam = 2 * x / (double)WIN_WIDTH - 1;
	ray->x_dir = vars->x_dir + (vars->x_cam_plane
			* x_current_cam);
	ray->y_dir = vars->y_dir + (vars->y_cam_plane
			* x_current_cam);
	ray->x_map = (int)vars->x_pos;
	ray->y_map = (int)vars->y_pos;
	ray->x_side_dist = 0;
	ray->y_side_dist = 0;
	if (ray->x_dir == 0)
	{
		ray->x_delta_dist = 1e30;
	}
	else
		ray->x_delta_dist = abs_double(1 / ray->x_dir);
	if (ray->y_dir == 0)
	{
		ray->y_delta_dist = 1e30;
	}
	else
		ray->y_delta_dist = abs_double(1 / ray->y_dir);
}

```
※解説
このコードは、プレーヤーの位置と視線の方向を基にレイの方向を設定します。レイの各成分が1ブロック進む際に進む距離（x_delta_dist と y_delta_dist）を計算し、それを ray->side_dist に代入しています。レイの方向が0の場合（水平または垂直）、非常に大きな値（1e30）を設定して、その方向には進まないようにしています。




レイの方向ベクトルが (cos(60°), sin(60°)) = (0.5, 0.8660) の場合、レイは60度の角度で射出されます。
```
       /|
    1 / | 
    /   |  0.866
  /     |
/_______|
   0.5
1は単位ベクトルの長さ=斜辺
```

次のコードは、レイが壁に当たるまでの距離を計算するための関数群です。このプロセスは、DDA記法を使用して実装されています。

```c
static bool	is_hit_wall(char **map, t_ray *ray)
{
	if ('0' < map[ray->x_map][ray->y_map]
		&& map[ray->x_map][ray->y_map] <= '9')
	{
		return (true);
	}
	return (false);
}

static int	calculate_step_x_direction(t_ray *ray, t_vars *vars)
{
	if (ray->x_dir < 0)
	{
		ray->x_side_dist = (vars->x_pos - ray->x_map)
			* ray->x_delta_dist;
		return (-1);
	}
	ray->x_side_dist = (ray->x_map + 1.0
			- vars->x_pos) * ray->x_delta_dist;
	return (1);
}

static int	calculate_step_y_direction(t_ray *ray, t_vars *vars)
{
	if (ray->y_dir < 0)
	{
		ray->y_side_dist = (vars->y_pos - ray->y_map)
			* ray->y_delta_dist;
		return (-1);
	}
	ray->y_side_dist = (ray->y_map + 1.0
			- vars->y_pos) * ray->y_delta_dist;
	return (1);
}

// perform DDA
int	get_nearest_axis(t_ray *ray, t_info *info)
{
	int	step_x;
	int	step_y;
	int	axis;

	//始めの整数座標までの値を求め、ray->side_distに代入
	step_x = calculate_step_x_direction(ray, &info->vars);
	step_y = calculate_step_y_direction(ray, &info->vars);
	while (1)
	{
		if (ray->x_side_dist < ray->y_side_dist)
		{
			ray->x_side_dist += ray->x_delta_dist;
			//現在地のrayの次の整数座標までの値を追加する
			ray->x_map += step_x;
			axis = X_AXIS;
		}
		else
		{
			ray->y_side_dist += ray->y_delta_dist;
			ray->y_map += step_y;
			axis = Y_AXIS;
		}
		if (is_hit_wall(info->map.map_data, ray))
			break ;
	}
	return (axis);
}

```
**解説**
関数 calculate_step_x_direction と calculate_step_y_direction は、レイがX軸とY軸のどちらに進むべきか（正方向または負方向）を計算します。これにより、プレイヤーの位置から最初の整数座標までの距離（ベクトルの長さ）を ray->side_dist に代入します。

get_nearest_axis 関数では、これらの side_dist 値を使用してレイが次にヒットするマップの壁を探索します。ここで、X軸とY軸のどちらに進むべきかを決定するために x_side_dist と y_side_dist を比較します。小さい方の値が選ばれ、レイが進むべき方向が決定されたら、side_dist は対応する delta_dist で更新され、レイのマップ上の位置も更新されます。

この関数は、レイが壁に当たるまで（is_hit_wall 関数によって判断される）繰り返されます。これにより、レイが最初に交差する壁までの距離と、その壁がX軸またはY軸のどちらに存在するかが決定されます。



<img width="600" alt="image.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/0d074b7e-6c6b-c7fe-ebe1-ad8065ce7d88.png">




### 壁のテクスチャを東西南北で指定
課題要件の一つである「東西南北でテクスチャを指定できる」機能の実装について説明します。先に示した壁の当たり判定プロセスを利用して、レイが壁に当たった場所がX軸の整数値の場所（東西の壁）なのか、Y軸の整数値の場所（南北の壁）なのかを判断します。

<img width="400" alt="image.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/e4a29937-6da6-bf9a-4c5e-f07db2605005.png">

上記の図では、Y軸の整数値にレイが当たっています。プレイヤーのY位置とレイのY位置の大きさを比較することで、壁が南面か北面のどちらに当たっているかを判断できます。

```c
//壁の東西南北のテクスチャの決定
static int	decide_draw_texture(t_ray *ray, t_vars *vars, int side)
{
	if (side == Y_AXIS)
	{
		if (ray->y_map < vars->y_pos)
		{
			return (NORTH_WALL);
		}
		return (SOUTH_WALL);
	}
	else if (ray->x_map < vars->x_pos)
	{
		return (WEST_WALL);
	}
	return (EAST_WALL);
}
```
解説
この関数では、レイが壁に当たった場所の方位に基づいて、適切なテクスチャを決定します。もしレイがY軸に当たった場合（南北の壁）、プレイヤーの位置とレイの位置を比較して、北面か南面のどちらに当たっているかを判断します。同様に、レイがX軸に当たった場合（東西の壁）、東面か西面に当たっているかを判断します。これにより、東西南北それぞれの壁に異なるテクスチャを適用することが可能になります。

### ヒットした壁のローカル座標を求める
ゲーム内でレイが衝突した壁のX座標（Y軸に関しては考慮しない）を計算します。
```c
static double	get_hit_wall_x(t_draw_wall *wall, t_ray *ray, t_vars *vars)
{
	double	wall_x;

	wall_x = 0.0;
	// 衝突したのが、X軸の整数値の場合
	if (wall->side == X_AXIS)
	{
		wall_x = vars->y_pos + wall->wall_dist
			* ray->y_dir;
	}
	else
	{
		wall_x = vars->x_pos + wall->wall_dist
			* ray->x_dir;
	}
	//計算された壁の座標から整数部分を除き、壁の座標を0.0から1.0の範囲に正規化する。
	//この結果は、テクスチャのどの部分が壁の表面に描画されるべきかを決定するために使用される。
	wall_x -= floor((wall_x));
	return (wall_x);
}
```
このコードでは、レイが壁に衝突した場所のグローバル座標系（マップ全体）を計算し、その後、ローカル座標系（壁の座標系）に変換します。グローバル座標系での wall_x はプレイヤーの位置からレイが衝突点までの距離を考慮して求められます。その後、floor(wall_x) を引くことで、壁の内部的なX座標（0から1の範囲）を得ることができます。

### 描画する壁の大きさ
壁とプレイヤーの距離により壁の描画サイズが変わります。テクスチャのどの部分を描画するかを示す texture->span 変数を設定します。例えば、テクスチャの高さが64ピクセルで壁の高さが128ピクセルの場合、span は0.5となります。これは、壁を1ピクセル表示するたびにテクスチャの current_pos にこの span の値が追加されることを意味します。

テクスチャ画像が64x64ピクセルの場合、span の計算式は次のようになります。
texture->span = 64（テクスチャの高さ） / 描画する壁の高さ

壁がプレイヤーから遠い場合、テクスチャは縮小され、近い場合は拡大されて描画されます。以下の画像は、プレイヤーと壁の距離が異なる場合の壁の描画を示しています。

プレイヤーと壁の距離が1.5ブロックの時
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/1307f04a-c864-c490-3544-4d5e2fa65c81.png)
テクスチャが拡大されて描画される。


プレイヤーと壁の距離が10.5ブロックの時: 
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/45f69088-ddab-4f11-9266-663e7a6ca288.png)
テクスチャが縮小されて描画される。


## 視点移動の実装
### カメラの回転機能
カメラ（視点）の左右回転を制御するための関数群について説明します。これらの関数はキーボードの ←→キー が押された際に呼び出されます。
```c
void	rotate_left_camera(t_vars *vars)
{
	double	x_old_dir;
	double	x_old_plane;

	x_old_dir = vars->x_dir;
	x_old_plane = vars->x_cam_plane;
	vars->x_dir = vars->x_dir * cos(MOVE_DIST)
		- vars->y_dir * sin(MOVE_DIST);
	vars->y_dir = x_old_dir * sin(MOVE_DIST) + vars->y_dir
		* cos(MOVE_DIST);
	vars->x_cam_plane = vars->x_cam_plane * cos(MOVE_DIST)
		- vars->y_cam_plane * sin(MOVE_DIST);
	vars->y_cam_plane = x_old_plane * sin(MOVE_DIST)
		+ vars->y_cam_plane * cos(MOVE_DIST);
}

```
この関数では、2次元の回転行列を使用して視点の移動を実現しています。プレイヤーが回転すると、方向ベクトルとカメラ平面の両方が同時に回転します。これらのベクトルは回転行列により更新され、視点の回転が可能になります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/653fdbc9-20b3-e982-ad06-83dcf2608213.png)

2次元回転行列の詳細な説明は下記の記事に分かりやすく説明されています。

https://www.krrk0.com/two-dimensional-rotationmatrix/

# プレイヤーの移動と壁の衝突判定
`W`,`A`,`S`,`D`キーが押された際のプレイヤーの移動と壁の衝突判定について見ていきます。最初に、`W`キーによる前方への移動について説明します。この移動は次の関数によって実現されます。
```c
void	move_forward(char **map, t_vars *vars)
{
	int		one_forward_x_pos_vec;
	int		one_forward_y_pos_vec;
	char	distination;

	one_forward_x_pos_vec = vars->x_pos + (vars->x_dir * MOVE_DIST);
	one_forward_y_pos_vec = vars->y_pos + (vars->y_dir * MOVE_DIST);
	distination = map[one_forward_x_pos_vec][(int)vars->y_pos];
	if (distination != '1')
		vars->x_pos += vars->x_dir * MOVE_DIST;
	distination = map[(int)vars->x_pos][one_forward_y_pos_vec];
	if (distination != '1')
		vars->y_pos += vars->y_dir * MOVE_DIST;
}
```
この関数では、プレイヤーの移動先の座標を計算し、その座標に壁がない場合に移動を行います。同様の考え方で、後方、右方、左方への移動も実装されます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/265671dc-6120-0287-6fa3-87539d0455cf.png)

右に移動する場合は、進行方向ベクトルを右に90度回転させ、左に移動する場合は左に90度回転させます。これは回転行列を用いて実現されます。

## 壁の当たり判定のバグ
### 初期の壁の当たり判定の問題
当初、移動キーが押された際の壁の当たり判定を実装したところ、壁をすり抜けるバグが発生しました。以下の動画はそのバグの状況を示しています。
<br>
<iframe width="560" height="315" src="https://www.youtube.com/embed/hraUxJ2Vmi4" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>
<br>

変更前のコードは次の通りです。
```c
	int		one_forward_x_pos_vec;
	int		one_forward_y_pos_vec;
	char	distination;

	one_forward_x_pos_vec = vars->x_pos + (vars->x_dir * MOVE_DIST);
	one_forward_y_pos_vec = vars->y_pos + (vars->y_dir * MOVE_DIST);
	distination = map[one_forward_x_pos_vec][one_forward_y_pos_vec];
	if (distination == '1')
		return ;
	else
	{
		vars->x_pos += vars->x_dir * MOVE_DIST;
		vars->y_pos += vars->y_dir * MOVE_DIST;
	}
```
###解決策とその効果
同じ課題を既にクリアした仲間からアドバイスを受け、問題を解決しました。それぞれの成分（xとy）に対して個別に移動先の壁のチェックを行い、壁がない場合のみその成分を移動するようにしました。以下の動画は、この変更後の状況を示しています。

<br>
<iframe width="560" height="315" src="https://www.youtube.com/embed/OVo1wlQQapI" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>
<br>

変更後のコードは次のようになりました。
```c
void	move_forward(char **map, t_vars *vars)
{
	int		one_forward_x_pos_vec;
	int		one_forward_y_pos_vec;
	char	distination;

	one_forward_x_pos_vec = vars->x_pos + (vars->x_dir * MOVE_DIST);
	one_forward_y_pos_vec = vars->y_pos + (vars->y_dir * MOVE_DIST);
	distination = map[one_forward_x_pos_vec][(int)vars->y_pos];
    //この条件式を追加
	if (distination != '1')
		vars->x_pos += vars->x_dir * MOVE_DIST;
	distination = map[(int)vars->x_pos][one_forward_y_pos_vec];
    //この条件式を追加
	if (distination != '1')
		vars->y_pos += vars->y_dir * MOVE_DIST;
}
```
この修正により、移動先の壁をx成分とy成分それぞれで確認し、壁が存在しない場合のみ移動するようになり、バグが解消されました。

# ミニマップ
ミニマップは2つ実装しました。
## corner map
<img width="600" alt="image.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/8d266a0b-9df9-8cf4-076b-7a651304e41b.png">

## central map
<img width="600" alt="image.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/28f3b304-a3dd-e279-1b7d-aeee87f9530b.png">

櫻井さんの動画で紹介されたminimapが非常に良さそうだったので、後からこのマップを追加しました。また、FOVのRayの描画も行いました。
<img width="400" alt="image.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1349017/4d928925-52c7-2388-8fa5-430c59ec6ba4.png">
引用: https://youtu.be/wHc_8DoWa-8

# 感想
製作期間1ヶ月半で無事に終われて良かったです。
42Tokyoに入学する前は、unityでゲーム開発をしていたのもあって、ゲームエンジンの内部構造への理解が深まった気がします。、あっという間の1ヶ月半でした。
42では、プログラミングの基礎をしっかりと理解することを重視しており、前半の課題ではc言語使った様々な再実装系が多く出されます。この前は、bashの再実装をチーム開発で行ったりもしました。

このチーム開発について少し触れてみたいと思います。今回の課題では、中盤までは各自が別々の機能を開発し、問題が発生した際は一緒に考えて課題を解決しました。壁のすり抜け問題では、この記事を書いている最中に見つけ、「Rayで判定」や「プレイヤーの方向より少し傾けたVectorを出力して判定」など、お互いが色々アイデアを出し合いました。チームメイトとは、プログラミングのレベルが同じくらいだったので、片方が一方的に教えるというよりは、互いに学び合う形で進めることができました。お互いに学び合う関係を築くことができ、これが非常に有益な経験になりました。

また、記事を書くのは慣れていなかったため、それなりに大変でした。しかし、コードへの理解を深めるためにも非常に良い経験になり、書いていて楽しむこともできました。これからも、長期のプロジェクトがある際には、その経験を記事にまとめていきたいと考えています。

最後まで読んでいただき、ありがとうございました！！


### リポジトリ

https://github.com/subarunrun0812/42-Cub3D.git

# 参考記事

https://harm-smits.github.io/42docs/projects/cub3d

https://jun-networks.hatenablog.com/entry/2021/03/04/130629

https://www.krrk0.com/two-dimensional-rotationmatrix/