# 2020q3 render
###### tags: `sysprog`
contributed by < `sciyen` >
[repository](https://github.com/sciyen/raycaster) on github

[Toc]

# 遊戲方法
- 按 :arrow_up:/:arrow_down: 前進/後退
- 按 :arrow_left:/:arrow_right: 向左轉/右轉
- 按 `e` 舉槍
- 按 `g` 開啟 God Mode 使出透視眼

# 特殊函數筆記
1. `float modff( float x, float * intptr );` in `math.h` ([Microsoft docs](https://docs.microsoft.com/zh-tw/cpp/c-runtime-library/reference/modf-modff-modfl?view=msvc-160))
Splits a floating-point value into **fractional** and **integer** parts.
- This function **returns the signed fractional portion of x**. There's *no error return*.
- Example:

    x = -14.87654321;      /* Divide x into its fractional */
   y = modf( x, &n );     /* and integer parts            */
   result: y = -0.876543, n = -14

# 程式原理分析
## Overview
### Map
從 `IsWall()` 中可以推敲出與地圖 `g_map` 有關的資訊：
- 地圖 `g_map` 定義在 `raycaster_data.h` 中，為 `uint8_t` 1d array with 32*4 elements.
- A bit as a pixel.
- 大小為正方形 (32x32) pixel, 四個 `uint8_t` element 為一個 X axis ，共分成 32 rows, that is, Y axis.

如果按照二維方向排列應該長這樣：

0b00000000, 0b00000000, 0b00000000, 0b00000000, 
0b00000000, 0b00000000, 0b00000000, 0b00000000, 
...
0b00000000, 0b00000000, 0b00000000, 0b00000000, 

橫向 32 bit，縱向 32 rows.

#### 圖片大小的線索：
`raycaster_float.cpp` line: 15

if (tileX < 0 || tileY < 0 || tileX >= MAP_X - 1 || tileY >= MAP_Y - 1) {
    return true;
}

- 可以知道當 `tileX` 小於 `0` 或超過 `MAP_X-1` 時，即算是出界，因此 X 軸邊界最大值為 `MAP_X` ，其值為 32 ， Y axis 同理。

`raycaster_float.cpp` line: 18

return g_map[(tileX >> 3) + (tileY << (MAP_XS - 3))] &
       (1 << (8 - (tileX & 0x7)));

- 此段程式碼用於判斷座標 (`tileX`, `tileY`) 是否為障礙物，由於 `g_map` 中，每個 element 為 `uint8_t` ，因此每個 element 可以代表 8 個 pixel ，$8=2^3$ ，因此 `tileX` 需除 8 ，也就是 `>> 3` 。
- `g_map` 是 1d array ，因此要計算 Y 方向應除掉 X 方向的長度， X 方向共包含 32 個 bit ($32=2^5$) ，但是一個 element 可以代表 8 個 bit ，因此，應除 $32/8=4$ 或 `>> 4`。
- `MAP_XS` 的意義為地圖大小的 2 指數，即 `2^5=32` ，其中 32 為 `MAP_X` ，`MAP_XS` 為指數部分。
- 第 18 行用來取 X axis 的 bit ，需注意的是，地圖中 LSB 為 X 正向， MSB 為 X 反向，與數值大小方向相反。取 7 的原因為，一個 element 可以代表 8 個 bit，這 8 個 bit 恰好是 X 座標的 3 個 LSBs 因此取 3 個 LSB 全為 1 的情況，即為 `0x7`。
:::warning
這邊的 `8-(tileX & 0x7)` 應該錯了，考慮 `tileX` 最大即最小情況：
- 最小 `tileX` =0 時，`8-0=8`：1<<8，會超過 uint8_t 的範圍
- 最大 `tileX` =7 時，`8-7=1`：1<<1=2，發現永遠沒有 1 的情況

因此應該將 8 修正為 7。
:::

修正後就會發現消失的牆壁回來了！

:::success
#### 更有彈性的寫法：
若地圖改以其他變數型態表示時，可以這樣設定：假設用 `uint32_t` 由於 32 為 $2^5$ 因此只要設定 `MAP_ELEMENT_SIZE` 為 5 就可以不用修改 `IsWall()` 內部的程式碼。

#define MAP_ELEMENT_SIZE 5    // 2^5 = 32
#define MAP_X (uint8_t)(1 << MAP_XS)
#define MAP_ELEMENT_MASK ((1 << MAP_ELEMENT_SIZE) - 1)
...
const uint32_t g_map[] = {
    0b00000000000000000000000000000000,
    ...
}
...
bool IsWall(...){
    ...
    return g_map[(tileX >> MAP_ELEMENT_SIZE) + (tileY << (MAP_XS - MAP_ELEMENT_SIZE))] &
       (1 << (MAP_ELEMENT_MASK - (tileX & MAP_ELEMENT_MASK)));
}

:::

### Texture
在程式碼中， texture 以 `uint8_t` 的陣列儲存，而大小是 `64x64` 的方塊，因此 $(2^6)^2 = 2^{12}=4096$。

線索：
`raycaster_data.h`中， `g_texture8` 的定義：

const uint8_t LOOKUP_TBL g_texture8[4096];

`renderer.cpp`中，對每個 texture 元素的存取：

auto tv = g_texture8[(ty << 6) + tx];

### Coordinate System
與一般數學上熟悉的角度定義不同，在遊戲中定義視角方向為 Y 方向，向視野右邊角度為正，向視野左邊角度為負。
<center><img src="https://i.imgur.com/lYkLG6w.png" style="width: 300px"></center>
<center>Fig. Gaming coordinate system</center>

一般來說，求 X 方向應該使用 $cos$ ，Y 方向使用 $sin$ 但在這邊會相反，可以在 `game.cpp` 中找到線索：

`game.cpp` line: 8

playerX += 0.5f * m * sin(playerA) * seconds * 5.0f;
playerY += 0.5f * m * cos(playerA) * seconds * 5.0f;

此外，在 `Distance()` 中也有類似的實作，將 `tileStep` 定義為如下的 vector：
<center><img src="https://i.imgur.com/5CM2HML.png" style="width: 300px"></center>
<center>Fig. Gaming coordinate system</center>

可以發現這邊重新定義的 unit vector 是以 $\theta$ 與 Y 軸夾角的情況下，投影在原本 X-Y 軸座標系下的單位向量。

`game.cpp` line: 42

int tileStepX = 1;
if (rayA > M_PI) {
    tileStepX = -1;
}

int tileStepY = 1;
if (rayA > M_PI_2 && rayA < 3 * M_PI_2) {
    tileStepY = -1;
}

# Raycasting Procedures
#### Assumption:
1. 視角僅可能為畫面中間，如此一來計算就只需要計算 `SCREEN_WIDTH` 次 `Distance()` (只要在畫面水平中線掃一次)

#### Procedures
- Trace Frame(`renderer.cpp`)
計算出畫面 (frame) 上每個 pixel 的顏色 (`GetARGB`) ，實際上，由於畫面上下對稱，因此只計算畫面水平中線，再往上下方向用 `Trace()` 計算畫面中的障礙物高度。
- Trace(`raycaster_float.cpp`, `raycaster_fixed.cpp`)
計算撞到的 Wall 在目前視角下的障礙物資訊，包含 texture、該視角障礙物高度等資訊。
- Distance

### TraceFrame()
對整個畫面 render ，沿著 X 方向執行 `trace()` :
<center><img src="https://i.imgur.com/r1F0Y3z.png" style="width: 300px"></center>
<center>Fig. Frame tracing direction</center>

障礙物在畫面中分成兩種情況:
- 障礙物高度低於畫面高度
<center><img src="https://i.imgur.com/CmzUBFX.png" style="width: 400px"></center>
<center>Fig. Field Of View</center>
- 障礙物高度超過畫面高度
<center><img src="https://i.imgur.com/MiRruGZ.png" style="width: 400px"></center>
<center>Fig. Field Of View</center>

因此要畫出畫面中特定 X 座標的障礙物我們需要以下資訊:
- screenY: 障礙物在畫面中最高位置的 y 像素
- textureY0: 障礙物開始 render 的 texture 起始位置(再來只要一直往正 Y 方向 render 就好)
- textureStep: 每在畫面中移動一個像素時， texture 的 Y 座標的變動值。

### Trace()
#### ==Function Objective==
計算給定的螢幕 X 的位置，撞到的 Wall 在目前視角下的畫面 ( Y 座標、材質等資訊)
- input:
- screenX: 往此畫面 X 座標看過去，此函式將回傳該點 Y 軸成像。
- output:
- screenY: 障礙物在視野中的 Y 軸高度(最高點)。
- textureNo: 障礙物的 ID。
- textureX: 看到的障礙物 texture X axis index(最高點)。
- textureY: 看到的障礙物 texture Y axis index(最高點)。
- textureStep: 隨著畫面 Y 軸往下移動一個像素，在 texture Y index 中移動的距離。

<center><img src="https://i.imgur.com/iduRPAm.png" style="width: 400px"></center>
<center>Fig. View window</center>

其中，特定 `screenX` 相對於畫面中心的角度差 $\Delta\theta$ 可以表示為：
$$
\Delta\theta = acrtan(\frac{ViewOffsetX}{View Window Distance}) = arctan(\frac{screenX-\frac{screenWidth}{2}}{\frac{screenWidth}{2}\frac{\tau_{max}}{2}})
$$

- 其中，$\tau_{max}$ 可以限制可視範圍，$screenX$ 為 0 時為最左側；$screenX$ 為 $\frac{screenWidth}{2}$ 時為最右側。
$$
\Delta\theta_{max}=acrtan(\frac{\pm2}{\tau_{max}}) \approx \pm51.8^{\circ}
$$
- $D_v$: View Window Distance 為視野畫面 (ViewWindow) 與 player (Origin) 的距離
:::success
#### 設定 Field Of View (FOV)
如果要讓視角的定義更直覺，應該設定 FOV 視角：

#define FOV_X (M_PI / 2)

`raycaster_float.cpp`

float deltaAngle = atanf(((int16_t) screenX - SCREEN_WIDTH / 2.0f) /
                             (SCREEN_WIDTH / (2.0f * tanf(FOV_X / 2.0f))));

如此一來
$$
\Delta\theta_{max}=acrtan(tan(\pm\frac{FOV_X}{2})) = \pm\frac{FOV_X}{2}
$$
$$
D_v = \frac{screenWidth}{2tan(\frac{FOV_X}{2})}
$$

重新定義的 FOV 如下圖：
- 綠線為水平 (X) 方向視角極限
- 藍線為垂直 (Y) 方向視角極限

<center><img src="https://i.imgur.com/IJhs2Qf.png" style="width: 300px"></center>
<center>Fig. Field Of View</center>

45 度:
90 度:
120 度:

:::

#### ==計算畫面中障礙物的高度==
<center><img src="https://i.imgur.com/ytddUtx.png" style="width: 300px"></center>
<center>Fig. Gaming coordinate system</center>

利用相似三角形，可以做以下推論
$$
\frac{\frac{screenY}{2}}{D_v}=\frac{\frac{WallHeight}{2}}{distance},\\ i.e. \ screenY=\frac{WallHeight \times D_v}{distance}=\frac{WallHeight \times screenWidth}{4 \times distance \times tan(\frac{FOV_X}{2})}
$$
:::success
為配合前面 FOV 的定義，可以做如下改寫：
將原本程式碼中的 `INV_FACTOR` 重新定義為

#define WALL_HEIGHT 1.0f
#define INV_FACTOR \
    (float) (WALL_HEIGHT * SCREEN_WIDTH  / (4.0f * tanf(FOV_X / 2)))

:::

#### ==texture rendering==
由於這個地圖中的障礙物都是 1x1 的方塊，要把 texture 貼到方塊上只要知道方塊上任意點的 x-y 座標，就可以計算出相應的 texture 。

求出 Wall 在視野內的高度 (`screenY`) 後，就得到視野內的方塊 x-y 資訊，這邊使用定點數表示 x-y 座標：
- Tecture X 方向:
在這個遊戲中因為視野不會傾斜，因此 y 方向皆為垂直線條， texture 的 X 座標隨螢幕的 X 座標成比例關係：
$$
x = TextureSize \times HitOffsetRatio
$$
`raycaster_float.cpp`

    *textureX = (uint8_t)(256.0f * modff(hitOffset, &dum));

**Note**: `textureSize` 為 $2^6=32$ ， 2 bits fixed point，因此 $2^{6+2}=256$
`renderer.cpp`

    const auto tx = static_cast<int>(tc >> 2);

先把界於 `0~1` 的 `hitOffset` 對應到 `uint8_t` 能夠表示的最大範圍後 (`textureX`) ， 在 `renderer.cpp` 再轉換到 texture 相對應的 size 。因為 texture size 為 $2^6=64$，`uint8_t` size 為 $2^8$ ，因此需要右移 $(8-2)=2$ ，相當於使用 2 bits 定點數。
:::info
這邊 X 方向使用 2 bits 定點數即可，是因為視野不會傾斜，不會對成像造成明顯影響。
:::
- Texture Y 方向，使用 10 bits fixed point:
目標為找出畫面上特定 Y 座標點對應的 texture 座標，因此可以看作兩個座標空間的轉換，這邊記作 ${Screen Coordinate}\to{Texture Coordinate}$：

將 texture 看作一線性變換：
$$
textureY^*=textureY_0+y\frac{TextureSize-2\times textureY_0}{WallHeight}
$$
$textureY_0$: texture 的起始座標。
$TextureSize$: texture 的圖片大小。
$WallHeight$: 視野中牆壁的高度，也就是 $2\times screenY$。若牆高超過視野高度，則 $WallHeight=ScreenHeight$

$$
textureY_0=TextureSize\frac{(ProjectHeight-ScreenHeight)/2}{ProjectHeight}
$$
$ProjectHeight$: 投影在成像平面上的牆壁高度。
這邊有兩種狀況:
- 牆壁高度沒有超過視野高度: $WallHeight=2 \times screenY \leq ScreenHeight$
由於牆壁會完全畫出來，因此 texture 從 0 開始畫，即 $textureY_0=0$。
$$
textureY^* = 0 + y \frac{TextureSize}{WallHeight}
$$
$y$ 為畫面取樣時的 y 座標，其範圍應為 $0\leq y\lt WallHeight$。
- 牆壁高度超過視野高度: $2 \times screenY \geq ScreenHeight = WallHeight$
從視野中只能看到部分牆壁，因此最高處從 $textureY_0$ 開始。

:::success
#### 原程式碼中的運算缺失
##### screenY overflow
可以發現，出現異常的地方總是在牆壁高度過高的時候(相較於左側視野範圍內，較低的牆壁高度總是沒有異常)

在原本程式碼中，並未判斷 `screenY` 是否超過 `screenHeight` 也未對超過的情況做處理。此外，在 $screenY$ 的計算中，原本的程式碼是以 `uint8_t` 的整數去接收 `INV_FACTOR / distance` 因此若牆壁高度的計算結果超過 255 ，便會導致 $screenY$ overflow。

`raycaster_float.cpp` 原程式碼:

*screenY = INV_FACTOR / distance;
auto txs = (*screenY * 2.0f);
if (txs != 0) {
    *textureStep = (256 / txs) * 256;
    if (txs > SCREEN_HEIGHT) {
        auto wallHeight = (txs - SCREEN_HEIGHT) / 2;
        *textureY = wallHeight * (256 / txs) * 256;
    }
}

##### 鋸齒畫面
此外，由於原本的做法是用 `textureStep(ts)` 做累加，在 Y 方向累加的同時，浮點誤差也會跟著變大導致畫面下半部型成鋸齒狀：

`renderer.cpp` 原程式碼:

auto ty = static_cast<int>(to >> 10);
auto tv = g_texture8[(ty << 6) + tx];

to += ts;

<center><img src="https://i.imgur.com/48cvuy1.png" style="width: 500px"></center>
<center>Fig. Fixed point 產生的鋸齒畫面</center>

#### 修正
利用前述的方式計算 `textureY` ，先在 `raycaster_float.cpp` 中判斷 $WallHeight$ ，若成像的高度大於畫面範圍 $ScreenHeight$，則再計算對應的 $textureY$
`raycaster_float.cpp` 改為:

auto txs = 2.0f * INV_FACTOR / distance;
if (txs > SCREEN_HEIGHT){
    *screenY = SCREEN_HEIGHT / 2;
    *textureY = static_cast<uint16_t>(TEXTURE_SIZE * (txs - SCREEN_HEIGHT) 
                                                / 2 / txs * (1 << 10));
}
else
    *screenY = txs / 2;

`renderer.cpp` 改為:

uint16_t ty = (tso + (((TEXTURE_SIZE / 2) << 10) - tso) 
                                    * y / sso) >> 10;

由於程式碼中使用 10 bits 定點數，因此 `textureY` 在運算開始前先乘 `(1 << 10)` ，並且在計算 $textureY^*$ 最後再右移 10。
<center><img src="https://i.imgur.com/CpyREFv.png" style="width: 500px"></center>
<center>Fig. Fixed point 修正後的畫面</center>

:::

#### ==消除魚眼==
當距離太近的時候，會產生如下的魚眼效果：
<center>Fig. Fisheye effect</center>

未校正前的影像是投影在「成像平面」上(見下圖)，產生 $M$ 點，可以發現，相較於投影在「投影球面」上的 $P$ 點
- 投影在成像平面上有**更寬闊的視野範圍**，但是會造成**失真**，因為成像位置與觀測位置每點的距離都不太一樣，越靠近左右成像距離越長。

要修正魚眼效果要修正成像距離，使其成像在「投影球面」上，因此：
$$
Distance=LineDistance\times tan(\Delta \theta)
$$
<center><img src="https://i.imgur.com/gF04T1T.png" style="width: 400px"></center>
<center>Fig. Fisheye effect compensation</center>

:::info
在程式碼中， $LineDistance$ 指的是 **物體** 至 **玩家** 的距離，而在這邊修正魚眼指的是 **成像平面投影點** 至 **觀測點** 的距離，但是由於 $screenY$ 的 [**計算**](https://hackmd.io/SgFjqgnWSpOWUrJRK1-16w?both#%E8%A8%88%E7%AE%97%E7%95%AB%E9%9D%A2%E4%B8%AD%E9%9A%9C%E7%A4%99%E7%89%A9%E7%9A%84%E9%AB%98%E5%BA%A6) 是線性的，因此先乘和後乘 $tan()$ 是等效的；$Distance$ 以此類推。
:::
:::success
#### 魚眼修正的加速
由魚眼校正的計算可以發現，每個 $\Delta \theta$ 、 $tan(\Delta\theta)$ 對於 $X$ 皆是 1 對 1 的對應關係，因此可以建立對應的 table 做查表，以節省計算。
:::

## raycaster_float.cpp
### Distance()
#### Function Objective
Find the distance to obstacles from current player's position and facing direction (ray).

- hitOffset: 用於計算 texture 的 X offset，為撞到 wall 的該點與 player 的距離，其方向依據撞到的是 X 方向或 Y 方向有關。
- hitDirection: 表示撞到的是 X 方向或 Y 方向。

為了判斷從 player 射出的 ray 最先碰撞到的障礙物，這邊先計算 X、Y 方向的 `startDelta` ，其意義為分別從 X 及 Y 方向出發，最先遇到的網格 (grid) 距離，接下來因為 grid 皆為單位大小，因此只要計算經過幾個 grid 就好。

整理在各個象限時的情況:

1. $0 \leq \theta < \frac{\pi}{2}$，$tan(\theta)>0$
<center><img src="https://i.imgur.com/S2qILq2.png" style="width: 300px"></center>

$$
\left\{
\begin{array}{lr}
startDeltaX=(1-offsetY)tan(\theta) \\
startDeltaY=\frac{1-offsetX}{tan(\theta)}
\end{array}
\right.
$$

2. $\frac{\pi}{2} \leq \theta < \pi$，$tan(\theta)<0$
<center><img src="https://i.imgur.com/lV9PFKf.png" style="width: 300px"></center>

$$
\left\{
\begin{array}{lr}
startDeltaX=offsetY \times (-tan(\theta)) \\
startDeltaY=\frac{1-offsetX}{tan(\theta)}
\end{array}
\right.
$$

3. $\pi \leq \theta < \frac{3\pi}{2}$，$tan(\theta)>0$
<center><img src="https://i.imgur.com/R2ckrO3.png" style="width: 300px"></center>

$$
\left\{
\begin{array}{lr}
startDeltaX=offsetY \times (-tan(\theta)) \\
startDeltaY=\frac{offsetX}{-tan(\theta)}
\end{array}
\right.
$$

4. $\frac{3\pi}{2} \leq \theta < 2\pi$，$tan(\theta)<0$
<center><img src="https://i.imgur.com/BhS8RH4.png" style="width: 300px"></center>

$$
\left\{
\begin{array}{lr}
startDeltaX=(1-offsetY)(-tan(\theta)) \\
startDeltaY=\frac{offsetX}{-tan(\theta)}
\end{array}
\right.
$$

:::success
#### Simplifying the calculation of startDelta
這邊發現一個很有趣的現象，如果將 $tan(\theta)$ 前的正負號提出來，恰好為 X、Y 象限的單位向量，因此可以將原本的計算改為
$$
\left\{
\begin{array}{lr}
startDeltaX = vecX \times tan(\theta) \times correctY \\
startDeltaY = vecY \times \frac{1}{tan(\theta)} \times correctX
\end{array}
\right.
$$
修正項與 X、Y 象限單位向量的關係為 $(correctY, correctX)=(unitX, unitY)$ ，這邊 X、Y 恰好相反。

<center><img src="https://i.imgur.com/5CM2HML.png" style="width: 300px"></center>
<center>Fig. Unit vector</center>

而 $(vecX, vecY)$ 則與象限有關，可以整理成下表

||$0 \leq \theta < \pi$|$\pi \leq \theta < 2\pi$|
|-|-|-|
|$vecY$|$1-offsetX$|$offsetX$|
|$unitX$|$1$|$-1$|

||$\frac{\pi}{2} \leq \theta < \frac{3\pi}{2}$|$0 \leq \theta < \frac{\pi}{2}$&&$\frac{3\pi}{2} \leq \theta < 2\pi$|
|-|-|-|
|$vecX$|$offsetY$|$1-offsetY$|
|$unitY$|$-1$|$1$|

如此一來可以大幅簡化原本 `startDelta` 的計算，也減少許多 if-else 的判斷次數

修改過的 `raycaster_float.cpp`:

float vecX = 1 - offsetY;  // The case that 3pi/2 ~ pi/2
float vecY = 1 - offsetX;  // The case that 0 ~ pi
int tileStepX = 1;         // The case that 0 ~ pi
int tileStepY = 1;         // The case that 3pi/2 ~ pi/2

// Generate directional unit vector according to player angle
if (rayA > M_PI) {
    tileStepX = -1;
    vecY = (offsetX == 0) ? 1 : offsetX;
}
if (rayA > M_PI_2 && rayA < 3 * M_PI_2) {
    tileStepY = -1;
    vecX = (offsetY == 0) ? 1 : offsetY;
}

// Calculate the starting delta
float startDeltaX = vecX * tan(rayA) * tileStepY;
float startDeltaY = vecY / tan(rayA) * tileStepX;

再來測量修改後的加速情形，以下資料取樣自進入遊戲後不動的情況下， 14.8 秒間共 74 筆數據 (每 0.2 秒一筆)的平均結果，時間計算方法請參考 [Performance Estimation](https://hackmd.io/SgFjqgnWSpOWUrJRK1-16w?both#Performance-Estimation) 實驗 [詳細資料](https://docs.google.com/spreadsheets/d/1ADTBi5f8Ap-Z2bWFIqjCS75Kltma4PXpWCXGmZTwI3s/edit#gid=0&range=A1:M81)

|實驗|fixed point(ms)|float point(ms)|diff(ms)|FPS(frame/sec)|
|:-:|:-:|:-:|:-:|:-:|
|Old|0.308|0.344|0.036|323.410|
|Old|0.293|0.330|0.037|407.674|
|New|0.263|0.289|0.026|286.609|
|New|0.285|0.325|0.040|401.003|

可以發現使用簡化後的 float point 平均來說比原本方法快一點，但是沒有很明顯。
:::

接下來要找與障礙物的碰撞點，這邊用 $0 \leq \theta \leq \frac{\pi}{2}$ 舉例：
<center><img src="https://i.imgur.com/phXx11b.png" style="width: 400px"></center>

以 $intercept$ 為起點
$$
\left\{
\begin{array}{lr}
interceptX&=rayX + startDeltaX \\
interceptY&=rayY + startDeltaY
\end{array}
\right.
$$

發射出的向量會以相同的方向，但以不同的大小前進，因此分成以下兩種可能:
- 撞到橫軸，即為綠色點，其 Y 座標為整數
$$
hitPos=(interceptX, tileY) \\
moveVec=(|tan(\theta)|sgn(unitX), 1\cdot sgn(unitY))
$$
- 撞到縱軸，即為紅色點，其 X 座標為整數
$$
hitPos=(tileX, interceptY) \\
moveVec=(1\cdot sgn(unitY), \frac{1}{|tan(\theta)|}sgn(unitX))
$$

因此，所有的碰撞點可以表示成如下:
$$
hitPos^*=hitPos + n \times moveVec, \quad n \in \mathbb{Z}
$$
<center><img src="https://i.imgur.com/Ict6Ezp.png" style="width: 500px"></center>
<center>Fig. Collision points</center>

如此一來只要重複比對是哪一個碰撞點最先撞到即可。
- 紅色: $tileY+1<interceptY$ 只要這個條件還滿足，表示下一個紅色仍然在綠色的範圍內，因此，下一個點仍然是紅色。
- 如果撞到牆壁一定是 Y 方向的面。

    while (((tileStepY == 1 && (interceptY <= tileY + 1)) ||
        (tileStepY == -1 && (interceptY >= tileY)))) {
        somethingDone = true;
        tileX += tileStepX;
        if (IsWall(tileX, interceptY)) {
            verticalHit = true;
            rayX = tileX + (tileStepX == -1 ? 1 : 0);
            rayY = interceptY;
            *hitOffset = interceptY;
            *hitDirection = true;
            break;
        }
        interceptY += stepY;
    }

- 綠色: $tileX+1<interceptX$ 只要這個條件還滿足，表示下一個綠色仍然在紅色的範圍內，因此，下一個點仍然是綠色。
- 如果撞到牆壁一定是 X 方向的面。

    while (!verticalHit && ((tileStepX == 1 && (interceptX <= tileX + 1)) ||
                                (tileStepX == -1 && (interceptX >= tileX)))) {
        somethingDone = true;
        tileY += tileStepY;
        if (IsWall(interceptX, tileY)) {
            horizontalHit = true;
            rayX = interceptX;
            *hitOffset = interceptX;
            *hitDirection = 0;
            rayY = tileY + (tileStepY == -1 ? 1 : 0);
            break;
        }
        interceptX += stepX;
    }

藉由重複以上兩個判斷，除非撞到牆壁，否則交替會一直延續。在這個地圖中一定會撞到某個點，因為在 `IsWall()` 中有設定邊界，撞到範圍外一定會停止。

為了防止形成無窮迴圈，這邊用一個變數 `somethingDone` 判斷射線是否仍在前進，否則就回傳 0 跳出迴圈。

# Fixed point implementation

## 定點數運算
### 數字系統
#### angle
在 fixed point 實作中，是以 8 bits 表示一個 $\frac{\pi}{2}$，可以在 `precalculator.cpp` 中找到線索:
`precalculator.cpp` line: 45

int16_t da = static_cast<int16_t>(deltaAngle / M_PI_2 * 256.0f);

也就是說，新變數 `da`
$$
da=deltaAngle \times \frac{256}{\frac{\pi}{2}}
$$
因此，若要判斷 `angle` 所在象限 (有多少個 $\frac{\pi}{2}$ )，只要取 `angle >> 8` 即可；而 `angle % 256` 則為佔 $\frac{\pi}{2}$ 的比例。例如:
`raycaster_fixed.cpp` line:101

const uint8_t quarter = rayA >> 8;
const uint8_t angle = rayA % 256;

注意: 和一般數學慣例不一樣的是，這邊的 `quarter` 是從第 0 象限開始。

#### 角度表示範圍與誤差
數學中 $tan(\theta)$ 與 $cot(\theta)$ 存在極端值 (當 $tan(\pi/2)$ 時為無窮大)，也就是會出現 `uint16_t` 無法表示的範圍。

##### 極值
$tan(\theta)$ 的極值出現在最靠近 $\frac{\pi}{2} + n \pi$ 的地方，其中 $n$ 為整數。

##### 誤差
由於電腦數值系統中，僅能以有限數量的位元儲存數字，因此對於像是 $tan()$ 這種無理數，僅能近似其數值，而近似結果與實際數字的差距就定義為誤差。
$$
Error(\theta_a) = tan_a(\theta_a) - tan(\theta)
$$
- $\theta_a$ 為在該數值表示方法下近似的 $\theta$ 為離散值。
- $\tan_a()$ 為選用的 $tan()$ 近似算法 為離散的 one to one mapping
- $\theta$ 及 $tan()$ 為連續值

<center><img src="https://i.imgur.com/cQRBi3K.png" style="width:500px"></center>
<center>Fig: Error of tan</center>

由於 $tan(\theta)$ 的微分為 $\frac{1}{sec^2(\theta)}$ ，其在 $0\leq\theta<\frac{\pi}{2}$ 的範圍內為嚴格遞增函數，可以得到 $abs(E_L(\theta)) < E_H(\theta) < \Omega(\theta)$ ，並且， $\theta$ 越接近 $\frac{\pi}{2}$， $\Omega(\theta)$ 越大。

<center><img src="https://i.imgur.com/CGLBhAT.png" style="width:400px"></center>
<center>Fig: 1/sec^2()</center>

##### 討論與比較
- 假設 $\theta$ 為 8 bits 定點數
- 極值: 在 $\theta$ 最接近 $\frac{\pi}{2}$ 時，也就是 $\theta=\frac{\pi}{2} \frac{255}{256}$ ，`tan` 有最大值 $tan(\frac{\pi}{2} \frac{255}{256}) = 162.937$。
- 最大誤差: $\tan(\frac{\pi}{2} \frac{255}{256}) - \tan(\frac{\pi}{2} \frac{254}{256}) = 81.489$。
- 假設 $\theta$ 為 10 bits 定點數
- 極值: 在 $\theta$ 最接近 $\frac{\pi}{2}$ 時，也就是 $\theta=\frac{\pi}{2} \frac{1023}{1024}$ ，`tan` 有最大值 $tan(\frac{\pi}{2} \frac{1023}{1024}) = 651.335$。
- 最大誤差: $\tan(\frac{\pi}{2} \frac{1023}{1024}) - \tan(\frac{\pi}{2} \frac{1022}{1024}) = 325.950$。
- 但是如果在 $\frac{\pi}{2} \frac{255}{256}$ 的誤差則為 $\tan(\frac{\pi}{2} \frac{1020}{1024}) - \tan(\frac{\pi}{2} \frac{1019}{1024}) = 32.595$

可以發現，使用 10 bits fixed point 的約比 8 bits fixed point 少 $60.0\%$ 的誤差。

### 無號乘法 `MulU()`
這是一個將 8 bits 整數 `v` 乘以 8 bits **無號**定點數 `f` 的運算，回傳的是四捨五入過後的 16 bits 無號整數。

uint16_t RayCasterFixed::MulU(uint8_t v, uint16_t f)
{
    const uint8_t f_h = f >> 8;
    const uint8_t f_l = f % 256;
    const uint16_t hm = v * f_h;
    const uint16_t lm = v * f_l;
    return hm + (lm >> 8);
}

Example:

v:  0000 0011 |
f:  0000 0001 | 0000 1000
fh: 0000 0001    -> higher bits
fl: 0000 1000    -> lower bits
hm: 0000 0011
lm: 0001 1000
re: 0000 0011

若 `lm` 小於 256 表示 `v * f` 的小數部分不超過 1 無法進位，因此會在 `lm >> 8` 的時候捨去。

### 有號乘法 `MulS()`
這是一個將 8 bits 整數 `v` 乘以 8 bits **有號**定點數 `f` 的運算，回傳的是四捨五入過後的 16 bits 有號整數。

int16_t RayCasterFixed::MulS(uint8_t v, int16_t f)
{
    const uint16_t uf = MulU(v, static_cast<uint16_t>(ABS(f)));
    if (f < 0) {
        return ~uf;
    }
    return uf;
}

這邊如果 f 小於 0 ，最後會做一個 not 運算變成 `1 補數`。
:::warning
Q: 為什麼不是用 `2 補數`?
:::

### `AbsTan()`
利用 $tan()$ 的對稱關係，可以用映射的方式得到不同象限的函數值。

<center><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/c/c1/Tan_proportional.svg/1200px-Tan_proportional.svg.png" style="width: 300px"></center>
<center>Fig. function of tan (wikimedia)</center>

如此一來，可以做個歸納: (這邊的象限定義使用前述的 [數字系統](#%E6%95%B8%E5%AD%97%E7%B3%BB%E7%B5%B1)，以第 0 象限作為開始)
- 第 1 象限: 垂直水平映射
- 第 2 象限: 不變
- 第 3 象限: 垂直水平映射

但是，`AbsTan()` 只需要做垂直映射，因此:

inline int16_t RayCasterFixed::AbsTan(uint8_t quarter,
                                      uint8_t angle,
                                      const uint16_t *lookupTable)
{
    if (quarter & 1) {
        return LOOKUP16(lookupTable, INVERT(angle));
    }
    return LOOKUP16(lookupTable, angle);
}

:::info
#### invert
這邊垂直映射是利用

#define INVERT(x) (uint8_t)((x ^ 255) + 1)

也就是說，利用 $a + b = 256$ 的關係，找出對稱的 index

000 -> 000
001 -> 255
254 -> 002
255 -> 001

:::

### 乘 `MulTan()`
這個 function 用查表的方式快速計算 $value \times tan(angle)$ 或是 $value \times cot(angle)$

由 $tan()$ 與 $cot()$ 的關係:
$$
tan(-\theta+\frac{\pi}{2})=\frac{sin(-\theta+\frac{\pi}{2})}{cos(-\theta+\frac{\pi}{2})}=\frac{-cos(-\theta)}{sin(-\theta)}=cot(\theta)
$$
可以發現 $tan()$ 和 $cot()$ 的關係其實是將 $tan()$ 取垂直映射後，右(左)移 $\frac{\pi}{2}$:
<center><img src="https://mathbitsnotebook.com/Algebra2/TrigGraphs/otherg97.gif" style="width: 300px"></center>
<center>Fig. function of cot (https://mathbitsnotebook.com/Algebra2/TrigGraphs/TGtanSecCscCot.html)</center>

而實際上，可以藉由對 $\frac{\pi}{4}$ 映射得到。

如此一來，可以做個歸納: (這邊的象限 `quarter` 定義使用前述的 [數字系統](#%E6%95%B8%E5%AD%97%E7%B3%BB%E7%B5%B1)，以第 0 象限作為開始)
- 需要左右映射的:
- $tan()$: 1、3 象限
- $cot()$: 0、2 象限
- 需要上下映射的 (負號):
- $tan()$: 1、3 象限
- $cot()$: 1、3 象限

也就是

uint8_t signedValue = value;
if (inverse) {
    if (value == 0) {
        if (quarter % 2 == 1) {
            return -AbsTan(quarter, angle, lookupTable);    // cot 上下映射
        }
        return AbsTan(quarter, angle, lookupTable);
    }
    signedValue = INVERT(value);
}
if (signedValue == 0) {
    return 0;
}
if (quarter % 2 == 1) {
    return -MulU(signedValue, LOOKUP16(lookupTable, INVERT(angle))); // cot 上下映射
}
return MulU(signedValue, LOOKUP16(lookupTable, angle));

### `CalculateDistance()`
這邊的 `CalculateDistance()` 與 `raycaster_float.cpp` 中的 `Distance()` 很像，不一樣的是
1. `CalculateDistance()` 中的 `tan()` 計算改以查表的方式進行。
2. 對於 `angle` 等於 0 的特例做了最佳化。
3. 使用 `goto` 的技巧簡化在 `angle == 0` 與 `angle != 0` 的情況中，計算 texture 的重複性程式碼。

# New Features

## Performance Estimation

利用 SDL2.0 的 API ，可以計算 High resolution 的 performance.
- `SDL_GetPerformanceCounter()`
Returns the current counter value.
- `SDL_GetPerformanceFrequency()`
Returns a platform-specific count per second.

為了分別計算 fixed point performance、float point performance、FPS 這三種指標，利用 counter 為其計時：
`main.cpp`:

const auto renderFloatTickStart = SDL_GetPerformanceCounter();
floatRenderer.TraceFrame(&game, floatBuffer);
const auto renderFloatTickEnd = SDL_GetPerformanceCounter();
const auto floatRenderSeconds = (renderFloatTickEnd - renderFloatTickStart) /
                     static_cast<float>(tickFrequency);

#### Exponential Filter
由於計算速度很快，容易產生許多高頻雜訊，所以引入 [Exponential Filter](https://gregstanleyandassociates.com/whitepapers/FaultDiagnosis/Filtering/Exponential-Filter/exponential-filter.htm)

$$
y(k) = a*y(k-1) + (1-a)*x(k)
$$
where
- $x(k)$ is the raw input at time step $k$
- $y(k)$ is the filtered output at time step $k$
- $a$ is called the `smoothing constant`, normally between 0.8 ~ 0.99

這邊 $T$ 我們用估計的 frame update rate ，大約是 0.00357 (s)， `smoothing factor` $\tau$ 選擇 0.95
$$
a = e^{\frac{-T}{\tau}} \quad or \quad \tau = \frac{-T}{log(a)}
$$
$\tau$ is the resulting `filter time constant` 大約為 0.16 (s) ，表示假設為 step input ，大概耗費 0.16 秒，資料會成長 $1/e \approx 36.8\%$

`main.cpp`:

void printPerformanceInfo(float floatRenderSec,
                          float fixedRenderSec,
                          float overallSec)
{
    const float smoothFactor = 0.95f;
    static auto lastPrintTick = SDL_GetPerformanceCounter();
    static float floatRC = floatRenderSec;
    static float fixedRC = fixedRenderSec;
    static float overRC = overallSec;
    auto currentTick = SDL_GetPerformanceCounter();
    const static auto tickFrequency = SDL_GetPerformanceFrequency();
    floatRC = smoothFactor * floatRC + (1 - smoothFactor) * floatRenderSec;
    fixedRC = smoothFactor * fixedRC + (1 - smoothFactor) * fixedRenderSec;
    overRC = smoothFactor * overRC + (1 - smoothFactor) * overallSec;
    if ((currentTick - lastPrintTick) / static_cast<float>(tickFrequency) >
        0.2f) {
        printf("fixed: %.6f(s), float: %.6f(s), FPS: %.6f(s)\n", fixedRC,
               floatRC, 1 / overRC);
        lastPrintTick = currentTick;
    }
}

## Multi obstacles
### 修改地圖儲存方式 `g_map32`
原本的地圖一個 position 只有兩種情況，因此只需要一個 bit 即可表示:
- It is a wall: 以 `1` 表示
- It is not a wall: 以 `0` 表示

若要儲存不同的 wall ，表示一個 position 有多種可能，需要在 `g_map` 中拓展一個 position 的儲存空間，由於原本的地圖是以 `uint8_t` 若將型態改為 `uint32_t` 即可以將一個 position 以 4 bits 表示，共可以表示 16 種牆壁，而不改變原本地圖 X-Y 座標的定義。

以下為將 8 bits 地圖轉換為 32 bits 地圖的轉換工具:

uint32_t out_map[sizeof(g_map)] = {0};

for (int i = 0; i < sizeof(g_map); i++) {
    uint8_t in = g_map[i];
    for (int j = 0; j < 8; j++) {
        out_map[i] |= (in & (1 << j)) << (4 * j - j);
    }
}

該程式在每個 g_map 後面插入三個 0:

0b   0   1   1   1   1   0   1   0  -> 表示 8 個牆壁，每個牆壁 1 bit
0b00000001000100010001000000010000  -> 表示 8 個牆壁，每個牆壁 4 bit

### 新地圖的牆壁判斷 `IsWall()`
接下來，關係會變得稍微複雜，首先定義以下常數
- `MAP_XS`: 地圖大小的指數 (假設地圖寬度為 32 ，則 `MAP_XS` 為 5 ，因為 $32=2^5$)
- `MAP_ELEMENT_WS`: Element 的意義為，儲存地圖的單位型態，例如:
- `uint8_t` 為 8 bits 因此 `MAP_ELEMENT_WS` 為 3 ($8=2^3$)；
- `uint32_t` 為 32 bits 因此 `MAP_ELEMENT_WS` 為 5 ($32=2^5$)。
- `OBSTACLE_SIZE`: 只用來儲存一個 obstacle (wall) 使用的 bits 數量，例如使用 4 bits 則會有 $2^4=16$ 種 wall 的可能。

接下來的常數是由以上使用者定義的常數衍生出來的，
- `MAP_X`: 地圖大小，為 $2^{MAP\_WS}$
- `MAP_ELEMENT_SIZE`: 儲存地圖的單位變數 bits 數量，為 $2^{MAP\_ELEMENT\_WS}$
- `OBSTACLES_PER_ELEMENT`: 每個單位變數能夠儲存的 obstacle 數量，為 $\frac{MAP\_ELEMENT\_SIZE}{OBSTACLE\_SIZE}$
- `ELEMENTS_PER_ROW`: 儲存每個橫軸 (X軸) 所需要的變數數量，為 $\frac{MAP\_X}{OBSTACLES\_PER\_ELEMENT}$
- `OBSTACLE_MASK`: 單一個 obstacle 的 bit mask ，用來取得單一 obstacle 的 filter，為 $2^{OBSTACLE\_SIZE}-1$

假設

MAP_XS         := 5        // map is 32 x 32 wide
MAP_ELEMENT_WS := 5        // using uint32_t
OBSTACLE_SIZE  := 4        // storing 1 wall with 4 bits
- then we can get:
MAP_X                 = 32
MAP_ELEMENT_SIZE      = 32
OBSTACLES_PER_ELEMENT = 8
ELEMENTS_PER_ROW      = 4
OBSTACLE_MASK         = 0b1111

將 `IsWall()` 中做判斷的程式碼改為如下

return (g_map32[(tileX / OBSTACLES_PER_ELEMENT) +
                (tileY * ELEMENTS_PER_ROW)] >>
        ((OBSTACLES_PER_ELEMENT - tileX % OBSTACLES_PER_ELEMENT) *
         OBSTACLE_SIZE)) &
       OBSTACLE_MASK;

首先要取得地圖中紀錄給定座標的變數，因此計算 index:
$$
index=tileY \times ELEMENTS\_PER\_ROW + \frac{tileX}{OBSTACLES\_PER\_ELEMENT}
$$

接下來要從每個變數中取得對應於目前 tileX 中相對應的 bits ，需注意的是，由於 LSB 對應於 tileX+ 方向，因此

     0   1   2   3   4   5   6   7    //  tileX % OBSTACLES_PER_ELEMENT = 4
0b00000001000100010001000000010000    // g_map32

假設 tileX 為 4 因此我們需要右移 3 格     // 7 - 4
0b00000000000000000001000100010001

最後加上 obstacle bits mask: 0b1111
0b00000000000000000000000000000001

即可得到

### 不同碰撞情況的表示方式
原本的程式碼利用 `hitDirection` 表示 ray 撞擊的方向，假如是在 vertical 方向則標示為 1 ；反之為 0 。

在擴增地圖版本中，為了同時傳達不同的 obstacles 與 `hitDirection` ，將 `hitDirection` 重新定義:
- `hitDirection` / 2 表示 texture id
- `hitDirection` 如為奇數，則為 vertical hit

如此一來就可以保留原本的實作，並且與舊版相容。

實際的改寫包含:
`raycaster_float.cpp`: line 85，將 hitDirection 指定為 `IsWall()` 的回傳值，其意義為撞到的 obstacle ID，並且由於是 vertical hit ，根據以上規則，將 `hitDirection` * 2 + 1

if (*hitDirection = IsWall(tileX, interceptY)) {
    verticalHit = true;
    rayX = tileX + (tileStepX == -1 ? 1 : 0);
    rayY = interceptY;
    *hitOffset = interceptY;
    // Use odd number to indicate different hit direction
    *hitDirection = (*hitDirection - 1) * 2 + 1;
    break;
}

`raycaster_float.cpp`: line 100，將 hitDirection 指定為 `IsWall()` 的回傳值，其意義為撞到的 obstacle ID，並且由於是 horizontal hit ，根據以上規則，將 `hitDirection` * 2

if (*hitDirection = IsWall(interceptX, tileY)) {
    horizontalHit = true;
    rayX = interceptX;
    *hitOffset = interceptX;
    rayY = tileY + (tileStepY == -1 ? 1 : 0);
    *hitDirection = (*hitDirection - 1) * 2;
    break;
}

`renderer.cpp`: line 43，將 **dark wall** 的定義改為判斷奇數:

if (tn % 2 == 1 && tv > 0) {
    // dark wall
    tv >>= 1;
}

:::success
這邊為了保留原本的 texture 相容性，設定 `textureNo` 為 0 時為 gray scale 模式，因此
:::

### 多種 texture
#### 32 bits color encode to 16 bits color
為了在有限的記憶體空間中表示彩色，我將一個 `uint16_t` 分成幾個 part:
- A (Apparent 透明度): 1 bits
- R (Red): 5 bits
- G (Green): 5 bits
- B (Blue): 5 bits

#define CHANNEL_BITS 5

#define CHANNEL_MASK (((1 << CHANNEL_BITS) - 1) << (8 - CHANNEL_BITS))
#define R_OFFSET (CHANNEL_BITS * 2 - (8 - CHANNEL_BITS))
#define G_OFFSET (CHANNEL_BITS * 1 - (8 - CHANNEL_BITS))
#define B_OFFSET (8 - CHANNEL_BITS)

- `CHANNEL_BITS`: 用來儲存單一顏色的 bits 數量
- `CHANNEL_MASK`: 由於要從原本的 8 bits 顏色轉換為 5 bits ，因此要犧牲一些精度，這邊只取 MSB 的 5 個 bits。
- `R_OFFSET`、`G_OFFSET`、`B_OFFSET`: 分別計算不同顏色 channel 所需的位移量

因此新的 16 bits 顏色就可以這樣取得:

uint16_t out = ((r & CHANNEL_MASK) << R_OFFSET) +
               ((g & CHANNEL_MASK) << G_OFFSET) +
               ((b & CHANNEL_MASK) >> B_OFFSET);

R:  0b11111000
G:       0b11111000
B:            0b11111000
   0b0111111111111111

這邊的色彩轉換是用我之前寫的一個 bmp 圖片讀取工具做的

if (openBMP(&bmp, filename)) {
    int width = getWidth(&bmp);
    int height = getHeight(&bmp);

    unsigned char r, g, b;
    for (int y = height - 1; y >= 0; y--) {
        for (int x = 0; x < width; x++) {
            // Obtain the rgb value of a pixel at (x, y)
            getPixelData(&bmp, x, y, &r, &g, &b);
            uint16_t out = ((r & CHANNEL_MASK) << R_OFFSET) +
                           ((g & CHANNEL_MASK) << G_OFFSET) +
                           ((b & CHANNEL_MASK) >> B_OFFSET);
            printf("%d, ", out);
        }
    }

    // Release bmp memory
    freeBmp(&bmp);
} else {
    printf("Fail to open bmp file");
    return 0;
}

#### 16 bits color decode to 32 bits color
我在 `raycaster.h` 中新增以下定義用於計算 decode 時所需的各個 mask 及 offset :

// Number of bits to representing a single color channel
#define TEXTURE_BITS_COLOR 5

#define TEXTURE_COLOR_MASK ((1 << TEXTURE_BITS_COLOR) - 1)
#define TEXTURE_R_MASK (TEXTURE_COLOR_MASK << (TEXTURE_BITS_COLOR * 2))
#define TEXTURE_G_MASK (TEXTURE_COLOR_MASK << (TEXTURE_BITS_COLOR * 1))
#define TEXTURE_B_MASK (TEXTURE_COLOR_MASK << (TEXTURE_BITS_COLOR * 0))
#define TEXTURE_R_OFFSET \
    (8 * 2 + (8 - TEXTURE_BITS_COLOR) - TEXTURE_BITS_COLOR * 2)
#define TEXTURE_G_OFFSET \
    (8 * 1 + (8 - TEXTURE_BITS_COLOR) - TEXTURE_BITS_COLOR * 1)
#define TEXTURE_B_OFFSET \
    (8 * 0 + (8 - TEXTURE_BITS_COLOR) - TEXTURE_BITS_COLOR * 0)

將 `uint16_t` 的顏色轉換為 `uint32_t` ，`renderer.h`: line 16

inline static uint32_t GetARGB_color(uint16_t color)
{
    return ((color & TEXTURE_R_MASK) << TEXTURE_R_OFFSET) +
           ((color & TEXTURE_G_MASK) << TEXTURE_G_OFFSET) +
           ((color & TEXTURE_B_MASK) << TEXTURE_B_OFFSET);
}

#### texture mapping
為了讓原本的 gray scale texture 可以相容，因此區分兩種 texture rendering method:
- Gray Scale: 使用 `GetARGB()` decode
- Colored: 使用 `GetARGB_color()` decode

記錄不同 texture 的 texture list:
`renderer.h`

const uint8_t *g_texture_gray[NUMBER_OF_GRAY_TEXTURE] = {g_texture8};
const uint16_t *g_texture_color[2] = {g_texture8_computer, g_texture8_cat};

根據 [前述](#%E4%B8%8D%E5%90%8C%E7%A2%B0%E6%92%9E%E6%83%85%E6%B3%81%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%96%B9%E5%BC%8F) `textureNo` 的定義，依據 ray 撞擊的 obstacle 種類 (`tn / 2`) 可以判斷出要以 gray scale 或是 colored 方式選擇 texture 及 render:
`renderer.cpp`:

uint16_t tv;
if (tn / 2 < NUMBER_OF_GRAY_TEXTURE) {
    // gray scale texture
    tv = (g_texture_gray[tn / 2])[(ty << 6) + tx];
    *lb = GetARGB(tv);
} else {
    // colored texture
    tv = (g_texture_color[tn / 2 - 1])[(ty << 6) + tx];
    *lb = GetARGB_color(tv);
}

原本程式碼的設計是當遇到 vertical hit 的 obstacles 的時候，會將原本的 texture 以亮度變暗的方式做 render ，但如果是 colored 的 textu部則不能直接右移，因為不同的 color channel 會互相影響，因此在平移之前加一個 `0xFEFEFE` 的 mask ，確保 LSB 都是 0 再做平移。
`renderer.cpp`:

// View with different direction
if (tn % 2 == 1 && *lb > 0) {
    // dark wall
    *lb = (*lb & 0xFEFEFE) >> 1;
}

#### 效果比較
- 8 bits texture 效果 (Ax2, Rx2, Gx2, Bx2)，色彩深度: 64
<table>
<tr><th>原圖 (64x64 bmp)</th><th>8 bits texture</th><tr>
<tㄉˇ
<td><img src="https://i.imgur.com/2QGQoq3.png" style="width: 300px"></td>
<td><img src="https://i.imgur.com/UMSdYGy.png" style="width: 400px"></td></tr>
</table>
- 16 bits texture 效果 (Ax2, Rx2, Gx2, Bx2)，色彩深度: 32768
<table>
<tr><th>原圖 (64x64 bmp)</th><th>16 bits texture</th><tr>
<tr>
<td><img src="https://i.imgur.com/2QGQoq3.png" style="width: 300px"></td>
<td><img src="https://i.imgur.com/HzSe3KS.png" style="width: 400px"></td></tr>
</table>

## 遊戲體驗加強
再來我加入一些遊戲的元素，例如持槍、準心等等。

我在 `Renderer` 中新增了一個 function `RenderGame()` 負責所有非 raycasting 的 render.
### 顯示槍枝
- Gun Side View: 在 player 未舉槍之前，槍枝以 side view 方式呈現，並且隨著 player 行動，槍枝會跟著步伐晃動。
- 準心晃動: 因為槍枝晃動所以準心也會跟著變大變小。
- Gun Center View: 舉槍後，視野縮小，準心也縮小。

#### Gun Side view
我將 color 的 MSB 作為圖片透明控制，因此在 render 的時候檢查 color 的 MSB 是 0 才需要 override 該像素的 color buffer.

// rendering hand and gun
uint32_t *lb =
    fb +
    (SCREEN_HEIGHT - TEXTURE_GUN_SIDE_HEIGHT + (uint8_t) offset) *
        SCREEN_WIDTH +
    (SCREEN_WIDTH - TEXTURE_GUN_SIDE_WIDTH);
for (int j = 0; j < TEXTURE_GUN_SIDE_HEIGHT - (uint8_t) offset; j++) {
    for (int i = 0; i < TEXTURE_GUN_SIDE_WIDTH; i++) {
        auto tv = g_texture_gunside[j * TEXTURE_GUN_SIDE_WIDTH + i];

        if ((tv & 0x8000) == 0)
            *lb = GetARGB_color(tv);
        lb++;
    }
    lb += SCREEN_WIDTH - TEXTURE_GUN_SIDE_WIDTH;
}

#### Arming point
準心大小可以從 `game.h` 設定

#define ARM_POINT_LEN 10
#define ARM_POINT_RAD 10
#define ARM_POINT_COLOR 0x00FFFFFF

`renderer.cpp` 把準心畫出來

// rendering aiming point
lb = fb + (SCREEN_HEIGHT / 2) * SCREEN_WIDTH + (SCREEN_WIDTH / 2);
for (int l = 0; l < ARM_POINT_LEN; l++) {
    uint8_t len = offset + l + ARM_POINT_RAD;
    *(lb - len * SCREEN_WIDTH) = ARM_POINT_COLOR;
    *(lb + len * SCREEN_WIDTH) = ARM_POINT_COLOR;
    *(lb - len) = ARM_POINT_COLOR;
    *(lb + len) = ARM_POINT_COLOR;
}


#### Moving
為了呈現人物在走動時晃動的效果，讓 `Game` 多紀錄一個參數 `moving` ，表示該 time step 時人物的移動距離，然後再用一個週期函數 (這邊用 sin ) 讓 offset 持續震盪，最後，為了讓 offset 在人物沒有移動時逐漸回到原點，將 offset 乘上一個小於 0 的值。

static float time = 0, offset = 0;
if (g->moving > 0) {
    time += 0.02f;
    offset = (10 * (sin(time) + 1));
} else {
    offset *= 0.99f;
}

#### Gun Center view
增加舉槍動作，當按下 `e` 時，可以切換為舉槍姿勢，

我把 player 的姿態記錄在 `Game` 裡，定義 enum 為:

enum PlayerPose {POSE_STAND, POSE_SQUAT};

並且在 `Game` 中加入

PlayerPose pose;

取得鍵盤事件，我將 `main.cpp` 中的 `ProcessEvent()` 增加了一個 `e` 的判斷:

static bool ProcessEvent(const SDL_Event &event,
                         int *moveDirection,
                         int *rotateDirection, Game *game)
{
    ...
        case SDLK_e:
            game->pose = p ? POSE_SQUAT : POSE_STAND;
    ...
}

修改槍枝的 render ，若為蹲下的 pose (`POSE_SQUAT`) ，則畫出另一個槍枝的 texture:

// rendering hand and gun
if (g->pose == POSE_SQUAT) {
    const int sx = SCREEN_WIDTH / 2 - TEXTURE_GUN_CENTER_WIDTH / 2 + 1;
    const int sy = SCREEN_HEIGHT - TEXTURE_GUN_CENTER_HEIGHT;
    uint32_t *lb = fb + sy * SCREEN_WIDTH + sx;
    for (int j = 0; j < TEXTURE_GUN_CENTER_HEIGHT; j++) {
        for (int i = 0; i < TEXTURE_GUN_CENTER_WIDTH; i++) {
            auto tv = g_texture_gun_center[j * TEXTURE_GUN_CENTER_WIDTH + i];

            if ((tv & 0x8000) == 0)
                *lb = GetARGB_color(tv);
            lb++;
        }
        lb += SCREEN_WIDTH - TEXTURE_GUN_SIDE_WIDTH;
    }
} else {
    uint32_t *lb =
        fb +
        (SCREEN_HEIGHT - TEXTURE_GUN_SIDE_HEIGHT + (uint8_t) offset) *
            SCREEN_WIDTH +
        (SCREEN_WIDTH - TEXTURE_GUN_SIDE_WIDTH);
    for (int j = 0; j < TEXTURE_GUN_SIDE_HEIGHT - (uint8_t) offset; j++) {
        for (int i = 0; i < TEXTURE_GUN_SIDE_WIDTH; i++) {
            auto tv = g_texture_gun_side[j * TEXTURE_GUN_SIDE_WIDTH + i];

            if ((tv & 0x8000) == 0)
                *lb = GetARGB_color(tv);
            lb++;
        }
        lb += SCREEN_WIDTH - TEXTURE_GUN_SIDE_WIDTH;
    }
}

效果展示:

### 碰撞
在更新 player 位置之前，先檢查會不會撞到牆，如果會撞到的話讓 player 往反方向反彈。
`game.cpp`:

float try_move_x = 0.5f * m * sin(playerA) * seconds * 5.0f;
float try_move_y = 0.5f * m * cos(playerA) * seconds * 5.0f;
int x = playerX + try_move_x;
int y = playerY + try_move_y;
if (((g_map32[(x / OBSTACLES_PER_ELEMENT) + (y * ELEMENTS_PER_ROW)] >>
      ((OBSTACLES_PER_ELEMENT - x % OBSTACLES_PER_ELEMENT) *
       OBSTACLE_SIZE)) &
     OBSTACLE_MASK) == 0) {
    playerX += try_move_x;
    playerY += try_move_y;
} else {
    playerX -= try_move_x;
    playerY -= try_move_y;
}

## 透明牆壁
### Allow the ray keep going
能夠看到障礙物後面的物體，表示光線能夠穿透障礙物，在這個專題的意思就是，在 raycasting 的時候， ray 不能夠被牆壁阻擋。於是乎我把腦筋動到 `Distance()` 上，如何重複呼叫 `Distance()` 是關鍵的問題。

一開始我多加一個參數叫做 `keepGoing` 來判斷是否是上次的 ray: `raycaster_float.cpp`

float RayCasterFloat::Distance(float playerX,      // In, Player location X
                               float playerY,      // In, Player location Y
                               float rayA,         // In, Player location Angle
                               float *hitOffset,   // Out,
                               int *hitDirection,  // Out,
                               bool keepGoint)     // In
{
    ...
}

但是這樣我發現必須從 `Trace()` 就傳入 `keepGoing` 的參數，因此連 `Trace()` 都要修改函數原型，導致 `raycaster.h` 中 `Raycaster` 的 virtual function `Trace()` 要連帶修改，最後連毫無關聯的 `raycaster_fixed.cpp` 也要修改，因此這樣不是一個好的辦法。

`raycaster.h`

virtual void Trace(uint16_t screenX,
                   uint8_t *screenY,
                   uint8_t *textureNo,
                   uint8_t *textureX,
                   uint16_t *textureY,
                   uint16_t *textureStep) = 0;

但後來我發現，如果在同一個地方發出 ray ，則 x 座標應該是一樣的，在 `Distance()` 內部判斷就可以避免修改 `Raycaster` 的原型。
`raycaster_float.cpp`

void RayCasterFloat::Trace(uint16_t screenX,
                           uint8_t *screenY,
                           uint8_t *textureNo,
                           uint8_t *textureX,
                           uint16_t *textureY,
                           uint16_t *textureStep)
{
    static uint16_t previousX = UINT16_MAX;
    bool keepGoing = false;
    if (screenX == previousX)
        keepGoing = true;
    previousX = screenX;
    ...
    float lineDistance = Distance(_playerX, _playerY, _playerA + deltaAngle,
                                  &hitOffset, &hitDirection, keepGoing);
    ...
}

我用了一個 `static` 的變數去紀錄上一次 X 座標的值，當這次與前次不一樣表示 ray 應該 keepGoing ，並且把這個資訊傳給 `RaycasterFloat` 的 private function `Distance()`

在 `Distance()` 中，我發現若要沿用上一次的結果，大部分參數都不需要重新計算，唯一要注意的是 $(tileX, inceptionY)$ 與 $(inceptionX, tileY)$ 的資料更新，因此，我將大部分參數設定為 `static` 並用 `keepGoing` 決定要不要計算初始值 $(startDeltaX, startDeltaY)$

設定為 `static` 的參數:

static float rayX = playerX;
static float rayY = playerY;
static float tileX = 0, tileY = 0, offsetX = 0, offsetY = 0,
             startDeltaX = 0, startDeltaY = 0, interceptX = 0,
             interceptY = 0;
static int tileStepX = 0, tileStepY = 0;

將初始 `startDelta` 、 `inception` 、 `tile` 的計算放進 `keepGoing` 檢查:

if (!keepGoing) {
    rayX = playerX;
    rayY = playerY;
    offsetX = modff(rayX, &tileX);
    offsetY = modff(rayY, &tileY);

    float vecX = 1 - offsetY;  // The case that 3pi/2 ~ pi/2
    float vecY = 1 - offsetX;  // The case that 0 ~ pi
    tileStepX = 1;             // The case that 0 ~ pi
    tileStepY = 1;             // The case that 3pi/2 ~ pi/2

    // Generate directional unit vector according to player angle
    if (rayA > M_PI) {
        tileStepX = -1;
        vecY = (offsetX == 0) ? 1 : offsetX;
    }
    if (rayA > M_PI_2 && rayA < 3 * M_PI_2) {
        tileStepY = -1;
        vecX = (offsetY == 0) ? 1 : offsetY;
    }

    // Calculate the starting delta
    startDeltaX = vecX * tan(rayA) * tileStepY;
    startDeltaY = vecY / tan(rayA) * tileStepX;

    interceptX = rayX + startDeltaX;
    interceptY = rayY + startDeltaY;
}

最後我發現 inception 需要一個補償，但我不確定原因為何，若沒有補償會出現下面的現象，穿透牆壁後， texture 的位置錯開了。

我在 `Distance()` 的最後加入下面的補償，以 vertical hit 的 case 看得話，我覺得原因應該是在判斷碰撞的 while 迴圈中，可以發現只有 tileX 被往前推進，而在判斷牆壁之後就直接 break 了，因此 inceptionY 會少一次推進，而 horizontal hit 也是如此。

if (verticalHit)
    interceptY += stepY;
else
    interceptX += stepX;

vertical hit 的計算:

while (((tileStepY == 1 && (interceptY <= tileY + 1)) ||
        (tileStepY == -1 && (interceptY >= tileY)))) {
    somethingDone = true;
    tileX += tileStepX;    // 這邊 X 軸被推進
    if (*hitDirection = IsWall(tileX, interceptY)) {
        verticalHit = true;
        rayX = tileX + (tileStepX == -1 ? 1 : 0);
        rayY = interceptY;
        *hitOffset = interceptY;
        // Use odd number to indicate different hit direction
        *hitDirection = (*hitDirection - 1) * 2 + 1;
        break;             // 遇到 break 之後
    }
    interceptY += stepY;   // 這個不會執行到
}

### Rendering apparent walls
現在我們已經可以偵測牆壁後面的牆壁了，只要在同一個 X 軸下重複呼叫 `RaycasterFloat` 的 `Trace()` 即可，他會回傳牆壁之後的牆壁的計算結果。

接下來為了簡化程式碼，我在 `renderer.cpp` 中重新設計了一個 general 版本的 `TraceFrame()` Helper，可以簡化多次做 Render 一個 X 座標的程式碼，並且使之後增加功能更易於維護。

我發現對於牆壁後牆壁的 Render 可以設計為重複的工作，只是範圍不太一樣而已。
<center><img src="https://i.imgur.com/SqJr16G.png" style="width: 500px"></center>

`raycaster_float.cpp`

uint16_t Renderer::RecursiveTraceFrame(
    uint32_t *fb,    // In, Frame buffer
    int x,           // In, screen X
    uint16_t up,     // In, upper screen position
    uint16_t down,   // In, lower screen position
    uint8_t offset)  // In, downscale
{
    uint8_t sso;   // top point of wall
    uint8_t tc;    // x axis of texture (256 -> 64)
    uint8_t tn;    // texture number
    uint16_t tso;  // y axis of texture
    uint16_t tst;  // texture step (currentlt not used)
    uint32_t *lb = fb + x + up * SCREEN_WIDTH;  // frame buffer

    _rc->Trace(x, &sso, &tn, &tc, &tso, &tst);

    auto tx = static_cast<int>(tc >> 2);
    if (sso >= HORIZON_HEIGHT)
        sso = HORIZON_HEIGHT;
    
    // render top sky
    for (int y = up; y < HORIZON_HEIGHT - sso; y++) {
        if (offset > 0)
            *lb = DOWN_SCALE(*lb) +
                  DOWN_SCALE(GetARGB(96 + (HORIZON_HEIGHT - y)));
        else
            *lb = GetARGB(96 + (HORIZON_HEIGHT - y));
        lb += SCREEN_WIDTH;
    }

    // render obstacle
    for (int y = 0; y < sso * 2; y++) {
        // paint texture pixel
        uint16_t ty =
            (tso + (((TEXTURE_SIZE / 2) << 10) - tso) * y / sso) >> 10;

        uint16_t tv;
        uint32_t color;
        if (tn / 2 < NUMBER_OF_GRAY_TEXTURE) {
            // gray scale texture
            tv = (g_texture_gray[tn / 2])[(ty << 6) + tx];
            color = GetARGB(tv);
        } else {
            // colored texture
            tv = (g_texture_color[tn / 2 - 1])[(ty << 6) + tx];
            color = GetARGB_color(tv);
        }

        if (offset > 0)
            *lb = DOWN_SCALE(*lb) + DOWN_SCALE(color);
        else
            *lb = color;

        lb += SCREEN_WIDTH;
    }

    // render bottom sky
    for (int y = HORIZON_HEIGHT + sso; y < down; y++) {
        if (offset > 0)
            *lb =
                DOWN_SCALE(*lb) + DOWN_SCALE(GetARGB(96 + y - HORIZON_HEIGHT));
        else
            *lb = GetARGB(96 + y - HORIZON_HEIGHT);
        lb += SCREEN_WIDTH;
    }
    return sso;
}

透明的方法就是保留原本一半的顏色，混入被遮蓋物體一半的顏色:
$$
\left\{
\begin{array}{lr}
B_{k+1} = \frac{1}{2}B_k + \frac{1}{2}C_k \\
B_0 = 0
\end{array}
\right.
$$
- $B_k$ 是第 k 次的 frame buffer
- $C_k$ 是第 k 次的 trace 的顏色

為了簡化顏色 down scale 的計算，用這個 macro 將顏色變為原本的一半。
`renderer.h`

#define DOWN_SCALE(color) (((color) & 0xFEFEFE) >> 1)

剩下要注意的是:
- first trace() 的時候，`frame buffer` 會殘留有過去的影像，因此直接覆值。
- second trace() (或是還有更多次的話)，要更新為過去的一半 加上 現在的一半。

這樣一來，原本的 `TraceFrame()` 就可以寫得相當簡單:

void Renderer::TraceFrame(Game *g, uint32_t *fb)
{
    _rc->Start(static_cast<uint16_t>(g->playerX * 256.0f),
               static_cast<uint16_t>(g->playerY * 256.0f),
               static_cast<int16_t>(g->playerA / (2.0f * M_PI) * 1024.0f));

    for (int x = 0; x < SCREEN_WIDTH; x++) {
        uint16_t sso = RecursiveTraceFrame(fb, x, 0, SCREEN_HEIGHT, 0);
        sso = RecursiveTraceFrame(fb, x, HORIZON_HEIGHT - sso,
                                  HORIZON_HEIGHT + sso, 1);
    }
}

由於視角始終都在地平線上的關係，可以保證下一次 trace 後的 sso 絕對比前一次的值要小 (距離遠的物體看起來比較矮)

||first trace|second trace|
|:-:|:-:|:-:|
|up|0|HORIZON_HEIGHT - sso|
|down|SCREEN_HEIGHT|HORIZON_HEIGHT + sso|

### God mode
最後我新增一個 god mode 的模式，當按下 `g` 鍵後就會開啟透視外掛
`renderer.cpp`

if (g->godMode > 0)
    sso = RecursiveTraceFrame(fb, x, HORIZON_HEIGHT - sso,
                              HORIZON_HEIGHT + sso, 1);

`game.h`

class Game
{
public:
    ...
    int godMode;
    ...
};

效果:
<center><img src="https://i.imgur.com/PexcrJA.png" style="width:500px"></center>

#### 破壞場景

## 增強遊戲體驗
#### 關於 Z 軸的可能性
好像，沒有這個可能
- ray 會穿透牆壁背後，也就是 `traceFrame()` 裡面的 `sso` 範圍會有好幾個，也很難判斷什麼時候要停。
- 頂部的 texture 要包含 X 方向 offset
- 從最近開始 (螢幕下方) 直到撞到邊屆為止