Python

一、前言 一个人进行推理时…… 这种过程如果是用语词进行的，他便是在心中把各部分的名词序列连成一个整体的名词或从整体及一个部分的名词求得另一个部分的名词。 —— 托马斯·霍布斯《利维坦》第一部分 论人类 第五章 论推理与学术 当霍布斯将他的机械唯物主义运用于人的思想时，语言便成为了人脑的齿轮。人的精神当然并非机械，可这种认识却也敏锐地察觉到了语言的一些本质，那就是语言是一些规则，通过这些规则的拼凑，我们得以表述我们的思想。如今，这种规则我们称之为文法。 语言学家的一部分工作是从现有的自然语言中总结文法，让语言成为机械。但是这并不是我们的重点，我们所要探索的是一个更加年轻的领域，这个领域的研究从机械出发，却要去创造千变万化的语言，让机械成为语言。 二、自然语言的文法：一个例子 但是要开始我们的旅程，还需要从自然语言开始。当我们听别人说话，或者阅读一段句子的时候，我们究竟在理解什么？比如说，现在有这样一句话，你知道我的叉子被放在哪里吗。让我们尝试理解这个句子。 这部分默认各位已有了对词性的基本认识，至少知道名词、形容词、动词、副词等等的大致含义。否则的话，这部分内容实难描述。 另外注意对于自然语言的相关表述可能并不完全符合人的认知的真实情况，这一部分只是为了方便理解。 首先需要明确一点，抛开我们所有的经验来看，语言就是符号的序列。也就是说语言是在时间上存在先后顺序的许多符号。这意味着我们的理解过程必定是从前到后的。对于上述句子来说，我们先读到 你，之后才能读到 知，再之后 道、我 等等。 另外，在这样不断读到一个个符号的时候，我们也并非单纯的按照字母或音节分别认识，而是首先明确哪些音节或符号共同组成相同含义，并将其作为一个单词来识别。在自然语言处理领域，这称为“分词”；而对于编译来说，这称为“词法分析”。 我们理解这个句子的过程可能是这样的： 读到 你，这指代一个事物，为名词 读到 知道，这指代一个行为，为动词 读到 我的，这描述了事物的属性，为形容词 读到 叉子，这指代了另一个事物，为名词 形容词 我的 和名词 叉子 组成 我的叉子，也是个名词 读到 被放，这是动词。 读到 在，这表达了一个关系，为介词 读到 哪里，这是名词 介词 在 和 名词 哪里 组成 在哪里，用于描述行为，为副词 动词 被放 和副词 在哪里 组成 被放在哪里，也是个动词。 名词 我的叉子 和动词 被放在哪里 组成 我的叉子被放在哪里，用于陈述一个事实，称为陈述句 名词 你、动词 知道 和句子 我的叉子被放在哪里 组成了 你知道我的叉子被放在哪里，是另一个陈述句。 读到 吗，这是一个疑问语气词，用于表达疑问。 句子 你知道我的叉子被放在哪里 和疑问语气词 吗 组成 你知道我的叉子被放在哪里吗，表达对被陈述的事情真实性的询问，是疑问句。 读完了所有的单词，最后得到的疑问句就是整个句子。 在上述过程中，我们不断将小的句子成分归纳为大的句子成分，在这样归纳的过程中，我们将句子中的每个单词相互关联起来，最终理解句子表达的含义。从中我们可以知道这是一个疑问，想要得到的回答是“你”与“我的叉子被放”两个事物间是否存在“知道”的关系等等。（这样说话好别扭。）...

一、前言——对象与过程 碎碎念：这篇文章里提到的语言是真的多：c、c++、c#、java、python、golang c 语言怎么能面向对象呢？c 语言的设计当然并非为面向对象做出考虑，但是其拥有的语法却足以使我们写出具有面向对象味道的代码了。因为无论是面向过程或面向对象，其背后的本质思想都是相同的，那就是这样一个著名的公式： $$ 程序 = 数据结构 + 算法 $$ 面向过程无非是强调其算法的一面；面向对象无非是强调其数据结构的一面。当我们使用面向过程的思想编写代码时，我们所想的是数据是函数中的参数和变量，数据在过程中流动和变化。而在面向对象中情况则反了过来：方法成为了类的成员，被类型所划分，并从属于一定数据的集合。 了解了这一点之后，再看程序语言从面向过程到面向对象的发展过程也能有新的认识。这一发展背后实际上是程序的关注点由机器向人的转变。在面向过程的时代，人们所关注的是如何操纵数据。那时的机器还没有蒙在名为抽象的面纱之下，呈现在操作者面前的依旧是赤裸裸的整个内存空间，数据与数据之间没有清晰的边界，是操作者自己组织起整个系统，为各个空间划分边界，定下名称。而在这一构筑起来的系统之上，数据本身就没有那么重要了，因为更底层已经为其提供了随时取用的接口。这时，管理流程成了另一个关键问题。因为在底层的支持下构建起来的日益庞大的应用，其自身的结构却往往不能支持其质量。于是人们以数据为界，将面条一般的数据流切割成彼此独立却又相互关联的部分。这样对象才得以诞生。 二、c语言的面向对象何以可能 说回 c 语言，当其以结构体的方式组织起数据的时候，就已经有了对象的雏形了。如果我们将函数视为所属于其第一个参数类型的方法，那么对象的方法也可以表示。但是只有这两点并非真正的面向对象，因为面向对象的三大特征——封装、继承和多态，其中的后两者还未实现。 让我们来详细分析一下继承和多态到底在表明什么。继承是两个类型间的关系，类型 A 继承了类型 B，则类型 A 具有类型 B 所具有的一切属性和方法，这意味着对于 A 和 B 这两个不同的类型，都具有所属于 B 的部分。从这一点来说，两者是相同的（也因为这种相同，子类才能不加转换的赋给父类变量）。而多态（在这里指方法的重写而不包括重载）则指子类 A 对从 B 所继承的方法的重写，使得虽是相同方法，其表现却能有所不同。 明确了继承和多态，接下来我们从数据的角度分析 c 语言为何可以面向对象。所谓的一个对象，即在地址空间中的一段连续区域。此时继承中所谓的相同，即对两个不同类型的对象，其内存空间中相同位置所表达的含义相同。如果对于 B 类型来说，偏移 4 个字节之后的 4 个字节表示一个 int 字段，那么对于继承 B 类型的 A 类型来说，偏移 4 个字节之后的 4 个字节应同样表示一个 int 字段。类似的，多态中所谓的不同，可以表达为类型中相同的方法名对应的具体过程不同。由于过程在机器码中表现为地址，那么本质上来说，多态的这种不同不过是指相同字段中的值不同罢了。 此时 c 语言中实现继承和多态的方法呼之欲出，那就是使用指针。地址指示了变量所处空间的起始位置，却不表明按何种方式解释这块区域，而指针完成了这份工作。对于所有赋给指针的地址值，其都如实翻译其中的数据，那么如果想要子类与父类按照同样的方式进行翻译，就需要子类在组织其结构时保持和父类一致。而对于多态来说，事情则更简单了，函数指针同样是指针，只要使其指向不同的函数即可。 这样也可以理解为什么 c++ 中只能使用指针实现多态（引用本质还是指针）。 Child c; Father *f = &c; // 正确 Father f2 = c; // 错误 而 c++ 中使用 new 关键字申请内存这一点也被 java、c# 等面向对象语言学了过去。java、c# 等中的类变量，实际上也和指针或引用没有区别...

一、前言 最近在尝试写一个简单的游戏引擎，我决定用 python 作为脚本，所以了解了一些混合编程的知识。 （1）python api 从原理来说，根据文档所述，python 提供了 Python.h 头文件，能够将 c 或 c++ 代码编译成可供 python 引入的动态链接库。该库中定义的可供 python 调用的函数中所有的入参都是名为 PyObject 结构体的指针。在代码中可以通过一系列函数对 PyObject 进行操作。 举一个简单的例子，我们希望 python 调用一个由 c 编写的简单的加法函数 int add(int a, int b) { return a + b; } 我们期望在 python 中这样调用 # test_mymodule.py from mymodule import add a = 10 b = 20 c = add(a, b) assert c == 30 那么我们首先需要对该函数进行包装，包装函数 _add 的参数和返回值都应该是 PyObject *。在包装函数中调用了 PyArg_ParseTuple 将传入的参数转换为 int 类型，调用原本的 add 函数得到返回值，之后又通过 PyLong_FromLong 将 int 转换为 PyObject。...

一、前言 这篇文章只是记录一些自己编写脚本时用到的零碎知识而已。这也是这一系列的最后一篇。 二、shell 的异常处理 有时我们希望在 shell 脚本命令执行出现异常时进行处理，比如说输出异常情况或退出等等。我们知道发生异常时返回值不为 0，如果是在 c 语言中我们可以这样处理 if (!do_something()) { // handle exception } 类似的在 shell 中 dosomething arg1 arg2 if [ $? -ne 0 ] then # handle exception if 但是这样编写起来太过麻烦了，我们可以采用另一种方法，那就是使用短路逻辑运算符。 我们还先以 c 语言为例，假设现在我们有两个函数，对他们取逻辑或 int r = func1() && func2() 那么在 func1 的返回值为 0 时，就会发生短路，不执行 func2。而在返回值为；而当 func1 的返回值不为 0 时，则会继续执行 func2。我们可以让 func2 完成 func1 的异常处理。 当然，在 c 语言中这种方法很是牵强，因为不同函数的栈帧并不一样，很难跨函数进行处理。可是 shell 中就不同了，所有的变量都是全局变量。 但还需要注意一点，shell 中 0 表示真，1 表示假。（因为 0 表示程序正常结束，所以为真。）所以在 shell 中就需要使用 || 而非 &&。...

一、前言 本文是“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....