&img src=&/50/v2-cfdc925b3c0e21a95e67bfd_b.jpg& data-rawwidth=&660& data-rawheight=&380& class=&origin_image zh-lightbox-thumb& width=&660& data-original=&/50/v2-cfdc925b3c0e21a95e67bfd_r.jpg&&&h2&第一阶段：java基础&br&&/h2&&br&&br&Java基础超级重要！！！ &br&学习java基础语法，确实很乏味，又没有项目成就感。我当时就走马观花地看完了相关语法，就迫不及待地去学习J2EE部分，那种能快速地基于框架，造成系统来了。&br&但是很快由于基础底子不好，在遇到一些问题，我根本想不出来这是为什么会出现这个问题？如果基础扎实的话，立马能从原理上看出问题所在。&br&所以很快我就被打回去了，这种项目实现不了挫败感就更强了。&br&那些岁月里，我应该断断续续重新学习j2SE不下五遍，但都不形成系统。&br&直到我看到了毕向东老师的那套java基础视频，讲得真精彩，比我大学里那挂着博导名号的老师讲得好太多了。&br&这个视频适合零基础的新人（非科班，完全没接触过编程的），也适合java基础部分不扎实的同学。&br&&br&&img src=&/v2-b999f94cccb_b.png& alt=&用户上传的图片& class=&content_image&&&br&&br&毕向东这套视频，不仅仅是java基础，同时涵盖了常见的设计模式、算法、数据结构。这套视频的知识点多，每天三四个小时左右视频教学，一共三十天这样。&br&我当时是全天都在学习，看完这套视频需要一个多月，整整一个暑假。很多人也推荐马士兵老师那套视频，我也看过几集。但是我还是推荐大家看毕向东老师的这套。跟着一个老师的教学走就行，中途易师，反而会导致学习节奏变乱。&br&关注我公号：我叫陈龙，关键词回复“java”，即可获得资源。&br&&h2&书籍推荐：&br&&/h2&&br&&br&&img src=&/v2-1d499827bffa8cd_b.jpg& alt=&用户上传的图片& class=&content_image&&&br&《Head First Java 》&br&这本书适合零基础人群，生动有趣，图文并茂，也简单易懂，基本画风如下：&br&&br&&img src=&/v2-e4d9b6fcb8afa649ec7d03b_b.jpg& alt=&用户上传的图片& class=&content_image&&&br&&br&&br&&img src=&/v2-6b51fff12b2fa14cc4975aaaf129e434_b.jpg& alt=&用户上传的图片& class=&content_image&&&br&无所不会，无所不能的李刚编著的《疯狂Java讲义》&br&这本书是我最近一直在看，相对很多大牛推荐的外国经典技术字典书，我更愿意推荐你看李刚这本《疯狂java讲义》，知识点全而细，讲解上也通俗易懂，同时没有外文汉译的那种语法拗口。使用情况：当做一本java字典书，需要了解某个知识点时再去翻看。不要以这本书当做入门教材，否则看多了会困。&br&&br&&img src=&/v2-940cf61c2bdb7f8d4cd1_b.jpg& alt=&用户上传的图片& class=&content_image&&&br&诸多大神强烈推荐的《Thinking In Java》&br&当时我学习Java的时候，有很多人推荐我看这本《java编程思想》，我当时也有借阅过同学的看过，并没有看完。但我感觉这是一本好书，知识点讲得很深刻，既然是大神推荐的，大家有空也看看！我会看的。&br&&br&&h2&第二阶段：java基础进阶&br&&/h2&&br&很多非科班培训机构出来的同学，在应用开发方面有所能力，但在计算机基础方面非常薄弱。计算机基础课程是哪些？
&br&数据结构与算法、操作系统、计算网络、计算机组成原理、编译原理、Linux。&br&这几大课程可以说是计算机科班的核心课程，几乎是现在一切应用层面开发的基础构成。&br&比如我们的代码是如何跑出来的？代码编译经过哪些过程？从编译原理那里，我们知道java代码要先编译成字节码，字节码再编译成机器码，最终以二进制形式被CPU识别运行。那CPU的工作原理是怎么样的呢？在计算机组成原理那里可以得到答案。&br&Java中集合类是如何实现的？这些其实可以在数据结构与算法中找到答案。&br&很多培训出来的同学在进行开发时候，是不知所以然的。反正业务代码能跑通就行，这样的程序员大概这辈子就去小公司了，搬砖达人。&br&大公司在招聘的时候，或在笔试或在面试，一定会考察这些知识点的。基本上在大学，能把这些基础课程学得好的同学，在校招中基本是offer收割小能手。&br&因为是Java学习，所以深入理解Java虚拟机也是极其重要的。推荐看这本书，也就叫《深入理解java虚拟机》&br&&br&&img src=&/v2-6e60ddb10f28c778ef8ba_b.jpg& alt=&用户上传的图片& class=&content_image&&&br&特此声明：如果你现在着急学习找工作或项目紧急需要，这个阶段的学习完全可以先搁置，面试前稍微理解即可。&br&真要去学习的话，没有一两年的长期战线是没法完成的。&br&如果你还是在校大学生，你比我幸运多了，有足够的时间，一定要仔仔细细地深入学习。&br&我现在就在学习，每天晚上会看看，以考试认证驱动我去再去系统地学习。&br&我下半年准备考软考认证，高级系统架构师，关于软考下次再说说。&br&&br&&h2&第三阶段：java基础进阶&br&&/h2&&br&搞javaWeb的连个页面都不会调，后台页面组件不会使用，真的会很尴尬。不要觉得自己不是前端工程师，不用写页面，这部分就不需要学习了。&br&对于这部分的学习，不需要熟练，但需要掌握！&br&主要的学习内容是：HTML、CSS、JavaScript、JQuery、Bootstrap。&br&这部分的学习，主要给大家推荐w3cschool：&a href=&/?target=http%3A//.cn/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&w3school 在线教程&i class=&icon-external&&&/i&&/a&&br&JavaScript学习：慕课网上的JavaScript入门篇&br&&a href=&/?target=http%3A///learn/36& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&JavaScript入门篇-JavaScript入门视频教程-慕课网&i class=&icon-external&&&/i&&/a&&br&慕课网上的JavaScript进阶篇&br&&a href=&/?target=http%3A///learn/10& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&JavaScript进阶篇_JavaScript视频教程-慕课网&i class=&icon-external&&&/i&&/a&&br&JQuery学习：慕课网JQuery系列教程&br&&a href=&/?target=http%3A///learn/418& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&jQuery基础视频教程-样式篇-慕课网&i class=&icon-external&&&/i&&/a&&br&&a href=&/?target=http%3A///learn/530& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&jQuery基础修炼圣典_DOM篇_jQuery视频教程-慕课网&i class=&icon-external&&&/i&&/a&&br&&a href=&/?target=http%3A///learn/429& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&jQuery基础修炼圣典-事件篇&i class=&icon-external&&&/i&&/a&&br&&a href=&/?target=http%3A///learn/430& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&jQuery基础修炼圣典-动画篇&i class=&icon-external&&&/i&&/a&&br&&br&&h2&第三阶段 数据库相关&br&&/h2&&br&页面已经能做了，那么页面渲染的数据是从哪儿来的？数据库！&br&这里主要学习MySql，Oracle看实际开发中需要再进行学习。&br&又在想java是怎么连接数据库，这里就要学习JDBC了。&br&&br&&b&关注我公号：我叫陈龙，关键词回复“java”，即可获得资源。&/b&&br&&br&&h2&第四阶段 javaWeb核心&br&&/h2&&br&这部分核心内容也是javaWeb的基础。现在框架当行，实际开发中几乎都是基于框架进行开发的。但是这部分的内容是框架的原理所在，要熟练掌握。学完这部分，就可以做动态网站了。&br&主要内容为：Http、Tomcat、Servlet、JSP、Ajax、cookie与session&br&学完之后，尝试动手，不依赖框架进行实战项目开发。&br&&br&&b&关注我公号：我叫陈龙，公号关键词回复“java”，即可获得资源。&/b&&br&&br&&h2&第五阶段
javaWeb核心&br&&/h2&&br&当下，Java后端框架众多，集合使用为主。目前较为受欢迎的两大框架集合：SSH、SSM。&br&SSH=Spring+Struts+Hibernate。&br&SSM=Spring+SpringMVC+MyBatis。&br&我目前在学习使用的SSM框架，Maven作为构建工具，似乎这套技术栈越来越受欢迎。看实际情况来学习。&br&框架就是工具，如果前面基础扎实了，对框架的学习上手就很快了。正比如练武之人，内功十年，招式一年。可见基础之重要。&br&这部分没有什么多说的，主要在练习，环境配置是最痛苦的了。一定要自己亲手去实现几个Dome，才能深刻理解框架设计的思想。&br&&br&&b&关注我公号：我叫陈龙，公号关键词回复“java”，即可获得资源。&/b&&h2&第六阶段
综合进阶&/h2&&p&&b&设计模式：&/b&记住这是在你实战编程两年以上，攒够了10万行代码之后才去下功夫学习高阶知识。要不你看有关设计模式任何书籍，都像看玄学一样。&b&没有足够的代码量，你也体会不到这些老前辈总结下来的设计模式有何巧妙之处。&/b&&/p&&p&但新人深刻了解单例模式，单例模式简单，在面试和实际开发中最为常见。&/p&&p&一分钟学会单例模式，再也忘不了&a href=&/question/& class=&internal&&如何用一个简单的比喻，让完全不懂编程的女生瞬间明白 Java 中的单例模式是什么，以及项目开发中在哪里用？&/a&&/p&&p&为了让大家深入地了解设计模式，引进知乎都有大牛参与回答两个问题：&/p&&a href=&/question/& class=&internal&&如何正确地使用设计模式？ - 知乎&/a&&br&&a href=&/question/& class=&internal&&设计模式有何不妥，所谓的荼毒体现在哪？ - 知乎&/a&&br&&p&&b&重构：&/b&一本武林秘籍，友情建议：重构需谨慎。&img src=&/v2-aacbb5961c08bcdfa1de3ef5e8712d74_b.png& data-rawwidth=&600& data-rawheight=&400& class=&origin_image zh-lightbox-thumb& width=&600& data-original=&/v2-aacbb5961c08bcdfa1de3ef5e8712d74_r.png&&&/p&&br&&br&&p&&b&为了初学者入门学习不迷茫，这里引借&a href=&/people/1fadc735b16850c0fbc9367aea9f8c5e& data-hash=&1fadc735b16850c0fbc9367aea9f8c5e& class=&member_mention& data-editable=&true& data-title=&@八戒& data-hovercard=&p$b$1fadc735b16850c0fbc9367aea9f8c5e&&@八戒&/a&的学习路径图，如下：&/b&&/p&&p&&b&&img src=&/v2-894ba729b00e3ce008cf11c4f2c8469d_b.png& data-rawwidth=&1819& data-rawheight=&1478& class=&origin_image zh-lightbox-thumb& width=&1819& data-original=&/v2-894ba729b00e3ce008cf11c4f2c8469d_r.png&&希望对你有用！&/b&&/p&&p&PS：再推荐一个我一直比较喜欢的Java公号，来自&a href=&/people/facc01df54eb5e5348287& data-hash=&facc01df54eb5e5348287& class=&member_mention& data-hovercard=&p$b$facc01df54eb5e5348287& data-editable=&true& data-title=&@刘欣&&@刘欣&/a&老师的&b&码农翻身&/b&，刘老师以非常白话、有趣的故事将Java的一些概念讲述得很好。&/p&&br&&p&PS：此篇文章，在公众号里和知乎上还是有点不一样的，我特地省去了一些没要的细节。&/p&&blockquote&&p&&b&在你们看到这篇文章之前，我特地拿着这篇文章的草稿去，请教了某java大神，八年大厂工作经验，履历牛X到你想跪舔的那种大神，反正我是跪舔了。&/b&&/p&&p&&b&大神也是一个严谨的人，对此篇文章的学习方向细节都提出了很大的改进建议。&/b&&/p&&p&&b&我也对应地做了反复修改，最终才更新出来。&/b&&/p&&/blockquote&
第一阶段：java基础 Java基础超级重要！！！ 学习java基础语法，确实很乏味，又没有项目成就感。我当时就走马观花地看完了相关语法，就迫不及待地去学习J2EE部分，那种能快速地基于框架，造成系统来了。 但是很快由于基础底子不好，在遇到一些问题，我根本…
&a href=&/?target=http%3A///share/home%3Fuk%3D%23category/type%3D0& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&视频集合&i class=&icon-external&&&/i&&/a&&p&链接在上面。这个集合不是我收集的，我也是找资料意外撞见的，作者孜孜不倦搜集了好几年的各种视频资料，计算机，机械，通信一应俱全，最新的AI，机器学习也都有。youtube上著名的深度学习课程也收集了，还是有很多你压根不知道有的机器学习课程。还有中科院的内部研究生课程，网上其他地方压根找不着的，他也搜集到了。我怀疑作者是中科院的学生。连本人前几天出的“小明教IC”都收集进去了。都是免费的哦，简直活雷锋！&/p&&p&顺便广播一下本人出品的《小明教IC》：&/p&&p&优酷地址：&a href=&/?target=http%3A///albumlist/show/id_& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&小明教IC-一天学会Verilog&i class=&icon-external&&&/i&&/a&&/p&&p&B站地址：&a href=&/?target=http%3A///video/av/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&小明教IC-一天学会Verilog&i class=&icon-external&&&/i&&/a&&/p&&p&优酷地址：&a href=&/?target=http%3A///albumlist/show/id_& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&小明教IC-IC设计概览&i class=&icon-external&&&/i&&/a&&/p&&p&B站地址：&a href=&/?target=http%3A///video/av/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&小明教IC-IC设计概览&i class=&icon-external&&&/i&&/a&&/p&
链接在上面。这个集合不是我收集的，我也是找资料意外撞见的，作者孜孜不倦搜集了好几年的各种视频资料，计算机，机械，通信一应俱全，最新的AI，机器学习也都有。youtube上著名的深度学习课程也收集了，还是有很多你压根不知道有的机器学习课程。…
&p&先说一句：随着Google那边的难度的水涨船高（参考Google的APAC Test/Kickstart），LeetCode上的知识点范围扩大不是不可能的，甚至是必然趋势。今天一看，连LeetCode上都有线段树/树状数组的题了，而且还是二维的，还有几何的题（求凸包的裸题，啊顺带一提，我MS的manager，辛苦想了半天实习生转正面试题，结果就想出来这么个东西，我表示比较失望……）那这样下去，以后冒出来二分图匹配/网络流什么的，似乎也没什么好奇怪了……&/p&&p&=====================更新的分割线=======================&/p&&p& 12:50&/p&&p&一爬起来，居然有100+的赞了，受宠若惊。怀疑是不是被最后一个题吓到了？&/p&&p&这当然不是面试真题了~不过和我Google某一轮面试的观感差不多。开门先问一个很经典、就要烂大街的并查集问题（动态加1的LeetCode 200，即LeetCode 305，其实根本不Hard，不过是这个并查集太少出题罢了），然后问，在上一问写了会路径压缩+按权合并（启发式合并）的并查集的基础上，请加入回撤上一步操作的功能（回撤只会使用1次，不会连续使用2次或更多次，即一定会是：修改-回撤-修改）……&/p&&p&整场面试就这么两问，像高考数学一样，递进的两问。&/p&&p&（幸好自己似乎听说过这种东西，想起来了，不然可能栽了。）&/p&&p&对Google这样的公司来说，在选择校招/很短工作经验的面试者的时候，出这种题可能是个必然的选择。问经验来看你的水平的话，肯定很不足的，那就考察思维能力和相关素质。考这个的话，我问原题，很可能还把背面经的人选进来了，那我也只能辛苦自己，（可以基于原题基础上）想一些至少在面经中比较新的idea了。&/p&&p&然后题目就显得比较过分了……比如 2016微软探星夏令营在线技术笔试 （hihocoder上的），还好，就有些剧毒了。&/p&&p&&a href=&///?target=http%3A///problemset/problem/1343& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/problemse&/span&&span class=&invisible&&t/problem/1343&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&p&&a href=&///?target=http%3A///problemset/problem/1344& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/problemse&/span&&span class=&invisible&&t/problem/1344&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&p&感兴趣的同学可以试试看。&/p&&br&&br&&p&至于最后一题的思路……其实中间的问题2就是提示。有2种思考方向，不妨都试试看？&/p&&p&更进一步的提示：能否给出一个，与坑数相关的，非指数/阶乘级别时间复杂度的算法（如果假设这里大整数加减乘除计算操作的时间复杂度是O(1)的话）（&&我没说线性哦~）？&/p&&br&&p&&b&剧透警告：已经有人在评论区给出了最后一题的原题地址和思路了。请在想到idea前，或者放弃思考前，不要去开评论区。&/b&（要完整通过（Accepted掉）原题，还涉及到离散数学/数论中逆元的知识，面试中很小可能把这个作为考点……当然，要你解释RSA原理的这类时候例外，但这个已经是比较专门的领域了）&/p&&p&=====================更新的分割线=======================&/p&&br&&p&我们先打住。LeetCode上提供了按Tag选题的功能，而且还提供了Tag对应的题数（有重复，一题可以打多Tag）。我们不妨看看从多到少，分别是哪些题型/知识点非常泛滥：&/p&&br&&img src=&/v2-87ec17ec6e52d6ece3cab2_b.png& data-rawwidth=&452& data-rawheight=&809& class=&origin_image zh-lightbox-thumb& width=&452& data-original=&/v2-87ec17ec6e52d6ece3cab2_r.png&&&br&&p&先说一下：有些分类（数组、字符串、数学）中的最简单的那批题目，其实有时候应该拉出来，单独搞一个分类，implementation（粗暴地实现），也就是说，按理说你学了一种常见语言就应该会写的。&/p&&br&&p&数据结构中，其实结构就2大类：线性的、非线性的。&/p&&p&线性的，按实现方式区分，连续的数组，非连续的链表。其中有2种特殊操作方式的，栈和队列。&/p&&p&非线性的，树形结构和图结构。&/p&&p&仔细观察，可以发现，线性结构中，数组上搞事占了绝对大头：数组自己这个分类就很大，然后一部分二分搜索、双指针方法等都有不少相关题目。&/p&&p&非线性结构中，树比图的题目多，深度优先搜索比广度优先搜索的题目多。&/p&&p&然后哈希表名列前茅，也没什么奇怪的吧……数组下标不方便用字符串？没关系，扔进Key-Value的数据结构里去，不需要有序就哈希表Hashmap，需要有序再上基于平衡树的map Treemap。如果要维护一个有没有x的集合，而x范围很大，那和map的道理类似，用相应的set就行了。&/p&&p&然而大部分时候不需要有序的，那哈希表这种理论复杂度O（1）的东西受青睐也没什么奇怪的了。&/p&&br&&p&算法方向上，&/p&&p&动态规划非常热门（我觉得有些属于递推的题目很可能划进去了，而且这个分类这么热，有些出乎意料但在情理之中）。&/p&&p&字符串类的题目……其实啥都沾边，暴力的实现、动态规划的思想、字典树这种数据结构，还有一些诸如后缀数组、KMP等算法。&/p&&p&数学……看了一眼，已经有按每位算过去的数位dp/递推了哦~当然，如果什么时候出现了费马小定理/中国剩余定理什么的，大家可以掀桌子不玩了（我的意思是，现在当然没有，在可见的5~10年内，也不太可能有，毕竟动态规划那边的潜力没挖掘完，除非岗位对数论要求高，否则没必要做出（相当于向普通程序员出网络流/线段树的题这种）出特定的人才学过的数论题的行为来）。&/p&&p&然后我们可以发现，接下去2位是二分搜索和双指针/尺取法了。&/p&&p&二分搜索比较有名气了，这个不知道请自行补课。双指针/尺取法的思想……较新的面经书上似乎开始讨论这个话题了，也可以自己搜一下。&/p&&p&然后深度优先搜索和广度优先搜索，2种暴力枚举所有情况的经典框架。不过树上深搜相对多一点，图上找最短路，其实可以把广度优先搜索改一改，就行了。而且，在有些时候，可能通过不同的途径，搜索到相同的子状态，这时候用记忆化的方法，去除之后的重复搜索来加速（这已经变成动态规划了，不过是从要解决的目标开始的自顶向下的顺序，而不是递推解动态规划的，从最小问题开始往上合并的自底向上了）。后面的极大极小搜索（2个人对弈游戏，问谁会赢这种，不过一般极大极小搜索的话，数据范围不大）也可以算在深度优先搜索里面。&/p&&br&&p&再往后，贪心的题，如果没见过，要想出来就太看脸了，很少出；排序，单机上的，基本都是固定套路，多机上的那是另一回事了；分治是泛化的二分搜索，也就是，我不一定二分了，可能三分什么的；图论的，考得少主要因为，那个存储图的结构，哪边写都烦；剩下的，10题以内的，都是国内公司基本不可能去考的了。&/p&&br&&p&然后还有一个分类，构造。直接说就是，分析题目意思，想出一种办法，保证能够满足题目要求并实现出来。可以划成贪心，因为大部分时候，每步操作非常简单粗暴；但是也和那些贪心题不一样，贪心的题，不少比较难证明正确性，构造类的相对还好一点……&/p&&p&==============================================================&/p&&p&最后提一点自己的思考？&/p&&p&1、Google什么的，可能是比较合适的风向标啊？比如Google Code Jam出了一个构造类的题，然后第二年就见到2家公司校招题把这个拿出来了……而且一个题型似乎会很容易流行开来，比如区间dp类的（最早腾讯实习生，最长回文子序列，然后Google、爱奇艺都搞了一个区间dp的题……）&/p&&p&2、其实面试题什么的，不一定说要考你数据结构上/算法上相当麻烦的部分（除非你去面对这方面有需求的岗位，比如机器学习、编译器等），对普通程序员岗位来说，理清一个问题，尽量无错又高效地实现出来，才是最重要的吧？&/p&&p&个人感觉：炫技的，看过才可能知道的那种小技巧类题目，会越来越不受待见。但是这两类题目还是会很多的：&/p&&p&1、要求似乎不难，比较清晰，但是一些要注意的细节比较多。&/p&&p&2、需要对题目进行一定分析，才能想到解答思路的。&/p&&p&==============================================================&/p&&p&顺带附赠动态规划/递推类题目的完整例子一个：（反正是陈题了，哪家公司现在还抄过去，那就有点逗了）&/p&&p&1、如下图，从左上角的a走到右下角的b，每一步，你只可以向右走一格或向下走一格。请问你有多少种不同的路线？（2种路线，只要不是完全重合的，就被认为不同。或者说，如果存在某一步第x步，这两个路线中，这一步采取的行动不一样，就被认为是不一样的。）&/p&&br&&img src=&/v2-f241a7885adc51a0abc43_b.png& data-rawwidth=&330& data-rawheight=&321& class=&content_image& width=&330&&&p&2、我们来加码了。&/p&&p&现在这个地图上，还有一些坑（黑色格子），我们不能踩进去，当然也不能从坑里走出来。&/p&&p&对下面这两张图，请单纯用纸笔计算从a走到b的不同的方案数，并展示你的计算过程。&/p&&p&（允许2张图用2种不同的思路，当然也可以用同一种思路）&/p&&br&&img src=&/v2-0e5fbbace7c165d16bc79a302f89a18f_b.png& data-rawwidth=&328& data-rawheight=&321& class=&content_image& width=&328&&&br&&img src=&/v2-a8daafb732_b.png& data-rawwidth=&395& data-rawheight=&421& class=&content_image& width=&395&&&p&3、我们继续加码。&/p&&p&这个地图最后不只是5*5/6*6那么小了，你需要处理最大10万*10万的地图了。不过幸运的是，坑增加的不多，整个地图上最多1000个坑。我们保证，起点a一定在左上角，终点b一定在右下角，并且a和b 2点上一定没有坑。&/p&&p&请根据上述的情况，设计一个尽可能高效的算法。（假设实现你的算法的时候，所用的编程语言提供了非常高效的高精度计算方法，大整数计算这里的效率损失不需要考虑）&/p&
先说一句：随着Google那边的难度的水涨船高（参考Google的APAC Test/Kickstart），LeetCode上的知识点范围扩大不是不可能的，甚至是必然趋势。今天一看，连LeetCode上都有线段树/树状数组的题了，而且还是二维的，还有几何的题（求凸包的裸题，啊顺带一提，…
&p&日更新：越来越多人私信我推荐全脑学习训练的书，2015年底应承了某出版社的翻译邀请，翻译美国心理学教授西格比的美国畅销书《如何高效记忆》，历时一年多的凌晨终于完成了出版社的期待，一定不让各位读者失望，新书出版时将在这里更新通知，谢谢一直期待的朋友。&/p&&p&日更新：最近太多人评论和私信我怎么记英语单词，我的回答：如果你是高二以上英语水平，可以按照刘一男词源法记单词，有逻辑、有趣。非广告，网络有免费视频下载。&/p&&p&本人2011年参加世界脑力锦标赛，获得世界记忆大师（当然很多人认为这个称号不权威，不科学等等，这里我也不做其他说明，你们自己评论，最重要是我的内容对大家有帮助），世界排名就不说了，目前不想在知乎实名。&/p&&br&&p&重新看了自己的回答，也看了所有的评论，有朋友提到要实践，但是如果不先讲清楚这些基本的原理直接讲实践会收到更多私信了，这题就答不下去了。&br&&br&以下内容是本人近6年全脑经验，任何商业用途的转载请先私信联系取得邮件授权。&br&&br&谢邀，在知乎上好像很少被邀请答题，我也就装摸做样“谢邀”一下&br&&br&目前排名第一的答案讲了原理，也讲了实践，都是比较赞同的，我补充一点，通常扑克牌记忆高手会在一个地点（也就是组成一个小的记忆宫殿的一环）联结两张扑克，这两张扑克联结的时候会有先后顺序，熟练运用的人可以采取主动被动、左右空间、上下空间等等来区分。对于初学者，你可以理解为地点是舞台，扑克转换成图形是演员，你的大脑是导演，想要演什么戏都听你的。&br&&br&我再总结一下，想要成为记忆高手需要加强三个方面的训练，相当于将记忆训练分成了三个环节：成像、联结、搭建宫殿。&br&&br&今天先到这，手机码字不易，先吃饭了。&br&&br&&br&以下3月8日凌晨更新&br&&br&周六的夜晚睡不着，想起知乎还有题没有答完。接着前面的说。&br&&br&成像&br&&br&通常来说图片的记忆比文字更深刻、长久（具体原理就不说了，大家体会一下：平时我们很容易记得电影的剧情，但是对于个别的人物名字却可能忘记）。提高记忆首先要提高大脑的成像能力，这里又可以分为三步操作。&br&1、积累大脑中的图片存储。平时看到鲜明的图像，刻意闭眼回想并仔细想图片的细节；多让自己接触陌生新鲜的事物，增加大脑图片；等等。&br&2、控制图片的变化。当我们的内存多了，要让自己可以随意调取（调取这个词用得不是很准）。练习在大脑中缩小放大图片，甚至可以让图片变形，当然一定要保持一定的逻辑性，这种逻辑只要自己可以理解就行。&br&3、随时成像。平时不管是否需要记忆的内容，看到了文字就立刻想到大脑中第一反应的图片，尽可能让图片清晰（不一定全部清晰，只要图片的独一无二特征能够成现在脑海中就可以）。看到一些图片，自然地联想到其他图片。&br&以上三步要练到自然反应潜意识的地步很难，目前我知道的《最强大脑》的诸多选手都是在有意识的阶段，我也是在有意识的阶段。所以各位练习不要觉得很难，能做到有意识的熟练成像就很好了。&br&&br&今天先到这，明天还要加班。后续再更新，各位慎重点赞，私信我的朋友还没有来得及回复，很抱歉。&br&&br&以下内容更新于3月8日晚&br&&br&该说说联结了，对于基础的人来说更应该讲第三点搭建宫殿的，很多人给我私信问得最多的就是怎么搭建自己的记忆宫殿了。但是记忆宫殿的搭建篇幅很多，还是放在后面讲。&br&&br&联结有两种，首先是图片与图片的联结，当然此时图片在脑海中都是真实的物品了，让它们产生动作，互相发生效果—碰撞、敲打、缠绕、压、滚动等等。按惯例，举个栗子：香蕉和手机，黄色芳香的香蕉肉涂抹在手机屏幕上（这16个字在大脑中不过是1-2秒的动画，印象会很深刻）。再来一个栗子，哑铃和滑板，冰凉沉重的哑铃用力砸断了滑板（注意想象声音等其他相应的效果）。这里特别还要注意先后顺序，第一个栗子，如果是手机和香蕉，可以联结为，一个坚硬的手机（脑补诺基亚）砸断了黄色芳香的香蕉（香蕉肉都被挤出来了，画面太美，一定要脑补到位），这是第一种“内容”的联结。&br&再说说内容与载体的联结，记忆的内容多了，需要载体来装载，如同书多了需要书架，否则怎么随时找到你想要的书呢？这里的载体就是记忆宫殿的一个部分了，很多人可能误以为会创建记忆宫殿就可以记任何内容了，这里要让有的人失望了，不是这样的，先透露一点记忆宫殿搭建的内容，现在可以脑补一个微型记忆宫殿（我尽可能用常见物品），一个房间，左上角有床（颜色材质自行想象，这样有利于你们的宫殿更“牢固”），右上角有冰箱（属性同样自行脑补，一定要脑补），右下角有茶几（记得脑补），左角有沙发（一定要脑补）。讲完宫殿搭建，你们自然会明白，这里还是继续说联结，需要用到刚刚搭建的微型宫殿，继续往下阅读前请一定确保宫殿已搭牢固（检验的方式是闭上眼可以在大脑中非常清晰地看到房间的四个地点（物品，世锦赛选手习惯称之为地点或者桩）。&br&接下来我用8张扑克来举个栗子，分别是&br&黑桃6&br&钻石Q&br&梅花8&br&黑桃10&br&红心6&br&梅花K&br&红心Q&br&黑桃2&br&先保存一下，手机敲字不小心右滑一下就全没了。&br&按照前面的步骤先成像（这里实际是在教大家如何用将抽象易混淆的东西成像），8张扑克分别对应：&br&黑桃6（六个核桃应该都知道吧，这里可不是做广告，大家试着成像为奶白色的六个核桃液体）&br&钻石Q（扑克中Q是王后，戴着钻石的王后，引申为钻石王冠，这个引申可能有少部分人无法接受，这里我另外说几句，每张扑克或者其他需要记忆的内容成像的时候是想到大脑中第一反应最清晰的图，世锦赛或者《最强大脑》的选手，扑克是固定的，这种成像通常也是固定的，例如钻石Q成像为钻石王冠就不再经常变动了，就是为了想到钻石王冠的时候最快速的反应为钻石Q）&br&梅花8（简读为花八，再谐音为花瓣，成像粉红色的牡丹花瓣）&br&黑桃10（简读谐音为黑市，成像为一张盖满红手印的高利贷借据，由黑市我的第一反应就是这个了，读者们可自行脑补）&br&红心6（谐音红路，成像为红地毯，看官们可以成像为红毛巾等等，取决于你们的第一反应最清晰的是什么）&br&梅花K（谐音为画框，谐音有困难的请不要私信了，评论让读者们一起解决吧，私信我回答不过来，成像为蒙娜丽莎图）&br&红心Q（谐音为红圈，成像为红色心形图案的呼啦圈，可能有人会反驳黑圈也可以是呼啦圈，是的，这个主观意识占了很多因素，难以考虑到每个人的思维方式，请参考钻石Q的成像解读）&br&黑桃2（简读桃二，谐音套儿，是的，很多人第一反应应该是避孕套，成像避孕套自行脑补就行。另外有一点非常重要的因素这里告诉大家，我们成像的时候多往自己熟悉的领域联想，讲成像的时候我也提到了要多往陌生的方向扩张图像，也就是增加熟悉领域的范围。我增加几点成像的方向，暴力，夸张，惊恐，两性等这些都是让人印象深刻的画面。所以这里成像避孕套，对于一个正常的成年男女应该都是有益于增加印象的）&br&&br&手机码字真的不容易，今天先到这了，后面一定会更新，不过大概是一周以后了。有问题私信的真的没法及时回复，见谅。&/p&&br&&p&以下内容更新于3月14日晚&/p&&br&&p&是的，各位知乎的朋友，我又来了，这一周过得非常兴奋，一是工作节奏非常紧，今天周六加班刚刚回；二是这个回答每天都有人点赞、感谢，真让我受宠若惊，以前被成群的学员围着要签名也没有这么激动，第一次在知乎有这么多赞和感谢（原本我前文说的排名第一的答案是由wink chow提供的，特此说明，以免带来阅读障碍）。好了，不废话了，说你们想要听的。&/p&&br&&p&上次说完了8张扑克的具体成像，要进入到联结的具体操作了。先回想一遍前文我说的小房间（从左上角开始，床，冰箱，茶几，不记得的一定闭上眼在脑海中多复习几遍）。8张扑克的成像我就不带大家复习，一定清晰成像。&/p&&p&考虑到很多朋友是零基础，我先将扑克联结，然后再联结地点（桩），实际练习和记忆时应该是同步完成的。另外补充一点，一般稍有基础的学员或者比赛选手是一个地点联结两张扑克，觉得有困难的可以先尝试一个地点联结一张扑克。&/p&&p&奶白色的核桃液洒满了钻石皇冠，皇冠上的白点散发出核桃的味道，这个故事发生在左上角的床上，同时床上也被洒了核桃液。&/p&&p&粉红色的牡丹花瓣纷纷落在印有鲜红手印的高利贷拮据上（注意花香和血腥味的强烈对比），这个场景当然发生在右上角的冰箱里面（可以配合想象冰箱冒冷气的情景）。&/p&&p&红毛巾蒙住了蒙娜丽莎的半边脸，这个故事发生在右下角的茶几，完整的故事可以是红毛巾蒙住了坐在茶几上的蒙娜丽莎的脸（注意其中坐在茶几上这个动作其实是不完全有逻辑，也就是一种非逻辑，恰好是这种逻辑与非逻辑的结合更容易让人印象深刻，试想抛开人性的善恶你会更关注人咬狗还是狗咬人呢？自己体会，这个词我在这个回答里面多次提到，后面还会提到）&/p&&p&红色的呼啦圈滚动着轧到使用过的避孕套，避孕套流出液体（这里应该不用我详细描述了，相信你们早已脑补完成），故事发生在沙发上，注意不同材质的沙发呼啦圈滚动的方式不同，根据你们脑中所想沙发的材质和属性自行完善。&/p&&p&以上故事闭上眼重新回忆一遍画面（不能完整回忆的，再复习一遍联结的画面，仍有问题的可以具体问题私信我，太多人私信的话可能要下个周末才能回复全面了），如果你的小房间记忆清晰，8张扑克的成像原因很清楚并且成像清晰，那么恭喜你，这8张扑克你已经记住了。是不是略有成就了？！如果你的小房间有10个地点，并且每张扑克都有成像，稍加训练，5分钟记住20张扑克就不难了。&/p&&p&讲到这里，关于成像和联结再补充一些重要的内容。&/p&&p&数字的成像对于很多比赛选手（代指世界脑力锦标赛参赛选手，下同）都差不多，包括11年比赛我和英国、德国、日本、美国、哈萨克斯坦等选手交流时也是如此：00~99总计100个两位数大多根据谐音、特殊意义、形状等对应不同的图片，例如16对应石榴，61对应儿童（通常会引申为哪吒、红孩儿等具体的儿童），97对应拳皇的某个人物或者招式，更多数字对应图片可以百度，直接搜数字编码表就可以。如果这也想做伸手党，我觉得你不是真的想要提高记忆力。个别图片（行业里面我们一般称编码，不称图片）可以私信或者评论交流。有德国选手在12年邮件交流时说到已经采用四位数编码了，也就是，总计一万幅图。不过更多人还是两位数编码。&/p&&p&选手的扑克编码（也就是图片，后文的编码也是图片的意思）通常也是基于数字的，除去JQK其余四十张扑克（比赛是不记大小王的，这里就不讨论大小王了）对应10到49四十个两位数，原则或者说规律是：花色按照黑桃、红心、梅花、钻石排序分别对应1、2、3、4作为两位数的十位（玩过扑克的应该都懂，不懂得也可以这样理解。黑桃有一个尖，红心有两个凸起，梅花有三瓣，钻石有四个尖角），扑克的数字作为个位，例如红心5就对应25的图片，梅花2对应32的图片。JQK可以自己对应人物和物品，这里不多说了，比赛的东西说多了就和原来的问题歪得太多了，有机会专门写一些关于比赛的。&/p&&br&&p&终于写到第三步搭建宫殿了，今晚用surface答题果然效率高很多，只是不确定今晚能否答完搭建宫殿的内容。先稍稍休息一下，五分钟后回来。&/p&&p&休息一会反而有点瞌睡了，能写多少算多少了，今晚估计是答不完了。&/p&&p&通过前面联结的讲解，相信大家都理解什么是最简单的记忆宫殿了（利玛窦的〈记忆宫殿〉一书中所说的最简单的记忆宫殿大概就是我说的小房间，不推荐大家读这本书，真的不好看，看了也许你会对记忆宫殿更加疑惑了，先练习一些基础吧），我这里再重新说个记忆宫殿的概念：多个房间按照一定的顺序（通常就是空间顺序）组成的一幢大宅，房间是多个地点（物品）按照一定顺序组成的一组地点（注意，一般不说地点组，三五个房间连在一起称之为地点组，大家理解就好）。&/p&&p&通常选手都会有很多组地点，每组也就是每个房间26个（适应记扑克）或者其他个数地点。一个房间不一定是真实的一个房间，可能只是一片封闭的区域。也有人不采取封闭的区域，这里就不展开讨论了，我认为还是封闭的区域好，不容易受到干扰。&/p&&p&最开始建立宫殿大多从自己最熟悉的环境开始，例如家中卧室，有学生的朋友也可以是宿舍，总之就是自己经常待的地方，门口通常是一组地点开始的地方，想要实际操作的朋友先尝试在一个自己最熟悉的环境找十个地点（最好不要重复，熟练了也是可以重复的，但依旧不建议），最好写下来，反复在脑海中复习，同样要求做到像成像一般清晰有特征。&/p&&p&按照上面的方式找了两三处熟悉的环境就要开始发挥自己的想象力拓展房间的大小了，原来十个地点的房间可以在比较空白的位置凭想象力加入地点，将一个房间的地点数目延伸到20个甚至更多。&/p&&p&不知什么原因，写到头疼了，今天先到这把，刚好各位先尝试建立两到三组地点。我会回来的。&/p&&br&&p&又到周六，感谢朋友们赞和感谢，我又回来了，今天再延伸讲讲宫殿的搭建，如果有朋友按照我前面所说的实践了，应该都有1-3组地点了，貌似这段时间私信的问题中没有人提到怎么找这样的1-3组地点，我姑且就认为你们都看懂了。以下内容更新于3月21日晚。&/p&&br&&p&有了基础的几组地点，如果你对成像和联结都有一定练习，可以尝试记点有意义的知识了。这样会促进你有动力搭建更多的地点，这里插一句，你们搭建的地点一定要写下来，电子档或者纸质的都好，再好的设计师也有可能忘记自己曾经设计过的房子，我们脑海中搭建的房子当然也要保存下来，不然找不回的一天可就后悔莫及。&/p&&p&用心的朋友可能很快就会发现，能积累的房间实在有限，想要记忆更多内容根本不够用，是的，这种问题评论区有提到，以前也有很多学生问过我，只要你成功的在脑海中搭建过10个房间，更多房间就绝不是问题了。至少有三种方向可以尝试。&/p&&p&一、去新鲜陌生的地方。增加大脑接受更多新鲜陌生的事物也有利于我们成像的练习。每当我们去到一个陌生的环境，例如：咖啡厅、图书馆、餐厅、银行、奶茶店、棋牌室、办公室、候车厅等等，我尽可能列举了不同人群可能去到的地方，只要我们待上几分钟用心观察（不要害怕他人的异样眼光，我曾经为了比赛准备足够多的地点无缘由的去到银行大厅只为记下银行环境，这么说你会不会觉得我是抢银行的？是的，差点被保安赶出来，其实赶出来也无所谓），在脑海中数下自己标记的明细地点，回到家马上画出记忆中的地图，即使有不记得的地点也没所谓，反正不记得了，随便用自己喜欢的物品代替就好了，然后反复复习几遍，根据复习效果做细微的调整，直到大脑最愿意接受的样子。再说说我自己，有段时间走到哪里都会记下周边环境，回头就积累成了自己的房间。我大概有一两千地点就是这样积累的。&/p&&p&二、虚构房间。随着房间越来越多，你的大脑的空间感觉也会越来越好，随意给你一间空房子都可以“装修“成你想要的模样，这时候就可以随意找一个相对封闭的环境，脑海中摆上自己想要的东西组成一组新的地点，像第一种方式一样再多复习修改几次，新房间就搭建好了。这种方式有很多热和我说过刚开始有点难，因为确实刚开始这种想象方式有些难度，但也很容易克服，有过一两次经验就好了。以前背【道德经】的时候，我有一半的地点就是这样的方式来的。（背【道德经】肯定有不少人感兴趣，但是这里就不展开了，对于基础不多的人要展开还真不容易，写得不够清晰不知道有多少人要私信我了。不知道在知乎写专栏是怎么回事？好像不是想写就可以写的，有知道的朋友麻烦私信我，先谢谢。）&/p&&p&三、万事万物皆能成为房间。这种方向扩充地点一般不作为比赛用，但是对于学习实践很有帮助，具体讲之前，我再和大家回忆一下什么是地点（房间），就是一组有序的地点。重点在有序和地点，为什么要有序？为什么是地点？因为有序大脑才有线索，因为地点脑中才有图片。反过来只要满足有序和图片都可以成为房间。我就不再说什么更多理论了，你们继续看例子。&/p&&p&1、床前明月光，疑是地上霜，十个字可以对应十幅图，下面看详解，有领悟到的朋友请跳过。&/p&&p&床，图片就是一张床，有了前面的讲解，该怎样想象这张床就不用我多说了吧？什么颜色？什么材质？大小形状你们自行想象。&/p&&p&前，当然是谐音成“钱“了，至于是人民币还是美元、欧元、英镑、卢比或者面额多少就看你对什么钱最熟悉了。你乐意用元宝的图片也行。&/p&&p&明，我不知道你们最快出的图片是什么，我的是名字相近的一个朋友。&/p&&p&月，弦月，半月，圆月，或者其他你最快想到的清晰图片。&/p&&p&光，台灯，不解释，你们自由发挥就好。&/p&&p&疑，姨，很简单吧。&/p&&p&是，我想到了西红柿。&/p&&p&地，弟弟，帝王，土地，多给几个大家参考。&/p&&p&上，楼梯，这个我只想到了一个，欢迎评论区高手神回复。&/p&&p&霜，霜雾，双飞（不知不觉已被网络邪恶了）&/p&&p&以上是不是很简单，这样的熟悉诗句随手拈来嘛。可能也有朋友发现了，房间不仅要有序有图，还要熟悉，所以我们只能找自己熟悉的诗词，这里就涉及到记忆学中饱含哲学的四个字，我相信能看到这里的朋友是可以体会的--以熟记新。慢慢体会，祝你们在记忆的路上越来越顺。&/p&&p&写到这里可能有人觉得没有了，怎么会？我还有很多没有说的。主要是对于补充问题一直还没有正面回答，先回答一下补充问题&/p&&p&问题补充：如果左撇子的话应该右脑比较发达，而右脑主要负责图像处理，这是否是说左撇子更易掌握记忆宫殿方法？&/p&&p&我认识的人没有发现左撇子更容易掌握记忆宫殿，不过我认为练习左手对于右脑图片思维是有帮助的，10年开始我练习用左手吃饭和刷牙，现在基本一半时间左手，一半时间右手。但是这种帮助我很难量化，我一直训练，并没有发现水平突飞猛进的时候，一直是波动地前进。我的解释是：记忆宫殿的掌握不仅是图像感就可以的，也需要逻辑思维的辅助，所以我一直认为记忆是左右脑结合的事情。&/p&&p&答题时间过得很快，明天全天都有安排了，赶紧休息了。&/p&&p&知道怎么在知乎写专栏的请私信我。&/p&&p&下次是否需要继续讲万事万物都可以成为房间看你们的评论和私信内容了。&/p&&br&&p&以下内容更新于3月29日晚。&/p&&p&昨晚有通宵牌局，只好中间抽空发了几条评论，久等周六能更新的“忆友（以前网络沟通，我对记忆感兴趣的朋友通常这么称呼）“，向你们说声抱歉。不过今晚我还是来了。&/p&&br&&p&继续万事万物都可以成为房间的内容，看到评论区的留言，有“忆友“似乎没有理解房间是做什么用的。今天我先强调房间的意义，也就是大家看到的记忆宫殿到底在记忆的环节中起到什么作用，房间和宫殿只是记忆内容的载体，想象一个书架，知识是书本，我们利用脑海中搭建虚拟的书架，也就是房间，来盛放知识，接下来是复习和熟练知识，知识一定是有内在的逻辑关系的，渐渐脱离了宫殿也将知识记住了。感谢评论区@薏米红枣八宝粥 的留言，相信这段解释已经回复了你的第一个问题。&/p&&p&注意，不是宫殿记好了内容就结束了，还有，复习！&/p&&br&&p&万事万物皆可成为房间，上次只举了一种例子，熟悉的诗词可以转化为宫殿。以下继续距离。&/p&&p&2、身体定位&/p&&p&头顶、耳朵、鼻子、嘴巴、脖子、肩膀、肚子、大腿、膝盖、脚&/p&&p&这十个从上到下的身体部位也可以是一个房间，因为完全符合有顺序和熟悉的两大特点。&/p&&p&也可以试试用你的五个手指定位，平时很多人也会掰手指记忆东西，只是运用得不够彻底。&/p&&p&3、数字定位&/p&&p&还记得前面讲的数字编码吗？既然每个两位数都转化成图片了，如果你已经熟悉了，作为房间使用已经完全没问题。&/p&&p&4、内容转换成房间&/p&&p&如果想记忆“马关条约“的内容，假设刚好四条内容（以前有学生咨询过我，是不是四条我不确定），马关条约四个字刚好成为房间对应四条内容。&/p&&p&马，这个已经非常容易了，颜色，大小等属性各位自行脑补。&/p&&p&关，鸡冠，皇冠，随便什么了，第一印象什么最清晰了。属性自己加。&/p&&p&条，皮带，条形码，调料包，能看到这里的“忆友“不需要我解释了吧。&/p&&p&约，这个词最近两年都很热，你们自己想吧，我就不给参考了。&/p&&p&万事万物作为房间我就说这么多吧。&/p&&br&&p&@薏米红枣八宝粥 的评论提的非常好，显然是有自己的经历再提出的问题。原话如下：“我小的时候看到一个最简单的一个记忆训练方法：第一阶段，专注的看一面砖墙，你一眼看到的面积马上闭上眼睛要说出多少块砖。开始可能是十块那么大面积，慢慢累加增大面积，直到能把视觉范围内的砖块能一眼看出来是多少。平时也可以按照这种方法看其他的静止的东西来锻炼。第二阶段，同样的方法改成看活动的东西，比如天上飞的鸽子、鸟群等等。实际上第一阶段如果完成一大半就会完全变了一个人。大神您觉得写方法行么 ”&/p&&p&这种记忆的方式我在很多书中也接触过，一般称之为“照相式记忆“，我尝试过，不过和比赛关联不大，练习不多，问我这种方法是否可行，我的回答当然是可行！&/p&&p&同样是这位“忆友“也提到想了解我的全脑学习和实践历程，简单说吧，比赛的训练也是基础成像能力和房间搭建能力的训练，比赛前半年我每天8小时以上的训练，内容就是针对比赛项目训练我在此回答前面的内容。最开始是接受了2天的专业培训（现在网络资源很充足我就不做推荐了，不花钱也是可以学到的），后面通过自身看书和交流学习不断进步，这中间看了至少有20本相关书籍吧，对我帮助最大的是托尼博赞和七田真的作品（网上很容易找到），博赞的书适合实际操作，七田真的书对理论和身体的调节有非常大的帮助，各位可以理解为前者是招式，后者是内功心法。&/p&&br&&p&不知不觉写了很多，六年的积累确实是有不少东西，自己都有些吃惊。连续更新了四个星期，这个回答不会再更新了，接下来工作更忙，出差也会增多。感谢各位“忆友“的关注，特别感谢知乎好友@czMay 的鼓励与支持。&/p&&p&评论私信可继续，我差不多每天都会上知乎，可能不一定即时回复，但总会回复的，我在知乎也不是什么大牛，还不至于私信和评论多到回复不过来。&/p&&br&&p&最后，祝你们进步，感谢你们的赞、分享和收藏，我的回答也让我更充实。&/p&&p&记忆总结成四个字就是“以熟记新“&/p&
日更新：越来越多人私信我推荐全脑学习训练的书，2015年底应承了某出版社的翻译邀请，翻译美国心理学教授西格比的美国畅销书《如何高效记忆》，历时一年多的凌晨终于完成了出版社的期待，一定不让各位读者失望，新书出版时将在这里更新通知，谢谢…
&p&技能学习路线这事儿，可以参考一下我之前做的：&a href=&///?target=https%3A///phodal/sherlock& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&phodal/sherlock&i class=&icon-external&&&/i&&/a&&/p&&br&&img src=&/v2-895dba812da3d738ec490cfabe656746_b.png& data-rawwidth=&2168& data-rawheight=&1210& class=&origin_image zh-lightbox-thumb& width=&2168& data-original=&/v2-895dba812da3d738ec490cfabe656746_r.png&&&br&&p&如果不方便的话，可以使用技能树的移动版『&b&Growth 技能树&/b&』。&/p&&img src=&/v2-5a567bedeeb6f8c08f96be_b.jpg& data-rawwidth=&600& data-rawheight=&300& class=&origin_image zh-lightbox-thumb& width=&600& data-original=&/v2-5a567bedeeb6f8c08f96be_r.jpg&&&br&&p&如果他们还不能满足你的话，我还有开源应用 &b&Growth&/b& （PS: 其实我是来打个广告）：&a href=&///?target=https%3A///phodal/growth& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&phodal/growth&i class=&icon-external&&&/i&&/a&。&/p&&blockquote&Growth是一款专注于Web开发者成长的应用，涵盖Web开发的流程及技术栈，Web开发的学习路线、成长衡量等各方面。在这里，你将通过不断检验自己的学习成效，形成属于你自己的独一无二的个性技能图谱。&/blockquote&&p&算了，我还是上图：&/p&&img src=&/v2-457d7150acdd8fac1fc458_b.png& data-rawwidth=&600& data-rawheight=&450& class=&origin_image zh-lightbox-thumb& width=&600& data-original=&/v2-457d7150acdd8fac1fc458_r.png&&&p&内置了接近 5,000 个 star 的开源电子书 &a href=&///?target=https%3A///phodal/growth-ebook& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&phodal/growth-ebook&i class=&icon-external&&&/i&&/a& 的首页&/p&&br&&p&丰富的探索项目，可以让你找到练手项目：&/p&&img src=&/v2-82e093ef7c3f57dd6ecc1d0cb4baf13f_b.png& data-rawwidth=&600& data-rawheight=&337& class=&origin_image zh-lightbox-thumb& width=&600& data-original=&/v2-82e093ef7c3f57dd6ecc1d0cb4baf13f_r.png&&&p&测试自己的能力：&/p&&img src=&/v2-7cdbf4e4e4a4d4cebbb00552_b.png& data-rawwidth=&600& data-rawheight=&337& class=&origin_image zh-lightbox-thumb& width=&600& data-original=&/v2-7cdbf4e4e4a4d4cebbb00552_r.png&&&p&寻找相应的学习路线：前端、后台、DevOps&/p&&img src=&/v2-bab9c6cebbf764cbf10d8_b.png& data-rawwidth=&600& data-rawheight=&337& class=&origin_image zh-lightbox-thumb& width=&600& data-original=&/v2-bab9c6cebbf764cbf10d8_r.png&&&p&并且内置了丰富的软件解决方案：&/p&&img src=&/v2-51a5f21be33dc5c_b.png& data-rawwidth=&600& data-rawheight=&337& class=&origin_image zh-lightbox-thumb& width=&600& data-original=&/v2-51a5f21be33dc5c_r.png&&&p&各式各样的工具：&/p&&img src=&/v2-e8be93df105_b.png& data-rawwidth=&600& data-rawheight=&337& class=&origin_image zh-lightbox-thumb& width=&600& data-original=&/v2-e8be93df105_r.png&&&p&还有其他 &a class=&member_mention& href=&///people/fea2f801ab1dc87a87f8bdeb6fdb3394& data-hash=&fea2f801ab1dc87a87f8bdeb6fdb3394& data-hovercard=&p$b$fea2f801ab1dc87a87f8bdeb6fdb3394&&@phodal&/a& 写的各个电子书&/p&&img src=&/v2-cadbfed0f_b.png& data-rawwidth=&600& data-rawheight=&337& class=&origin_image zh-lightbox-thumb& width=&600& data-original=&/v2-cadbfed0f_r.png&&&br&&p&&b&原价 999 元的全栈工程师套餐，现在对年薪百万的各知友通通免费。&/b&&/p&&p&&b&原价 999 元的全栈工程师套餐，现在对年薪百万的各知友通通免费。&/b&&/p&&p&&b&原价 999 元的全栈工程师套餐，现在对年薪百万的各知友通通免费。&/b&&/p&&p&各大 Android 应用商店和 App Store 都可以免费下载到。&/p&&p&iTunes: &a href=&///?target=https%3A///cn/app/growth/id%3Fl%3Dzh%26ls%3D1%26mt%3D8& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Growth: 带你成为顶尖开发者&i class=&icon-external&&&/i&&/a&&/p&&p&应用宝：&a href=&///?target=http%3A//a./o/simple.jsp%3Fpkgname%3Dren.growth& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Growth&i class=&icon-external&&&/i&&/a&&/p&&br&&p&欢迎入圈打赏，&a href=&///?target=https%3A///mweb/views/joingroup/join_group.html%3Fgroup_id%3D%26secret%3Dg6pdt8ffwxxt2nmf0qh2e3wbh8w0diiu%26extra%3Dd962a3de2e1f1a701f109c50f79e5acd067c805be30& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&phodal's 的全栈圈&i class=&icon-external&&&/i&&/a&&/p&
技能学习路线这事儿，可以参考一下我之前做的： 如果不方便的话，可以使用技能树的移动版『Growth 技能树』。 如果他们还不能满足你的话，我还有开源应用 Growth （PS: 其实我是来打个广告）：。Growth是一款专注于Web开发者成…
&p&不要没事去搭建hadoop, spark集群!!!&/p&&p&不要没事去搭建hadoop, spark集群!!!&/p&&p&不要没事去搭建hadoop, spark集群!!!&/p&&br&&p&初学者不要关注性能调优!!!&/p&&p&初学者不要关注性能调优!!!&/p&&p&初学者不要关注性能调优!!!&/p&&p&牢记上面两点忠告, 这将节省你大量宝贵的时间。懂得取舍也是一种智慧。&/p&&p&我的建议, 下载完安装包, 配置成单机版, 开搞。&/p&&p&学习hadoop, 首先要了解什么是倒排索引. 然后尝试用mapreduce实现inner join, 解决top-k问题, 解决简单的好友推荐问题, 之后可以深入了解一下hive里的join, group by, distribute by的实现, 搞清楚怎么样把一段SQL拆分成各个stages，深入总结一下，什么样的情况下必须要有merge stage，假如给你十亿的样本，你该怎么借鉴mr的基本思想实现全局排序？&/p&&p&学习spark, 推荐用scala. 首先了解rdd和dsstream, 用mllib从头到尾实现一下官网的决策树, 逻辑斯蒂回归, 线性回归, 找到成就感, 在这个过程中你也许会踩到不少坑, 也会学习到一些基础的也是核心的概念, 比如何时需要persist, 何时需要cache, 何时需要广播变量, 全局accumulator, rdd stage划分, 为什么需要避免在class内的函数的rdd里引用外部变量, driver和executor区别.&/p&&br&&p&这些是基础, 搞懂这些, 再尝试去系统性地看书, 看资料. 在此之前, 官网加博客就能让你掌握6-7成的技能.&/p&&br&&p&搞懂以上知识点，然后再深入进阶，推荐一些进阶资料:&/p&&p&1. hadoop相关的不想多说, 网上太多了, 推荐一下hulu的董西城大神的&深入hadoop技术内幕&系列.&/p&&p&2. spark相关:&/p&&p&&b&[Spark Streaming 源码解析系列] (&/b&&a href=&///?target=https%3A///lw-lin/CoolplaySpark/tree/master/Spark%2520Streaming%%25BA%%25A0%%25A7%25A3%25E6%259E%%25B3%25BB%25E5%& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&lw-lin/CoolplaySpark&i class=&icon-external&&&/i&&/a&&b&)&/b&&/p&&p&&b&[&a href=&///?target=https%3A///mahmoudparsian/data-algorithms-book& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&data-algorithms-book&i class=&icon-external&&&/i&&/a&-Scala Spark Solutions] (&/b&&a href=&///?target=https%3A///mahmoudparsian/data-algorithms-book/tree/master/src/main/scala/org/dataalgorithms& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&mahmoudparsian/data-algorithms-book&i class=&icon-external&&&/i&&/a&&b&)&/b&&/p&&p&&b&[SparkDeepDoc](&/b&&a href=&///?target=https%3A///codlife/SparkDeepDoc& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&codlife/SparkDeepDoc&i class=&icon-external&&&/i&&/a&&b&)&/b&&/p&&p&&b&[Mastering Apache Spark 2](&/b&&a href=&///?target=https%3A///book/jaceklaskowski/mastering-apache-spark/details& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Mastering Apache Spark 2&i class=&icon-external&&&/i&&/a&&b&)&/b&&/p&&br&&p&最后的忠告, 多动手, 少看书, 多一些实践, 少一些套路. &/p&&br&&p&bless~&/p&&br&&p&有人问spark为什么不推荐用python写。当然可以用python，不过仅限于小型的项目。像我现在做的一个项目，用scala写的，模型训练和评估的代码量已经接近2万行了。用python写的话我没信心能把控得像现在这么好，另外scala 代码量一大idea都感觉hold不住了，很难想象丢到pycharm里会变成什么样子。以前用flask写过中等规模的服务，代码量上去后ide连自动补全都失效了。scala写的话，错误提示失效了，至少类型检查和自动补全还勉强能用。&/p&&p&另外推荐一下用scala或java写大型程序的一个小技巧。方法签名和返回值很复杂时建议用idea的quickdoc获取。高效而且准确。尤其是传嵌套的数据结构进去时，这是静态语言的一大优点。&/p&
不要没事去搭建hadoop, spark集群!!!不要没事去搭建hadoop, spark集群!!!不要没事去搭建hadoop, spark集群!!! 初学者不要关注性能调优!!!初学者不要关注性能调优!!!初学者不要关注性能调优!!!牢记上面两点忠告, 这将节省你大量宝贵的时间。懂得取舍也是一种…
----------------------------&br&&br&本文同时发在我的 Blog，在那里或可获得更好的阅读体验：&br&&a href=&///?target=http%3A///post/-open-world& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&[知乎] 开放世界游戏中的大地图背后有哪些实现技术？&i class=&icon-external&&&/i&&/a&&br&&br&----------------------------&br&&br&首先肯定一下，这是一个非常有趣的问题。在这个答案里，我将尝试先回答主干问题，再对补充说明里的几个问题简单说一下。&br&&br&下面是本文将涉及到的一些相关技术的列表，（需要说明的是，这些技术单独来看并不复杂，实际动手实现并理解各种取舍以后，在项目当中针对具体的需求去设计和搭配才是关窍之所在）&br&&br&----------------------------&br&&br&&b&一、程序技术篇：算法和架构（Programming Algorithms & Architecture）&/b&&br&1. 无限循环的平铺地图（Infinite Tiling）&br&2. 可预测随机数和无限宇宙（Predictable Random）&br&3. 精度问题解决方案（Precision Problem Solving）&br&4. 超大地形的处理 （Terrain Visualization）&br&
4.1 古典算法（从 GeoMipMapping，Progressive Mesh 到 ROAM） &br&
4.2 层次的艺术（Quadtree 和 Chunked LOD）&br&
4.3 以GPU为主的技术（Paging，Clipmap 到 GPU Terrain）&br&5. id tech 5 的 megatexture （超大地表上的非重复性海量贴图）&br&6. 过程式内容生成 （Procedural Content Generation）&br&
6.1 过程式纹理（Procedural Texturing）&br&
6.2 过程式建模（Procedural Modeling）&br&&br&&b&二、内容制作篇：设计和创造（Content Design & Creation）&/b&&br&1. 随机地图类游戏 (Diablo II) 中地图的拼接&br&2. 无缝大世界 (World of Warcraft) 中区域地图的拼接&br&3. 卫星地质数据的导入，规整化和再加工（一些飞行模拟类游戏）&br&4. 超大地图的协同编辑：并行操作，数据同步，手动和自动锁的运用&br&&br&&b&三、异次元篇：我们的征途是星辰大海&/b&&br&1. 终极沙盒（EVE）：当规模大到一定程度——宇宙级别的混沌理论与蝴蝶效应&br&2. 打通两个宇宙（EVE & Dust）：发现更广阔的世界——宇宙沙盒游戏和行星射击游戏联动&br&&br&----------------------------&br&&br&## 一、程序技术篇：算法和架构（Programming Algorithms & Architecture）&br&&br&### 1. 无限循环的平铺地图（Infinite Tiling）&br&&br&我们就从最平淡无奇的无限循环平铺地图说起吧。这应该是最原始，也是最没有技术含量的开放世界构筑方式了。&br&&br&技术上由于过于朴素，也没什么好说的，就是在同一个坐标系内像铺地砖那样展开，坐标对齐即可，就是接头处需要注意一下，不要穿帮就行。但是千万别因为简单就小看这个技术哟，上面列表里面的不少技术都是在循环平铺的基础上发展起来的，下面我们就来瞧一瞧吧。&br&&br&按照维度的不同，循环平铺有下面三大类：&br&&br&a. 在一维方向上扩展的横版卷轴游戏（以动作类游戏为主）和纵版卷轴游戏（以射击类游戏为主）。这些类型的游戏里，为了避免循环平铺给玩家带来的重复的疲劳，卷轴游戏会添加一些随机或动态的元素，比如超级玛丽里的背景上云朵的位置，分出多个层次以不同速率卷动的背景层，等等。&br&&br&&img src=&/ba1ab15421cdadd00a30dd3c736e997d_b.jpg& data-rawwidth=&392& data-rawheight=&220& class=&content_image& width=&392&&&br&&br&&br&b. 在二维方向上循环平铺的固定视角2D游戏。这一类游戏里，比较典型的就是 Diablo。暗黑中的随机地图生成，在本质上，就是叠加了一定的随机性，约束和边界条件的循环平铺效果。&br&&br&&img src=&/47a0c8c78f1adf3afcee_b.jpg& data-rawwidth=&550& data-rawheight=&413& class=&origin_image zh-lightbox-thumb& width=&550& data-original=&/47a0c8c78f1adf3afcee_r.jpg&&&br&&br&&br&c. 在 3D 游戏里循环平铺高度图，形成连绵不断的地形效果。这在早期的模拟飞行射击类游戏里比较常见，现在已经很难搜到图了，我在上大学的时候写的第一个地形渲染 demo 就是平铺的，可惜刚刚翻硬盘已经找不到了555。这一类游戏，在平铺时适当地辅以一些贴图的变化，可以在很省内存的条件下，做出非常不错的效果。&br&&br&找不到游戏内的图，拿下面这个高度图来凑数吧。请大家脑补一下，把下面这个灰度图立体化之后，一块一块像地砖一样循环平铺以后，3D渲染出来的连绵起伏的直抵地平线（好吧，直抵远裁剪面）的山脉的壮观效果吧。&br&&br&&img src=&/b9c4ebfd28bccc8475ac1d_b.jpg& data-rawwidth=&512& data-rawheight=&512& class=&origin_image zh-lightbox-thumb& width=&512& data-original=&/b9c4ebfd28bccc8475ac1d_r.jpg&&&br&&br&----------------------------&br&&br&### 2. 可预测随机数和无限宇宙（Predictable Random）&br&&br&（本节内的描述和算法，部分参考了《Game Programming Gems I》 [“2.0 Predictable Random Numbers”](&a href=&///?target=http%3A//www.gameenginegems.net/gemsdb/article.php%3Fid%3D75& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Graphics and Game Gems Database&i class=&icon-external&&&/i&&/a&) 一文，请感兴趣的同学自行查找原文通读）&br&&br&有个传说中的游戏叫 Elite ，不知道有没有同学玩到过。据说这游戏运行在32K内存的机器上，其中16K还是只读的ROM。这游戏据说拥有难以匹敌的游戏深度：近乎无限个行星，每一个都有各自的名字和特征。&br&&br&可预测随机数本身是游戏内运用非常广泛的一个技术，这里我们着重谈一下它在为游戏提供（微观上）更丰富的细节和（宏观上）更广阔的世界的作用。这一技术的最重要原则是，为了在一个游戏世界中给出无限空间的幻觉，我们需要满足两个分解条件，可以把它们成为宏无限（macro-infinite）和微无限（micro-infinite）”。前者涉及到问题的空间规模，后者则任意一个对象所支持的最小细节层次级别。&br&&br&----------------------------&br&&br&从实现上来说，如何设定随机种子是这个技术的核心。由于给定一个随机种子，生成的随机序列是完全可预测的，那么根据游戏内的一些时空的设定，通过对随机种子进行一些定制，得到在游戏内任意某个时刻和某个空间点上完全可预测的行为就是可行的了。&br&&br&最简单的是使用以下几个元素与随机种子配合计算：&br&1. 世界坐标（即 X Y Z 值，既可以表示空间中的某个点，也可以表示某个区域）&br&2. 系统时间（可以用真实时间，也可以用游戏内设计者定义的时间，如果是前者的话需要考虑离线时的处理）&br&3. 正态分布（在游戏里建一个查找表即可，这是最廉价的方案）&br&&br&这些因素加上对应的随机序列，已经可以营造出宏观上比较有深度的一个宇宙空间了。理论上，如果所有的随机性都是由给定的随机种子产生，而这些随机种子要么是游戏定义的常量，要么是查表得到，要么是均匀流逝，要么是由更高层次的随机种子生成，那么这样一层一层上溯到尽头的话，任何一个游戏内的宇宙，都可以归因到一个初始的种子，这个种子，就是决定论中经典物理学的所谓的&b&第一推动&/b&吧。其实如果真做到了这一点，我们大可以把这个种子交给玩家，在首次进入游戏的时候掷一个 2^64 骰子。这是真正的上帝创世的感觉，想象一下，上帝说，要有光，于是掷出了骰子，第一推动怦然落地，整个时空的巨大齿轮开始运转，在不同的时间点和空间点上，更多的随机序列被生成出来...&br&&br&&img src=&/50bde2249146cce4ea9c_b.jpg& data-rawwidth=&640& data-rawheight=&517& class=&origin_image zh-lightbox-thumb& width=&640& data-original=&/50bde2249146cce4ea9c_r.jpg&&&br&&br&&br&这幅图来自于游戏 Frontier：Elite II（出自[这篇文章](&a href=&///?target=http%3A////from-the-archive-frontier-elite-ii-a-retrospective-review/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&&/span&&span class=&invisible&&//from-the-archive-frontier-elite-ii-a-retrospective-review/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&)），下面配的字样是：&b&“This picture doesn't even begin to show the scale of the universe.”&/b& 大家感受一下。&br&&br&----------------------------&br&&br&微观上本质上也是一样的，只是把发散的过程倒过来，变成了逐级收敛的过程。为了在某一个点上放大时，能得到尽可能细致，准确和一致的表现，我们需要对较低层次的世界定义更丰富的规则和约束，比如黑洞对周围的影响情况，双星体系的轨道，恒星的种类与行星个数之间的对应关系，不同恒星系结构下行星表面的大气构成，等等。这样才能较好地平衡多样性和独特性，带来更真实的模拟效果和更令人信服的游戏体验。&br&&br&----------------------------&br&&br&### 3. 精度问题解决方案&br&&br&当足够大尺度的世界被创建出来时，就会自然而然地遇到精度的问题。同时这也是补充说明中提到的一个问题，这里我们简单介绍一下几种实践中的解决方案。&br&&br&先描述一下问题吧，我们知道，IEEE754 中规定的32位浮点数中，有23位是用来表示尾数的。也就是说，对于接近1的浮点数，可能会带来 2E-24 左右的误差（大约是 0.）以现实单位计算的话，如果游戏世界是边长为100km的正方形，那么在这个正方形的最远角落里，我们的最小空间单位是约 7.8 毫米；而如果是中国这么大的面积的话，空间误差将达**半米**左右。那么可以想象一下，如果是宇宙级别的游戏，采用32位浮点数作为全地图精度，那么实际误差可能会有多么大。&br&&br&在实践中，这种误差可能会带来以下这些影响：&br&&br&1. &b&无法将相邻的对象对齐&/b&。这种情况，场景美术（关卡设计师）应该会比较头疼，这对于游戏的编辑器来说是大问题了。物件没法在引擎编辑器里对齐；在不同的平台上，对齐也不一样；甚至不同的编译器，同一个编译器的不同版本编出来的引擎；对齐都不一样 ... 所以说处女座不要做 LD :P。&br&2. &b&模型间的穿插和裂缝&/b& 本来封闭的墙角可能漏个洞，本来放在地上的石头变成了悬浮在空中。这实际上是上一种的变种。&br&3. &b&骨骼动画的抖动&/b& 由于世界矩阵往往参与骨骼动画的运算，误差可能会被逐级放大，在那些最远离根骨骼的骨头上（也是玩家最容易注意到的地方），抖动可能会发生得非常剧烈。&br&4. &b&物理模拟失真&/b& 一些柔体的模拟可能会直接失败，而刚体也可能会产生怪异的运动。碰撞系统也可能无法正常工作。&br&&br&所有这些一旦发生，都是很容易觉察的。一旦你发现在一个很大的坐标上有这些问题，而接近原点处问题却消失了，那么很有可能就是精度在作怪。而需要注意的是，出现这种问题，只和游戏中出现的数字的规模和跨度有关，和游戏选择了什么样的长度单位（如用毫米还是公里做单位）无关。&br&&br&----------------------------&br&&br&那么怎样使用有限的坐标精度来描述较大尺度的世界呢？&br&&br&最直接的方案是 &b&使用双精度浮点数 &/b&（64 位），如果这是可接受的选择，那么就不必费心引入后面讨论的复杂度了。&br&&br&其次是 &b&区域划分法&/b& 。我看到 &a data-hash=&1e2cccc3ce33& href=&///people/1e2cccc3ce33& class=&member_mention& data-editable=&true& data-title=&@Milo Yip& data-hovercard=&p$b$1e2cccc3ce33&&@Milo Yip&/a&
同学已提到，不过这里出于完整性的考虑，再简单说一下。正如 Milo 同学所说，“把世界划分成不同的区域，在区域内的计算使用其局部坐标系统。”相对应的跨区访问，需要对应的“本地A -& 世界 -& 本地B”的坐标转换。&br&&br&还有一个方案是 &b&节点中转法&/b&。正如移动电话的基站用来承载和协调整个通信网络那样，我们在游戏的给定活动区域使用静态信标，所有的逻辑上与之相关的单位，都以该信标的坐标作为参考单位，这样也可以做到把数据访问局部化。相距足够远的两个物体（相当于上面的跨区访问）交互总是通过静态信标来完成（正如移动电话网络中发生的那样），这样的好处是相关的复杂度可以隔绝在这个中转系统的内部。&br&&br&此外
&a data-hash=&9a5b0b946e064a3a170f04c2d3563a78& href=&///people/9a5b0b946e064a3a170f04c2d3563a78& class=&member_mention& data-editable=&true& data-title=&@凯丁& data-hovercard=&p$b$9a5b0b946e064a3a170f04c2d3563a78&&@凯丁&/a&
同学提到了一个&b&坐标转换法&/b&，“所有位置信息都以角色位置为中心做一次转换”。这正是 《Game Programming Gems IV》 [“4.0 Solving Accuracy Problems in Large World Coordinates”](&a href=&///?target=http%3A//www.gameenginegems.net/gemsdb/article.php%3Fid%3D280& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Graphics and Game Gems Database&i class=&icon-external&&&/i&&/a&) 文中的方案。这个方案可以解决部分问题（主要是渲染相关的问题），但是仍有一些问题需要考虑，比如：1. （上面提到的）编辑器内操作的物体，在序列化到文件中时，精度丢失的问题。2. 大部分物理模拟通常需要一个角色无关，摄像机无关的全局坐标系。等等。&br&&br&----------------------------&br&&br&### 4. 超大地形的处理 （Terrain Visualization）&br&&br&终于说到对超大地形的处理了。可以说从上世纪九十年代起，超大地形的可视化，一直是3D游戏领域热门的话题。今天我们就借着这个机会，把相关的算法和实现理一理吧。&br&&br&考虑到篇幅太长的话，俺的手指头招架不住，再一个不少对这个话题感兴趣的同学可能压根就不是程序员，一些实现细节可能我就只是简单提一下，贴代码什么的还是算了，尽量保证整篇文章的信息浓度适中吧。&br&&br&----------------------------&br&&br&总的来说，这十多年来，地形渲染技术的发展史就是一部生动的对现代GPU的开发，利用和改进史。整个过程大致可以分成三个阶段：一开始，GPU处理顶点能力很弱，这个时期的各种精巧算法（如一些VDPM和后期的ROAM），**尽力在用CPU来降低顶点的总量**，避免一不留神压垮图形系统；后来，图形系统的能力上去了，人们开始更多地考虑到**把地形系统融入到通用的场景管理**中去，如四叉树八叉树什么的就是在这个阶段被广泛应用的；再往后，GPU已经很强大了，CPU由于要承担更复杂的游戏逻辑，越来越成了整个系统的瓶颈，这个阶段，人们琢磨的更多的是，怎么**利用GPU给CPU减负**了，一直到如今，由 GPGPU 带动起来的异构计算，也都是这个路数。&br&&br&----------------------------&br&&br&由于内容比较杂，超大地形这个段落，按上面的描述，咱们分为三个小段分开来讲吧。让俺先沏上一杯碧螺春，为客官一一道来。&br&&br&#### 4.1 古典算法（从 GeoMipMapping，Progressive Mesh 到 ROAM） &br&&br&&b&GeoMipMapping&/b& 是从纹理的 MipMapping 技术演化来的一个地表处理技术，原理上是根据任何一小块地形在屏幕上显示的实际尺寸（主要跟与摄像机的距离和起伏程度有关）来选择对应密度的网格，然后把不同分辨率的网格之间以某种方式拼接起来（没有这一步的话就会有裂缝），本质上是一种比较粗糙的区域 LOD 算法。顺便说一下，由于那时候针对顶点级的处理很多，导致这种T型裂缝很常见，以至于有个专门的名字叫“T-Junction”，针对这个的处理在当时也有很多方案。&br&&br&&img src=&/a009ae667fd9_b.jpg& data-rawwidth=&551& data-rawheight=&398& class=&origin_image zh-lightbox-thumb& width=&551& data-original=&/a009ae667fd9_r.jpg&&&br&&br&这是俺刚刚到老硬盘里刨出来的大三时写的 GeoMipMapping 代码，编了一下居然还能跑起来。有点土，别介意：P 可以看到不同的 MipMap 级别是用不同的颜色渲染的，也可以看到接头处 T 型裂缝的处理。唉，这代码勾起了俺的青葱回忆啊，那就顺便再来两张 T 型裂缝的示意图和消除过程吧。&br&&br&&img src=&/14d993ba8c1bdde03a2e_b.jpg& data-rawwidth=&522& data-rawheight=&535& class=&origin_image zh-lightbox-thumb& width=&522& data-original=&/14d993ba8c1bdde03a2e_r.jpg&&&br&&br&----------------------------&br&&br&&img src=&/cd4ebdf412bfe4538a6ddd1fb7b2a3fc_b.jpg& data-rawwidth=&612& data-rawheight=&495& class=&origin_image zh-lightbox-thumb& width=&612& data-original=&/cd4ebdf412bfe4538a6ddd1fb7b2a3fc_r.jpg&&&br&&br&----------------------------&br&&br&&b&Progressive Mesh&/b& 是后来很流行的技术 Simplygon 的前身，原理上基本也是一致的，就是以某种方式渐变性地化简某个给定的 Mesh。&br&&br&渐进式网格有两种：视点无关的 （View-Independent Progressive Mesh，VIPM） 和视点相关的 （View-Dependent Progressive Mesh，VDPM）。两者的区别就是，前者预先离线生成好所有的渐变过程，运行时直接用就行（也是后来 Simplygon 采用的方案），而后者随着摄像机的位置和角度的变化，生成对应的简化模型。两相对比，VIPM的好处是运行时运算开销低，简化模型的效果好，缺点是费内存（因为数据都存下来了，当然后来增量的方式能省一些），而VDPM在当时是不错的选择，因为跟VIPM相比不用费额外的内存，而且对于视点（就是摄像机）变化不剧烈的应用，不需要每帧处理和更新对应的简化模型（普通的MMO类的一般一秒一次就够了），此外由于一些简单的遮挡剔除和背面剔除，能够比VIPM裁掉多得多的顶点（一般能多裁1/3到一半吧，在当时这可是头等大事）。&br&&br&总的来说，至少在当时，两者的应用都比较广泛，而到了后来，显存越来越大，总线却越来越紧张，VDPM这种典型的刷顶点的算法（比较费总线带宽）就逐渐失去了市场，这是后话了。&br&&br&大家可以在[这里](&a href=&///?target=http%3A///3d/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&3d Page (/3d)&i class=&icon-external&&&/i&&/a&)看到一些 PM 在地形渲染上的应用。图咱就不上了，大家可以到 Simplygon 的网站上去看。&br&&br&----------------------------&br&&br&&b&ROAM&/b& 可算作是上面提到的 VDPM 更进一步了。这个算法实际上借鉴了当时主流引擎的标配BSP的思路，想利用二叉树这个最简洁的空间描述数据结构，把（CPU端的）顶点消减发挥到极致。整个地表被组织成一个巨大的二叉树，有两个队列，一个是分割队列，一个是合并队列，分别用于处理摄像机移动时，增加进入视野的区域细节和消减退出视野的区域细节。精心设计的 ROAM 效果非常华丽（尤其是在线框模式下），你会看到在各种因素的影响（包括局部坡度，与摄像机的夹角，遮挡情况等等）下，各种三角形像魔术般的不断地变幻，生成和擦除超多的细节，效果非常魔幻。我印象很深的是当时连续打Quake3两个小时完全无感的我，调试这玩意的时候，每每不到十分钟眼就花了。&br&&br&网上找了两张比较典型的 ROAM 大家感受一下吧。&br&&br&&img src=&/07be8d1e331b9b1b7ebae1_b.jpg& data-rawwidth=&1003& data-rawheight=&749& class=&origin_image zh-lightbox-thumb& width=&1003& data-original=&/07be8d1e331b9b1b7ebae1_r.jpg&&&br&&br&----------------------------&br&&br&&img src=&/d276affe4ed461cb33408e_b.jpg& data-rawwidth=&636& data-rawheight=&398& class=&origin_image zh-lightbox-thumb& width=&636& data-original=&/d276affe4ed461cb33408e_r.jpg&&&br&&br&----------------------------&br&&br&&br&#### 4.2 层次的艺术（Quadtree 和 Chunked LOD）&br&&br&其实用于空间管理的树状结构有四叉树和八叉树（还有上面的二叉树），但地表通常以前者居多。是因为，从小范围来看，变化剧烈的地形是3D的，适合八叉树在xyz三个方向上扩展；但当尺度大到一定规模之后，地形通常退化为相对扁平的2D空间，就像摊平了的地球表面那样，在竖直的Z方向上变化相对不大，而XY平面则是可能无限延伸的。&br&&br&&b&Quadtree&/b& 四叉树很直白，具体的细节我就不讲了。值得一提的是四叉树往往也同时用于场景管理的快速剔除和查找，从理论上来讲，四叉树是一个平面上最迅速的用于剔除空间，定位一个物体，内存开销也是相对较低的数据结构。当用于地形渲染时，顶点剔除的效率也很高，我印象中仅次于高度优化的 ROAM。内存开销低主要是因为四叉树是可以完美展开到一个位数组里的，这样的话意味着整个树的利用率达到了百分之百——所有的空间都用来存储数据而不是维持结构。&br&&br&不过四叉树也不是啥都好，T型裂缝就比 GeoMipMapping 难处理，因为存在跨级的多段 T 缝，如下图：&br&&br&&img src=&/1b93ffaf7dfefee85af1_b.jpg& data-rawwidth=&326& data-rawheight=&311& class=&content_image& width=&326&&&br&&br&&br&除此之外还有一些细节问题，这里就不一一说明了，地形的四叉树渲染还是有很多细节需要细心处理的，此处暂且放下不表。&br&&br&----------------------------&br&&br&&b&Chunked LOD&/b& 是一种杂合改良的 LOD，其实糅合了上面说的不少细节，本质上是一种分区块地消减细节的技术。所谓 Chunk 是批量处理的一种方式，只是一种粒度划分的单位而已，跟现在 Java 的 GC 里分区回收概念上差不多。&br&&br&下面是典型的 Chunked LOD 后的效果：&br&&br&&img src=&/f061aa7fd657ea01a4fbb4b5b7579c7a_b.jpg& data-rawwidth=&1015& data-rawheight=&378& class=&origin_image zh-lightbox-thumb& width=&1015& data-original=&/f061aa7fd657ea01a4fbb4b5b7579c7a_r.jpg&&&br&&br&顶点多次过滤优化后的效果：&br&&br&&img src=&/fcaffd00ee8d67b93aa2701_b.jpg& data-rawwidth=&901& data-rawheight=&439& class=&origin_image zh-lightbox-thumb& width=&901& data-original=&/fcaffd00ee8d67b93aa2701_r.jpg&&&br&&br&&br&效果在当时还是很惊艳的。通常不到50k的渲染数据量已经能有非常逼真的效果了。&br&&br&----------------------------&br&&br&#### 4.3 以GPU为主的技术（从 Paging，Clipmap 到 GPU Terrain）&br&&br&上面的基本上都是传统方案，这一节我们将逐渐过渡并挨个介绍一下以 GPU 为运算主体的算法。&br&&br&----------------------------&br&&br&所谓&b&分页&/b&（Paging）实际上是仿效虚拟内存的运行机制的一种方法。由于地表的顶点数据都是静态数据，适合常驻显存。当世界尺度较大时，显存没法一次放入所有数据，那么系统就像虚拟内存那样，把那些暂时没有用到的数据交换出去。随着游戏的进行，Paging In/Out 也在不断进行，辅以一定的异步机制，加载到显存的延迟可以被很好地掩盖。玩家的直观感受就是：哇，海量的细节。&br&&br&&img src=&/ea740fdbaed05c5102354_b.jpg& data-rawwidth=&996& data-rawheight=&798& class=&origin_image zh-lightbox-thumb& width=&996& data-original=&/ea740fdbaed05c5102354_r.jpg&&&br&&br&----------------------------&br&&br&而 &b&Clipmap &/b&则比 Paging 更进一步，以金字塔的形式逐级把数据排列好，直接整体更新和渲染。从这里也可以看出 GPU 时代人们的思维方式的逐步变迁。从以前顶点级别（Vertex Level）的“锱铢必较”，到后来的一次多塞一点也无所谓，只要批次（Batch）少就 OK。下图可以看出 Clipmap 的基本思路。&br&&br&&img src=&/811bdc0e3fb8be4ab928d5_b.jpg& data-rawwidth=&1071& data-rawheight=&467& class=&origin_image zh-lightbox-thumb& width=&1071& data-original=&/811bdc0e3fb8be4ab928d5_r.jpg&&&br&&br&----------------------------&br&&br&所谓的 &b&GPU Terrain Rendering&/b& 就是把高度图从内存里经由 2D Vertex Texture 搬到 VS 里去生成三角面，这样的好处是 CPU 和内存就被彻底解放出来了。只是访问上有一些限制，不像直接处理内存那样方便。具体的细节可以看这里：[GPU Gems 2: Terrain Rendering Using GPU-Based Geometry Clipmaps](&a href=&///?target=http%3A//http./GPUGems2/gpugems2_chapter02.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&GPU Gems - Chapter 2. Terrain Rendering Using GPU-Based Geometry Clipmaps&i class=&icon-external&&&/i&&/a&)&br&&br&在 GPU 上做还有个巨大的好处是可以借助 Gaussian Noise 即时生成更多的细节了。直接拿一小块预生成的高斯噪点图在需要的时候叠加一下，就能在没太大额外开销的情况下，增加各种细节。如下图所示：&br&&br&&img src=&/fba8d154a04fe4c1e3a8c24e4d8645fe_b.jpg& data-rawwidth=&418& data-rawheight=&194& class=&content_image& width=&418&&&br&&br&----------------------------&br&&br&随着大家对 GPU 理解的深入，地形的处理又有很多的小技巧可以做，尤其是在 PS 里面，比如法线生成，动态uv展开，光照按需叠加/衰减什么的。不过呢据我所知没有什么非常别具一格的架构上的新思路了，所以就不再深入了。&br&&br&### 5. id tech 5 的 megatexture （超大地表上的非重复性海量贴图）&br&&br&&b&megatexture &/b&在当年（2007）是一个非常值得一提的技术。在这个技术出现之前，几乎所有的地表渲染用到的贴图都是若干张 blend 到一起后，以 tiling 的形式重复平铺在地表上的（包括比较典型的魔兽世界也是如此），这样的直接后果是图片的种类用多了耗资源，用少了又很容易感到单调和重复。而 megatexture 则是一张全局的超大贴图，从根本上避免了重复这个问题，理论上（实践上也是）能够生成非常壮丽和独特的地质风貌，是传统的刷地表无法创作出的效果。可以说这个技术让&b&真正的全景地貌&/b&成为可能。&br&&br&----------------------------&br&&br&技术上的细节puzzy老