游戏编程经典算法里面有哪些经典或者很酷的算法
点击联系发帖人
时间：2016-10-29 05:35
年后就要去xx公司做游戏开发惹。。有哪镇得住场游戏开发用得到的牛逼的算法没呢，比如A*寻路、指尖计算啥的~。~多多指教==&补充：：有米有paper或者book呢，高大上的最好
已出现卡马克大深度的平方根算法
我挑一些有趣的算法，希望尽量提及相关算法在游戏中的应用。&br&&br&&b&光栅化&/b&&br&&ul&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Bresenham%2527s_line_algorithm& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Bresenham's line algorithm&i class=&icon-external&&&/i&&/a& [1]：经典的绘画直线算法，后来还可以稍作修改用于绘画圆弧[2]，都不用三角函数或除数，只需用整数加法、减法和乘法。 &/li&&/ul&&img src=&/b7cb85217babb238ac6c_b.jpg& data-rawwidth=&592& data-rawheight=&401& class=&origin_image zh-lightbox-thumb& width=&592& data-original=&/b7cb85217babb238ac6c_r.jpg&&&br&&ul&&li&Perspective-Correct Texture Mapping [3]：透视正确的光栅化纹理贴图算法是1980才出现的。第一代Quake引擎引入后，才开始支持不垂直的墙、不水平的地面天花。&/li&&/ul&&img src=&/24681fdb28cfc1e4342f_b.jpg& data-rawwidth=&1000& data-rawheight=&352& class=&origin_image zh-lightbox-thumb& width=&1000& data-original=&/24681fdb28cfc1e4342f_r.jpg&&（图片来自维基百科）&br&&br&&ul&&li&Polygon Rasterization with Edge Function [4]：Bresenham算法如果用来画多边形，两个多边形的共边会被重绘。后来发明了使用简单的edge function去解决这个问题，而且适合并行的硬件实现。现在的GPU都是使用这个算法。&/li&&/ul&&img src=&/bc6a762cbbfeb_b.jpg& data-rawwidth=&492& data-rawheight=&368& class=&origin_image zh-lightbox-thumb& width=&492& data-original=&/bc6a762cbbfeb_r.jpg&&&br&&br&&b&全局光照&/b&&br&&ul&&li&Precomputed Radiance Transfer (PRT) with Spherical Harmonics（SH）[5]：储存静态环境对于各个方向光源的漫反射数据，可以实现动态低频光源的全局光照效果。这种表示方式非常神奇。Halo 3也使用到这种技术[6]。&/li&&/ul&&img src=&/4225d10efdd85cb81c6ef6fe855b14a3_b.jpg& data-rawwidth=&694& data-rawheight=&295& class=&origin_image zh-lightbox-thumb& width=&694& data-original=&/4225d10efdd85cb81c6ef6fe855b14a3_r.jpg&&&br&&ul&&li&Screen-space Ambient Occlusion （SSAO）[7]：Crytek提出的首个屏幕空间环境光遮蔽算法，之后引来大量的研究及改进算法。也有用类似的概念去做近距离的反射，如SSDO[8]。&/li&&/ul&&img src=&/1faa1a94f23aa9b4b1eb_b.jpg& data-rawwidth=&798& data-rawheight=&316& class=&origin_image zh-lightbox-thumb& width=&798& data-original=&/1faa1a94f23aa9b4b1eb_r.jpg&&&br&&ul&&li&Light Propagation Volume （LPV）[9]：Crytek提出的首个动态全局光照算法，不需要预计算。但要在体积数据中计算传播，性能较慢，所以之后再优化成 Cascaded LPV [10]。&br&&/li&&/ul&&img src=&/cda20e301ccbaa6d3b823b22_b.jpg& data-rawwidth=&1198& data-rawheight=&377& class=&origin_image zh-lightbox-thumb& width=&1198& data-original=&/cda20e301ccbaa6d3b823b22_r.jpg&&&br&&ul&&li&Voxel Cone Tracing [11]：也是不需要预计算的动态全局光照算法。把场景动态生成层阶式的体素数据（像mipmap那样的pre-filtering），从光源视角计算直接光照，然后逐像素追踪这组数据获取非直接光照。结果比LPV精确，也可以做到光泽反射（glossy reflection）。&/li&&/ul&&img src=&/a5bc6edfaf47c2be14ba70_b.jpg& data-rawwidth=&1086& data-rawheight=&333& class=&origin_image zh-lightbox-thumb& width=&1086& data-original=&/a5bc6edfaf47c2be14ba70_r.jpg&&&br&&b&阴影&/b&&br&&ul&&li&Shadow Volume [12]：阴影体积是1977年发表的阴影技术，在屏幕空间光栅化阴影体积，可准确判断每个屏幕像素是否在阴影之内。可以处理平行光源和点光源的阴影。1991年[13]讲述如何用stencil buffer来实现此算法，适合在图形加速硬件（当时还没有所谓GPU）上使用。但很多人发现，如果摄像机在阴影体积内，就会出错。在年有多人发现一种解决方法，需要把John Carmack在2000年的电邮[14]中提及这个想法，后来成为2004年《毁灭战士3（Doom 3）》引擎的重要特徵，因他把这项技术发扬光大，即使他非首个发明人，此项技术通常被称为Carmack's Reverse。&/li&&/ul&&img src=&/c0aefec2d7cab_b.jpg& data-rawwidth=&461& data-rawheight=&346& class=&origin_image zh-lightbox-thumb& width=&461& data-original=&/c0aefec2d7cab_r.jpg&&&br&&br&&ul&&li&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有点差异，被广泛使用于现时大部分游戏引擎中。&/li&&/ul&&img src=&/dba24fba68e2ff8eb5a5ab819c50a1a5_b.jpg& data-rawwidth=&511& data-rawheight=&327& class=&origin_image zh-lightbox-thumb& width=&511& data-original=&/dba24fba68e2ff8eb5a5ab819c50a1a5_r.jpg&&&br&&ul&&li&Variance Shadow Map（VSM）[18]：之前谈到用PCF做软阴影，它的坏处就是要做多次采样。那么可否把阴影贴图直接模糊化来实现软阴影？答案是否定的。但是在2006年有学者发表了VSM，它是一种用统计方式来逼近软阴影的效果。 &a href=&/question//answer/& class=&internal&&如何推导方差阴影贴图（variance shadow map, VSM) ? - Milo Yip 的回答&/a&&/li&&/ul&&img src=&/6bb2fb0efc1d_b.jpg& data-rawwidth=&856& data-rawheight=&300& class=&origin_image zh-lightbox-thumb& width=&856& data-original=&/6bb2fb0efc1d_r.jpg&&&br&&b&场景管理&/b&&br&&ul&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Binary_space_partitioning& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Binary Space Partitioning&i class=&icon-external&&&/i&&/a& （BSP）&br&&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Portal_rendering& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Portal rendering&i class=&icon-external&&&/i&&/a&&br&&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Quadtree& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Quadtree&i class=&icon-external&&&/i&&/a&、&a href=&///?target=http%3A//en.wikipedia.org/wiki/Octree& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Octree&i class=&icon-external&&&/i&&/a&：&a href=&/question//answer/?group_id=696704& class=&internal&&游戏场景管理的八叉树算法是怎样的？ - Milo Yip 的回答&/a&&/li&&li&Potential Visibility Set （PVS）&/li&&li&Occlusion Culling by Software Rasterization&/li&&/ul&&br&&b&动画／物理&/b&&br&&ul&&li&Particle System&/li&&li&Smoothed Particle Hydrodynamics（SPH）&/li&&li&Curl Noise&/li&&li&Dual Quaternion Skinning&/li&&/ul&&br&&b&碰撞测试&/b&&br&&ul&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Hyperplane_separation_theorem& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Hyperplane separation theorem&i class=&icon-external&&&/i&&/a& （或称separating axis theorem/SAT）：凸形状相交测试的基本原理。在&a href=&/question//answer/& class=&internal&&怎样判断平面上一个矩形和一个圆形是否有重叠？ - Milo Yip 的回答&/a&中，其实背后也是使用了SAT。&br&&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Gilbert%25E2%Johnson%25E2%Keerthi_distance_algorithm& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Gilbert-Johnson-Keerthi distance algorithm&i class=&icon-external&&&/i&&/a& (GJK距离算法)：计算两个凸形状的距离（可用于相交测试）&br&&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Sweep_and_prune& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Sweep and prune&i class=&icon-external&&&/i&&/a&：用于broad phase碰撞检测，找出物体AABB是否相交。对于时空上连续的物体运动，算法最坏O(n^2)、最好O(n)。&br&&/li&&/ul&&br&&b&人工智能&/b&&br&&ul&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Minimax& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Minimax&i class=&icon-external&&&/i&&/a&&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Alpha%25E2%beta_pruning& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Alpha-Beta Pruning&i class=&icon-external&&&/i&&/a&&br&&/li&&li&A* path finding&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Dijkstra%2527s_algorithm& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Dijkstra's algorithm&i class=&icon-external&&&/i&&/a&&br&&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Finite-state_machine& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Finite-state machine&i class=&icon-external&&&/i&&/a&&br&&/li&&li&Behavior Tree&/li&&/ul&&br&（中午吃饭时间写不完，后补）&br&&br&&b&参考&/b&&br&&br&[1] Bresenham, Jack E. &Algorithm for computer control of a digital plotter.& &i&IBM Systems journal&/i& 4.1 (1965): 25-30. &a href=&///?target=http%3A//www.cse.iitb.ac.in/%7Eparagc/teaching/2011/cs475/papers/bresenham_line.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&cse.iitb.ac.in/~paragc/&/span&&span class=&invisible&&teaching/2011/cs475/papers/bresenham_line.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[2] Bresenham, Jack. &A linear algorithm for incremental digital display of circular arcs.& &i&Communications of the ACM&/i& 20.2 (1977): 100-106. &a href=&///?target=http%3A//www.cse.iitb.ac.in/%7Eparagc/teaching/2014/cs475/papers/bresenham_circle.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&cse.iitb.ac.in/~paragc/&/span&&span class=&invisible&&teaching/2014/cs475/papers/bresenham_circle.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[3] Catmull, Ed, and Alvy Ray Smith. &3-D transformations of images in scanline order.& &i&ACM SIGGRAPH Computer Graphics&/i&. Vol. 14. No. 3. ACM, 1980. &a href=&///?target=http%3A///Papers/CG/2pass80.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/Papers/CG/2&/span&&span class=&invisible&&pass80.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[4] Pineda, Juan. &A parallel algorithm for polygon rasterization.& &i&ACM SIGGRAPH Computer Graphics&/i&. Vol. 22. No. 4. ACM, 1988. &a href=&///?target=http%3A//people.csail.mit.edu/ericchan/bib/pdf/p17-pineda.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&people.csail.mit.edu/er&/span&&span class=&invisible&&icchan/bib/pdf/p17-pineda.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[5] Sloan, Peter-Pike, Jan Kautz, and John Snyder. &Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments.& &i&ACM Transactions on Graphics (TOG)&/i&. Vol. 21. No. 3. ACM, 2002. &a href=&///?target=http%3A//www1.cs.columbia.edu/%7Eravir/6998/papers/p527-sloan.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&www1.cs.columbia.edu/~r&/span&&span class=&invisible&&avir/6998/papers/p527-sloan.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[6] Chen, Hao, and Xinguo Liu. &Lighting and material of Halo 3.& &i&ACM SIGGRAPH 2008 Games&/i&. ACM, 2008. &a href=&///?target=http%3A///wordpress/media/08-Chen-Lighting_and_Material_of_Halo3.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/wordp&/span&&span class=&invisible&&ress/media/08-Chen-Lighting_and_Material_of_Halo3.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[7] Mittring, Martin. &Finding next gen: Cryengine 2.& &i&ACM SIGGRAPH 2007 courses&/i&. ACM, 2007. &a href=&///?target=http%3A///wordpress/media/2012/10/Chapter8-Mittring-Finding_NextGen_CryEngine2.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/wordp&/span&&span class=&invisible&&ress/media/2012/10/Chapter8-Mittring-Finding_NextGen_CryEngine2.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[8] Ritschel, Tobias, Thorsten Grosch, and Hans-Peter Seidel. &Approximating dynamic global illumination in image space.& &i&Proceedings of the 2009 symposium on Interactive 3D graphics and games&/i&. ACM, 2009. &a href=&///?target=https%3A//people.mpi-inf.mpg.de/%7Eritschel/Papers/SSDO.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&people.mpi-inf.mpg.de/~&/span&&span class=&invisible&&ritschel/Papers/SSDO.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[9] Kaplanyan, Anton. &Light propagation volumes in cryengine 3.& &i&ACM SIGGRAPH Courses&/i& 7 (2009): 2. &a href=&///?target=http%3A///download/Light_Propagation_Volumes.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&/download/Lig&/span&&span class=&invisible&&ht_Propagation_Volumes.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[10] Kaplanyan, Anton, and Carsten Dachsbacher. &Cascaded light propagation volumes for real-time indirect illumination.& &i&Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games&/i&. ACM, 2010. &a href=&///?target=http%3A//www.vis.uni-stuttgart.de/%7Edachsbcn/download/lpv.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&vis.uni-stuttgart.de/~d&/span&&span class=&invisible&&achsbcn/download/lpv.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[11] Crassin, Cyril, et al. &Interactive indirect illumination using voxel cone tracing.&&i&Computer Graphics Forum&/i&. Vol. 30. No. 7. Blackwell Publishing Ltd, 2011. &a href=&///?target=https%3A///sites/default/files/publications/GIVoxels-pg2011-authors.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&/sit&/span&&span class=&invisible&&es/default/files/publications/GIVoxels-pg2011-authors.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[12] Crow, Franklin C. &Shadow algorithms for computer graphics.& &i&ACM SIGGRAPH Computer Graphics&/i&. Vol. 11. No. 2. ACM, 1977. &a href=&///?target=http%3A//excelsior.biosci.ohio-state.edu/%7Ecarlson/history/PDFs/crow-shadows.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&excelsior.biosci.ohio-state.edu&/span&&span class=&invisible&&/~carlson/history/PDFs/crow-shadows.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[13] Heidmann, Tim. &Real shadows, real time.& &i&Iris Universe&/i& 18 (1991): 28-31.&br&[14] Carmack, John, &e-mail to Mark Kilgard on Shadow Volume&, 23 May 2000. &a href=&///?target=http%3A//web.archive.org/web/35/http%3A///attach/6832& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&web.archive.org/web/200&/span&&span class=&invisible&&//attach/6832&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[15] Zhang, Fan, et al. &Parallel-split shadow maps for large-scale virtual environments.& &i&Proceedings of the 2006 ACM international conference on Virtual reality continuum and its applications&/i&. ACM, 2006.&br&[16] Zhang, Fan, Hanqiu Sun, and Oskari Nyman. &Parallel-split shadow maps on programmable gpus.& &i&GPU Gems&/i& 3 (2007): 203-237. &a href=&///?target=http%3A//http./GPUGems3/gpugems3_ch10.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&GPU Gems 3 - Chapter 10. Parallel-Split Shadow Maps on Programmable GPUs&i class=&icon-external&&&/i&&/a&&br&[17] Dimitrov, Rouslan. &Cascaded shadow maps.& &i&Developer Documentation, NVIDIA Corp&/i& (2007). &a href=&///?target=http%3A//www.cse.chalmers.se/edu/year/2011/course/TDA361/Advanced%2520Computer%2520Graphics/cascaded_shadow_maps.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&cse.chalmers.se/edu/yea&/span&&span class=&invisible&&r/2011/course/TDA361/Advanced%20Computer%20Graphics/cascaded_shadow_maps.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[18] Donnelly, William, and Andrew Lauritzen. &Variance shadow maps.&&i&Proceedings of the 2006 symposium on Interactive 3D graphics and games&/i&. ACM, 2006. &a href=&///?target=http%3A//www.punkuser.net/vsm/vsm_paper.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&punkuser.net/vsm/vsm_pa&/span&&span class=&invisible&&per.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&
我挑一些有趣的算法，希望尽量提及相关算法在游戏中的应用。 光栅化
[1]：经典的绘画直线算法，后来还可以稍作修改用于绘画圆弧[2]，都不用三角函数或除数，只需用整数加法、减法和乘法。 Perspective-Correct Texture Mapping …
过会就要有人把卡马克大神的平方根倒数算法放出来。。。
过会就要有人把卡马克大神的平方根倒数算法放出来。。。
已有帐号？
无法登录？
社交帐号登录
吾将上下而知天下游戏开发要学哪些算法 - 开源中国社区
当前访客身份：游客 [
当前位置：
本人未毕业，去面游戏公司，面试官让我吃透算法再来。请问游戏常用算法要掌握哪些，基本的，必须掌握的。
共有6个答案
<span class="a_vote_num" id="a_vote_num_
用引擎做游戏,掌握一些基本数据结构和三角学知识就可以了.主要还是逻辑实现上的,时间换空间,空间换时间,这个没具体定理,要看应用场景再规划.如果是搞引擎的,就是计算机图形学算法,说白了就是光线跟踪算法+高等几何知识,这个可以查阅国外论文等文献来学习.如果是搞物理的,就要学习力学和流体动力学.搞数值策划的就要学些线性代数等.搞游戏服务器后台的则主要在架构方面,实时和海量并发需要规划好.不过说到底,先自己做几个简单的游戏出来,就就会明白你的短板再那里了.
<span class="a_vote_num" id="a_vote_num_
减法公式：受到伤害=敌人攻击力-防御力
除法公式：受到伤害＝敌人攻击力*敌人攻击力/（防御力+敌人攻击力）
乘法公式：受到伤害＝敌人攻击力*（1-免伤率）
经典概率算法
圆桌概率算法
属性池概念
<span class="a_vote_num" id="a_vote_num_
<span class="a_vote_num" id="a_vote_num_
--- 共有 1 条评论 ---
(3年前) &
<span class="a_vote_num" id="a_vote_num_
游戏开发这东西，有很多现成的代码了，主要看效率
<span class="a_vote_num" id="a_vote_num_
起码要对常用算法有基本概念吧，我估计他就是这样的要求，不然估计写出来的东西 性能会有问题
更多开发者职位上
有什么技术问题吗？
Vek_lip...的其它问题
类似的话题热度:6060℃
本文整理自知乎，文/我挑一些有趣的算法，希望尽量提及相关算法在游戏中的应用。光栅化 [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派党)
开发者服务}
已出现卡马克大深度的平方根算法
我挑一些有趣的算法，希望尽量提及相关算法在游戏中的应用。&br&&br&&b&光栅化&/b&&br&&ul&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Bresenham%2527s_line_algorithm& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Bresenham's line algorithm&i class=&icon-external&&&/i&&/a& [1]：经典的绘画直线算法，后来还可以稍作修改用于绘画圆弧[2]，都不用三角函数或除数，只需用整数加法、减法和乘法。 &/li&&/ul&&img src=&/b7cb85217babb238ac6c_b.jpg& data-rawwidth=&592& data-rawheight=&401& class=&origin_image zh-lightbox-thumb& width=&592& data-original=&/b7cb85217babb238ac6c_r.jpg&&&br&&ul&&li&Perspective-Correct Texture Mapping [3]：透视正确的光栅化纹理贴图算法是1980才出现的。第一代Quake引擎引入后，才开始支持不垂直的墙、不水平的地面天花。&/li&&/ul&&img src=&/24681fdb28cfc1e4342f_b.jpg& data-rawwidth=&1000& data-rawheight=&352& class=&origin_image zh-lightbox-thumb& width=&1000& data-original=&/24681fdb28cfc1e4342f_r.jpg&&（图片来自维基百科）&br&&br&&ul&&li&Polygon Rasterization with Edge Function [4]：Bresenham算法如果用来画多边形，两个多边形的共边会被重绘。后来发明了使用简单的edge function去解决这个问题，而且适合并行的硬件实现。现在的GPU都是使用这个算法。&/li&&/ul&&img src=&/bc6a762cbbfeb_b.jpg& data-rawwidth=&492& data-rawheight=&368& class=&origin_image zh-lightbox-thumb& width=&492& data-original=&/bc6a762cbbfeb_r.jpg&&&br&&br&&b&全局光照&/b&&br&&ul&&li&Precomputed Radiance Transfer (PRT) with Spherical Harmonics（SH）[5]：储存静态环境对于各个方向光源的漫反射数据，可以实现动态低频光源的全局光照效果。这种表示方式非常神奇。Halo 3也使用到这种技术[6]。&/li&&/ul&&img src=&/4225d10efdd85cb81c6ef6fe855b14a3_b.jpg& data-rawwidth=&694& data-rawheight=&295& class=&origin_image zh-lightbox-thumb& width=&694& data-original=&/4225d10efdd85cb81c6ef6fe855b14a3_r.jpg&&&br&&ul&&li&Screen-space Ambient Occlusion （SSAO）[7]：Crytek提出的首个屏幕空间环境光遮蔽算法，之后引来大量的研究及改进算法。也有用类似的概念去做近距离的反射，如SSDO[8]。&/li&&/ul&&img src=&/1faa1a94f23aa9b4b1eb_b.jpg& data-rawwidth=&798& data-rawheight=&316& class=&origin_image zh-lightbox-thumb& width=&798& data-original=&/1faa1a94f23aa9b4b1eb_r.jpg&&&br&&ul&&li&Light Propagation Volume （LPV）[9]：Crytek提出的首个动态全局光照算法，不需要预计算。但要在体积数据中计算传播，性能较慢，所以之后再优化成 Cascaded LPV [10]。&br&&/li&&/ul&&img src=&/cda20e301ccbaa6d3b823b22_b.jpg& data-rawwidth=&1198& data-rawheight=&377& class=&origin_image zh-lightbox-thumb& width=&1198& data-original=&/cda20e301ccbaa6d3b823b22_r.jpg&&&br&&ul&&li&Voxel Cone Tracing [11]：也是不需要预计算的动态全局光照算法。把场景动态生成层阶式的体素数据（像mipmap那样的pre-filtering），从光源视角计算直接光照，然后逐像素追踪这组数据获取非直接光照。结果比LPV精确，也可以做到光泽反射（glossy reflection）。&/li&&/ul&&img src=&/a5bc6edfaf47c2be14ba70_b.jpg& data-rawwidth=&1086& data-rawheight=&333& class=&origin_image zh-lightbox-thumb& width=&1086& data-original=&/a5bc6edfaf47c2be14ba70_r.jpg&&&br&&b&阴影&/b&&br&&ul&&li&Shadow Volume [12]：阴影体积是1977年发表的阴影技术，在屏幕空间光栅化阴影体积，可准确判断每个屏幕像素是否在阴影之内。可以处理平行光源和点光源的阴影。1991年[13]讲述如何用stencil buffer来实现此算法，适合在图形加速硬件（当时还没有所谓GPU）上使用。但很多人发现，如果摄像机在阴影体积内，就会出错。在年有多人发现一种解决方法，需要把John Carmack在2000年的电邮[14]中提及这个想法，后来成为2004年《毁灭战士3（Doom 3）》引擎的重要特徵，因他把这项技术发扬光大，即使他非首个发明人，此项技术通常被称为Carmack's Reverse。&/li&&/ul&&img src=&/c0aefec2d7cab_b.jpg& data-rawwidth=&461& data-rawheight=&346& class=&origin_image zh-lightbox-thumb& width=&461& data-original=&/c0aefec2d7cab_r.jpg&&&br&&br&&ul&&li&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有点差异，被广泛使用于现时大部分游戏引擎中。&/li&&/ul&&img src=&/dba24fba68e2ff8eb5a5ab819c50a1a5_b.jpg& data-rawwidth=&511& data-rawheight=&327& class=&origin_image zh-lightbox-thumb& width=&511& data-original=&/dba24fba68e2ff8eb5a5ab819c50a1a5_r.jpg&&&br&&ul&&li&Variance Shadow Map（VSM）[18]：之前谈到用PCF做软阴影，它的坏处就是要做多次采样。那么可否把阴影贴图直接模糊化来实现软阴影？答案是否定的。但是在2006年有学者发表了VSM，它是一种用统计方式来逼近软阴影的效果。 &a href=&/question//answer/& class=&internal&&如何推导方差阴影贴图（variance shadow map, VSM) ? - Milo Yip 的回答&/a&&/li&&/ul&&img src=&/6bb2fb0efc1d_b.jpg& data-rawwidth=&856& data-rawheight=&300& class=&origin_image zh-lightbox-thumb& width=&856& data-original=&/6bb2fb0efc1d_r.jpg&&&br&&b&场景管理&/b&&br&&ul&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Binary_space_partitioning& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Binary Space Partitioning&i class=&icon-external&&&/i&&/a& （BSP）&br&&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Portal_rendering& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Portal rendering&i class=&icon-external&&&/i&&/a&&br&&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Quadtree& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Quadtree&i class=&icon-external&&&/i&&/a&、&a href=&///?target=http%3A//en.wikipedia.org/wiki/Octree& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Octree&i class=&icon-external&&&/i&&/a&：&a href=&/question//answer/?group_id=696704& class=&internal&&游戏场景管理的八叉树算法是怎样的？ - Milo Yip 的回答&/a&&/li&&li&Potential Visibility Set （PVS）&/li&&li&Occlusion Culling by Software Rasterization&/li&&/ul&&br&&b&动画／物理&/b&&br&&ul&&li&Particle System&/li&&li&Smoothed Particle Hydrodynamics（SPH）&/li&&li&Curl Noise&/li&&li&Dual Quaternion Skinning&/li&&/ul&&br&&b&碰撞测试&/b&&br&&ul&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Hyperplane_separation_theorem& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Hyperplane separation theorem&i class=&icon-external&&&/i&&/a& （或称separating axis theorem/SAT）：凸形状相交测试的基本原理。在&a href=&/question//answer/& class=&internal&&怎样判断平面上一个矩形和一个圆形是否有重叠？ - Milo Yip 的回答&/a&中，其实背后也是使用了SAT。&br&&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Gilbert%25E2%Johnson%25E2%Keerthi_distance_algorithm& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Gilbert-Johnson-Keerthi distance algorithm&i class=&icon-external&&&/i&&/a& (GJK距离算法)：计算两个凸形状的距离（可用于相交测试）&br&&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Sweep_and_prune& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Sweep and prune&i class=&icon-external&&&/i&&/a&：用于broad phase碰撞检测，找出物体AABB是否相交。对于时空上连续的物体运动，算法最坏O(n^2)、最好O(n)。&br&&/li&&/ul&&br&&b&人工智能&/b&&br&&ul&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Minimax& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Minimax&i class=&icon-external&&&/i&&/a&&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Alpha%25E2%beta_pruning& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Alpha-Beta Pruning&i class=&icon-external&&&/i&&/a&&br&&/li&&li&A* path finding&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Dijkstra%2527s_algorithm& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Dijkstra's algorithm&i class=&icon-external&&&/i&&/a&&br&&/li&&li&&a href=&///?target=http%3A//en.wikipedia.org/wiki/Finite-state_machine& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Finite-state machine&i class=&icon-external&&&/i&&/a&&br&&/li&&li&Behavior Tree&/li&&/ul&&br&（中午吃饭时间写不完，后补）&br&&br&&b&参考&/b&&br&&br&[1] Bresenham, Jack E. &Algorithm for computer control of a digital plotter.& &i&IBM Systems journal&/i& 4.1 (1965): 25-30. &a href=&///?target=http%3A//www.cse.iitb.ac.in/%7Eparagc/teaching/2011/cs475/papers/bresenham_line.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&cse.iitb.ac.in/~paragc/&/span&&span class=&invisible&&teaching/2011/cs475/papers/bresenham_line.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[2] Bresenham, Jack. &A linear algorithm for incremental digital display of circular arcs.& &i&Communications of the ACM&/i& 20.2 (1977): 100-106. &a href=&///?target=http%3A//www.cse.iitb.ac.in/%7Eparagc/teaching/2014/cs475/papers/bresenham_circle.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&cse.iitb.ac.in/~paragc/&/span&&span class=&invisible&&teaching/2014/cs475/papers/bresenham_circle.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[3] Catmull, Ed, and Alvy Ray Smith. &3-D transformations of images in scanline order.& &i&ACM SIGGRAPH Computer Graphics&/i&. Vol. 14. No. 3. ACM, 1980. &a href=&///?target=http%3A///Papers/CG/2pass80.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/Papers/CG/2&/span&&span class=&invisible&&pass80.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[4] Pineda, Juan. &A parallel algorithm for polygon rasterization.& &i&ACM SIGGRAPH Computer Graphics&/i&. Vol. 22. No. 4. ACM, 1988. &a href=&///?target=http%3A//people.csail.mit.edu/ericchan/bib/pdf/p17-pineda.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&people.csail.mit.edu/er&/span&&span class=&invisible&&icchan/bib/pdf/p17-pineda.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[5] Sloan, Peter-Pike, Jan Kautz, and John Snyder. &Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments.& &i&ACM Transactions on Graphics (TOG)&/i&. Vol. 21. No. 3. ACM, 2002. &a href=&///?target=http%3A//www1.cs.columbia.edu/%7Eravir/6998/papers/p527-sloan.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&www1.cs.columbia.edu/~r&/span&&span class=&invisible&&avir/6998/papers/p527-sloan.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[6] Chen, Hao, and Xinguo Liu. &Lighting and material of Halo 3.& &i&ACM SIGGRAPH 2008 Games&/i&. ACM, 2008. &a href=&///?target=http%3A///wordpress/media/08-Chen-Lighting_and_Material_of_Halo3.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/wordp&/span&&span class=&invisible&&ress/media/08-Chen-Lighting_and_Material_of_Halo3.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[7] Mittring, Martin. &Finding next gen: Cryengine 2.& &i&ACM SIGGRAPH 2007 courses&/i&. ACM, 2007. &a href=&///?target=http%3A///wordpress/media/2012/10/Chapter8-Mittring-Finding_NextGen_CryEngine2.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/wordp&/span&&span class=&invisible&&ress/media/2012/10/Chapter8-Mittring-Finding_NextGen_CryEngine2.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[8] Ritschel, Tobias, Thorsten Grosch, and Hans-Peter Seidel. &Approximating dynamic global illumination in image space.& &i&Proceedings of the 2009 symposium on Interactive 3D graphics and games&/i&. ACM, 2009. &a href=&///?target=https%3A//people.mpi-inf.mpg.de/%7Eritschel/Papers/SSDO.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&people.mpi-inf.mpg.de/~&/span&&span class=&invisible&&ritschel/Papers/SSDO.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[9] Kaplanyan, Anton. &Light propagation volumes in cryengine 3.& &i&ACM SIGGRAPH Courses&/i& 7 (2009): 2. &a href=&///?target=http%3A///download/Light_Propagation_Volumes.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&/download/Lig&/span&&span class=&invisible&&ht_Propagation_Volumes.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[10] Kaplanyan, Anton, and Carsten Dachsbacher. &Cascaded light propagation volumes for real-time indirect illumination.& &i&Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games&/i&. ACM, 2010. &a href=&///?target=http%3A//www.vis.uni-stuttgart.de/%7Edachsbcn/download/lpv.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&vis.uni-stuttgart.de/~d&/span&&span class=&invisible&&achsbcn/download/lpv.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[11] Crassin, Cyril, et al. &Interactive indirect illumination using voxel cone tracing.&&i&Computer Graphics Forum&/i&. Vol. 30. No. 7. Blackwell Publishing Ltd, 2011. &a href=&///?target=https%3A///sites/default/files/publications/GIVoxels-pg2011-authors.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&/sit&/span&&span class=&invisible&&es/default/files/publications/GIVoxels-pg2011-authors.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[12] Crow, Franklin C. &Shadow algorithms for computer graphics.& &i&ACM SIGGRAPH Computer Graphics&/i&. Vol. 11. No. 2. ACM, 1977. &a href=&///?target=http%3A//excelsior.biosci.ohio-state.edu/%7Ecarlson/history/PDFs/crow-shadows.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&excelsior.biosci.ohio-state.edu&/span&&span class=&invisible&&/~carlson/history/PDFs/crow-shadows.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[13] Heidmann, Tim. &Real shadows, real time.& &i&Iris Universe&/i& 18 (1991): 28-31.&br&[14] Carmack, John, &e-mail to Mark Kilgard on Shadow Volume&, 23 May 2000. &a href=&///?target=http%3A//web.archive.org/web/35/http%3A///attach/6832& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&web.archive.org/web/200&/span&&span class=&invisible&&//attach/6832&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[15] Zhang, Fan, et al. &Parallel-split shadow maps for large-scale virtual environments.& &i&Proceedings of the 2006 ACM international conference on Virtual reality continuum and its applications&/i&. ACM, 2006.&br&[16] Zhang, Fan, Hanqiu Sun, and Oskari Nyman. &Parallel-split shadow maps on programmable gpus.& &i&GPU Gems&/i& 3 (2007): 203-237. &a href=&///?target=http%3A//http./GPUGems3/gpugems3_ch10.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&GPU Gems 3 - Chapter 10. Parallel-Split Shadow Maps on Programmable GPUs&i class=&icon-external&&&/i&&/a&&br&[17] Dimitrov, Rouslan. &Cascaded shadow maps.& &i&Developer Documentation, NVIDIA Corp&/i& (2007). &a href=&///?target=http%3A//www.cse.chalmers.se/edu/year/2011/course/TDA361/Advanced%2520Computer%2520Graphics/cascaded_shadow_maps.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&cse.chalmers.se/edu/yea&/span&&span class=&invisible&&r/2011/course/TDA361/Advanced%20Computer%20Graphics/cascaded_shadow_maps.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[18] Donnelly, William, and Andrew Lauritzen. &Variance shadow maps.&&i&Proceedings of the 2006 symposium on Interactive 3D graphics and games&/i&. ACM, 2006. &a href=&///?target=http%3A//www.punkuser.net/vsm/vsm_paper.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&punkuser.net/vsm/vsm_pa&/span&&span class=&invisible&&per.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&
我挑一些有趣的算法，希望尽量提及相关算法在游戏中的应用。 光栅化
[1]：经典的绘画直线算法，后来还可以稍作修改用于绘画圆弧[2]，都不用三角函数或除数，只需用整数加法、减法和乘法。 Perspective-Correct Texture Mapping …
过会就要有人把卡马克大神的平方根倒数算法放出来。。。
过会就要有人把卡马克大神的平方根倒数算法放出来。。。
已有帐号？
无法登录？
社交帐号登录
吾将上下而知天下游戏开发要学哪些算法 - 开源中国社区
当前访客身份：游客 [
当前位置：
本人未毕业，去面游戏公司，面试官让我吃透算法再来。请问游戏常用算法要掌握哪些，基本的，必须掌握的。
共有6个答案
<span class="a_vote_num" id="a_vote_num_
用引擎做游戏,掌握一些基本数据结构和三角学知识就可以了.主要还是逻辑实现上的,时间换空间,空间换时间,这个没具体定理,要看应用场景再规划.如果是搞引擎的,就是计算机图形学算法,说白了就是光线跟踪算法+高等几何知识,这个可以查阅国外论文等文献来学习.如果是搞物理的,就要学习力学和流体动力学.搞数值策划的就要学些线性代数等.搞游戏服务器后台的则主要在架构方面,实时和海量并发需要规划好.不过说到底,先自己做几个简单的游戏出来,就就会明白你的短板再那里了.
<span class="a_vote_num" id="a_vote_num_
减法公式：受到伤害=敌人攻击力-防御力
除法公式：受到伤害＝敌人攻击力*敌人攻击力/（防御力+敌人攻击力）
乘法公式：受到伤害＝敌人攻击力*（1-免伤率）
经典概率算法
圆桌概率算法
属性池概念
<span class="a_vote_num" id="a_vote_num_
<span class="a_vote_num" id="a_vote_num_
--- 共有 1 条评论 ---
(3年前) &
<span class="a_vote_num" id="a_vote_num_
游戏开发这东西，有很多现成的代码了，主要看效率
<span class="a_vote_num" id="a_vote_num_
起码要对常用算法有基本概念吧，我估计他就是这样的要求，不然估计写出来的东西 性能会有问题
更多开发者职位上
有什么技术问题吗？
Vek_lip...的其它问题
类似的话题热度:6060℃
本文整理自知乎，文/我挑一些有趣的算法，希望尽量提及相关算法在游戏中的应用。光栅化 [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派党)
开发者服务}
我要回帖
更多关于 编程算法基础 的文章
更多推荐
- ·华硕b75主板参数小吹雪和小吹雪有什么区别吗？
- ·莱斯曼瓷砖的生产基地在哪里陶瓷属于什么档次？
- ·对于贴了威固VK70感觉有纹路的性能，你了解吗？如何评价漫彩FR70？
- ·莱鹿贝斯贝伦妮斯包包是哪个国家的品牌啊种类型的包？
- ·关于现音学院作曲系最好的音乐学院创作系，它的教学质量和口碑如何？
- ·李易峰有多少钱什么时候出道
- ·梦见男朋友的周云鹏前妻男朋友扔垃圾在我身上
- ·与江河湖海有关的成语的数字成语
- ·lv国外代言人是米歇尔米歇尔.威廉姆斯女儿吗
- ·画蛇的那蛇碰到蛇死是什么游戏戏
- ·夏天汗蒸的好处和坏处面皮爱坏放啥东西防腐
- ·向日葵的样子是在什么时间开放开放的时间是什么样子的把你观察到的写下来
- ·恳请高手帮我鉴定一下，这几个币有收藏品鉴定价值吗？
- ·有关2016大理州州庆放假的成语
- ·如何改变securecrt 改背景颜色背景颜色
- ·微微一笑同人堇年遇你有什么成语
- ·10岁的金牛座小女生QQ网名叫什么好，可以带符号也可以好听网名女生唯美意境境非主流
- ·王者荣耀未来皮肤什么时间能开出未来世纪
- ·金星秀161019金星秀潜规则说得是谁谁
- ·游戏编程经典算法里面有哪些经典或者很酷的算法
- ·速度太速度速度加快是什么歌歌
- ·蛋清猪油的功效与作用能一起用吗
- ·长隆海洋王国 生日票生日
- ·魔兽世界苏拉玛散布谣言在哪接播谣言任务怎么有个npc没找到
- ·琼海市美女喝啤酒乔任梁死亡真的吗是真的吗
- ·求黑执事所有的ova，加上马戏团篇的最后一集，ova和马戏团篇的最后一集，拜托了老师ova百度云拜托了老师ova百度云，在这现等百度云
- ·你哪的?你哪的?山东老乡 微电影啊!这部电影台词的电影叫什么
- ·网上都有哪些现在最流行的麻将将游戏？
- ·什么韩国电影 奇怪的姐姐姐姐
- ·想起四个字的名字名字，程李??……谢谢
- ·中国有灵能百分百龙套实力之多少的人梦见龙
- ·b站弹幕墙那个读弹屏的怎么弄？
- ·女的向男的说她妈妈是魔术师被日本人韩娱 强奸徐贤妈妈的电视剧
