热度:6835℃
本文整理自知乎，文/我挑一些有趣的算法，希望尽量提及相关算法在游戏中的应用。光栅化 [1]：经典的绘画直线算法，后来还可以稍作修改用于绘画圆弧[2]，都不用三角函数或除数，只需用整数加法、减法和乘法。Perspective-Correct Texture Mapping [3]：透视正确的光栅化纹理贴图算法是1980才出现的。第一代Quake引擎引入后，才开始支持不垂直的墙、不水平的地面天花。（图片来自维基百科）Polygon Rasterization with Edge Function [4]：Bresenham算法如果用来画多边形，两个多边形的共边会被重绘。后来发明了使用简单的edge function去解决这个问题，而且适合并行的硬件实现。现在的GPU都是使用这个算法。全局光照Precomputed Radiance Transfer (PRT) with Spherical Harmonics（SH）[5]：储存静态环境对于各个方向光源的漫反射数据，可以实现动态低频光源的全局光照效果。这种表示方式非常神奇。Halo 3也使用到这种技术[6]。Screen-space Ambient Occlusion （SSAO）[7]：Crytek提出的首个屏幕空间环境光遮蔽算法，之后引来大量的研究及改进算法。也有用类似的概念去做近距离的反射，如SSDO[8]。Light Propagation Volume （LPV）[9]：Crytek提出的首个动态全局光照算法，不需要预计算。但要在体积数据中计算传播，性能较慢，所以之后再优化成 Cascaded LPV [10]。Voxel Cone Tracing [11]：也是不需要预计算的动态全局光照算法。把场景动态生成层阶式的体素数据（像mipmap那样的pre-filtering），从光源视角计算直接光照，然后逐像素追踪这组数据获取非直接光照。结果比LPV精确，也可以做到光泽反射（glossy reflection）。阴影Shadow Volume [12]：阴影体积是1977年发表的阴影技术，在屏幕空间光栅化阴影体积，可准确判断每个屏幕像素是否在阴影之内。可以处理平行光源和点光源的阴影。1991年[13]讲述如何用stencil buffer来实现此算法，适合在图形加速硬件（当时还没有所谓GPU）上使用。但很多人发现，如果摄像机在阴影体积内，就会出错。在年有多人发现一种解决方法，需要把John Carmack在2000年的电邮[14]中提及这个想法，后来成为2004年《毁灭战士3（Doom 3）》引擎的重要特徵，因他把这项技术发扬光大，即使他非首个发明人，此项技术通常被称为Carmack's Reverse。Parallel Split Shadow Map (PSSM) [15][16] / Cascaded Shadow Map（CSM）[17]：虽然Shadow Volume很吸引，但它需要大量的内存频宽，而且通常不能实现软阴影。后来大部分游戏改为使用Shadow Map（阴影贴图），这更适合GPU，并且可以通过多次采样（Percentage Closer Filtering, PCF）来实现软阴影。然而，阴影贴图也有许多问题，例如远近景物都采用同一张纹理，就会令到近景的精度不足，出现锯齿。2006年香港中文大学的博士生Fan Zhang等人发表了一种 PSSM 算法 [15]，为不同距离的场景渲染多张阴影贴图，在采样的时候按距离决定使用那一张。这个方法的变种CSM，在切割上和PSSM有点差异，被广泛使用于现时大部分游戏引擎中。Variance Shadow Map（VSM）[18]：之前谈到用PCF做软阴影，它的坏处就是要做多次采样。那么可否把阴影贴图直接模糊化来实现软阴影？答案是否定的。但是在2006年有学者发表了VSM，它是一种用统计方式来逼近软阴影的效果。参考：场景管理、： - Milo Yip 的回答Potential Visibility Set（PVS）Occlusion Culling by Software Rasterization动画/物理Particle SystemSmoothed Particle Hydrodynamics（SPH）Curl NoiseDual Quaternion Skinning碰撞测试（或称separating axis theorem/SAT）：凸形状相交测试的基本原理。中，其实背后也是使用了SAT。 (GJK距离算法)：计算两个凸形状的距离（可用于相交测试）：用于broad phase碰撞检测，找出物体AABB是否相交。对于时空上连续的物体运动，算法最坏O(n^2)、最好O(n)。人工智能A* path findingBehavior Tree*欢迎分享好的算法。参考[1] Bresenham, Jack E. &.& IBM Systems journal 4.1 (1965): 25-30.&[2] Bresenham, Jack. &.& Communications of the ACM 20.2 (1977): 100-106.&[3] Catmull, Ed, and Alvy Ray Smith. &.& ACM SIGGRAPH Computer Graphics. Vol. 14. No. 3. ACM, 1980.&[4] Pineda, Juan. &.& ACM SIGGRAPH Computer Graphics. Vol. 22. No. 4. ACM, 1988.[5] Sloan, Peter-Pike, Jan Kautz, and John Snyder. &.& ACM Transactions on Graphics (TOG). Vol. 21. No. 3. ACM, 2002.&[6] Chen, Hao, and Xinguo Liu. &.& ACM SIGGRAPH 2008 Games. ACM, 2008.&[7] Mittring, Martin. &.& ACM SIGGRAPH 2007 courses. ACM, 2007.&[8] Ritschel, Tobias, Thorsten Grosch, and Hans-Peter Seidel. &.& Proceedings of the 2009 symposium on Interactive 3D graphics and games. ACM, 2009.&[9] Kaplanyan, Anton. &.& ACM SIGGRAPH Courses 7 (2009): 2.&[10] Kaplanyan, Anton, and Carsten Dachsbacher. &.& Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games. ACM, 2010.&[11] Crassin, Cyril, et al. &.&Computer Graphics Forum. Vol. 30. No. 7. Blackwell Publishing Ltd, 2011.&[12] Crow, Franklin C. &.& ACM SIGGRAPH Computer Graphics. Vol. 11. No. 2. ACM, 1977.&[13] Heidmann, Tim. &Real shadows, real time.& Iris Universe 18 (1991): 28-31.[14] Carmack, John, &&, 23 May 2000.&[15] Zhang, Fan, et al. &Parallel-split shadow maps for large-scale virtual environments.& Proceedings of the 2006 ACM international conference on Virtual reality continuum and its applications. ACM, 2006.[16] Zhang, Fan, Hanqiu Sun, and Oskari Nyman. &Parallel-split shadow maps on programmable gpus.& GPU Gems 3 (2007): 203-237. GPU Gems 3 - Chapter 10. Parallel-Split Shadow Maps on Programmable GPUs[17] Dimitrov, Rouslan. &.& Developer Documentation, NVIDIA Corp (2007).&[18] Donnelly, William, and Andrew Lauritzen. &.&Proceedings of the 2006 symposium on Interactive 3D graphics and games. ACM, 2006.&
开发者交流群：3467414
(加群请输入:来自苹果i派党)
开发者服务游戏编程算法与技巧
Sanjay Madhav
本书围绕程序设计典型算法，精心编织了一个扣人心弦又趣味横生的侦探缉凶故事。小说主人公运用高超的搜索技巧和精深的算法知识，最终识破阴谋、缉拿元凶。其间，用二分搜索...
本书介绍在互联网行业中经常涉及的算法，包括排序算法、查找算法、资源分配算法、路径分析算法、相似度分析算法，以及与机器学习相关的算法，包括数据分类算法、聚类算法、...
这是一本非常有趣的编程启蒙书，全书从中小学生的角度来讲述，没有生涩的内容，取而代之的是生动活泼的漫画和风趣幽默的文字。并配合超萌的编程软件，从开始学习与计算机对...
梳理了阿里巴巴校园招聘笔试题集、主要技术领域业务点和亟待解决的难点、阿里巴巴技术岗位校招人才需求等信息。主要面向在校学生的可读性书籍，以传播阿里巴巴乃至中国互联...
本书介绍了若干常见算法，既包括排序、哈希等基础算法，也包括无约束优化、插值与拟合等数值计算方法。本书在介绍算法的同时，结合了作者自己对数学背景、应用场景的理解，...
本书共分为12个章节，首先介绍了一些基础的数据结构，以及常用的排序算法和查找算法；其次介绍了两个稍微复杂一些的数据结构——树和图，还介绍了每种数据结构和算法的适...
本书详细综述了应用在许多重要视频游戏编程中的算法和技术。书中采用了一种独立于平台和结构的方法，能协助开发几乎任何风格、语言和框架的游戏，并展现2D和3D图像、物理、人工智能、相机等工作的基本技术。书中的每个概念都是用C#、Java或 C++程序员直观明白的伪代码阐述的，并且作者已经改进和证实过这些伪代码。本书最后作者详细分析了两个完整的游戏，清楚展现了前面章节讲到的很多技术和算法。
腾讯专家倾情翻译，全面介绍游戏行业中会用到的算法和技术，专注于实际应用
当瀚阳让我为他的译作作序的时候，我还是有些吃惊的。我并非业界名人，虽然在游戏行业摸爬滚打了十几年，但并没有多少建树，为了配得上译者所散发出的光芒，我多少也要发掘出自己的一些亮点。如果资历也算亮点的话，我倒是有些的。1993 年我有了自己的第一台电脑，那时的电脑还处于386 的时代，硬盘不过200MB，内存不过4MB，用着5 英寸的软驱，光驱还在萌芽状态。当时我一心想做游戏，玩着《Wolf3D》、《Doom》，仰望着id Soft的成就。2001 年我终于如愿进入了游戏行业，有幸赶上了西山居《月影传说》的后期开发。之后在三大游戏公司转了一圈，如今沉浮于手机游戏开发的大潮中。其间也曾参与了两款3D引擎的早期开发工作，其中的成果已融合在两三款早已上市的游戏当中。我参与程度最深，也算稍微有点名气的游戏就是《斗战神》了。
我和瀚阳相识缘于我们现在共同参与的这个项目，我是项目的第一个客户端程序员，瀚阳是第二个。当项目还只有我一个前台程序员的时候，我一个人要面对十几个美工产出的资源和四五个策划提出的需求，真是压力很大。瀚阳的加入仿佛给项目增加了第二台引擎，各种架构迅速完善起来，功能也越来越完整，项目顺利度过了Demo 期，得以立项。瀚阳在游戏开发方面涉猎广泛，精通多种语言，做过端游，写过手游，参与过3D 引擎开发。游戏开发之外瀚阳也有着广泛的兴趣，他的博客就是自己搭建的，跑在租用的服务器上，可以称得上是全栈程序员。游戏行业加班是出了名的，对于瀚阳能在繁忙的工作之余抽出时间来翻译这本书，我是十分佩服的，每一个程序员都不应该局限于自己所在的公司与工作，而应该在更广阔的空间拓展自己的职业生涯。
最后回到本书。如果你想进入游戏开发行业，或者对于游戏开发你已经入门但还缺乏一个全面的了解，本书可以作为不错的入门书籍。本书读起来不会那么累，能够使你快速了解游戏开发所涉及的众多领域，建立一个较为全面的认识。在此之后你可以针对感兴趣的方面购买学习更加深入的书籍。
腾讯互娱前台程序技术指导
陈鹏译者序我与本书的一些缘分
我自己是多年的玩家了。在中学时期就暗自下定决心，一定要做游戏。于是不顾反对，大学选择了游戏专业，后来通过一套类似XNA 的框架进行开发，在学习的过程中一边写游戏，一边扩展框架。从最初的使用DirectX 绘制2D 精灵开发俄罗斯方块，到写3D 骨骼蒙皮动画做3D 射击游戏，慢慢地学会了很多技术，比如AI、网络、物理、脚本等。这些知识是“成长”起来的，于是每学到一点新技术都可以往里面塞，逐渐地形成了自己系统的理解。
雕爷有一篇文章说的好，临摹是最好的学习方法。因为临摹不仅需要你拆解分析对象作为输入，还需要以自己的理解作为输出。这种带着主动思考的输入/输出，无形中就对临摹对象有了深刻的理解，这不是走马观花那种被动的学习效率能比拟的。这种经过充分思考的练习，最能够将知识“内化”，而只有站在前人的基础之上，创新才会比较靠谱。在我看来，本书的内容，属于手把手地对各种GamePlay 拆解，然后实现，让知识一点一点地成长起来。更加难得的是，因为作者从业界转向了教育界，所以本书不仅内容上系统全面，而且语言上简单清晰，让人易于理解。
兴趣是最好的老师，GamePlay 不像操作系统、渲染引擎、物理引擎那么“枯燥”，本书可以很轻松就读完。初学者完全可以从GamePlay 入手，在XNA 框架上实现书中的内容，然后在深入的过程中补全游戏开发中各个系统的知识。而有经验者也可以从本书中补全对游戏软件的系统理解，比如一开始作者就阐明了游戏程序的三要素：游戏时间、游戏对象、游戏循环，还有一些有意思的诀窍，比如用xyzzy 口诀记住叉乘运算，也有一些案例分析——《魔兽世界》的UI 插件系统，以及工作中的教训——《指环王》中音频引擎的设置。
除此之外，本书还提供了专业方向上的参考资料，让读者在感兴趣的话题上深入学习。每章都会提出关键问题并列出有深度的参考资料，这些资料大部分是行业经典，比如像《游戏引擎架构》、Real-Time Rendering 这样的神作当然没有错过。
游戏行业是一个很有意思、充满朝气的行业，有很多真正热爱游戏的人。当然，同时有很多问题，但这何尝不是机会呢？
刘瀚阳前言
不久之前，开发商业游戏的知识还只有少数游戏界精英才知道。在那时候，学习真正用于AAA 游戏的算法就像学习一些黑暗禁忌的魔法一样（比如Michael Abrash 的Graphics ProgrammingBlack Book）。如果一个人想要接受游戏编程教育，那么只能去为数不多的培训学校。可是10 多年过去之后，游戏编程教育发生了非常大的变化。现在一些顶尖的大学也提供了游戏编程的课程和学位，而且每年加入这个领域的人数也越来越多。
游戏开发课程爆发的结果就是，游戏产业更容易招到需要的人员。21 世纪早期的时候，大多数想参与游戏开发的年轻人都拥有着很强的计算机科学背景及创造游戏的热情。这些有着良好基础的年轻人，会在后续工作中不断学习更加高级的游戏编程技巧。今天，有了更多的专注于游戏教育的地方，大量的游戏公司希望他们的年轻程序员可以拥有游戏编程相关的丰富阅历。为什么需要这么一本游戏编程的书
游戏课程的增长也激发出大学课程设计的需求。可是现在市场上大多数的书都只面向两种读者：希望利用业余时间做点小游戏的爱好者和有着多年经验的专业人员。两种书都会让在校学生感到迷惑。爱好者系列图书不够系统严谨，太过专业的书学生又看不懂。
我在南加利福尼亚大学讲的其中一门课程是ITP 380：游戏编程。课堂上的学生大多数都是大二或者大三的，懂一点编程。有些学生已经能很熟练地运用GameMaker 或者Unity 开发游戏原型了。但ITP 380 是学生们第一门正式的游戏编程课程。我希望本书能够成为这种课程的最佳补充。虽然受众是在校学生，但是其他对游戏编程感兴趣的人也能获得很大价值。
本书的一个特色就是前12 章与任何平台和框架无关。这就是说，本书适用于大部分语言和平台。这与市场上其他书籍不一样，那些书往往因为适用某个版本的框架导致几年之后就没用了。正因为这种独立性，本书将会长期适用。这对大学课程设置来说很有帮助，因为他们运用不同的开发框架和语言。这就是说，示例代码总是有价值的。也因此，最后两章会使用两种不同的框架去开发游戏，之前的示例代码会在这些游戏上体现。谁应该读这本书
本书认为读者已经掌握一门面向对象编程语言（C++、C#、Java），同时也能熟练运用各种数据结构，比如链表、二叉树及哈希表。这些内容通常在计算机科学的前两个学期就会学到，因此对于那些已经完成这些课程的人来说阅读本书是没问题的。更进一步来讲，如果能够掌握微积分，那么后面的线性代数和物理章节读者会更容易理解。
虽然不是必需的，但如果读者提前掌握了基础的游戏策划或者有熟悉的游戏会有不少帮助。同时，本书会专门讨论某种特定的编程机制，所以阅读参考资料会有更多收获。有过GameMaker 制作游戏原型经验的话会更好，但仍然不是必需的。
虽然本书意在为学校而写，但是对于已经掌握了通用编程技巧而又对游戏专业感兴趣的人来说，会很有帮助。不像一些学院派的理论书籍，书中的话题总是通过例子形象地展开。
最后，因为本书涵盖非常多话题，对希望掌握游戏编程多个方面的人来说也很有帮助。还有一点需要说明，资深游戏开发者不会在本书中找到太多的最新技术。本书是怎么组织的
本书的前12 章在游戏实战中演示了许多算法与技术。这些话题涵盖2D 到3D、物理学、人工智能、摄像机等。虽然设计上第1 章到第12 章是顺序阅读的，但是有些章节可以直接阅读。图P.1 把各章节的依赖关系罗列了出来。所以，最好先阅读依赖章节。
最后两章的游戏示例是为了运用前面12 章所学到的算法和技术。两个示例游戏分别是2D滚轴iOS 游戏（用Objective-C 在Cocos2D 上开发）和PC/Mac/Linux 平台的3D 塔防游戏（用C# 在XNA/MonoGame 上开发）。两个游戏的源码可以在本书的网站上下载：http://gamealgorithms.net。本书演示风格
这节讲本书的一些演示约定，比如代码和公式。侧边栏和注意
在本书某些位置你能看到一些“侧边栏”和“注意”版块，像下面这样。（图P.1
前12 章的依赖关系）侧边栏
在侧边栏中，会讨论某些运用在某款游戏中特定的算法和技术。有时候会是一些我所开发的游戏中的趣闻轶事，也有时候会是其他游戏的。不管怎样，这里会更加深入地讨论这些在真实游戏开发中会遇到问题的概念。注意
注意里更多的是不相关的有趣内容。虽然它们不是那么相关，但可能会让我们对话题有更加深刻的认识。伪代码
为了保持语言的中立性，算法已经以伪代码的形式展现。伪代码的语法与Lua 比较近似，虽然也有点像C++ 和C#。代码展示会像这样：function Update(float deltaTime)
foreach Object o in world
o.Update(deltaTime)
代码高亮与IDE 近似。关键词用蓝色，注释用绿色，类名用蓝绿色，变量用斜体。在所有的示例中，访问都是通过点成员方法和变量实现的。
有些情况下，代码要被多次讨论。在这种情况下，展示的不是代码的最终版本。通常最后会将所有代码再展示一次，像清单P.1 那样。清单P.1 示例代码清单function Update(float deltaTime)
foreach Object o in world
if o is alive
o.Update(deltaTime)
注意，上面伪代码中简单地检查Object“is alive”，而不是直接调用某个函数。这样写会更加清晰。
还有就是，一些代码可能会由于篇幅原因省略。通常是由于前面刚演示过，中间有大段重复的部分，我们用省略号替代。function Update(float deltaTime)
// 更新代码
...end公式
一些章节（主要是线性代数、3D 渲染、物理学）会通过公式来解释。这么做会比使用伪代码更加清晰易懂。公式会居中处理如下：
?? (??) = ?? + ??本书网站
本书的网站是http://gamealgorithms.net，内含第13 章和第14 章中游戏的源码及本书的勘误。最后，网站中有一个论坛，读者可以上去提与本书内容或游戏编程相关的问题。
游戏编程概述1
游戏编程的发展2
Atari时期（年） 2
NES和SNES 时期（年） 3
PS和PS2时期（年） 3
Xbox360、PS3和Wii时期（年） 3
游戏的未来4
传统的游戏循环4
多线程下的游戏循环6
时间和游戏8
真实时间和游戏时间8
通过处理时间增量来表示游戏逻辑8
游戏对象10
游戏对象的类型10
游戏循环中的游戏对象11
相关资料14
游戏编程的发展14
游戏循环14
游戏对象14第2章
2D 图形 15
2D渲染基础16
CRT显示器基础16
像素缓冲区和垂直同步17
绘制精灵18
动画精灵20
精灵表单23
单轴滚屏24
无限滚屏26
平行滚屏27
四向滚屏28
砖块地图29
简单的砖块地图29
斜视等视角砖块地图31
相关资料33
Cocos2D 33
SDL 33第3章
游戏中的线性代数 34
长度、单位向量和正规化38
标量乘积39
问题举例：向量反射41
问题举例：旋转一个2D 角色45
线性插值46
加法/减法48
标量乘法49
用矩阵变换3D 向量51
相关资料53第4章
模型坐标系56
世界坐标系56
视角/摄像机坐标系60
投影坐标系62
光照与着色64
顶点属性65
Phong光照模型68
再探画家算法72
深度缓冲区73
再探世界变换74
3D游戏对象的表示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　习题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　　Lua194　　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　代码分析236　　设置236　　单件236　　游戏类237　　游戏状态237　　游戏对象238　　关卡239　　计时器239　　寻路240　　摄像机和投影241　　输入241　　物理242　　本地化242　　图形242　　声音243　　用户界面243　练习245　总结246附录A 习题答案247附录B 对开发者有用的工具260
小编说：寻路就是一个看似简单问题的解：给定点A 和B，AI 该怎么智能地在游戏世界中行走？这个问题的复杂来自于实际上A 和B 之间存在大量的路径可走，但只有一条是最佳的。只是找到一条两点之间的有效路径是不够的。理想的寻路算法需要查找所有...
版权所有& · 北京博文视点资讯有限公司 · All Rights Reserved
京ICP备号-1
出版物经营许可证 新出发 京零字 第 丰140025号概述/游戏核心算法编程内幕
——图书作者：
总策划 （） 编著 邱仲潘 译 爱亿尔（北京）国际游 出版社：&&环境科学出版社 希望电子出版社 ISBN：&& 出版时间： 版 印刷时间：&&次印刷 开 本： 16 价 格(元)：&&58 本书特点 *经过时间测试的编码技术与算法，而不是趋势性的方法或对单个API的介绍。 *C++完整代码样本，用于OpenGL与DirectX APIs中。 *代码设计与布局方法。数据结构、算法和游戏特定设计模式。 *人工智能技术，包括面向动作AI、战术AI以及，都用Java和Lua编写脚本。 *网络编程，从简单游戏到大量用户多方游戏。 *二维编程，分析Maria Bras与Zelda等经典游戏的算法，研究经典二维特效。 *三维管道，包括分析几何处理、选取、剪取、遮挡探测和细节量技术。 本书适用于： ?游戏工程中的研发人员 ?游戏编程的业余爱好者 ?仅想更好地理解所玩游戏信息的人 本书主要介绍市面上大多数计算机与视频游戏编程的基本核心算法与技术，以及游戏编程理论和许多PC与控制台上的AAA级产品的实现细节，使之成为游戏编程导论课程教材。书中大多数相关方法都有全面解释、框图和必要的代码样本，使读者可以了解幕后工作原理、工作方法和工作本质。 全书由三部分组成。其中第一部分主要介绍游戏编程的基本概念；第二部分详细介绍游戏编程中的各种技术和算法；第三部分是附录，介绍游戏编程中相关技术和知识以及其他相关读物。
目录/游戏核心算法编程内幕
第一部分 游戏编程&&第1章 游戏编程时间表&&1.1 第一阶段：“星球大战”之前&&1.2 第二阶段：从“星球大战”到Atari&&1.3 第三阶段：游戏控制台与个人计算机&&1.3.1 游戏控制台与游戏开发人员&&1.3.2 个人计算机&&1.4 第四阶段：调整与汇总&&1.5 第五阶段：游戏引擎的出现&&1.6 第六阶段：手指式革命&&1.7 第七阶段：移动现象&&1.8 第八阶段：多方游戏&&1.9 结束语&&第2章 游戏体系结构&&2.1 实时软件&&2.2 游戏逻辑段&&2.2.1 玩家更新&&2.2.2 世界更新&&2.3 显示段&&2.3.1 世界绘制&&2.3.2 NPC绘制&&2.3.3 玩家&&2.3.4 问题：网络游戏&&2.4 编程过程关卡&&2.5 结束语&&第3章 数据结构与算法&&3.1 类型、结构和类&&3.2 数据结构&&3.2.1 静态数组&&3.2.2 链表&&3.2.3 双向链表&&3.2.4 队列&&3.2.5 堆栈&&3.2.6 双头队列&&3.2.7 表&&3.2.8 树&&3.2.9 &&3.2.10 图&&3.3 标准模板库&&3.3.1 容器&&3.3.2 迭代器&&3.4 结束语&&第4章 设计模式&&4.1 设计模式定义&&4.2 一些重要编程模式&&4.2.1 单体模式&&4.2.2 策略模式&&4.2.3 工厂模式&&4.2.4 空间索引&&4.2.5 复合模式&&4.2.6 轻量级模式&&4.3 可用性模式&&4.3.1 屏蔽模式&&4.3.2 状态模式&&4.3.3 自动方式取消&&4.3.4 磁化&&4.3.5 焦点模式&&4.3.6 进程模式&&4.4 结束语&&第5章 用户输入&&5.1 键盘&&5.2 鼠标&&5.3 游戏杆&&5.4 硬件抽象&&5.5 力量反馈&&5.6 结束语&&第6章 基本人工智能技术&&6.1 情境&&6.2 人工智能系统结构&&6.2.1 感知世界&&6.2.2 记忆&&6.2.3 分析/推理核心&&6.2.4 动作/输出系统&&6.3 特定技术&&6.3.1 有限状态机&&6.3.2 规则系统&&6.3.3 规划与解题&&6.3.4 生物灵感人工智能&&6.4 结束语&&第7章 面向动作的人工智能&&7.1 动作游戏&&7.2 动作设计人工智能&&7.3 对象跟踪&&7.3.1 眼睛接触:二维半平面测试&&7.3.2 三维版本：半球&&7.4 追赶&&7.4.1 二维追赶：固定速度&&7.4.2 预测性追赶&&7.5 逃避&&7.6 巡逻&&7.7 隐藏与遮盖&&7.8 射击&&7.8.1 无限速度瞄准&&7.8.2 实际瞄准&&7.8.3 机关枪&&7.9 综合起来&&7.9.1 并行自动化&&7.9.2 AI同步&&7.10 结束语&&7.10.1 平台游戏&&7.10.2 射击游戏&&7.10.3 格斗游戏&&7.10.4 赛车游戏&&第8章 战术性人工智能&&8.1 战术性思维&&8.1.1 路径寻找&&8.1.2 团队活动&&8.2 军事分析：影响图&&8.2.1 数据结构&&8.2.2 一些重要测试&&8.3 表示战术&&8.4 结束语&&第9章 脚本&&9.1 建立脚本语言&&9.1.1 简单分析语言&&9.1.2 分析结构化语言&&9.2 嵌入语言&&9.2.1 学习Lua&&9.2.2 Java脚本&&9.3 基于套接的脚本&&9.4 结束语&&第10章 网络编程&&10.1 Internet的实际工作&&10.2 从编程人员角度看套接&&10.3 客户机&&10.3.1 简单TCP客户机&&10.3.2 简单UDP客户机&&10.4 简单TCP服务器&&10.5 多客户机服务器&&10.5.1 并发的器&&10.5.2 迭代的面向连接服务器&&10.6 UDP服务器&&10.7 防止套接受阻&&10.8 设计客户机/服务器游戏&&10.9 大量用户的多方游戏&&10.9.1 数据外推&&10.9.2 层次消息&&10.9.3 空间分割&&10.9.4 只发送状态改变&&10.9.5 使用&&10.9.6 动态服务器与勇士综合症&&10.10 结束语&&第二部分 引擎编程&&第11章 二维游戏编程&&11.1 旧式硬件&&11.2 二维游戏的数据结构&&11.3 贴图矩阵地砖表&&11.4 二维游戏算法&&11.4.1 屏幕游戏&&11.4.2 双向与四向卷轴&&11.4.3 多方引擎&&11.4.4 视差卷轴&&11.4.5 各向异性引擎&&11.4.6 翻页卷轴&&11.5 特殊效果&&11.5.1 调色板效果&&11.5.2 点刻效果&&11.5.3 灰贴&&11.5.4 火&&11.6 结束语&&第12章 三维管道概述&&12.1 简介&&12.2 基本数据类型&&12.2.1 顶点&&12.2.2 索引图元&&12.2.3 颜色&&12.2.4 纹理贴图&&12.3 几何格式&&12.4 一般性图形管道&&12.4.1 剪取&&12.4.2 挑选&&12.4.3 闭合测试&&12.4.4 确定分辨率&&12.4.5 变换与灯光&&12.4.6 光栅化&&12.5 结束语&&第13章 室内绘制&&13.1 一般分析&&13.2 基于闭合的算法&&13.3 二叉空间划分算法&&13.3.1 构造&&13.3.2 视图相关排序&&13.3.3 层次式剪取&&13.3.4 闭合探测&&13.3.5 绘制&&13.4 门户绘制&&13.5 层次式闭合图&&13.6 混合方法&&13.6.1 门户/八叉树混合&&13.6.2 四叉树/BSP混合&&13.7 硬件辅助闭合测试&&13.8 结束语&&第14章 户外算法&&14.1 概述&&14.2 户外绘制的数据结构&&14.2.1 高度域&&14.2.2 四叉树&&14.2.3 二叉三角形树&&14.3 几何贴图&&14.4 ROAM&&14.4.1 第一遍：构造变差树&&14.4.2 第二遍：网格重构&&14.4.3 优化&&14.5 块LOD&&14.6 以GPU为中心的方法&&14.7 户外视景图&&14.8 结束语&&第15章 角色动画&&15.1 分析&&15.2 显式与隐式方法&&15.3 显式动画技术&&15.3.1 帧动画&&15.3.2 关键帧动画&&15.3.3 标记插值&&15.4 隐式动画概述&&15.4.1 &&15.4.2 框架动画的数学&&15.4.3 硬件辅助框架动画&&15.5 道具处理&&15.6 关于机车&&15.7 四肢分解&&15.8 面部动画&&15.9 逆向动力学&&15.9.1 分析逆向动力学&&15.9.2 派生&&15.10 混合正向与逆向动力学&&15.11 结束语&&第16章 制片术&&16.1 第一人称视角射击游戏&&16.2 处理惯性&&16.3 飞行模拟器与四元数&&16.4 第三人称视角镜头&&16.5 制片镜头：镜头样式&&16.6 制片镜头：位置算法&&16.6.1 选择镜头目标&&16.6.2 选择相关信息&&16.6.3 选择视图角度&&16.7 基于agent的方法&&16.8 结束语&&第17章 色档&&17.1 实际照明&&17.1.1 简单绘制方程&&17.1.2 按顶点与按像素照明&&17.2 灯光贴图&&17.2.1 扩散贴图&&17.2.2 镜面贴图&&17.2.3 使用灯光图的全局照明&&17.2.4 实现光贴图：DirectX&&17.2.5 用DirectX实现灯光贴图&&17.2.6 生成灯光贴图&&17.3 &&17.3.1 平均向量&&17.3.2 阴影&&17.4 非照片真实绘制&&17.4.1 铅笔绘制&&17.4.2 外形线绘制&&17.4.3 划线外形&&17.4.4 单帧色档&&17.4.5 油画绘制&&17.5 结束语&&第18章 纹理贴图&&18.1 纹理类型&&18.1.1 纹理贴图&&18.1.2 XYZ贴图&&18.1.3 圆柱贴图&&18.1.4 球形贴图&&18.1.5 三角形纹理贴图&&18.2 平铺与贴花&&18.3 过滤&&18.4 &&18.5 纹理优化&&18.5.1 纹理压缩&&18.5.2 纹理缓存与分页&&18.6 多遍方法&&18.7 多纹理&&18.8 纹理运算与组合&&18.9 细节纹理&&18.10 环境贴图&&18.11 鼓包贴图&&18.11.1 浮雕鼓包贴图&&18.11.2 Dot3鼓包贴图&&18.12 上光贴图&&18.13 结束语&&第19章 微粒系统&&19.1 微粒系统剖析&&19.2 微粒&&19.2.1 一般性微粒系统&&19.2.2 派生微粒&&19.2.3 微粒行为&&19.2.4 微粒消除&&19.2.5 绘制微粒&&19.3 关于体系结构&&19.4 加速技术&&19.4.1 避免内存分配与释放&&19.4.2 空间索引&&19.4.3 LOD微粒系统&&19.4.4 基于色档的微粒系统&&19.5 结束语&&第20章 有机构绘制&&20.1 自然与细节&&20.2 树&&20.2.1 告示牌&&20.2.2 基于图像方法&&20.2.3 平行方法&&20.2.4 正交IBR方法&&20.3 草&&20.3.1 分层草&&20.3.2 统计分法&&20.4 云&&20.4.1 天框与园顶&&20.4.2 招贴板云&&20.4.3 容积云&&20.5 海洋&&20.5.1 逼真海洋几何&&20.5.2 海洋外观&&20.5.3 焦散性&&20.6 结束语&&第21章 过程性技术&&21.1 过程性列表&&21.2 Renderman&&21.3 实时色档语言&&21.3.1 当前语言&&21.3.2 Cg&&21.3.3 HLSL&&21.3.4 GL2色档语言&&21.4 色档程序类型&&21.4.1 色档程序集合&&21.4.2 几何效果&&21.4.3 灯光&&21.5 纹理贴图&&21.6 微粒系统&&21.7 动画&&21.8 特殊效果&&21.9 结束语&&第22章 几何算法&&22.1 点包括测试&&22.1.1 球上的点&&22.1.2 AABB中的点&&22.1.3 凸多边形的点&&22.1.4 多边形的点（凹与凸）：约当法&&22.1.5 曲线定理&&22.1.6 凸实体的点&&22.1.7 实体的点（约当曲线定理）&&22.2 光束相交测试&&22.2.1 光束平面&&22.2.2 光三角形&&22.2.3 光AABB测试&&22.2.4 光球测试&&22.2.5 光凸形外壳&&22.2.6 光一般实体（三维DDA）&&22.3 运动测试&&22.4 点与三角形集合碰撞（基于BSP）&&22.5 网格与网格（清扫与修剪方法）&&22.6 计算凸形外壳&&22.6.1 二维方案&&22.6.2 三维方案&&22.7 三角形简化&&22.7.1 顶点重合&&22.7.2 边重合&&22.7.3 递进网格&&22.7.4 非保守式三角形简化&&22.8 结束语&&第三部分 附录&&附录A 性能调整&&附录B OpenGL&&附录C Direct3D&&附录D 数学知识&&附录E 更多读物& &
&|&相关影像
互动百科的词条（含所附图片）系由网友上传，如果涉嫌侵权，请与客服联系，我们将按照法律之相关规定及时进行处理。未经许可，禁止商业网站等复制、抓取本站内容；合理使用者，请注明来源于。
登录后使用互动百科的服务，将会得到个性化的提示和帮助，还有机会和专业认证智愿者沟通。
此词条还可添加&
编辑次数：4次
参与编辑人数：4位
最近更新时间： 08:58:12
贡献光荣榜}