2020q3 render

tags: `sysprog`

contributed by < sciyen >
repository on github

2020q3 render
遊戲方法
特殊函數筆記
程式原理分析
- Overview
Raycasting Procedures
- - TraceFrame()
  - Trace()
- raycaster_float.cpp
  - Distance()
Fixed point implementation
- 定點數運算
New Features

遊戲方法

按
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
/
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
前進/後退
按
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
/
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
向左轉/右轉
按 e 舉槍
按 g 開啟 God Mode 使出透視眼

特殊函數筆記

float modff( float x, float * intptr ); in math.h (Microsoft docs)
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。
這邊的 8-(tileX & 0x7) 應該錯了，考慮 tileX 最大即最小情況：
- 最小 tileX =0 時，8-0=8：1<<8，會超過 uint8_t 的範圍
- 最大 tileX =7 時，8-7=1：1<<1=2，發現永遠沒有 1 的情況
因此應該將 8 修正為 7。

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

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

更有彈性的寫法：

若地圖改以其他變數型態表示時，可以這樣設定：假設用 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 方向，向視野右邊角度為正，向視野左邊角度為負。

Fig. Gaming coordinate system

一般來說，求 X 方向應該使用

c o s

，Y 方向使用

s i n

但在這邊會相反，可以在 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：

Fig. Gaming coordinate system

可以發現這邊重新定義的 unit vector 是以

θ

與 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:

視角僅可能為畫面中間，如此一來計算就只需要計算 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() :

Fig. Frame tracing direction

障礙物在畫面中分成兩種情況:

障礙物高度低於畫面高度
Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →
Fig. Field Of View
障礙物高度超過畫面高度
Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →
Fig. Field Of View

因此要畫出畫面中特定 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 中移動的距離。

Fig. View window

其中，特定 screenX 相對於畫面中心的角度差

Δ θ

可以表示為：

Δ θ = a c r t a n (\frac{V i e w O f f s e t X}{V i e w W i n d o w D i s t a n c e}) = a r c t a n (\frac{s c r e e n X - \frac{s c r e e n W i d t h}{2}}{\frac{s c r e e n W i d t h}{2} \frac{τ_{m a x}}{2}})

其中，
$τ_{m a x}$ 可以限制可視範圍，
$s c r e e n X$ 為 0 時為最左側；
$s c r e e n X$ 為
$\frac{s c r e e n W i d t h}{2}$ 時為最右側。

$Δ θ_{m a x} = a c r t a n (\frac{\pm 2}{τ_{m a x}}) \approx \pm {51.8}^{\circ}$
$D_{v}$ : View Window Distance 為視野畫面 (ViewWindow) 與 player (Origin) 的距離

設定 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))));

如此一來

Δ θ_{m a x} = a c r t a n (t a n (\pm \frac{F O V_{X}}{2})) = \pm \frac{F O V_{X}}{2}

D_{v} = \frac{s c r e e n W i d t h}{2 t a n (\frac{F O V_{X}}{2})}

重新定義的 FOV 如下圖：

綠線為水平 (X) 方向視角極限
藍線為垂直 (Y) 方向視角極限

Fig. Field Of View

45 度:

90 度:

120 度:

計算畫面中障礙物的高度

Fig. Gaming coordinate system

利用相似三角形，可以做以下推論

\frac{\frac{s c r e e n Y}{2}}{D_{v}} = \frac{\frac{W a l l H e i g h t}{2}}{d i s t a n c e}, i . e . s c r e e n Y = \frac{W a l l H e i g h t \times D_{v}}{d i s t a n c e} = \frac{W a l l H e i g h t \times s c r e e n W i d t h}{4 \times d i s t a n c e \times t a n (\frac{F O V_{X}}{2})}

為配合前面 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 = T e x t u r e S i z e \times H i t O f f s e t R a t i o$
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 定點數。

這邊 X 方向使用 2 bits 定點數即可，是因為視野不會傾斜，不會對成像造成明顯影響。
Texture Y 方向，使用 10 bits fixed point:
目標為找出畫面上特定 Y 座標點對應的 texture 座標，因此可以看作兩個座標空間的轉換，這邊記作
$S c r e e n C o o r d i n a t e \to T e x t u r e C o o r d i n a t e$ ：

將 texture 看作一線性變換：

$t e x t u r e Y^{*} = t e x t u r e Y_{0} + y \frac{T e x t u r e S i z e - 2 \times t e x t u r e Y_{0}}{W a l l H e i g h t}$

$t e x t u r e Y_{0}$ : texture 的起始座標。

$T e x t u r e S i z e$ : texture 的圖片大小。

$W a l l H e i g h t$ : 視野中牆壁的高度，也就是
$2 \times s c r e e n Y$ 。若牆高超過視野高度，則
$W a l l H e i g h t = S c r e e n H e i g h t$

$t e x t u r e Y_{0} = T e x t u r e S i z e \frac{(P r o j e c t H e i g h t - S c r e e n H e i g h t) / 2}{P r o j e c t H e i g h t}$

$P r o j e c t H e i g h t$ : 投影在成像平面上的牆壁高度。
這邊有兩種狀況:
- 牆壁高度沒有超過視野高度:
  $W a l l H e i g h t = 2 \times s c r e e n Y \leq S c r e e n H e i g h t$
  由於牆壁會完全畫出來，因此 texture 從 0 開始畫，即
  $t e x t u r e Y_{0} = 0$ 。
  
  $t e x t u r e Y^{*} = 0 + y \frac{T e x t u r e S i z e}{W a l l H e i g h t}$
  
  $y$ 為畫面取樣時的 y 座標，其範圍應為
  $0 \leq y < W a l l H e i g h t$ 。
- 牆壁高度超過視野高度:
  $2 \times s c r e e n Y \geq S c r e e n H e i g h t = W a l l H e i g h t$
  從視野中只能看到部分牆壁，因此最高處從
  $t e x t u r e Y_{0}$ 開始。

原程式碼中的運算缺失

screenY overflow

可以發現，出現異常的地方總是在牆壁高度過高的時候(相較於左側視野範圍內，較低的牆壁高度總是沒有異常)

在原本程式碼中，並未判斷 screenY 是否超過 screenHeight 也未對超過的情況做處理。此外，在

s c r e e n Y

的計算中，原本的程式碼是以 uint8_t 的整數去接收 INV_FACTOR / distance 因此若牆壁高度的計算結果超過 255 ，便會導致

s c r e e n Y

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;

Fig. Fixed point 產生的鋸齒畫面

修正

利用前述的方式計算 textureY ，先在 raycaster_float.cpp 中判斷

W a l l H e i g h t

，若成像的高度大於畫面範圍

S c r e e n H e i g h t

，則再計算對應的

t e x t u r e Y

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) ，並且在計算

t e x t u r e Y^{*}

最後再右移 10。

Fig. Fixed point 修正後的畫面

消除魚眼

當距離太近的時候，會產生如下的魚眼效果：

Fig. Fisheye effect

未校正前的影像是投影在「成像平面」上(見下圖)，產生

M

點，可以發現，相較於投影在「投影球面」上的

P

點

投影在成像平面上有更寬闊的視野範圍，但是會造成失真，因為成像位置與觀測位置每點的距離都不太一樣，越靠近左右成像距離越長。

要修正魚眼效果要修正成像距離，使其成像在「投影球面」上，因此：

D i s t a n c e = L i n e D i s t a n c e \times t a n (Δ θ)

Fig. Fisheye effect compensation

在程式碼中，

L i n e D i s t a n c e

指的是物體至玩家的距離，而在這邊修正魚眼指的是 成像平面投影點 至 觀測點 的距離，但是由於

s c r e e n Y

的計算是線性的，因此先乘和後乘

t a n ()

是等效的；

D i s t a n c e

以此類推。

魚眼修正的加速

由魚眼校正的計算可以發現，每個

Δ θ

、

t a n (Δ θ)

對於

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 就好。

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

$0 \leq θ < \frac{π}{2}$ ，
$t a n (θ) > 0$

{\begin{array}{lr} s t a r t D e l t a X = (1 - o f f s e t Y) t a n (θ) \\ s t a r t D e l t a Y = \frac{1 - o f f s e t X}{t a n (θ)} \end{array}

$\frac{π}{2} \leq θ < π$ ，
$t a n (θ) < 0$

{\begin{array}{lr} s t a r t D e l t a X = o f f s e t Y \times (- t a n (θ)) \\ s t a r t D e l t a Y = \frac{1 - o f f s e t X}{t a n (θ)} \end{array}

$π \leq θ < \frac{3 π}{2}$ ，
$t a n (θ) > 0$

{\begin{array}{lr} s t a r t D e l t a X = o f f s e t Y \times (- t a n (θ)) \\ s t a r t D e l t a Y = \frac{o f f s e t X}{- t a n (θ)} \end{array}

$\frac{3 π}{2} \leq θ < 2 π$ ，
$t a n (θ) < 0$

{\begin{array}{lr} s t a r t D e l t a X = (1 - o f f s e t Y) (- t a n (θ)) \\ s t a r t D e l t a Y = \frac{o f f s e t X}{- t a n (θ)} \end{array}

Simplifying the calculation of startDelta

這邊發現一個很有趣的現象，如果將

t a n (θ)

前的正負號提出來，恰好為 X、Y 象限的單位向量，因此可以將原本的計算改為

{\begin{array}{lr} s t a r t D e l t a X = v e c X \times t a n (θ) \times c o r r e c t Y \\ s t a r t D e l t a Y = v e c Y \times \frac{1}{t a n (θ)} \times c o r r e c t X \end{array}

修正項與 X、Y 象限單位向量的關係為

(c o r r e c t Y, c o r r e c t X) = (u n i t X, u n i t Y)

，這邊 X、Y 恰好相反。

Fig. Unit vector

而

(v e c X, v e c Y)

則與象限有關，可以整理成下表

	$0 \leq θ < π$	$π \leq θ < 2 π$
$v e c Y$	$1 - o f f s e t X$	$o f f s e t X$
$u n i t X$	$1$	$- 1$

	$\frac{π}{2} \leq θ < \frac{3 π}{2}$	$0 \leq θ < \frac{π}{2}$ && $\frac{3 π}{2} \leq θ < 2 π$
$v e c X$	$o f f s e t Y$	$1 - o f f s e t Y$
$u n i t Y$	$- 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 實驗詳細資料

實驗	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 θ \leq \frac{π}{2}

舉例：

以

i n t e r c e p t

為起點

{\begin{array}{lr} i n t e r c e p t X & = r a y X + s t a r t D e l t a X \\ i n t e r c e p t Y & = r a y Y + s t a r t D e l t a Y \end{array}

發射出的向量會以相同的方向，但以不同的大小前進，因此分成以下兩種可能:

撞到橫軸，即為綠色點，其 Y 座標為整數

$h i t P o s = (i n t e r c e p t X, t i l e Y) m o v e V e c = (| t a n (θ) | s g n (u n i t X), 1 \cdot s g n (u n i t Y))$
撞到縱軸，即為紅色點，其 X 座標為整數

$h i t P o s = (t i l e X, i n t e r c e p t Y) m o v e V e c = (1 \cdot s g n (u n i t Y), \frac{1}{| t a n (θ) |} s g n (u n i t X))$

因此，所有的碰撞點可以表示成如下:

h i t P o s^{*} = h i t P o s + n \times m o v e V e c, n \in Z

Fig. Collision points

如此一來只要重複比對是哪一個碰撞點最先撞到即可。

紅色:

t i l e Y + 1 < i n t e r c e p t Y

只要這個條件還滿足，表示下一個紅色仍然在綠色的範圍內，因此，下一個點仍然是紅色。

如果撞到牆壁一定是 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;
}

綠色:

t i l e X + 1 < i n t e r c e p t X

只要這個條件還滿足，表示下一個綠色仍然在紅色的範圍內，因此，下一個點仍然是綠色。

如果撞到牆壁一定是 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{π}{2}

，可以在 precalculator.cpp 中找到線索:
precalculator.cpp line: 45


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

也就是說，新變數 da

d a = d e l t a A n g l e \times \frac{256}{\frac{π}{2}}

因此，若要判斷 angle 所在象限 (有多少個

\frac{π}{2}

)，只要取 angle >> 8 即可；而 angle % 256 則為佔

\frac{π}{2}

的比例。例如:
raycaster_fixed.cpp line:101


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

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

角度表示範圍與誤差

數學中

t a n (θ)

與

c o t (θ)

存在極端值 (當

t a n (π / 2)

時為無窮大)，也就是會出現 uint16_t 無法表示的範圍。

極值

t a n (θ)

的極值出現在最靠近

\frac{π}{2} + n π

的地方，其中

n

為整數。

誤差

由於電腦數值系統中，僅能以有限數量的位元儲存數字，因此對於像是

t a n ()

這種無理數，僅能近似其數值，而近似結果與實際數字的差距就定義為誤差。

E r r o r (θ_{a}) = t a n_{a} (θ_{a}) - t a n (θ)

$θ_{a}$ 為在該數值表示方法下近似的
$θ$ 為離散值。
$\tan_{a} ()$ 為選用的
$t a n ()$ 近似算法為離散的 one to one mapping
$θ$ 及
$t a n ()$ 為連續值

Fig: Error of tan

由於

t a n (θ)

的微分為

\frac{1}{s e c^{2} (θ)}

，其在

0 \leq θ < \frac{π}{2}

的範圍內為嚴格遞增函數，可以得到

a b s (E_{L} (θ)) < E_{H} (θ) < Ω (θ)

，並且，

θ

越接近

\frac{π}{2}

，

Ω (θ)

越大。

Fig: 1/sec^2()

討論與比較

假設
$θ$ 為 8 bits 定點數
- 極值: 在
  $θ$ 最接近
  $\frac{π}{2}$ 時，也就是
  $θ = \frac{π}{2} \frac{255}{256}$ ，tan 有最大值
  $t a n (\frac{π}{2} \frac{255}{256}) = 162.937$ 。
- 最大誤差:
  $\tan (\frac{π}{2} \frac{255}{256}) - \tan (\frac{π}{2} \frac{254}{256}) = 81.489$ 。
假設
$θ$ 為 10 bits 定點數
- 極值: 在
  $θ$ 最接近
  $\frac{π}{2}$ 時，也就是
  $θ = \frac{π}{2} \frac{1023}{1024}$ ，tan 有最大值
  $t a n (\frac{π}{2} \frac{1023}{1024}) = 651.335$ 。
- 最大誤差:
  $\tan (\frac{π}{2} \frac{1023}{1024}) - \tan (\frac{π}{2} \frac{1022}{1024}) = 325.950$ 。
- 但是如果在
  $\frac{π}{2} \frac{255}{256}$ 的誤差則為
  $\tan (\frac{π}{2} \frac{1020}{1024}) - \tan (\frac{π}{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 補數。

Q: 為什麼不是用 2 補數?

`AbsTan()`

利用

t a n ()

的對稱關係，可以用映射的方式得到不同象限的函數值。

Fig. function of tan (wikimedia)

如此一來，可以做個歸納: (這邊的象限定義使用前述的數字系統，以第 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);
}

invert

這邊垂直映射是利用


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

也就是說，利用

a + b = 256

的關係，找出對稱的 index

乘 `MulTan()`

這個 function 用查表的方式快速計算

v a l u e \times t a n (a n g l e)

或是

v a l u e \times c o t (a n g l e)

由

t a n ()

與

c o t ()

的關係:

t a n (- θ + \frac{π}{2}) = \frac{s i n (- θ + \frac{π}{2})}{c o s (- θ + \frac{π}{2})} = \frac{- c o s (- θ)}{s i n (- θ)} = c o t (θ)

可以發現

t a n ()

和

c o t ()

的關係其實是將

t a n ()

取垂直映射後，右(左)移

\frac{π}{2}

Fig. function of cot (https://mathbitsnotebook.com/Algebra2/TrigGraphs/TGtanSecCscCot.html)

而實際上，可以藉由對

\frac{π}{4}

映射得到。

如此一來，可以做個歸納: (這邊的象限 quarter 定義使用前述的數字系統，以第 0 象限作為開始)

需要左右映射的:
- $t a n ()$ : 1、3 象限
- $c o t ()$ : 0、2 象限
需要上下映射的 (負號):
- $t a n ()$ : 1、3 象限
- $c o t ()$ : 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() 很像，不一樣的是

CalculateDistance() 中的 tan() 計算改以查表的方式進行。
對於 angle 等於 0 的特例做了最佳化。
使用 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

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

τ

選擇 0.95

a = e^{\frac{- T}{τ}} o r τ = \frac{- T}{l o g (a)}

τ

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^{M A P_W S}$
MAP_ELEMENT_SIZE: 儲存地圖的單位變數 bits 數量，為
$2^{M A P_E L E M E N T_W S}$
OBSTACLES_PER_ELEMENT: 每個單位變數能夠儲存的 obstacle 數量，為
$\frac{M A P_E L E M E N T_S I Z E}{O B S T A C L E_S I Z E}$
ELEMENTS_PER_ROW: 儲存每個橫軸 (X軸) 所需要的變數數量，為
$\frac{M A P_X}{O B S T A C L E S_P E R_E L E M E N T}$
OBSTACLE_MASK: 單一個 obstacle 的 bit mask ，用來取得單一 obstacle 的 filter，為
$2^{O B S T A C L E_S I Z E} - 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:

i n d e x = t i l e Y \times E L E M E N T S_P E R_R O W + \frac{t i l e X}{O B S T A C L E S_P E R_E L E M E N T}

接下來要從每個變數中取得對應於目前 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;
}

這邊為了保留原本的 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};

根據前述 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

原圖 (64x64 bmp)	8 bits texture
Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →

原圖 (64x64 bmp)	16 bits texture
Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →

遊戲體驗加強

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

我在 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() 中，我發現若要沿用上一次的結果，大部分參數都不需要重新計算，唯一要注意的是

(t i l e X, i n c e p t i o n Y)

與

(i n c e p t i o n X, t i l e Y)

的資料更新，因此，我將大部分參數設定為 static 並用 keepGoing 決定要不要計算初始值

(s t a r t D e l t a X, s t a r t D e l t a Y)

設定為 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 可以設計為重複的工作，只是範圍不太一樣而已。

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;
}

透明的方法就是保留原本一半的顏色，混入被遮蓋物體一半的顏色:

{\begin{array}{lr} B_{k + 1} = \frac{1}{2} B_{k} + \frac{1}{2} C_{k} \\ B_{0} = 0 \end{array}

$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;
    ...
};

效果:

破壞場景

增強遊戲體驗

關於 Z 軸的可能性

好像，沒有這個可能

ray 會穿透牆壁背後，也就是 traceFrame() 裡面的 sso 範圍會有好幾個，也很難判斷什麼時候要停。
頂部的 texture 要包含 X 方向 offset
從最近開始 (螢幕下方) 直到撞到邊屆為止

2020q3 render

tags: sysprog

遊戲方法

特殊函數筆記

程式原理分析

Overview

Map

圖片大小的線索：

更有彈性的寫法：

Texture

Coordinate System

Raycasting Procedures

Assumption:

Procedures

TraceFrame()

Trace()

Function Objective

設定 Field Of View (FOV)

計算畫面中障礙物的高度

texture rendering

原程式碼中的運算缺失

screenY overflow

鋸齒畫面

修正

消除魚眼

魚眼修正的加速

raycaster_float.cpp

Distance()

Function Objective

Simplifying the calculation of startDelta

Fixed point implementation

定點數運算

數字系統

angle

角度表示範圍與誤差

極值

誤差

討論與比較

無號乘法 MulU()

有號乘法 MulS()

AbsTan()

invert

乘 MulTan()

CalculateDistance()

New Features

Performance Estimation

Exponential Filter

Multi obstacles

修改地圖儲存方式 g_map32

新地圖的牆壁判斷 IsWall()

不同碰撞情況的表示方式

多種 texture

32 bits color encode to 16 bits color

16 bits color decode to 32 bits color

texture mapping

效果比較

遊戲體驗加強

顯示槍枝

Gun Side view

Arming point

Moving

Gun Center view

碰撞

透明牆壁

Allow the ray keep going

Rendering apparent walls

God mode

破壞場景

增強遊戲體驗

關於 Z 軸的可能性

Read more

Writing Equations in Microsoft Publisher

陸軍餐盤

2020 KGHS i2trc2 Summary

Graph Theory

tags: `sysprog`

無號乘法 `MulU()`

有號乘法 `MulS()`

`AbsTan()`

乘 `MulTan()`

`CalculateDistance()`

修改地圖儲存方式 `g_map32`

新地圖的牆壁判斷 `IsWall()`