这篇文章是在没有搭建这个Blog之前帮jobbole翻译的。“关于寻路算法的一些思考”是一个系列，其它部分均由伯乐翻译组其它小伙伴贡献。 关于寻路算法的一些思考（1）：A* 算法介绍 关于寻路算法的一些思考（2）：Heuristics 函数 关于寻路算法的一些思考（3）：A* 算法的实现 关于寻路算法的一些思考（4）：A* 算法的变体 关于寻路算法的一些思考（5）：处理移动中的障碍物 关于寻路算法的一些思考（6）：预先计算好的路径的所用空间 关于寻路算法的一些思考（7）：地图表示 关于寻路算法的一些思考（8）：长期和短期目标 关于寻路算法的一些思考（9）：寻路者的移动成本 关于寻路算法的一些思考（10）：最短路径的用户体验 关于寻路算法的一些思考（11）：寻路算法的其他应用 关于寻路算法的一些思考（12）：AI 技术 除了查找一条可沿着移动找到一个单位的路径之外，寻路在其它方面还有很多用途。 ...
这篇文章是在没有搭建这个Blog之前帮jobbole翻译的，现在只是复制回来自己做个存档，jobbole链接在这。 各位好！今天，我将告诉你如何做这样的事情：（在框中四处移动你的鼠标） 这种效果用于我新开发的开源游戏《Nothing To Hide》。许多其他的 2D 游戏（如Monaco，Gish）也都有。如果按着本教程来实现……也许下个就是你的游戏！ ...
这篇文章是在没有搭建这个Blog之前帮jobbole翻译的，现在只是复制回来自己做个存档，jobbole链接在这。 2D的俯视图经常用于从给定点计算可视区域。例如，你可能想把某些东西隐藏在玩家看不见的地方，亦或你想知道点燃火炬后能看见什么地方。 拖动圆点转一圈，看看玩家都能看到些什么： 这个算法也能计算出给定光源所照亮的区域。对每条光线，我们可以构建出被照亮区域的光线图。如果我们给上面的迷宫放上24个灯呢？见光线图。 roguelike（译注：类地下城RPG游戏统称）社区已经收集了好几种算法，尤其是网格类的。消减算法是从可见的一切区域开始，减去不可见区域；添加算法是从不可见区域开始，加上可见区域。我将描述一种可工作于线段的添加算法，不仅仅是固体分块或者网格。 ...
这篇文章是在没有搭建这个Blog之前帮jobbole翻译的，现在只是复制回来自己做个存档，jobbole链接在这。 我毫不犹豫的把这个算法称为“超酷”，虽然我自己发明了它，但我还是觉得它相当的酷，而且它很适合我算法系列的主题，所以无论如何要把它写下来。 ...
这篇文章是在没有搭建这个Blog之前帮jobbole翻译的，现在只是复制回来自己做个存档，jobbole链接在这。 作为开始，我假设你知道什么是排列，简单说就是按特定的顺序对序列进行洗牌。比如，值域1-10的排列为{5,2,1,6,8,4,3,9,7,10} 。一个安全的排列是攻击者即使有该排列的任意子集，都无法确定其它任何一个元素的顺序。这里有个简单的例子是使用一个安全加密的伪随机数生成器，用一个密钥作为种子，并用它来打乱你的序列。 如果你想生成一个非常非常大的排列，一个如此大的预计算和存储是不是不太现实？此外，你是否希望它是个安全序列？这里有个非常巧妙的方法，我们可以使用分组密码，使我们能够产生超过数值范围内的任何一个安全排列，而不必对它们进行预计算。 分组密码，没人不熟悉，它是密码学中一种常见的基础元素。它是由多块一定长度的密文组成，密文一般为64或128位的加密串。相同的密钥和相同的明文，它只可能生成相同的密文。超过一个块大小的信息使用一系列操作模式中的某一种方式加密，继而可以针对比单个块大许多的消息进行安全的加密和解密。使用分组密码加密，选择操作模式是至关重要的。为了能生成一个安全排列，无论如何，我们只打算每次加密单个块，所以我们不必担心操作模式。 如果你知道分组密码是如何运作的，你肯定能获得一个安全的排列。将给定长度的任意块（考虑下块的数量非常大的情况）用唯一的方式转换为另外一个块，且能将它再次转换回来。如果我们逐步加密更大的数字（1,2,3等等），我们保证能得到看上去随机的序列，只要不重复输入。这点很容易证明：假如它是重复的，那你会有两个输入数字被解码为同一个输出数字，这样就不可能有独一无二的解码。分组密码所持有的这些特性也正是对我们有用的特性。 你说，一切都挺好，但如果我想要一个不是2的幂次值域内的排列该如何？这里有个聪明的小技巧，就是取一个块长度略大于你想要的长度的分组密码，使用上面描述的方法，逐步加密序列中的更大数值，以产生排列中的元素。当加密后的值超出你想要的排列值域之外，只需再次加密。重复这样的方式直到你给到你想要的值域内的数值。同样，我们能保证分组密码的唯一性，并且我们也能保证（穷举方式）最终获得了一个理想值域内的数值。 很显然，在追寻这条路之前我们需要考虑一些因素。你要选择一个分组密码，是不是比你想生成的序列的值域要大，最好是2的幂次。密码值域和排列值域的比率确定了你运行的平均时间， 因此，如果密码是你排列的值域的四倍时，你就对每个值平均需要四次加密。这可能产生问题，因为大多数密码是64，128或者更多位。为了这个目的，我们找到适应性比较强的TEA加密算法，它很容易构造32,64,128或者更长位的变体，并且位操作在main主循环那很容易调整，也可产生4的幂次长度的密码，而无需将密码缩短至容易被暴力破解的长度。 另外值得一提的是，虽然这个技术的目的是生成非常大的安全排列，但对那些并不注重安全的排列同样有用 - 你的密钥可作为生成排列的随机种子。在许多情况下这种方法同样有帮助，基本上它是个映射函数可以用来索引排列的数值，这样你可以计算出该排列的任意子集的值。 最后，请记住，由于可能的排列数呈阶乘级增长，你的密钥空间肯定大大小于排列的数量。这个对于大多数应用可能并不重要，因为如此庞大的排列不可能一个个枚举过去。但是，如果你的密钥过短，它就有可能被攻击者利用枚举密钥的方式来找出可能生成的排列。 更新：Yossi Oren在评论里留了分优秀的论文连接。它涵盖了我的描述（当然更全面）。
这篇文章是在没有搭建这个Blog之前帮jobbole翻译的，现在只是复制回来自己做个存档，jobbole链接在这。 这是『超酷算法』系列的第一篇文章。基本上，任何一种算法我觉得都很酷，尤其是那些不那么明显简单的算法。 BK树或者称为Burkhard-Keller树，是一种基于树的数据结构，被设计于快速查找近似字符串匹配，比方说拼写检查器，或模糊查找，当搜索"aeek"时能返回"seek"和"peek"。为何BK-Trees这么酷，因为除了穷举搜索，没有其他显而易见的解决方法，并且它能以简单和优雅的方法大幅度提升搜索速度。 BK树在1973年由Burkhard和Keller第一次提出，论文在这《Some approaches to best match file searching》。这是网上唯一的ACM存档，需要订阅。更细节的内容，可以阅读这篇论文《Fast Approximate String Matching in a Dictionary》。 在定义BK树之前，我们需要预先定义一些操作。为了索引和搜索字典，我们需要一种比较字符串的方法。编辑距离（ Levenshtein Distance）是一种标准的方法，它用来表示经过插入、删除和替换操作从一个字符串转换到另外一个字符串的最小操作步数。其它字符串函数也同样可接受（比如将调换作为原子操作），只要能满足以下一些条件。 现在我们观察下编辑距离：构造一个度量空间（Metric Space），该空间内任何关系满足以下三条基本条件： d(x,y) = 0 <-> x = y (假如x与y的距离为0，则x=y) d(x,y) = d(y,x) (x到y的距离等同于y到x的距离) d(x,y) + d(y,z) >= d(x,z) 上述条件中的最后一条被叫做三角不等式（Triangle Inequality）。三角不等式表明x到z的路径不可能长于另一个中间点的任何路径（从x到y再到z）。看下三角形，你不可能从一点到另外一点的两侧再画出一条比它更短的边来。 编辑距离符合基于以上三条所构造的度量空间。请注意，有其它更为普遍的空间，比如欧几里得空间（Euclidian Space），编辑距离不是欧几里得的。既然我们了解了编辑距离（或者其它类似的字符串距离函数）所表达的度量的空间，再来看下Burkhard和Keller所观察到的关键结论。 假设现在我们有两个参数，query表示我们搜索的字符串，n表示字符串最大距离，我们可以拿任意字符串test来跟query进行比较。调用距离函数得到距离d，因为我们知道三角不等式是成立的，所以所有结果与test的距离最大为d+n，最小为d-n。 由此，BK树的构造就相当简单：每个节点有任意个子节点，每条边有个值表示编辑距离。所有子节点到父节点的边上标注n表示编辑距离恰好为n。比如，我们有棵树父节点是"book"和两个子节点"rook"和"nooks"，“book"到"rook"的边标号1，“book"到"nooks"的边上标号2。 从字典里构造好树后，取任意单词作为树的根节点。无论何时你想插入新单词时，计算该单词与根节点的编辑距离，并且查找数值为d(neweord, root)的边。递归得与各子节点进行比较，直到没有子节点，你就可以创建新的子节点并将新单词保存在那。比如，插入"boon"到刚才上述例子的树中，我们先检查根节点，查找d(“book”, “boon”) = 1的边，然后检查标号为1的边的子节点，得到单词"rook”。我们再计算距离d(“rook”, “boon”)=2，则将新单词插在"rook"之后，边标号为2。 在树中做查询，计算单词与根节点的编辑距离d，然后递归查找每个子节点标号为d-n到d+n（包含）的边。假如被检查的节点与搜索单词的距离d小于n，则返回该节点并继续查询。 BK树是多路查找树，并且是不规则的（但通常是平衡的）。试验表明，1个查询的搜索距离不会超过树的5-8%，并且2个错误查询的搜索距离不会超过树的17-25%，这可比检查每个节点改进了一大步啊！需要注意的是，如果要进行精确查找，也可以非常有效地通过简单地将n设置为0进行。 回顾这篇文章，写的有点长哈，似乎比我预期中的要复杂。希望你在阅读之后，也能感受到BK树的优雅和简单。