老老实实学数据结构与算法

最近2周,看了很多关于数据结构与算法的东西,老老实实写代码,不在weibo上和他们吐口水谈什么架构了。简述一下最近用到的东西。

首先是一些基本的平面几何算法,比如某个平面区域内有很多点,然后在这个区域内画一个矩形,求这个矩形内有哪些点。然后发现做服务器端开发也是需要学图形学的,图形学的结果未必非要用在屏幕显示上。比如,假如服务器是按格子存储障碍点信息,那么给定两点,问这两点能否相互可见(直线可达),其实就是图形学最基本的划线算法。

另外A*其实也蛮有意思。虽然算法本身看起来很简单,但是实现技巧很多。传说lch为了写这个算法并反复优化,写了至少有3个月。其中一个常见技巧就是不要用Set来存OpenList,而是用Heap。但是其实用Heap的时候也有细节上的不同,比如某个元素的值如果改变了,那么是remove并add呢,还是从它到根做一次调整呢,还是干脆不删除旧值,直接插入一个新的进去。第一种和第三种,不需要改现有的接口,用java.util下的优先队列就可以了,但是第二种需要自己重新写一下这个数据结构。

multiverse 0.7中的collections基本处于不可用的状态,让我很郁闷很愤怒。所以接下来我和Peter会将之完善,并重写很多数据结构。

解决问题最简单的方法就是蛮搜,所有可能性都试一遍,稍微聪明的程序员会考虑采用更较为合适的算法。但是,这个时候会发现选择往往不只有一个,而且最佳选择往往是依赖于数据集的规模,而不同算法在不同数据规模下的效率,这个知识的积累过程可比学懂并实现一个算法慢很多了也难多了,需要长期的经验和形式化分析的能力。更倒霉的是,需求的提出方往往估计不了市场的反应。

AOI这个问题,我在想怎么更好。先想最基本的问题,对象移动以及视野广播。假如,每个角色的视野距离可以是不一样的,比如魔兽世界里面那样。那么我能看见你不代表你就能看见我。于是,当我的位置发生移动的时候,不能按照我的视野范围来做广播,而是看我到底是在哪些人的视野范围内。那么可以采用观察者模式,当对象移动位置的时候不断的register/unregister被观察者。这样才能保证被观察者突然下线或者发生某种行为的时候能及时被该看见的人都看见。但是我又在想,如果人很少,与其这样,还不如遍历整张地图所有角色来的快呢。

用堆做A*的OpenList的时候,让我想到一个问题,就是,大多数搜索结构,可能为了封装的更严谨,于是根本没有提供更改key值的方法。例如常见的Hash、red-black tree、btree等等。但是,游戏就是现实世界一个活生生的例子。value总是在原来的值的一个小范围内变化。hp也好,坐标值也好,level也好都是如此。比如某个red-black tree里面的key是坐标值,那么对象在移动的时候,虽然这个值经常变,但是如果它走来走去都没看见人,那么这个树可能根本就不用调整。

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥