\documentclass[12pt]{article}
\usepackage{CJK}
\topmargin 0in
\headheight 0in
\headsep 0in
\textheight 9.5in
\textwidth 6.3in
\evensidemargin 0in
\oddsidemargin 0in
\parskip 0.2in
\begin{document}
\begin{CJK*}{Bg5}{ming}
\title{Game Programming 2006 Final Examination}
\author{R94922149 周恩冉}
\date{\today}
\maketitle
You should choose at least five questions to answer from the following seven questions: (5/7)
\begin{enumerate}

% #1
\item Please describe the major processes of game development pipeline.

本題未作答。

% #2
\item What are the three layers of motion behavior?

%slide 11 page 58
\begin{description}
\item[Action selection]先決定角色要做什麼動作（例如，走到某個位置），可能是\ game AI engine 決定的，或是根據\ script 檔，或是使用者決定的等等。
\item[Steering]這階段會根據目前的行為（例如：seek, flee, \dots）決定移動的路線，可能需要作\ path finding 之類的工作。
\item[Locomotion]這階段會依據角色的物理結構決定\ model 的細部狀態、將角色轉向或移動、播放動畫，這部份主要由\ game engine 完成。
\end{description}

% #3
\item Please describe the three major types of character format used in real-time 3D games and analyze their pros and cons.

本題未作答。

% #4
\item Please describe the three basic culling techniques for improving the 3D rendering performance.

% slide 12 page 11
\begin{description}
\item[Visibility culling]不在視角內的東西不用\ render.
\item[Backface culling]只\ render 東西面對攝影機的一面，背面不用\ render.
\item[Occlusion culling]被別的東西遮住的部份不用\ render.
\end{description}

% #5
\item What are the AABB and OBB? Please describe the their differences in usage.

% slide 6 page 18
AABB (Axis-Aligned Bounding Box) 與\ OBB (Oriented Bounding Box) 是兩種決定\ bounding box 的原則，其中：
\begin{description}
\item[AABB]Bounding box 是可包住物體的最小長方體，其中長方體的每個邊都各與某個座標軸平行。
\item[OBB]與\ AABB 類似，但去掉長方體的邊與座標軸平行的限制。
\end{description}

在使用上\ AABB 建構相當容易，只需找到物體三個軸的範圍就可以了，做碰撞偵測時計算量也很少，只需判斷其中其中一個\ bounding box 的頂點是否在另一個\ bounding box 內就可以了。OBB 在建構時需較多計算才能找到\ bounding box, 在碰撞偵測時則需判斷其中一個\ bounding box 的邊是否與另一個\ bounding box 的面有相交。因此不論是在建構或是碰撞偵測，OBB 的計算都較為複雜、耗時。

但\ AABB 是\ OBB 的一個特例，因此\ OBB 在碰撞偵測的判斷上較為準確，特別是物體有一個明顯較長的軸且不與任何一個座標軸平行的時候，AABB 誤判的機會較高。

% #6
\item Please write down the A* algorithm.

% slide 11 page 22
\begin{enumerate}
\item $Q$ 為一空\ priority queue, 紀錄目前待走訪的\ node, key 為\ node, value 為該\ node 預估到目標所需的\ cost.
\item $T$ 為一空\ set, 紀錄已走訪過的\ node.
\item 把\ root node $r$ 放進\ priority queue $Q$ 中，value 為\ $r$ 到目標的估計\ cost.
\item 當\ $Q$ 未空時取出一個\ node $n$, 已空則跳至\ (l)
\item 若\ $n$ 已經是目標了，則建構出\ $n$ 的\ path 並傳回搜尋成功\。 
\item 令\ $N$ 為\ $n$ 的\ children nodes, 對每個\ $N_i \in N$ 做以下動作，結束後跳至\ (j)
\item 計算\ $N_i$ 到\ $r$ 的\ cost $C$, 若\ $C$ 大於同一個\ node（在\ $Q$ 或 $T$ 中）到\ $r$ 已知的\ cost 則忽略不處理，回到\ (f) 繼續下一個\ child node.
\item 若\ $N_i$ 在\ $T$ 中，自\ $T$ 中移除。
\item 估計\ $N_i$ 到目標的\ cost $E$, 將\ $N_i$ 加入\ $Q$ 中，value 為\ $C + E$, 若\ $N_i$ 已經存在\ $Q$ 中，則更新\ value 即可，不必重複加入。
\item $n$ 放入\ $T$ 中。
\item 回到\ (c)
\item 若\ $Q$ 已空，但仍未回傳成功\，則回傳搜尋失敗。
\end{enumerate}

% #7
\item Please describe the following three common processing models of FSMs in game AI applications.

% slide 11 page 47
\begin{description}
\item[Polling]每個\ frame 或以固定的頻率檢查各個\ FSM 是否符合轉到下一個\ state  條件。這樣的作法簡單、直覺但較浪費時間。
\item[Event-driven]每個\ FSM 可以\ subscribe 自己有興趣的事件，當事件發生時\ game engine 可通知其相關的\ FSM 進行狀態轉移。每個\ FSM 只會處理跟自己有關的事件，較\ polling 有效率。
\item[Multi-thread]每個\ FSM 都自己跑成一個\ thread, game engine 本身也是一個\ thread.  各個\ FSM 可同時且獨立地對目前環境做出反應，用\ FSM 控制角色時清晰且簡單，但缺點是\ thread 間時必須處理的同步以及溝通問題，相當複雜。
\end{description}

\end{enumerate}
\end{CJK*}
\end{document}