游戏与算法的必经之路 -pg电子游戏网站

3顶
0踩

引用
作者:姜雪伟,创业公司技术合伙人,畅销书作者。csdn社区专家,资深3d游戏引擎开发者,it高级讲师,计算机图形学方向研究生。
本文为姜雪伟原创文章,未经允许不得转载, 点此作者有关《》经验分享

前言
作为一个在it行业工作十五年的老兵,笔者在这里将自己多年的学习游戏算法经验分享给读者,希望能够帮助那些想学习算法提升自己的读者。算法是it产品研发的核心,在it的任何领域都离不开算法,目前比较流行的it领域有:大数据,人工智能,深度学习,游戏开发,虚拟现实,增强现实等,这些领域的核心都是算法,可见算法在it领域的重要性。本文主要聚焦游戏算法,游戏开发不外乎3d引擎接口调用和游戏逻辑编写,3d游戏引擎的主要功能是渲染,渲染使用的是图形学算法针对gpu编程的。客户端逻辑的编写也会用到一些算法,比如抛物线算法,曲线插值算法,a*寻路算法等等。算法的优势主要体现在游戏核心功能和效率优化上面,作为it程序员来说,如果对算法不精通,或者不知道如何在程序中使用算法,随着时间的推移会逐步被行业淘汰。当然大家也不必为此担心,笔者在此总结了学习算法必经之路的三个主要阶段。

第一阶段 基础篇
对于初始学习的读者,首先要把基础算法学好,也就是把大厦的地基要打牢,“理论联系实际”,学习算法先要把理论知识学好,给读者推荐的学习资料是大学的经典课程《数据结构与算法》,涉及到的主要知识点有:快速排序,二叉树排序,二分查找,哈希表,二叉树等。掌握这些数据结构并能运用它们解决实际问题,千万不要死记硬背,亲自动手将算法书写一遍,编程的过程就是要反复的练习。另外,还要学习一些关于矩阵、向量运算的知识点,这些知识点也是游戏开发必备的。给读者推荐的资料是大学课程《线性代数》。掌握这些知识的方法就是读者都要动手将它们逐行代码敲一遍并且用脑子反复琢磨领会贯通。

以二叉树为例,介绍其在游戏开发中使用的案例,二叉树在图论中是这样定义的:二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点。它在游戏中应用案例给读者介绍一下,在游戏开发中经常使用图集,就是把多张小图片合成一张大的图片一次性加载到内存中,优化了内存加载效率,生成图集的算法就是用二叉树算法实现的,算法流程就是首先生成一块内存用于存储大图片,然后新建一个空的二叉树,把小图片看作是二叉树的子节点,依次去挂载到二叉树的叶子节点上,挂接的顺序采用的是先序遍历的思想,这样一张图集就生成了。如果本阶段的知识点读者已经掌握了可以直接略过,接下来进入第二阶段进阶篇。

第二阶段 进阶篇
在进阶篇阶段是学习一些相对基础篇比较复杂的算法,进阶篇的算法主要包括:a*算法,八叉树算法,perlin噪音等,笔者建议学习的资料是关于游戏编程方面的书籍《游戏编程大师技巧》(上下册)这两本书非常经典,虽然其接口有些旧,但里面的编程理论非常适用游戏开发,笔者利用它的编程思想编写了一本适合初学者学习的《手把手教你架构3d游戏引擎》一书。

下面以八叉树算法为例给读者介绍其应用,八叉树(octree)是三维空间划分的数据结构之一,它用于加速空间查询, octree的实现原理主要分为六步:
  • 第一步、设定最大递归深度;
  • 第二步、找出场景的最大尺寸,并以此尺寸建立第一个立方体;
  • 第三步、依序将单位元素丢入能被包含且没有子节点的立方体
  • 第四步、若没有达到最大递归深度,就进行细分八等份,再将该立方体所装的单位元元素全部分担给八个子立方体;
  • 第五步、若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的,则该子立方体停止细分,因为跟据空间分割理论,细分的空间所得到的分配必定较少,若是一样数目,则再怎么切数目还是一样,会造成无穷切割的情形;
  • 第六步、重复3步骤,直到达到最大递归深度;
给读者举个游戏案例,假设:我们有一个大的房间,房间里某个角落站了一只小动物,我们想很快的把小动物找出来,该如何做?我们可以把房间当成一个立方体,先切成八个小立方体,
然后排除掉没有放任何东西的小立方体,再把有可能藏小动物的小立方体继续切八
等份….如此下去,平均在log8(房间内的所有物品数)的时间内就可找到小动物。
因此,八叉树就是用在3d空间中的场景管理,可以很快地知道物体在3d场景中的位置,或侦测与其它物体是否有碰撞以及是否在可视范围内。进而八叉树的应用场景可以推广到解决如下技术问题:
  • 一、用其加速用于可见性判断的视锥裁剪;
  • 二、加速射线投射,如用作视线判断或枪击判定;
  • 三、邻近查询,如查询玩家角色某半径范围内的敌方npc;
  • 四、碰撞检测的粗略阶段,找出潜在可能碰撞的物体对;
实现的八叉树效果图展示如下所示:


第三阶段 提高篇
掌握了第二阶段的学习后,接下来到了真正的提高篇,也就是“武林秘籍”的最高境界。提高篇主要是学习图形学算法编程,推荐给读者学习的书籍是:
引用
《mathematics for 3d game programming and computer graphics》和《real-time rendering》这两本书相对来说比较难。但是写的非常好,有助于提升技术水平。市面上比较知名的引擎都使用了gpu编程技术,这些技术算法主要包含:pssm算法、ssao算法、bloom算法、blur算法、hdr算法、deferred算法等,它们也是引擎的核心算法。
点此作者有关《》经验分享。

以pssm算法为例,给读者分享一下应用案例,如何在游戏中使用,首先要了解其原理:pssm全称 parallel-split shadow map
pssm算法的核心就是把视椎体进行分割,然后分别渲染组合。语言讲解不如看图直观,先通过视锥体分割说起。效果如下图所示:
视锥体分割效果图

pssm实时阴影的绘制首先需要灯光,在现实生活中,白天只有太阳出来了才可以看到影子。在虚拟世界中也是一样的,场景使用的是directional(平行光)相当于现实世界的太阳光。上图左边部分显示的是视景体的投影,利用pssm算法将其平行的分割成多个部分,然后对每个部分进行渲染,分割成的块数是可以自己设置的。右半部分是顶视角观看的分割效果,把物体分成三块进行实时阴影的渲染。渲染的计算是gpu中执行的,在gpu中执行的流程如下图所示:
渲染分解效果图

上图的处理流程首先是场景中的灯光照射到需要投影的物体上,接下来程序对投影的物体顶点进行矩阵变换将其转换到投影空间中,再转换到裁剪空间进行视口的平行分割,最后将其分别渲染出来。原理清楚了代码编写就很简单了,具体代码读者可以查看《手把手教你架构3d游戏引擎》一书,下面给读者展示效果图如下所示:

下面笔者分享一下学习算法的感受,刚踏入it行业时也不会算法编程,对算法有一种恐惧感,总感觉算法很神秘,更不知道如何使用,自己为此也苦恼过。刚入职公司的时候跟大多数程序员一样写写逻辑,两年后,自己感觉水平也比较牛了。为此,自己申请加入到公司核心部门引擎部,初衷就是看看引擎组都做些什么事情,当然也是想学习一些知识为了跳槽涨工资。

加入引擎组后,经历了一件事情彻底改变了我,更让我认识到算法的重要性。事情是这样的,端游中实现的刀光拖尾算法,功能包括:取样插值并且实现材质的扭曲效果,当时接到任务一下子就懵了,在网上不停的翻资料,那时网上没有这方面的技术实现,最后只能硬着头皮自己动手写了,经过一周的折腾,选择了b样条曲线插值算法,再经过一周将其实现了出来,最后一周的时间,度日如年,晚上基本上都没睡好,做梦都想着如何实现算法。有时自己都想离职走人了,感觉压力太大了,但是最终还是实现出来了。经历过这段刻骨宁心的经历,让我明白了算法是如何与游戏开发相结合的,也让我明白了自己算法知识的薄弱,需要从头开始把算法学好,最终我也是按照上面这三个阶段学习的。在学习算法的过程中痛并快乐着,学习算法首先要明白其原理,然后再用代码敲一遍实现出来,切记眼高手低。

后来笔者独立写过几款3d引擎包括:3d渲染引擎,海水渲染引擎,物理引擎等。现将实现的效果给读者展示如下:
海水渲染反射折射效果

实时航行轨迹模果

最后给读者一个建议:学习算法关键是我们要有一个正确的学习方法再结合着实战项目就可以快速的提升自己的技战水平。算法的学习不是一朝一夕的,只要找对学习方法,分阶段学习,持之以恒,相信随着经验的积累将来在it“武林“真的可以独步天下,以此文与读者共勉。
引用
点此作者有关《》经验分享

  • 大小: 286.3 kb
  • 大小: 77.5 kb
  • 大小: 252.7 kb
  • 大小: 237.5 kb
  • 大小: 329.6 kb
  • 大小: 508.9 kb
  • 大小: 85.6 kb
3
0
评论 共 1 条 请登录后发表评论
1 楼 2017-01-04 17:31
不是游戏方面的算法进阶有什么好的建议吗?

发表评论

您还没有登录,请您登录后再发表评论

相关推荐

  • 请各小组在live space上以组为单位建立博客,并加教师博客为好友,然后在这篇日志下面回复小组博客地址。 谢谢 转载于:https://www.cnblogs.com/xinz/archive/2010/04/16/1881119.html...

  • 首先说明,我的回答是基于你是软件学院的学生这个前提来说的。  你的三个方向里,如果要做到一定层次,其实嵌入式是最简单的,网络是最难的,web居中。  不过问题在于,如果在一个基本面上讨论,则web是最简单的,网络居中,嵌入式最难。  区别在哪里呢?在于你能学到什么程度。说句武断的话,站在一个比较高的层次上来说,嵌入式系统如果去和网络通信、超大型系统编程相比,简直就是些小儿科的东西。但是也正如

  •                             应当正确解读“成功”                             ——从北大一位同学离校出走引发的思考     最近有媒体报道,北京大学信息科学技术学院的一位硕士研究生,于8月15日凌晨离校出走,至今音讯全无。据分析这位同学一贯学习成绩优异,考上北大后目标更高,发誓要混出个人样来。但在临近毕业之际,却遇许多不如意之事:“周

  • "机器学习、深度学习该如何入门?"这是不少读者朋友经常会在后台向我们问起的问题。如何系统化学习机器学习,第一时间掌握该领域最新的学习资料呢?这里跟大家推荐一个朋友红色石头...

  • 前言作为一个在it行业工作十五年的老兵,笔者在这里将自己多年的学习游戏算法经验分享给读者,希望能够帮助那些想学习算法提升自己的读者。

  • 作为一个在it行业工作十五年的老兵,笔者在这里将自己多年的学习游戏算法经验分享给读者,希望能够帮助那些想学习算法提升自己的读者。算法是it产品研发的核心,在it的任何领域都离不开算法,目前比较流行的it领域有...

  • 常见的机器学习算法 以下是最常用的机器学习算法,大部分数据问题都可以通过它们解决: 1.线性回归 (linear regression) 2.逻辑回归 (logistic regression) 3.决策树 (decision tree) 4.支持向量机(svm) 5.朴素...

  • 这需要开发者能将算法与实际项目开发完美的结合起来。算法是支撑项目开发的灵魂,不论是在web端还是在pc端以及移动端,很难想象如果一个项目没有算法,这个项目会怎样?在游戏公司,算法都是封装在引擎中,对于一般...

  • 混合算法是必经之路。 混合算法结合了两个或多个其他解决相同问题的算法,可以选择一个,也可以在整个处理过程之间进行切换。 这样做是为了组合每个组件的期望功能,因此总体性能要比单个组件的总体性能更好。 例如...

  •   小时候就梦想自己以后能够参与游戏的制作,自己开发出来的游戏是最受欢迎,但是成功的背后充满了泪水和努力,只看表面是永远不会成功的.假如你对游戏开发充满...必经之路:说到底就是"看书,写程序",但是不要盲目的

  • 该篇博文是从周志明教授编写的《深入理解 java 虚拟机》巨著里面的内容结合自身的一些理解,整理出来的一些内容,垃圾收集算法是内存回收的方法论:分代收集理论(弱分代学说、强分代学说、跨代引用学说)标记-清除...

  • java内存区域与垃圾收集算法 前言 好几天不更新了,之前说的设计模式相关文章暂时搁置了,因为我发现了一本好书,是由小傅哥编写的《重学java设计模式》,推荐想学习设计模式的可以购买一本,里面对常见设计模式讲解...

  • <body><div id="baidu_dup_fp_wrapper" style="left: -1px; width: 0px; height: 0px; bottom: -1px; overflow: hidden; display: none; visibility: hidden;...ifr...

  • 而选择何种的编程语言来搞算法,完全没有区别,只是在代码的实现上不同,而其背后的算法原理其实是一模一样的,而本片所采用的主流编程语言便是c/c 。上述注意事项,便是由百度的文心一言所直接生成的,内容很深刻...

  • shell编程排序算法 日历中的下一个任务,您最喜欢的运动队在联盟中的排名,手机中的联系人列表,所有这些都有一个订单。 当我们处理信息时,顺序很重要。 我们使用秩序来理解我们的生活并优化我们的决策。 想象一下...

  • _init__3.3 属性查找与绑定方法3.4 案例3.4.1 跑步案例3.4.2 家具案例3.5 私有属性3.6 继承3.6.1 面向对象的三大特性3.6.2 单继承3.6.2.1 继承的概念3.6.2.2 继承的语法3.6.2.3 方法的重写3.6.2.4

  •                                      软 件 测 试 基 础一、软件测试概述    软件测试是软件开发过程的重要组成部分,是用来确认一个程序的品质或性能是否符合开发之前所提出的一些要求。软件测试的目的,第一是确认软件的质量,其一方面是确认软件做了你所期望的事情(do the right thing),另一方面是确认软件以正确的方式来做了这个事件(do i

  •  jsp网站与phpwind论坛同步登入的解决思路 在上一篇文章中,笔者介绍了在windows上安装apache、php、mysql等软件的过程,以及apache与resin整合的方法。在这篇文章中,笔者将介绍jsp网站如何与phpwind论坛实现同步登入和同步退出的方案思路。本文以phpwind 7.5 sp3的源码为例,但由于笔者曾在源码中插入过一些测试代码,后虽作了删除,但尚

  •                                                            unix操作系统的入门与基础   与大家熟悉的windows用户界面和使用习惯不同,unix是常使用命令运行、极具灵活性的操作系统,目前的产品主要有ibm-aix、sun-solaris、hp-unix等。初期接触unix操作系统,下列的问题几乎是常遇的:由图形界面操作转到以命令行

global site tag (gtag.js) - google analytics
网站地图