Posts

一、反射简介 反射是一种程序动态访问修改其状态或行为的机制。具体来说，反射提供了在程序运行时对代码进行操作的手段。 反射提高了程序的灵活性和扩展性，能使程序员通过字符串动态地实现程序的修改。它降低了代码间的耦合度，可以避免硬编码，实现代码的组件化。反射的这些特点在对灵活性和扩展性要求很高的框架上有巨大的作用。 当然，也需要注意到，反射通过字符串进行操作的方式是解释性的，这将导致性能的降低。 二、反射的原理 对于拥有虚拟机（或者类似的东西，虚拟机只是一个不正规的名词）的语言，都存在加载字节码（同样不正规的名词）到虚拟机的过程。在这个过程中，虚拟机获取了有关类的信息，包括继承关系、包含的字段和方法等等。对于java来说，局部变量放在栈中，类实例放在堆中，程序方法放在方法区中。 对不使用反射的一般情况来说，方法调用更加直接。调用时虚拟机将根据编译时即确定的方法地址进行跳转。而对于反射，则需要根据字符串查找对应的类或方法。这样查找而非硬编码的过程就会影响性能。 二、java中的反射 通过反射我们能获取java语言中的如下组成部分：包、类（和接口）、方法（一般/构造）、字段、注解。反射不能操作方法中的内容。 类是面向对象的基本单元，我们通过获取类来实现对程序的动态操作。 （1）类和包 “类” Class<?> 是一个用于表示类的类型。它有三种获取方式 ClassName.class // 类型名.class obj.getClass(); // 对象.getClass Class.forName(String className); // Class.forName("包含包路径的类型全称") 前两种较好理解，相当于获取一个类型，我们可以用这编写一个类似于 instanceof 的函数。 boolean typeof(Object obj, Class<?> cls) { return obj.getClass() == cls; } 当然这无法将子类也判断为真。值得注意的是这里我们直接使用了 == 而不是 equals。因为对于每一个类，Class只用一个实例。 但第三种才最为重要，它通过字符串获取了一个类型。这就为程序提供了灵活性。 获取了一个 Class 对象后，我们可以进一步获取其父类和实现的接口 Class<?> cls = Class.forName("somepackages.someClass"); Class<?> superCls = cls.getSuperclass(); Class<?>[] interfaces = cls.getInterfaces(); 值得注意的是获取接口方法返回的是一个 Class 数组。这说明对于虚拟机来说本没有类和接口之分。 调用 getPackage 可以获取包 Package p = cls.getPackage(); Package 类型保存了该包的一些信息，如名称、版本等等，不一一列举。...

一、前言 本文是“2D物理引擎基础”的第三篇文章，主要介绍物体刚体力学的相关知识以及碰撞发生后的处理办法。后者背后的数学原理较为复杂，因此这里大多情况只是罗列公式并做简要说明。 二、刚体力学 连续的刚体力学 我们考虑二维的情况。假设有一刚体，质量为 $M$，转动惯量为 $I$，在距质心 $\vec{r}$ 处受到一力 $\vec{F}$ 的作用。 那么刚体所受相对于质心的力矩 $\vec{M}$ 为： $$ \vec{M} = \vec{r} \times \vec{F} $$ 注意 $\vec{M}$ 的方向垂直于平面，后面的角速度同理。 在 $\Delta{t}$ 时间内速度变化 $\Delta{\vec{v}}$ 有 $$ \Delta{\vec{v}} = \int_{t_0}^{t0+\Delta{t}} \frac{\vec{F}(t)}{M} dt $$ 同样的，角速度变化 $\Delta{\vec{w}}$ 有 $$ \Delta{\vec{w}} = \int_{t_0}^{t0+\Delta{t}} \frac{\vec{M(t)}}{I} dt $$ 类似的，也有位置和角度的变化 $$ \Delta{\vec{p}} = \int_{t_0}^{t0+\Delta{t}} \vec{v}(t) dt $$ $$ \Delta{\vec{\theta}} = \int_{t_0}^{t0+\Delta{t}} \vec{w}(t) dt $$ 还有冲量 $$ \vec{I} = \int_{t_0}^{t0+\Delta{t}} \vec{F}(t) dt $$ 以及角冲量（或称冲量矩） $$ \vec{H} = \int_{t_0}^{t0+\Delta{t}} \vec{M}(t) dt $$ 并有等式 $$ \vec{I} = M \Delta{\vec{v}} $$ $$ \vec{H} = I \Delta{\vec{w}} $$ 离散的刚体模拟 正如第一篇文章中说过的，一般情况下计算机无法计算连续，只能通过离散的方式进行近似。物理引擎中进行的模拟会导致误差，但这对于视觉效果来说已经足够了。...

一、前言 本篇是“2D物理引擎基础”的第二篇文章，将主要讲解碰撞检测的基本原理和算法。 碰撞检测是物理引擎十分重要的组成部分。碰撞检测及后续的碰撞约束反映了物质的不可入性，是物理模拟真实性的基础。另外碰撞检测也能有效用于游戏逻辑的实现，如触发陷阱、探测障碍等等。 二、碰撞检测的基本概念 碰撞检测的目标就是判断两个几何体是否存在重合部分，如果存在重合部分，则得到接触点、碰撞法线和穿透深度。 接触点（Contact Point）指的是两个几何体相接触的位置。当然对于碰撞检测而言，接触的部分并非点而是区域，但是我们可以通过算法从中近似地取出接触点，一般位于其中一个几何体的顶点或边上。 碰撞法线指示了一个物体与另一个物体发生碰撞后，后者为了分离而应该采取的运动方向。这一法线大多是几何体中某一条边的法线 穿透深度是沿碰撞法线方向最终分离所需的距离，这一数值常用来修正碰撞后两几何体的位置，避免两几何体在视觉上发生重叠。 三、分离轴定理（SAT，Separating Axis Theorem） 分离轴定理是如下内容：若两个凸物体没有重合，则总会存在一条直线，能将两个物体分离。这样的直线称为分离轴。对于高维物体来说这同样适用，只不过分离轴将变为分离超平面。 利用分离轴定理可以实现凸几何体的碰撞检测。对于多边形，算法是这样的： 对两个多边形的每一条边，做垂直于该边的直线 对两个多边形的每一个顶点，分别做到步骤1中所得直线的投影 如果存在一条直线，两个多边形对这条直线的投影并不重合，则两个多边形不重合 如果不存在步骤3中的直线，则两个多边形重合。 完全按照算法思路得到代码如下 def sat(body_a, body_b): return not find_separate_axis(body_a, body_a, body_b) and not find_separate_axis(body_b, body_a, body_b) def find_separate_axis(lines_body, body_a, body_b): for i in range(len(lines_body) - 1): p1 = lines_body[i] p2 = lines_body[i] + get_normal(lines_body[i+1] - lines_body[i]) a_min, a_max = body_cast(p1, p2, body_a) b_min, b_max = body_cast(p1, p2, body_b) if p1[0] != p2[0]: max_min = a_min if a_min[0] > b_min[0] else b_min min_max = a_max if a_max[0] < b_max[0] else b_max if max_min[0] < min_max[0]: continue else: max_min = a_min if a_min[1] > b_min[1] else b_min min_max = a_max if a_max[1] < b_max[1] else b_max if max_min[1] < min_max[1]: continue return True return False def body_cast(a, b, body): body_min = body_max = point_cast(a, b, body[0]) for p in body: p_cast = point_cast(a, b, p) if p_cast[0] < body_min[0] or (p_cast[0] == body_min[0] and p_cast[1] < body_min[1]): body_min = p_cast if p_cast[0] > body_max[0] or (p_cast[0] == body_max[0] and p_cast[1] > body_max[1]): body_max = p_cast return body_min, body_max def point_cast(a, b, p): u = p - a v = b - a p_cast = a + v * (np....

一、前言 本系列是我学习物理引擎相关知识的总结。虽说最初的目标是自己实现一个完整的物理引擎，但是随着学习的深入我认识到，为了让引擎更好地模拟实际，所需要的各种数学原理和处理技巧远远超出了“涉猎”的程度。因此我决定就此止步，但是还是留下了自己的实践成果和经验总结，就在这系列文章中。 本文是“2D物理引擎基础”的第一篇，将介绍物理引擎中物体所需的物理属性 二、物理引擎中的物体 在物理引擎中，模拟的物体对象被假定为刚体。刚体是如此致密坚硬的一种物体，以至于任何碰撞都无法改变其形状。同时物理引擎还常常假定对象的密度均匀，这样对象的质心将只由其几何形状决定。通过这样的假设，物理引擎将能够通过算法优化高效地进行计算模拟： 刚体说明物体不会改变形状，这样当物体受到力的作用时，力的作用效果就不会造成改变物体运动之外的其他影响，如质心改变。 密度均匀使得质心的求解更为方便，将质心位置和偏转角度作为物体属性，就可以完全表示物体上各点的位置信息 接下来所说的物理属性也是在如上约定的基础上的。 三、运动学属性 形状的表示 物理引擎中的形状用描述物体边界的属性表示。不同形状的物体通过不同的几何参数进行表示，如矩形可用长宽表示，圆可用半径长度表示，这些较为简单。更一般地我们考虑多边形，多边形可用顶点坐标表示，但是我们希望形状是位置无关的，那么多边形的顶点坐标也不能在坐标轴上随意选取。虽然 $(0, 0), (1, 0), (1, 1), (0, 1)$ 和 $(1, 1), (2, 1), (2, 2), (1, 2)$ 表示相同形状的多边形，但我们需要选择与位置无关的那一个。我们可以选择使多边形的质心在坐标原点的顶点集合，因为我们后续需要通过质心确定运动学属性。对于均质物体来说，这也就是多边形的几何中心在原点。 我们不能人为地在设置形状时就限制顶点围成的形状中心必须在原点，这对于复杂的形状来说十分困难。我们可以根据顶点集合先确定几何中心位置，再对每一顶点减去中心坐标以将物体平移到集合中心为原点的位置。 对于多边形，计算几何中心的公式为 $$ A = \frac{1}{2} \sum_{i=0}^{N-1}(x_iy_{i+1} - x_{i+1}y_i) $$ $$ c_x = \frac{1}{6A} \sum_{i=0}^{N-1}(x_i + x_{i+1})(x_iy_{i+1} - x_{i+1}y_i) $$ $$ c_y = \frac{1}{6A} \sum_{i=0}^{N-1}(y_i + y_{i+1})(x_iy_{i+1} - x_{i+1}y_i) $$ 其中 $A$ 为多边形面积， $(c_x, c_y)$ 即几何中心位置。需要注意的是，在这个公式中，顶点序列为逆时针，且第一个和最后一个应是同一个坐标，以暗示这是一个闭合图形并且方便公式表示。$N$ 是不重合的顶点个数/边数。 如下是求集合中心的 python 代码 def get_geometric_center(points): area = 0 c_x = c_y = 0 n = points....

一、歌词生成项目 想要在 nlp 方面深入，于是选择训练生成一个 RNN 网络，主要目标是自动生成歌词。在这里受到了 最浅显易懂的 PyTorch 深度学习入门 的启发，并利用 up 主提供的 源码 中的数据集。 相关代码的编写也有参考该 up 主的部分，但均为在理解内容的基础上自行编写的。另外也有对该 up 主代码中的疏漏进行修改的地方。 二、数据的获取 （1）编写数据集 原作者用爬虫获取的歌词数据被保存在 lyrics.txt 文件中。我们要将数据按可供训练的模型加载。具体来说 我们希望每一次获取数据，都能得到输入和目标输出（对本项目来说就是两段有一个文字偏差的序列） 并且将文字数字化，即 nlp 的 tokenize 为了实现批量训练，需要每次获取定长的序列 为了实现第一点，我们要继承 dataset；实现第二点，需要根据数据建立字符表；实现第三点，需要定长截取歌词句子的一部分。 另外，为了减少每次加载数据所用的时间，还需要将数据集的信息持久化。 我们的 LyricsDataset 具体实现如下。首先，我们在构造函数中通过传入的路径加载数据，判断是否已经存在处理过后的数据，如存在则加载；如不存在则读入原始数据并处理 class LyricsDataset(Dataset): def __init__(self, root_path, seq_size): self.seq_size = seq_size processed_name = "/processed/lyrics.pth" raw_name = "/raw/lyrics.txt" if os.path.exists(root_path + processed_name): print("find processed data") self.__load_processed_data(root_path + processed_name) else: print("processed data not found, will process raw data") self....

一、自然语言处理（nlp）简介 一份思绪奔驰的前言： 语言的边界就是思想的边界。如果从人类所具有的一切中挑出一个事物，让它来显示出人与其他生物的不同之处，那一定是语言。语言是我们用来思考和交流的方式，我们的一切文明都构筑在这简单的一维序列中，可我们却几乎不曾深入了解过它。 有人说，我们不曾真正的理解语言，我们所有对语言的运用和理解，不过建立在婴儿及此后对他人的声音与书本上符号的猜测上。或许正是如此，但是我们依旧要做出猜测，向着语言的神秘进发，这是我们的信念，是我们认识我们的认识的开始。 （1）作为语言学的 nlp 早在计算机的上古时代，深度学习还未诞生的时候，自然语言处理作为语言学的一个领域就已诞生了，这个领域也被语言学家们称为计算机语言学。两个名称在一起，才表达出 nlp 的真正含义——通过机器处理语言。nlp 最早的研究方向是机器翻译，那时人们人为地总结语言的规律，对词汇进行标注，对语句进行句法分析。结果是人为的规则覆盖面不足，所设计的系统无法扩展。 （2）作为机器学习研究领域的 nlp 随着计算机的发展，出现了基于传统统计学习模型的自然语言处理方式。这些原始的模型较之之前有所进步，但受限于计算机性能，统计方法也遭遇了瓶颈。 直到近年来算力的发展，使得深度神经网络成为可能。深度神经网络结构中潜在的学习能力，在 nlp 领域发挥了作用。通过多维数据表示语言和含义，深度学习以高效且与人类认知过程相似的方式发挥了巨大的效果。 二、词向量 词汇作为符号，其形象是离散的；但词汇的所指作为定义，其含义却是丰富而连续的。比如说“母亲”这个词汇，既表示了这个概念所对应的事物是在一种血缘关系中的一方（她是孩子的母亲）；又表示了这个事物是能繁殖者（母鸡）；在一定程度上，同样表示了非血缘关系，但具有类似血缘关系的行为的个体（大地是母亲）。 偏个题，《来自深渊》中有对生骸语的类似的描述. 因此，我们就不能再将词汇只作为离散的符号看待了，不能认为词汇之间是相互排斥的关系了。我们需要将词汇看做某些元含义在不同程度下的集合，或者从机器学习的角度，把这些元含义称作特征。那么也就是说，我们将每个词汇都看成一定维度的向量。 但是我们要如何确定特征呢？特征的数量又有多少？如果人工地确定特征为“存在、含义、物质、精神”等等，这一过程将耗费精力且永无止境。实际上按照机器学习的一般策略，我们只需要通过统计文本，自发的构建词汇向量即可。 这一方面有许多算法，如 N-gram 算法，GloVe 算法等等。另外也可以在深度学习的过程中利用反向传播自发的调整词向量，在 pytorch 中这通过 Embedding 层来实现。 三、循环神经网络（RNN）及其变体 （1）朴素 RNN 考虑我们说话或写作时的基本逻辑。对于一段语言序列，在之后的词汇总是和之前的词汇有关，未表达的部分总是已表达部分的补全或补充。循环神经网络的机制类似，我们需要用一个或多个隐藏变量作为对之前语句含义的表示，在输出下一个词汇时，会让隐藏变量参与决策；同时每多说完一个词汇，这个词汇也会更新隐藏变量，以实现表达含义的更新。 具体来说，我们用 $t$ 表示时间序列，对某一时间 $t$，$x_t$ 表示输入，$y_t$ 表示输出，$h_t$ 表示隐含状态。那么朴素的 RNN 网络即： $$ h_t = tanh(W^{(hx)} x_t + W^{(hh)} h_{t-1}) $$ $$ y_t = W^{(S)} h_t $$ 容易看出 RNN 和 Moore 自动机有相似之处。 其中 $W^{(hx)}, W^{(hh)}, W^{(S)} h_t$ 分别为三个不同的矩阵。RNN 的激活函数也可以选择 ReLU。同时可以为激活函数中的部分添加偏置（bias）$b^{(hx)}, b^{(hh)}$ 等。...