Skywind Inside

作为 Yacc/Bison 的好搭档 Lex/Flex 是一个很方便的工具，可以通过写几行规则就能生成一个新的词法分析器，大到给你的 parser 提供 token 流，小到解析一个配置文件，都很有帮助；而用 Python 实现一个支持自定义规则的类 Flex/Lex 词法分析器只需要短短 56 行代码，简单拷贝粘贴到你的代码里，让你的代码具备基于可定制规则的词法分析功能。

原理很简单，熟读 Python 文档的同学应该看过 regex module 帮助页面最下面有段程序：

def tokenize(code):
    keywords = {'IF', 'THEN', 'ENDIF', 'FOR', 'NEXT', 'GOSUB', 'RETURN'}
    token_specification = [
        ('NUMBER',   r'\d+(\.\d*)?'),  # Integer or decimal number
        ('ASSIGN',   r':='),           # Assignment operator
        ('END',      r';'),            # Statement terminator
        ('ID',       r'[A-Za-z]+'),    # Identifiers
        ('OP',       r'[+\-*/]'),      # Arithmetic operators
        ('NEWLINE',  r'\n'),           # Line endings
        ('SKIP',     r'[ \t]+'),       # Skip over spaces and tabs
        ('MISMATCH', r'.'),            # Any other character
    ]
    tok_regex = '|'.join('(?P<%s>%s)' % pair for pair in token_specification)
    line_num = 1
    line_start = 0
    for mo in re.finditer(tok_regex, code):
        kind = mo.lastgroup
        value = mo.group()
        column = mo.start() - line_start
        if kind == 'NUMBER':
            value = float(value) if '.' in value else int(value)
        elif kind == 'ID' and value in keywords:
            kind = value
        elif kind == 'NEWLINE':
            line_start = mo.end()
            line_num += 1
            continue
        elif kind == 'SKIP':
            continue
        elif kind == 'MISMATCH':
            raise RuntimeError(f'{value!r} unexpected on line {line_num}')
        yield Token(kind, value, line_num, column)

上面这个官方文档里的程序，输入一段代码，返回 token 的：名称、原始文本、行号、列号 等。

它其实已经具备好三个重要功能了：1）规则自定义；2）由上往下匹配规则；3）使用生成器，逐步返回结果，而不是一次性处理好再返回，这个很重要，可以保证语法分析器边分析边指导词法分析器做一些精细化分析。

我们再它的基础上再修改一下，主要补充：

• 支持外部传入规则，而不是像上面那样写死的。
• 规则支持传入函数，这样可以根据结果进行二次判断。
• 更好的行和列信息统计，不依赖 NEWLINE 规则的存在。
• 支持 flex/lex 中的 “忽略”规则，比如忽略空格和换行，或者忽略注释。
• 支持在流末尾添加一个 EOF 符号，某些 parsing 技术需要输入流末尾插入一个名为 \$ 的结束符。

对文档中的简陋例子做完上面五项修改，我们即可得到一个通用的基于规则的词法分析器。

改写后代码很短，只有 56 行：

(点击 more 展开)

Read more…

帧同步可以轻松解决高互动的联网游戏（如格斗，RTS 等）的同步问题，但该方案对延迟很敏感，现在一般省内服务器延迟差不多 10-15ms （1帧），跨省一般 40ms （2-3 帧），在此情况下，使用 Run-Ahead 机制可以有效的掩盖延迟的体感，让用玩家立马看到自己的操作反馈。

该机制有很多其他名字比如：预测回滚（prediction and rollback），或者时间曲力（time warp），名字取的天花乱坠的，很多文章也只是云里雾里说一半天，结果还没说清楚，所以本文打算最简短的句子说清楚这个概念，并给出可以实际操作的实现步骤。

我觉得用 Run-Ahead 这个质朴的名字更容易说明这个算法背后的思想：提前运行，这个概念不光用在游戏同步里，也早已用在游戏模拟器中，为了便于理解，先说一下模拟器中的情况（更简单）。

RetroArch 使用 Run-Ahead 隐藏输入延迟，一般需要设置一下 Run-Ahead 的帧数，比如 0 是关闭，1 是提前运行一帧，2 是提前运行两帧，一般设置用 1 或者 2，不要超过 5，因为太高游戏表现会很奇怪：

运行时 RetroArch 为每帧保存快照，假定的是用户输入有持续性，那么运行时当前帧使用上一帧用户的输入作为本帧输入（假设 runahead 设置为 1），然后接着往下运行，如果用户新输入来了，一律把它算作当前帧-1 的输入，然后再去对比历史如果和上一帧所尝试假定的输入一致就继续，否则快照回退到上一帧，重新用新的输入去运行，然后再快进到当前帧。

通常手柄或键盘都有 5ms 左右的输入延迟（部分设备如 switch 的 pro 手柄延迟高达 15ms），再加上操作系统处理的延迟，投递到模拟器进程里，从按下到真正开始处理也许也差不多 1 帧的时间了，RetroArch 用这个功能，也只有用户真实输入和预测输入不一致时才会触发，由于间隔很短，所以即使纠正也难看出来，最终在模拟器上达到了物理设备一样的超低延迟体验。

理解了模拟器的 Run-Ahead 实现，其实在帧同步里的原理也就差不多了，无外乎是用远程的旧输入，搭配本地刚采集到的新输入，作为预测帧的输入值，产生新帧，不匹配了再回滚。

帧同步里引入类似 Run-Ahead 的机制，要求游戏最近所有状态都可以被快速保存、复制和恢复，实现有很多种，你可以用状态的反复前进、后退来实现，但是 BUG 率太高了，这里给出一个更简易的实现方式：

（点击 more 展开）

Read more…