« May 2026 | Main

June 25, 2026

从猎户座之王到群星

每个经典电子游戏的游戏设计都多少有一些之前作品的痕迹。我认为原因有二:成功的玩法必须有大量玩家实际游戏体验的打磨证明其有效,在经典玩法上培养出来的玩家习惯可以极大的减少游戏的学习门槛,一个新玩法如果门槛过高就无法吸引足够的玩家去玩,也就得不到打磨。

我一直想搞清楚一款吸引我的游戏的核心规则部分到底是怎么设计出来的。为什么我可以玩成百上千小时还可以发掘出新乐趣,而开发者在看似不算太长的时间就设计出了它们。当我这两年有足够的时间,我开始用一种慢方法弄清楚这点:玩一些更古老的游戏,找到它们和现代游戏之间的发展脉络。

Stellaris 群星是我游戏时间第二长的游戏(第一是 Factorio),我从 1.0 版就开始玩,并从 1.2 版开始维护它的中文翻译 mod ,断断续续玩了接近 900 小时。只是由于时间关系(玩其它游戏)最近两年的新版本还没有体验。

一开始玩这个游戏是因为 Paradox 在战略游戏上名声显赫,当时 P 社四萌众人皆知。我特别喜欢维多利亚 2 ,已在上面花了上百小时。我深知 P 社游戏如果不是一开始就跟着开发玩,游戏系统的复杂度就会像雪崩一样压下来,上手门槛会越来越高。跟住一款新品,乘它还不那么复杂的时候跟着游戏更新一点点学习体验会更好,更别说我对太空科幻题材情有独钟。所以我在 Stellaris 发售前就开始关注开发 log ,第一天就进入了游戏。

由于 P 社已有十字军之王、维多利亚、欧陆风云、钢铁雄心在前,我想当然的认为群星是他们招牌大战略类型游戏的科幻版延续。我在游戏系统里也发现了大量 P 社游戏中熟悉的东西:更加肯定了这个想法。招牌式即时带暂停玩法,靠战争点数和驱动的战争系统,相互堆叠的 Modifiers ,这些都太熟悉了。至于不一样的部分,我觉得是在一个新游戏项目上的创新尝试。虽然我短时间未能体验所有的游戏系统,作为一个新游戏老说还是太庞杂了,但通过翻译游戏文本,我还是深刻感受到这个游戏的设计量。即使去掉在 P 社其它大战略游戏中已有的系统,剩下不一样的“原创”部分还是相当多。而我作为一个萌新进入却能感觉到大多数游戏系统都玩起来那么自然。


Master of Orion 猎户座之王的重置版 Conquer the stars 是在 2016 年出上线的,比群星还早了几个月。但我一开始并没有关注它,玩到这个游戏已经是两年之后了。读高中时就从游戏杂志上听说了 MOO 和文明开创了 4X 游戏这一新类型,比我当时最喜欢的三国志系列更复杂更有趣。语言门槛阻止了当时的我。在最近 10 年我试着玩了很多过去曾经喜欢的老游戏,发现很难找回过去的感觉。老旧的低分辨率画面并不是主要障碍,但过时的交互设计会极大的降低游戏体验。很多细节在 20 年间已经被后续游戏打磨得很好了,如果只是想追求游戏乐趣,真的没有必要回头玩老游戏。所以,老游戏的现代重置版就是回顾游戏发展史最好的替代。我打开 MOO 重制版的动机就是想看看这个太空 4x 游戏的鼻祖当时到底创造了什么。

我在 MOO 中重新看到了群星中熟悉的那些东西:开局自定义的差异化种族,模块化舰船,对未知星系的调查,用星际航道互联的星图(区别于文明类的棋盘格)…… 当我真正完成了一盘 MOO 后,我在收官阶段又看到了熟悉的终局危机,这一度被我认为是群星最好的原创:在游戏结尾放上完全不对称的 NPC 天灾让玩家挑战它们,而不是和对称的 PC/NPC 进行冗长的拉锯战。玩 MOO 的开荒和收官体验是最好的,中间略有拖沓。游戏系统不复杂所以上手极快,中间帝国规模过大时遇到星球封锁时,微操工人分配有点麻烦,但终局又会回到紧张刺激的“再来一回合”心流。原来,群星是站在巨人的肩膀上的发展结果。

之后,我又浅尝了许多相关的新老游戏,似乎摸到了太空 4x 游戏的发展脉络。

文明是当今最著名 4x 类游戏,但实际上 4x (Explore, Expand, Exploit, Exterminate) 这个词是在 MOO 的商业宣传上首次出现的。MOO 虽然不是文明开发团队所创作,但同为 MicroProse 发行,它比文明初代略晚。MOO 二代则和文明 2 同年发售,早于后面的半人马 alpha 。MOO 中的星系航程限制,在重制版中被视觉化为势力投影,让星系间的联合产生了动态的国界线,我认为这启发了半人马 alpha 的国界设定(这在文明 2 中是没有的),而这到了文明 3 中被固化下来衍生出文明系列的政治疆域和文化疆域系统。半人马 alpha 中的模块化部队和差异性种族应该是受 MOO 的直接影响。

作为 4X 类游戏,文明和 MOO 的游戏流程有很多相似之处。一开始都是派部队出去侦察开图,探出周边资源后,选择合适的地点开拓新基地。然后在不同的基地发展人口,提升生产力,生产力可以换得发展优势和新的部队。当不同势力的部队相互接触时,会展开外交以及战争。最后(多半)通过战争政府世界。在这个过程中,玩家需要同时积累科技点推进科技树,解锁生产力科技和军事科技,提升发展效率。

但这两个系列在细节上也有明显不同之处。地图是最大的不同,文明是网格状的,地图由等大的四边形或六边形网格组成,地理原因靠格子数量决定。每个格子上都或多或少存在一些不同的资源,最后会被纳入附近的城市(基地)所有。MOO 类则是离散的, 1 和 2 代,星系散落在星图中,只由点和点的距离决定通路。改变星图拓扑关系的是星云,在星云中航行会极大的降低航速。对的,这个设定后来直接被继承到群星中。这种星图相对网格地图有体验上的巨大变化,但也存在一些问题(某些玩家觉得不是)。那就是建立战略防线极难。当玩家把航程科技极大升级后,可以轻易跳过对手前线的防区。所以从 MOO 3 代开始,就改成了预设星际航道的星图,这使得某些节点比其它节点有更重要的防守价值。同时,还增加了虫洞,可以把遥远的两个节点直接连接起来。这让星图的拓扑关系更为复杂。

但 MOO 3 并不成功,很多不成熟的新机制破坏了老玩家的体验。星路的改变算半个(很多老玩家不喜欢),它也影响了后来的大多数太空类 4x 游戏。2016 年的 MOO 重制版虽然骨架继承了 MOO 2 ,但在星路这边沿用的是 3 的固定航路规则。但为了尽可能还原 1 和 2 的体验,还加入了不稳定航路。在游戏初期解锁科技前,这些不稳定航路会阻断交通。大致相当于在前作中那些被距离隔断的节点(之前是用航程科技限制它们联通的)。

在星际航行方面,一定要提一下 Sword of the Stars 星际之剑这个系列。它有一个招牌设计是不同种族采取不同的 FTL 航行方案,多达 5 种以上。预设星际航路是其中一种,只靠星系间距离来自由跳跃也是一种,还有建设星门或虫洞进行远距跳跃的种族。群星的老玩家马上就会意识到,这就是群星 2.0 之前的设计,它完全照搬了星际之剑的异构 FTL 种的三种。即使是现代版本,虽然开局又统一成预设星路图,但也能找到高科技下的另两种 FTL 的痕迹。群星 2.0 之后换了制作人,曾经写过一篇开发日志谈论为什么把极具特色的异构 FTL 去掉:FTL 的多样性带来的混乱极大地限制了他们后续开发更有深度的内政、贸易、外交、银河议会等系统,同时方便制作后来加入的贸易路线、划分星区、宣战厌战等 P 社传统设计。

为什么星际之剑可以这么干?因为星际之剑是一款强调星际战争的游戏。内政运营方面是极端弱化的。它继承了 MOO1 的去微观管理化,每个星球用一个简单的滑条决定发展偏向性,而在 MOO2 和重制版中则演变成精确的工人放置系统,玩家需要精确的控制每个星球用几个小人作哪方面工作,科研还是种田还是工业。这个设计在群星中用 job 系统进行了进一步的发展。星际之间的主创团队深入参与过 Homeworld 家园系统的开发。家园是一款以 3d 太空战斗为卖点的 RTS 游戏,而星际之剑明显想作一个结合 4x 战略和太空战场战术体验的游戏。它作了相当复杂的战术模拟,激光、导弹、质量投掷器,不同的武器有不同的特点,在战术战场可以走位和战场上的障碍物来改变战局。在这里,群星的战斗系统中,又可以看到星际之剑的影子。

无论是猎户座之王还是星际之剑,它们都有着复杂的自定义舰船设计系统。这在后面变成了太空 4x 的标配:在一个有限空间内玩家可以自由搭配组件,让自己的舰船独具特色。群星也完整的继承了类似系统。文明系列的半人马 alpha 虽然和传统文明更相像一下,却在自定义战斗单位方面更接近这些太空 4x ,文明的后续版本却没有这个设计。

但是,MOO1 和 MOO2 在战术玩法上却有相当大的差异。MOO1 更像是重视数值的卡牌堆叠模式,MOO2 则需要玩家关注每艘舰船的朝向。武器和护盾甚至能指定前后左右。玩的时候需要个体微操,这个玩法成为了 MOO2 的招牌,为很多系列的老玩家津津乐道。到了 MOO3 又改成了战前布局,无法单个战舰微操。战场上变成了千军万马的观战体验而不是靠操作战术上击败对手。这也是 MOO3 被系列玩家诟病之处,但历史发展到今天已经说不清哪种对玩家体验更好,只能说有不同的玩家群罢了。星际之剑的初代晚于 MOO3 发售,或许是看到了这些差评,更多的应该是继承了家园的血脉,它在战术层面比 MOO2 更加细腻,而且从战术回合制转变为实时操控。而 MOO 2016 的重置版在继承了大部分 MOO2 骨架的基础上,战术玩法也改成了实时加暂停模式。这可谓顺应时代潮流,现代玩家恐怕再难适应一艘艘船单独操控了。但依旧有很多老玩家评论说不如 MOO2 的战术玩法好玩。因为它虽然保留了 MOO2 的单个舰船的方向设计,但却砍掉了单独原地转向这些机动能力,实时混战时很难操控。

MOO2 和星际之剑中都有极具特色的跳帮战。可以为舰船配备陆战单位,在太空战中直接登船抢夺敌舰(以及敌舰科技)。在后续的游戏中再难看到,MOO 2016 重置版中也砍掉了这个系统。

即使星际之剑的战术系统中有这么多 MOO2 的影子,但在仔细考证了一番后,我认为这两个游戏的战术玩法并没有明显的继承关系,它们却有个共同的源头,那就是桌游 starfire 。星际之剑尤甚,在自定义舰船方面更为接近。

Starfire 诞生的很早,在 1979 年就发行了第一版,风靡一时。和当时的桌面游戏一样,也有大量的文学衍生作品。不过它的流行年代比较久远,现在提到它的玩家就不多了。但这的确是一个有着很长生命周期的系列,直到 2012 年还发布了第六版规则。在 bgg 上有专门的 wiki 页面展示整个系列 。btw, starfire 的桌游官方设定是从 2200 前后开始的。星际之剑也把游戏设定在 2200 到 2400 年。至于群星玩家肯定对 2200 年这个设定非常熟悉。

Starfire 的核心战术规则是让玩家在纸上设计太空飞船,用一串字母表示每个模组,比如 S 表示护盾,L 表示激光,A 表示护甲,Q 表示剑桥和船员舱等等。当敌人命中你的飞船时,从左到右划掉对应字母,飞船的功能也随之受损,其推进力、转向机动力和攻击力也需要更新,非常直观。飞船在战斗时在一个六边形棋盘上进行,由于有护盾朝向和射击死角的设定,转向和走位都有很重要的战术意义。这套舰船设计和战斗机制深深的影响了星际之剑的战术系统,星际之剑比 MOO2 更接近这个桌游的配船系统。船头船身船尾的三段式设计,在战斗中可以分段破坏,几乎就是 starfire 桌游中逐步花掉功能字母的战术体验。

starfire 除了局部的战术对决,还包含了庞大的星际探索、技术研发和殖民地经济管理的战略战役。作为一个太空兵棋,在及其丰富的战略扩展中就设计了完全不同的种族 FTL 机制。异构 FTL 带来的非对称战略体验被星际之剑完美继承。btw, 当初我们的游戏《三国志战略版》立项之初,我正沉迷在群星 1.0 版本中,感叹于异构 FTL 在战略成面提供的奇妙体验。专门找三战主设计师聊了一下午,介绍这个系统。

Starfire 在长期战役中,科技研发具有相当的随机性,科技被分成几个类别,研发靠投骰。不同种族有随机的科技偏好,打扫战场和探索遗迹都有概率抽到随机科技。这些都能在后面的群星中看到影子。随机科技树也是 MOO 的招牌设定,和文明的固定科技树有着明显的对比。在 MOO 的诸多现代精神续作中也得到保留。

不管是星际之剑还是 MOO 以至于群星,都设定了中后期的银河灾难,这些设计灵感均来源于 starfire 的官方小说和剧本。

星际之剑(以及 MOO)采用的大地图回合制战略加实时战术对决架构也和 starfire 颇为相似。而电子游戏的优势就是借助计算机模拟,可以把原本在桌面上几周时间才能玩完的桌游战役以更快节奏展示给玩家。以往桌游上每天可能只能玩一场战术对决,现在在电脑上就只是半小时的战斗。

最对这一系列太空 4x 类游戏溯源的过程中,我不仅发现了 Starfire 这个桌游源头,还找到了另一款桌游 1975 年发行的 Stellar Conquest 。这个名字很多次的出现在这些电子游戏创作者的媒体访谈中。年代过早我自然是没有玩过,但我很好奇的下载阅读了它的说明书。原来,这才是太空 4x 的真正先驱。侦察舰/护卫舰/殖民船的设定,探索/殖民/建设前哨站/扩展/征服的概念都是这里提出的,甚至还包括在星云中减速的设定。殖民地上太空战过后再次用陆战队登陆战也如出一辙。最奇妙的是我在说明书上读到了将恒星分为蓝/白/黄/橙/红五类,玩家可以先看到恒星颜色就可以大略知道星系里会有什么,可以由此决定侦察的优先级。这个设定一直继承到了群星,但并没有在游戏内明显说明。如果没有玩过这同类游戏很容易忽略这点。但在 MOO 中,明确解释了黄色恒星周围存在宜居带行星的可能性更高。

太空 4x 和文明 4x 相比,有一个很大的不同点就是更难找到宜居的殖民地。不同种族的宜居星球类型也不相同,如果找不到合适宜居星,就会影响生产效率,通常需要开发类地化科技对星球改造。这一设计几乎贯穿所有太空类 4x 游戏。调查母星附近的星域,找到合适的殖民地几乎是这类游戏开局一致的操作。在 MOO1 中,在星图上发现一个恒星,就可以作为一个航行节点,并可以在上面开拓殖民地(如果允许);到 MOO2 后拓展了行星系统,同一星系可以有颗行星,还可能有小行星带等其它星体。星系结构更为复杂了。这个设定一直延续到后面多数同类游戏。最近几年有一款被称为 MOO2 的精神续作的商业游戏叫做 Interstellar space : Genesis 。我略玩了一下,感觉还不错。它在侦察星图方面又扩展了不少深度。每个星区都可以做不同程度的扫描,深度扫描可以发现更多星球,这样在对抗时就能更好的隐藏战略点:在通过深度扫描发现的星球上做基地,对敌人可能是不可见的。


前面提到了桌游 Starfire 对太空 4X 游戏的影响,这里就很值得提一下免费游戏 Aurora 4X 。这是一款免费的有着 20 年以上的免费游戏,至今(到 2026 年)仍然在继续开发。我了解到它是从读 Distant worlds 的攻略开始的,而 Distant worlds 被称为猎户座之王 3 事实上的精神续作。所以故事得从 MOO3 说起。

如果我们纵观 MOO 系列得发展历史,可以发现 MOO 的每一代都希望对前一代做出大的改变,而不是简单的打磨完善。btw, 这一点和文明系列颇为相像。文明的原创者席德·梅尔有一个注明的三分之一法则(Sid Meier's Rule of Thirds),大概是说,每代文明都保留 1/3 的传统系统,改进 1/3 ,引入 1/3 的新系统。MOO 系列在改变方面步子迈得更大。2 代除了上面提到得单星系多星球外,还改变得科技树,从发明概率(这是从 starfire 继承来的)改成了每级科技三选一互斥。初始种族的点数定制取代了 1 代的固定种族(这被继承到了群星中)。加入了终局 boss 。战术层面引入了极大的微操,战略层面也把滑条控制星球的偏向改成了工人分配的微操形式。

总的来说,MOO2 加入的新系统都颇受玩家欢迎,而玩法从宏观管理慢慢向微观管理转移也很成功。但到了 MOO3 ,设计者又想在宏观管理上发力,让玩家扮演帝王,而不必在微观上亲历亲为。只用做战略决策就够了。但它并不是简化内政系统,把原来需要微观操作的部分变成几个简单的数值,而是进一步的把系统微观化了,然后让 AI 通过自动化规则去运行它们。如果放在今天,这个理念倒是很现代的。Paradox 的几个著名系列都在往系统的复杂化方向走,并辅以自动化手段减轻玩家的决策强度。但 MOO3 执行的很糟糕。其中尤其重要的一点是,它做了微观的系统,却完全剥夺了玩家做微观操作的控制权。结果玩家玩游戏想在看一个自动化运行的机器,失去了参与感,尤其是 2 代的老玩家对旧的微观管理玩法保持着很高的满意度。

等到 2016 年推出重制版,又转回 MOO2 的思路,完全放弃 MOO3 的创新尝试。但复刻过去的游戏系统,面对同年有着组多现代游戏元素,完成质量颇高的群星,在太空 4x 这个玩家圈子中口碑已经无力回天。(当然,我觉得这个重制版还是很值得一玩的)

在我看来,MOO3 的思路是对的,如果执行的好也可以很好玩。但执行的好却很难。Distant worlds 初代于 2010 年发行,离 MOO3 发行的 2003 年已过去 7 年,我们在 DW 中发现了很多和 MOO3 几乎完全相同的设定,几乎肯定是受 MOO3 的影响。比如,游戏世界都分为民营经济和公共部门,玩家只能主动控制公共部门,但不可以干预民营经济。平民会自己根据市场需求买船运货赚钱,你只能从他们那里收税。很多民营经济下的设施和舰船,玩家可以参与设计和建造,但作出来的东西却不是你的,不受控制(有点怪怪的)。我没有玩过 MOO3 ,但我玩了 Distant world 。从玩家论坛以及 google 来的信息看,这些的确都是 MOO3 做过的。但不同在于,Distant worlds 允许玩家自动化所有的子系统(比如设计舰船,收税,派遣侦察舰等等),也可以让玩家手控。

我购买 Distant Worlds 后第一次是没玩进去的,直到最近重新研究太空 4x 系列,我照着一篇攻略重新尝试了一遍,这次会玩了。这篇攻略主打一个把所有的自动化(默认设置)全部调成手动,每个子系统都手操一番,让我可以直到游戏中到底发生了什么,游戏系统是怎样运作的。这次我才发现其中的乐趣。在阅读攻略时,作者写道,如果你觉得太麻烦,可以去试试更“简单”的 Aurora 4X 。从作者的写作风格看,我直到他在说反话,所以在研究 Aurora 4X 前,我就对游戏的复杂度有一定的心理准备。

Aurora 4X 的确更为复杂,对宇宙的模拟也更事无巨细。它被称为太空策略类游戏的矮人要塞,或是文本风格的宇宙模拟器。举个例子:你在设计一艘飞船前,需要对每个零件单独研究:发动机、燃油效率改进、武器的聚焦透镜、雷达的扫描波长等等。你需要率领不同领域的科学家团队,为他们组织实验室,他们会有不同领域的专长,在每个子领域单独做出科研突破。然后你再把每个零件的科研结果,通过不同的工厂和公司生产出来装备在一起,最终拼凑出一架独一无二的飞船。根据搭配的零件,再决定它用于侦察、殖民、运输还是战斗。 再以侦察为例,在其它游戏中点一下地图就可以派遣出侦察舰,而在 Aurora 4X 中却需要先创建一条命令,涉及侦察的路径,在不同场景下的行动(比如遇到敌人要回避,油箱见底前要回去加油,遇到不同的天体要决定侦察优先级等等),最后再把飞船绑定在命令上,最后自动化了。不光时领导实验室的科学家,帝国的军官等也有及其详细的履历,性格,技能加成,会生老病死拉帮结派,这在群星中倒能见到类似系统,只是没有 Aurora 4X 这么细致。

Aurora 4X 中还有复杂的天体引力系统,天体有着椭圆形轨道,和不同的公转周期。这使得星际航行的时间窗口都更为重要(更接近真实宇宙)。这在 Distant Worlds 中也有体现,但不如 Aurora 4X 系统复杂。和其它同类游戏不同,Aurora 4X 有独特的时间推进系统,玩家可以从 5 秒到 30 天的间隔。在太空狗斗时,需要按秒推演,可以通过微操舰船去拦截来袭的导弹。而进行宏大的研究建设项目时,往往以 30 天为周期跳跃,玩家只关注那个文本信息窗口,脑补游戏世界中发生了什么。

我饶有兴趣的搜索了 Aurora 4X 的历史,发现和 Starfire 有相当深厚的渊源。Aurora 4X 的作者的初衷就是想作一个辅助桌面玩 Starfire 的电子工具。(顺便学一下 VB ,他原本是个 C++ 程序员。选择 VB 应该是方便驱动 Access 数据库,而游戏的数据则选择放在 Access 中。他在学 VB 的过程中边学边做。不过最新的版本已用 C# 重制)这个工具在 starfire 完全圈子里风靡一时,但是最终和 starfire 开发团体吵了一架导致分道扬镳。

这段恩怨被记录在这个帖子的回复中 。喜欢八卦游戏史的我简单看了一下,大概是这样的:

Starfire 的电子辅助工具一开始是被官方推荐的,它基于 starfire 的第三版规则开发维护。但后来 starfire 大刀阔斧的改动推出了第四版规则。这种桌游规则的变化往往是剧烈的,更广为人知的对比参考是 DnD 的 3/4/5 版本变化,网络上可以找到很多讨论。总之,这个电子辅助工具未能更新到第四版,开发团队(准确说就一个人)希望在第三版规则上继续。在官方的口头承诺下,成立了一个粉丝组织叫 3DG ,继续维护第三版规则。3DG 的主导人物就是这个 Aurora 4X 的开发者。他们作了大量的迭代更新。在某个时间点,他暂时离开了 3DG ,3DG 就由官方接手。但 3DG 的其他成员并不满意新的官方领导,在后来原领导人回归后,矛盾就爆发了。

导火线是 3DG 在网上发布了新的基于第三版规则的修订版规则书,这侵害了官方(主要利益方也主要是一个人,也就是桌游开发者)的利益(至少在官方角度看是侵害了,他们在主推第四版)。所以 3DG 被要求解散,电子辅助工具也禁止继续维护。工具被下架了,但过了几个月就以 Aurora 4X 的形式重新上线,这次开发者就放飞自我了,完全不用考虑兼容 starfire 的规则限制,大规模的夹带了私货。这个事情最终没有真的闹上法庭,不了了之。

从另一篇访谈看 ,Aurora 4X 除了主要受 starfire 的影响外,还借鉴了一个古早的 DOS 游戏 Harpoon ,以及 战锤 40K , EVE Online 等等。

另一个桌游设计者(开发过类似桌游)写过一篇对 starfire 的评论 。他写道:

To put it another way, the original Starfire III campaign rules were 23 pages long. The last version of Starfire that I've purchased (Solar Starfire from 2012) is over 400 pages. To be fair, however, I think about 100 pages of that page count covers the tactical rules, but even then we are talking a 10x increase in content between the two editions. Is the game ten times better for the extra rules?

我觉得当桌游繁杂到需要几百页说明书时,电子化就成了必然之道。


回到 MOO 系列的主线上。市场上充斥着大量精神续作,这说明这个系列的玩法已经深深刻在老一代玩家的心中。除了官方重制版,上面还提及了星际之剑 SotS,ISG ,Distant Worlds 系列。我还略玩过一点 Endless space ,Polaris Sector 和 Star rules ,体验很少,不作评价。比较有名的还有银河文明系列,和太阳帝国的原罪系列,但我均未接触。

在免费游戏中,有完全复刻 MOO 一代的 Remnants of the Precursors (简称 ROTP),我虽然没有细完,但它在 MOO 老玩家中口碑颇佳。除了在交互和画面上最了现代化改进外,游戏系统几乎是完全复刻 MOO1 。是玩 MOO 重制版(核心还原的是 MOO2 )的之外的又一选择。

还有一个 freeorion 项目,也一直活跃。我没有玩过这款游戏,但曾经仔细阅读过源代码。主要是因为想了解一下这类 4x 游戏的程序结构。用开发者自己的话来说 ,它希望保持简单易上手,避免微观管理。所以在借鉴了 MOO2 一些有趣的新系统外,去掉了 MOO2 中的大多数微观管理,比如在我有限的游戏体验中,它并没有星球的工人放置系统,只需要为星球设定一个总的方向即可。也没有 MOO3 里面居多的水面之下自动化运作的复杂机制。

Endless space 其实也是个好游戏,我只试了一下 2 代,把教程过了一遍。印象比较深刻的是其中的卡牌驱动部分。它的战术部分用卡牌驱动,内政部分也用卡牌来表现其法律系统。用卡片还表达游戏中的选择在桌面游戏中及其常见,现在也越来越多的在电子策略游戏中见到。卡牌可以减少玩家的决策负担,过去很多独立的选项可以被合并在同一张卡片上,让单次选择变少,而通过组合增加变化。抽卡也可以增加一些随机性元素。采用卡牌驱动往往可以加快游戏速度。因为玩家面对的选择压力变少了,就可以快速决策。

在这方面有一款教新的游戏值得推荐一下,Nexus 5X 。它也是 Pardox 发行的,采用了群星的世界观。在 4X 基础上加了一个 X 为 Express ,它希望这类游戏可以摆脱单局动则数十小时的长度,在一个小时内可以玩一局。我玩了两局,的确节奏很快,但体验更像是一个数字化桌游。玩家群认为它是一个缩水版的黄昏帝国 Twilight Imperium 。我家里倒是有一套 Twilight Imperium 实体版本,只是一直凑不齐人开上一局,所以无法给出自己的评价。但通过抽卡打牌推进游戏的方式的确让人印象深刻。


这篇 blog 完全没有 AI 生成的文字,其中关于游戏的观点全部是我有了真实游戏体验后总结的。但在做这个课题(关于太空 4x 游戏类型)研究期间,我和 Gemini 做了大量的讨论。AI 的确可以给我很多思考角度上的启发,但是关于游戏本身的事实,很遗憾的是 AI 给的信息的正确率几乎在 50% 左右。也就是 Gemini 写的关于游戏本身的特点/规则/细节的描述,几乎有一半是错的。但它在语言上却铮铮有词,习惯了和 AI 讨论后,我必须把它和人讨论的过程区分开。如果和一个有经验的玩家讨论,我可以信任玩家的体验,但 AI 毕竟不会自己玩游戏,它只能从网上已知的文本中做总结。网上同类游戏讨论之多,让 AI 特别容易产生幻觉。或许以后的我们更应该学习的是如何更好的阅读 AI 产生的文本。

June 11, 2026

对基本有序的序列排序算法

quicksort 是基于比较的排序中表现最好的算法,它在大多数情况下都能接近时间复杂度 O(n log n) ,所以 qsort() 也是 C 标准库中排序的默认实现。但是,quicksort 是非稳定排序,即当原始序列中出现相同的元素时,经过 qsort ,这些相同元素的次序可能被调整。即两个 key 相同的元素,经过排序可能调换次序。

在某些场合,我们希望排序是稳定 stable 的。因为元素的 key 相同,但元素本身可以不相同。这些有着相同 key 的元素一开始以某种次序放入序列,我们不希望对 key 排序后,打乱原有的次序。当需要稳定性时,还有许多经典排序算法可供选择,例如插入排序,它非常简单,每次从无序序列中选择一个元素和有序序列的最后一个元素比较,要么追加在最后,要么向前依次比较,直到找到合适的位置插入。对已经有序的序列,插入排序的时间复杂度为 O(n) ,但对于逆序的序列,它会退化到 O(n^2) ,因为每个元素都要和之前所有元素比较一次,插入到最前。所以插入排序对于非特定场景(无特定规律的数据)的平均时间复杂度接近 O(n^2) 超过快速排序的 O(n log n) 。

但需要注意,光看大 O 时间复杂度是不够的。在 n 很小的时候,对实际开销影响更大的并非算法复杂度。因为复杂度是基于执行算法中每个单步操作的数量估算的,忽略了操作本身的时间差异。而 n 很小时,单个操作的开销占比就变大了。所以在 n 很小时,简单的算法每个操作都更短,对 CPU cache 也更友好,导致实际的总时间开销也越少。大部分排序算法的实现都选择在 n 很小时退化成插入排序。

对无规律数据集,基于比较的排序算法的理论极限是 O (n log n)。因为你需要至少对所有元素做一次比较,采用二分的形式分而治之是最好的方法,不断二分数据集的深度大致为 log n 。归并排序 merge sort 直观的体现了这个想法,它把数据不断对分,展开为一个完全平衡的二叉树,然后从叶节点逐级向根节点调整次序并合并,一路执行到根节点,就可以完成排序。所以它可以严格(即使在最坏情况)做到 O (n log n) 。或者这么看,合并两个有序序列只需要扫描两个序列各一遍,每次都挑出两个序列头部更考前的元素,插入新序列,就能得到合并后的有序序列。假设一共有 128 个元素,不断对分,就能分成 64 组元素每组 2 个。这两个元素调整位置合并成 32 组 4 元组,再继续为 16 组 8 元组,等等。

显然,merge sort 是很容易做到 stable ,但缺点是它难以在原地 in-place 排序,需要额外的空间。这导致实际实现时,需要额外的内存复制。在大多数要求 in-place 排序(大多数 sort api 都是这样)的场合,比 quicksort 要慢,且需要额外的运行空间。

但在真实世界的应用场合,大多数需要排序的数据并非毫无规律。针对有规律的数据排序就可以在工程上针对规律做出改进。一个普遍的规律是:往往需要排序的数据本身就是基本有序的,至少很多片段是局部有序的。因为你很难一次性获得海量的完全随机的数据集。数据都是逐步变多的,如果它们之前的片段是有序的,在整合到一起后,大部分还保持着次序;或者是原有的次序经过少量的调整,破坏了局部的次序。针对这点,就可以对 merge sort 做大幅改进。python 最早的版本直接封装 C 的 qsort() 实现排序,但随着 stable sort 的需求日益增加,在 2002 年 Tim Peters 针对这类情况改进了 merge sort 算法,最终成为 python 排序算法的标准实现。这是一个混合排序算法,一开始并未正式命名,但随着它作为一个比 merge sort 更能适应现实数据集的算法被引入 java 等其它语言的标准库,大家就用第一次工程实现者的名字命名为 timsort 。btw , 它的核心想法并不新,在 Knuth 的计算机算法艺术第三卷的排序算法中就有提到。

timsort 最重要的核心想法是:既然现实中的序列并非完全随机的,那么我们就先找出序列中的有序片段 (run) ,再对这些片段进行 merge sort ,这样就能大大的减少 N 。比如在极端情况下,一开始序列就是完全有序的,那么 N 就退化成了 1 。但是,如果我们一开始完全把序列的有序片段都标记出来,就需要等长甚至更大的内存空间记录这些 run 。原本 merge sort 的缺点就是需要更大的额外空间,但它需要的额外空间是固定的。如果在最坏情况下额外空间的上限更高 ,作为通用库,这是不可接受的。所以,需要一个有着固定上限的额外空间来处理这些 run ,且最坏情况也不能超过 merge sort 。

我们可以把 merge sort 的 run 看成是固定的 1, 2, 4, 8 ... 虽然算法描述是递归的,但由于我们不会处理超过 2^64 个元素,所以递归深度非常有限(低于 64 )。而且在这个固定规律下,很容易得到一个非递归的实现。当 run 的长度不固定时,Tim 认为用一个自适应的方法合并相邻 run 就可以了。应该尽量的将相邻的小 run 合并成更大的片段,而避免把已经很大的 run 上追加相邻的小 run 。至于为什么只能合并相邻的 run ,因为只有这样才能保证 stable 。

他提出顺着扫描序列,找到三个连起来的 run 就可以决定该合并哪两个更好。在 Wikipedia 上 timsort 页有简单的描述,还有一篇 blog 也有解释,cpython 的邮件列表里也有一篇叫 listsort.txt 的文档(链接以不可访问)。我全部读过后发现它们之间有细微的差别,这让我很疑惑。直到我读到 On the Worst-Case Complexity of TimSort 这篇 paper 才确定正确的描述。然后又看了 youtube 上 Quicksort, Timsort, Powersort - PyCon US 2023 talk 进一步印证了这点。

原始的算法是这样的:

用一个栈记录从头扫描每个 run 的长度。比如最后的三个 run 长度为 X Y Z ,其中 Z 是栈顶,也就是最后扫描到的 run 。

首先检查规则 A :当 Z 长度大于 X 时,把 X Y 合并起来,栈顶留下 (X+Y) 和 Z 。

如果不满足规则 A ,再检查规则 B :当 Z 大于等于 Y 时,合并 Y 和 Z ,即栈顶留下 X 和 (Y + Z) 。

若以上都不满足,但满足规则 C :若 Y+Z 大于 X ,则也合并 Y 和 Z ,结果和应用规则 B 一样。

若三条规则都不满足,就继续向栈顶添加后续的 run ,重复这个过程,直到整个序列扫描完,最后依次合并栈顶两个 run 。

这套规则的想法是:尽可能的把较小的相邻 run 合并在一起,但如果连着三个 run 长度类似,避免将仓促合并,而继续看下一个 run 。但实现上需要给栈设定一个最大的上限,因为它是利用 C 的 stack 实现的,需要避免 C stack 溢出。如果遵循以上规则,保留 run 长度的栈就会从大到小排列,因为一旦有更长的 run 入栈,就会引起合并。规则 C 则保证了最前面(栈底)的那一项长度超过后两项的和。这可以保证整个序列最坏情况类似斐波那契数列,大致上是指数分布的。这样,栈的最大容量在 64 位系统上也可以用一个较小的值就能保证不会溢出。

在很长时间里,没有人去验证这个假设是否是严格正确的。这个算法也被抄到了更多地方。直到有人试图用形式化证明 java 的 OpenJDK 正确性才发现有问题。

比如,我们构造这样一个序列,92 28 20 6 4 8 1 ,前 5 项(92 28 20 6 4 )依次入栈时,每一项都不会被合并,同时保证了依次递减,每一项都超过后两项之和。但接下来的 8 入栈就发生了变化,因为 8 > 6 ,所以 6 和 4 被合并位 10 ,序列变成了 92 28 20 10 8 ,这时,中间的 20 + 10 已经超过了前一项 28 。最后一项 1 入栈却并不会促使前面项的合并。这会导致算法根据算出的 2^64 项以内最坏情况下需要的栈容量上限偏小,精心构造一个序列就会导致栈溢出。Python 和 Java 在修复这个问题时采用了两种不同的方案。Python 增加了第四条规则:新入栈的 run 如果没有引起合并,要重复检查一次原有的栈顶三项,看前一轮合并适合做的彻底。这个方法后来被形式化证明是完备的,只不过每轮入栈可能需要多一次判断。Java 一开始的修复方案是重新计算了一个更大的理论上限。不过这个上限后来被证明又算小了,重新打了一次补丁。不过这只是理论值,构造一个超出错误上限造成栈溢出的序列,需要相当大的长度,所以实际上并没有发生过。


依赖形式化证明堆栈上限看起来过于隐晦,需要一个更简单明了的算法确定保存 run 的栈大小上限,这是 python 3.11 引入 Power sort 的动机。了解 power sort 的设计思路可以从回顾 merge sort 开始。merge sort 本质上是基于完全二叉树的逐层合并,所以,即使用递归实现,栈深度也严格保证在 log 2 之内,也就是 2^64 元素最多需要 64 层深度,这一目了然。当 run 的长度不确定,由原始序列中固有的有序片段长度决定,我们还是可以让合并策略尽可能的近似完全二叉树。由于我们假设了原始数据局部有序,所以可以看成是提前做了一些合并,那么理论上需要的栈深度不应超过 mergesort ,最坏情况也是和 mergesort 一致。

所以,可以先想象一个虚拟的完全二叉树,然后在遍历序列时,把每个 run 和虚拟完全二叉树的 run 对比,找到相邻的 run 对应到完全二叉树上是否应该合并,还是已经被合并过了。由于完全二叉树可以通过非常简单的公式算出每个分支片段,所以并不需要额外的储存空间。算法就变成了每次看栈顶两个相邻 run 的中点落在哪里,找到它和虚拟完全二叉树上最接近的节点,记录下它的层级(power),越靠叶子节点的 power 越小,越靠根的 power 越大。由于节点数量限制在 2^64 ,所以 power 最大就是 64 。而合并规则就可以简化成:让保存 run 的栈额外记录每连个相邻 run 的 power ,栈中元素的 power 必须依次增大,如果减少,就合并栈顶两个元素,并重新计算合并后的 power 。显然,栈的容量上限就是 64 ,不需要过多的形式化证明。

powersort 未必一定优于 timsort ,但在实践中它几乎总是略微好一点:更像 merge sort 表现的那样,尽可能的先合并较小的 run ,逐层合并成更大的 run 直到完全有序。当然,它虽然减少了每次合并前的条件判断,但增加了一个常量时间的 power 计算,使用 power 来拟合 merge sort 的完全二分也不总是正确,这些都有可能导致在某些条件下比 timsort 略慢。但关键在于,它运行需要的栈上限清晰明了。

如果想更进一步理解 powersort ,非常推荐上面提到的 PyCon US 2023 上的那个演讲,其中有非常清晰的算法视觉化演示。


除去改进了这个如何启发式合并 run 的算法,powersort 的其它部分和 timsort 是基本一致的。timsort 的其它对 mergesort 的改进几乎都是针对数据局部有序做的,长期实践也证明它的确非常有效。

其一,当数据基本有序时,合并两个 run 需要的额外空间可以大大减少。假设相邻的两个 run 原本就是基本有序的,只是很少的数据调换导致了分割成两片有序 run 。那么,我们可以用二分法找到前一个 run 中前一半不需要移动,以及后一个 run 中后一半不需要移动的两个端点。这两部分都不需要调整位置。剩下的两段,只需要更短的一半额外空间就可以整理成有序的序列。这是因为,我们只需要把其中一个 run 复制出去,然后在空出的位置上做合并。如果是前一半空出来,就从前到后合并;如果是后一半空出来,就从后向前合并。即使是最坏情况,也不会超过 N/2 的额外空间。

其二,在合并两个 run 时,如果发现连续取用其中一个 run 上的数据,就可以进入 Galloping 模式,即用二分法找到一段数据复制,而不是一个个比较。这里给 Galloping 设置了一个限界,逐个比较次数超过这个值时才启动 Galloping mode ,根据 Galloping 的成功率,动态调整这个值。

其三,针对逆序的数据做特别优化。因为把逆序序列倒转过来是很简单的,O(n) 就可以完成,但用传统 merge sort 的方法成本要高得多。在预扫描 run 时,检测前两个元素的次序就可以用来猜测这个 run 是正序还是逆序的。注:如果是逆序的,需要对相同元素做额外一点处理保证 stable 。

其四,由于 mergesort 是二分分治,所以在元素数量不足 2^n 时,复杂度其实是向上补足 2 的整数幂。即处理 1023 个元素和处理 1024 个元素近似,而处理 513 个元素也和处理 1024 元素类似。所以,分片的数量比 2 的整数幂略小一点最合适。timsort/powersort 解决这个问题的方法是设定最小的 run size ,它根据 n 的大小在 32 到 64 之间动态调整。在中间找到一个数 m ,让 n/m 最接近 2 的整数幂。这只需要取 n 的最高 6 位再加 1 就可以了。对于最小的无序 run ,采用插入排序。