遊戲編程算法與技巧

《遊戲編程算法與技巧》一書原作者 Sanjay Madhav，中文版由劉瀚陽譯，電子工業出版社2016年11月出版

基本介紹

• 書名：遊戲編程算法與技巧
• 作者：【美】Sanjay Madhav
• ISBN：978-7-121-27645-3978-7-121-27645-3
• 頁數：296
• 定價：89.00
• 出版時間：2016年10月
• 開本：296

內容提要

《遊戲編程算法與技巧》介紹了大量今天在遊戲行業中用到的算法與技術。《遊戲編程算法與技巧》是為廣大熟悉面向對象編程以及基礎數據結構的遊戲開發者所設計的。作者採用了一種獨立於平台框架的方法來展示開發，包括2D 和3D 圖形學、物理、人工智慧、攝像機等多個方面的技術。《遊戲編程算法與技巧》中內容幾乎兼容所有遊戲，無論這些遊戲採用何種風格、開發語言和框架。

《遊戲編程算法與技巧》的每個概念都是用C#、Java 或C++ 程式設計師直觀明白的偽代碼闡述的，並且這些偽代碼都已被作者改進和驗證過。《遊戲編程算法與技巧》中每章末均配有習題或練習，以幫助讀者對所學內容進行鞏固。《遊戲編程算法與技巧》最後，作者詳細分析了兩款完整的遊戲，清楚展現了前面章節講到的很多技術和算法。

目錄

第1 章遊戲編程概述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

遊戲編程的發展2

Atari 時期（1977—1985 年）2

NES 和SNES 時期（1985—1995 年）3

PS 和PS2 時期（1995—2005 年）3

Xbox360、PS3 和Wii 時期（2005—2013 年）3

遊戲的未來4

遊戲循環4

傳統的遊戲循環4

多執行緒下的遊戲循環6

時間和遊戲8

真實時間和遊戲時間8

通過處理時間增量來表示遊戲邏輯8

遊戲對象10

遊戲對象的類型10

遊戲循環中的遊戲對象11

總結13

習題13

相關資料14

遊戲編程的發展14

遊戲循環14

遊戲對象14

第2 章2D 圖形. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2D 渲染基礎16

CRT 顯示器基礎16

像素緩衝區和垂直同步17

精靈18

繪製精靈18

動畫精靈20

精靈表單23

滾屏24

單軸滾屏24

無限滾屏26

平行滾屏27

四向滾屏28

磚塊地圖29

簡單的磚塊地圖29

斜視等視角磚塊地圖31

總結32

習題32

相關資料33

Cocos2D 33

SDL 33

第3 章遊戲中的線性代數. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

向量35

加法36

減法37

長度、單位向量和正規化38

標量乘積39

點乘40

問題舉例：向量反射41

叉乘43

問題舉例：旋轉一個2D 角色45

線性插值46

坐標系47

矩陣48

加法/減法48

標量乘法49

乘法49

逆矩陣50

轉置50

用矩陣變換3D 向量51

總結52

習題52

相關資料53

第4 章3D 圖形. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

基礎55

多邊形55

坐標系55

模型坐標系56

世界坐標系56

視角/攝像機坐標系60

投影坐標系62

光照與著色64

顏色64

頂點屬性65

光照67

Phong 光照模型68

著色70

可見性71

再探畫家算法72

深度緩衝區73

再探世界變換74

四元數75

3D 遊戲對象的表示77

總結77

習題77

相關資料78

第5 章遊戲輸入. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

輸入設備80

數字輸入80

模擬輸入82

基於事件的輸入系統84

基礎事件系統85

一個更複雜的系統87

移動設備輸入89

觸屏和手勢89

加速器和陀螺儀91

其他移動設備輸入92

總結92

習題92

相關資料93

第6 章聲音. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

基本聲音95

原始數據95

聲音事件95

3D 聲音98

監聽者和發射者98

衰減100

環繞聲100

數位訊號處理101

常見數位訊號處理效果102

區域標記102

其他聲音話題103

都卜勒效應103

聲音遮擋104

總結105

目錄xiii

習題106

參考資料106

第7 章物理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

平面、射線和線段108

平面108

射線和線段109

碰撞幾何體110

包圍球110

軸對齊包圍盒111

朝向包圍盒111

膠囊體112

凸多邊形113

組合碰撞幾何體113

碰撞檢測113

球與球的交叉113

AABB 與AABB 交叉114

線段與平面交叉115

線段與三角片交叉117

球與平面交叉119

球形掃掠體檢測120

回響碰撞124

最佳化碰撞125

基於物理的移動126

線性力學概覽127

可變時間步長帶來的問題128

力的計算128

歐拉和半隱式歐拉積分129

Verlet 積分法129

其他積分方法130

角力學130

物理中間件130

總結131

習題131

相關資料131

第8 章攝像機. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

攝像機的類型133

固定攝像機133

第一人稱攝像機134

跟隨攝像機134

場景切換攝像機135

透視投影135

視場136

寬高比137

攝像機的實現138

基礎的跟隨攝像機138

彈性跟隨攝像機139

旋轉攝像機142

第一人稱攝像機144

樣條攝像機146

攝像機支持算法149

攝像機碰撞149

揀選149

總結151

習題151

相關資料151

第9 章人工智慧. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

“真”AI 與遊戲AI 153

尋路153

搜尋空間的表示154

可接受的啟發式算法156

貪婪最佳優先算法157

A* 尋路161

Dijkstra 算法163

基於狀態的行為164

AI 的狀態機164

基礎的狀態機實現165

狀態機設計模式167

策略和計畫168

策略168

計畫169

總結170

習題170

相關資料172

通用AI 172

尋路172

狀態172

第10 章用戶界面. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

選單系統174

選單棧174

按鈕175

打字176

HUD 元素177

路點箭頭177

準心180

雷達181

其他需要考慮的UI 問題186

支持多套解析度186

本地化187

UI 中間件189

用戶體驗189

總結189

習題189

相關資料190

第11 章腳本語言和數據格式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

腳本語言192

折中192

腳本語言的類型193

Lua 194

UnrealScript 195

可視化腳本系統196

實現一門腳本語言197

標記化197

正則表達式198

語法分析199

代碼的執行和生成200

數據格式202

折中202

二進制格式203

INI 203

XML 203

JSON 204

案例學習：《魔獸世界》中的UI Mod 205

布局和事件205

行為206

問題：玩家自動操作206

問題：UI 兼容性206

結論207

總結207

習題207

相關資料208

第12 章網路遊戲. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

協定210

IP 210

ICMP 211

TCP 212

UDP 214

網路拓撲215

伺服器/客戶端216

點對點218

作弊219

信息作弊219

遊戲狀態作弊220

中間人攻擊220

總結221

習題221

相關資料222

第13 章遊戲示例：橫向滾屏者（iOS）. . . . . . . . . . . . . . . . . . . . . . . . . . 223

概覽224

Objective-C 224

Cocos2D 225

代碼分析226

AppDelegate 226

MainMenuLayer 227

GameplayScene 227

ScrollingLayer 227

Ship 228

Projectile 229

Enemy 229

ObjectLayer 229

練習230

總結231

第14 章遊戲示例：塔防（PC/Mac）. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

概覽233

C# 233

XNA 235

MonoGame 235

xviii 目錄

代碼分析236

設定236

單件236

遊戲類237

遊戲狀態237

遊戲對象238

關卡239

計時器239

尋路240

攝像機和投影241

輸入241

物理242

本地化242

圖形242

聲音243

用戶界面243

練習245

總結246

附錄A 習題答案. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

附錄B 對開發者有用的工具. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260