Home

行为树及其实现

在笔者的项目中 NPC 要有自动化的行为, 例如怪物的巡逻, 寻敌和攻击, 宠物的跟随和战斗等. 完成这些需求最好的做法是使用行为树(Behavior Tree). 笔者查阅资料, 研究并实现了一个行为树, 可以满足游戏中相关的需求. 这里笔者简单作一些总结和分享, 推荐想要深入研究的同学去看文章最下面的参考资料, 这个一个非常好的行为树教程. 行为树的结构 顾名思义, 行为树首先是一棵树, 它有着标准的树状结构: 每个结点有零个或多个子结点, 没有父结点的结点称为根结点, 每一个非根结点有且只有一个父结点. 在行为树中, 每个节点都可以被执行, 并且返回 Success, Failure 或 Running, 分别表示成功, 失败或正在运行. 行为树会每隔一段时间执行一下根结点, ...

Read more

使用协程处理耗时过程

游戏服务器常常有一些耗时的操作, 比如说给全服玩家发放奖励. 如果直接写一个循环, 遍历全服玩家, 给每个玩家发放奖励, 那么整个过程可能持续几分钟, 十几分钟甚至几十分钟, 整个进程都阻塞在这个过程中了. 解决这个问题的一种做法是使用定时器, 比如说每处理完 50 个玩家, 就停 1 秒, 1 秒后继续处理, 就像这样: function deal(list) local p = 0 local function foo() local from, to = p + 1, math.min(p + 50, #list) for i = from, to do local id = list[i] ...

Read more

关于容错和断言的一些思考

实际项目中的代码总是多多少少会有一些问题的. 面对一些问题, 我们有两种做法: 一种是容错, 把错误自行消化掉, 让代码能够继续往下运行; 另一种是加断言, 让错误发生时抛出异常, 把错误暴露出来, 并且能中断当前过程, 避免后续行为未定义. 这两种策略中, 笔者更偏爱后者. 因为无脑的容错最后会导致问题的根源不被解决, 使问题堆积, 导致代码腐败. 毕竟解决问题的第一步是面对问题, 而不是回避它. 然而事情并没有这么简单. 无论是容错, 还是加断言, 都是要根据不同的场景进行思考. 无脑地容错和无脑地加断言都是不可取的. 我们来看两个例子: 1. 排行榜结算 游戏服务器中一个常见的需求就是结算排行榜, 给排行榜中的玩家发奖. 这样的代码通常是这样的: function sett...

Read more

RSA算法背后的数学原理

1. 引言 RSA算法(RSA algorithm)是一种非对称加密算法, 广泛应用在互联网和电子商务中. 它使用一对密钥进行加密和解密, 分别称为公钥(public key)和私钥(private key). 使用公钥加密的内容只能用私钥解密, 使用私钥加密的内容只能用公钥解密, 并且不能通过公钥在可行的时间内计算出私钥. 这使得加密通信不需要交换私钥, 保证了通信的安全. 那么它是怎么做到这一点的呢? 背后有哪些数学原理? 这篇文章我们来讨论这个问题. 本文会先介绍RSA算法中用到的数论概念和定理: 模算术, 最大公约数与贝祖定理, 线性同余方程, 中国余数定理, 费马小定理; 然后再介绍RSA算法的原理, 并证明其是有效的. 本文会假设你了解数论的基本概念, 如素数, 最大公约...

Read more

通过 UNIX domain socket 在进程间传递文件描述符

Linux 提供了一系列系统调用使我们能在进程间传递文件描述符. 这里的 "传递文件描述符" 不是简单地传递文件描述符这个32位整数, 而是真正地把这个文件句柄传递给目标进程, 使目标进程可以对文件执行读写操作. 现在假设 进程B 要给 进程A 发送文件描述符, 我们来看具体做法. 1. UNIX domain socket 要想传递文件描述符, 首先需要建立进程间通信. 这里我们需要用到 UNIX domain socket. UNIX domain socket 是一种进程间通信的方式, 它和普通的 socket 类似, 不同的是不需要用到 ip 地址, 而是使用一个 socket 文件. 我们要利用它发送控制信息, 从而传递文件描述符. 首先我们让进程A先创建一个 socket...

Read more

解数独算法

1. 引言 数独是一种经典的数字游戏, 玩家需要在一个 9*9 的棋盘上填数字, 保证每一行, 每一列和每一个小九宫格里的数字都是 1-9 且没有重复. 通常盘面上会给出一些提示数让玩家推导. 通常数独的解是唯一的, 但随着提示数的减少, 数独也可以有多个解; 极端情况下, 没有提示数, 数独也是可以解的, 只不过解的数量会非常多. 本文讨论解数独的算法, 并且尝试求出一个数独的所有可行解. 2. 合法的数 我们来看数独的规则: 玩家需要在一个 9*9 的棋盘上填数字, 保证每一行, 每一列和每一个小九宫格里的数字都是 1-9 且没有重复. 首先我们需要根据任意一个给定的棋盘, 快速地得出任意一个空白格子上可填的数. 怎样做到这一点呢? 遍历这个格子所在的行, 列和...

Read more

详解寻路算法(2)-生成图

1. 引言 上篇文章 中主要讲解了 A* 算法. 然而 A* 算法只是一个图搜索算法, 我们在游戏中的地图通常是用一些不规则图形定义的一片行走区域, A* 算法并不能识别这样的地图. 因此我们要做的工作就是把一张这样的地图抽象成可用邻接矩阵或邻接链表表示的数学上的图 $G=(V,E)$. 本文介绍两种方法, 可视图(visibility graph) 法和 导航网络(Navigation Meshes)法. 2. 可视图(visibility graph) 对于大多数地图来说, 我们可以看成由一个无限大的行走区域和若干个障碍物组成; 为了简化问题, 障碍物通常都可以看做多边形. 如下图所示: 想象我们处于起始点, 要绕过障碍物到达目标点. 当我们绕过障碍物时, 最短的方式...

Read more

编辑距离

题目源自Leetcode: 编辑距离-leetcode 给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 示例: 输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 解法: 动态规划 这是一道很漂亮的动态规划问题. 我们这样想: 越长的单词求解就越困难, 越短的单词求解就越简单: 长度为1的单词只需比较字母是否相...

Read more