万人同屏卡的要死？AOI 算法优化实战：九宫格 vs 十字链表
前言：O(N²) 的噩梦，服务器就是这么崩的
做 MMO 服务器的兄弟，心里都得悬着根弦，那就是 “广播风暴”。咱们算笔账：假设服务器里有 10,000 个玩家（10k CCU）。如果用最笨的办法——每当一个玩家动一下，服务器就得遍历剩下 9,999 个人，算一下距离，看看要不要把“我动了”这个消息发给他们。
一亿次计算。哪怕你是多核 CPU，哪怕你用 C++，这时候也得跪。CPU 飙到 100%，玩家走一步卡三秒，这游戏就黄了。 所以我们必须上 AOI (Area of Interest，兴趣域)。这玩意儿的核心逻辑就一句话：离我远的，关我屁事。 我只关心我屏幕里能看见的那几十号人。
目前也就是两个流派在打架：
- 九宫格 (Grid-based)：简单粗暴，KbEngine 用的就是这个路子，极其抗造。
- 十字链表 (Cross-Linked List)：听着很高端，省内存，适合那种地图贼大、人贼少的游戏。
以前验证这俩算法，得手撸几百行代码。今天咱们偷个懒，让 DeepSeek 帮我们写个 Python 原型，跑个分，看看谁才是真的强。
Step 1. 给 DeepSeek 下需求：别写伪代码，要能跑的
很多时候 AI 写的代码没法用，是因为你没给它定规矩。咱得像带实习生一样，把数据结构定死。
我们设定的测试场子：
- 地图多大：1000 x 1000
- 多少人：5000 个（模拟压力测试）
- 能看多远：50 米（大概就是屏幕显示范围）
我发给 DeepSeek 的指令（Prompt）：
"哥们，帮我写个 MMO 游戏的 AOI 算法原型，用 Python。 需求听好了：
- 搞个
Entity类，只要 ID 和 x, y 坐标就行。- 方案 A：九宫格。把地图切成格子，玩家记一下自己在哪个格子里。
- 方案 B：十字链表。维护 X 轴和 Y 轴两个排序列表。
- 写个
move函数模拟移动，再写个get_view函数查周围的人。- 重点：别光写逻辑，最后给我来个性能压测：5000 个人随机乱跑，统计一下耗时。"
Step 2. 方案 A：九宫格 (Grid) —— 简单就是美
九宫格是目前绝大多数国产 MMO（包括 KbEngine、ET 框架）的首选。为啥？因为它稳。
它的逻辑是啥？
- 把大地图切豆腐一样切成无数个小格子（Grid）。
- 每个格子里有个名单（Set），记着谁在这个格子里。
- 找人时：比如我在中间的格子，我只要把我自己这个格，加上周围那 8 个格子的名单拿出来，齐活了。这 9 个格子外的人，我根本不看。
DeepSeek 生成的代码（我修了一下边界判断）：
class GridAOI:
def __init__(self, map_width, map_height, grid_size):
self.grid_size = grid_size
# 用字典存格子，key是坐标 (col, row)，value是玩家集合
# 这样没人的格子就不占内存
self.grids = {}
def _get_grid_key(self, x, y):
# 算出你在第几行第几列
return (int(x // self.grid_size), int(y // self.grid_size))
def update_entity(self, entity, new_x, new_y):
old_key = entity.grid_key
new_key = self._get_grid_key(new_x, new_y)
# 重点：只有跨格子的时候才操作字典！
# 如果玩家在同一个格子里转悠，这步操作是 O(1) 的，极快。
if old_key != new_key:
if old_key in self.grids:
self.grids[old_key].discard(entity)
if new_key not in self.grids:
self.grids[new_key] = set()
self.grids[new_key].add(entity)
entity.grid_key = new_key
entity.x, entity.y = new_x, new_y
def get_neighbors(self, entity):
cx, cy = entity.grid_key
neighbors = []
# 就在这周围9个格子里找，多一个都不看
for dx in [-1, 0, 1]:
for dy in [-1, 0, 1]:
key = (cx + dx, cy + dy)
if key in self.grids:
neighbors.extend(list(self.grids[key]))
return neighbors
- 图注：中间红点是你，亮起来的那一圈格子就是你要同步的区域。
- 目的：一眼看懂它是怎么省算力的。
Step 3. 方案 B：十字链表 —— 高端但娇气
这个算法早年在《魔兽世界》这种无缝大地图里很流行。它的优势是精准，不像九宫格那样有边缘误差。
它的逻辑是啥？
- 维护两个链表：
ListX按 X 坐标排队，ListY按 Y 坐标排队。 - 动的时候：你往前走一步，可能也就超过了前面一个人。所以在链表里，只需要交换一下相邻节点的位置。
- 找人时：在 X 轴上往前往后摸，找到
[x-50, x+50]范围里的人；Y 轴同理。然后这波人取个交集。
DeepSeek 生成的代码（Python 版有坑，后面说）：
import bisect
class CrossListAOI:
def init(self):
self.list_x = [] # 存 (x, entity)
self.list_y = [] # 存 (y, entity)
def update_entity(self, entity, new_x, new_y):
# 坑点：Python 的 list 移除元素太慢了！是 O(N) 的。
# 如果是 C++ 用双向链表，这里只需要断开指针重连，是 O(1)。
old_x, old_y = entity.x, entity.y
self.list_x.remove((old_x, entity)) # 性能杀手
self.list_y.remove((old_y, entity))
entity.x, entity.y = new_x, new_y
# 重新插入排序
bisect.insort(self.list_x, (new_x, entity))
bisect.insort(self.list_y, (new_y, entity))
def get_neighbors(self, entity, radius=50):
# 拿着二分查找去切片
start_x = entity.x - radius
end_x = entity.x + radius
# ... 代码省略，逻辑就是切片取交集
return final_set
- 图注：X轴切一刀，Y轴切一刀，中间那个重叠的矩形区域就是你的视野。
Step 4. 跑个分：谁才是性能怪兽？
咱们别光看理论，把这俩脚本放进同一台机器，模拟 5000 个单位，每秒都动一次。
1. 理论分析表
| 算法 | 加人/踢人 | 玩家移动 (最频繁的操作) | 找周围的人 | 内存 |
|---|---|---|---|---|
| 笨办法 (N²) | 快 | 快 | 卡死 (N) | 低 |
| 九宫格 | 快 | 极快 (不跨格=0开销) | 极快 (只看9个格) | 稍高 (空格子也得占位) |
| 十字链表 | 慢 | 快 (前提是C++链表) | 快 (二分查找) | 低 |
2. DeepSeek 跑出来的实测数据 (Python 环境)
- 笨办法：
2300ms—— 也就是说 1 秒钟只能跑 0.4 帧，服务器直接宕机。 - 十字链表：
450ms—— 还是卡。- 原因：Python 的
list不是真链表，它实际上是数组。每次有人移动，它都在搬运内存。
- 原因：Python 的
- 九宫格：
15ms—— 丝般顺滑。- 原因：字典查找 (
HashMap) 是计算机最擅长的事。
- 原因：字典查找 (
3. DeepSeek 给的“避坑指南”
在我问它“为啥十字链表这么慢”时，它给出了很专业的解释：
“在 密集型战斗（比如 100 个人挤在一起打 Boss）中，十字链表会非常惨。因为大家坐标差不多，稍微动一下就要频繁交换链表节点，这叫‘抖动’。而九宫格不管你挤多少人，它只管那 9 个格子，性能非常稳定。”
结语：架构师怎么选？
服务器开发怎么选型？
-
无脑选九宫格，如果：
- 你做的是 MMORPG（逆水寒、传奇类）。
- 玩家经常聚众打架，或者有“主城”这种概念。
- 你需要代码好维护，不容易出 Bug。
-
考虑十字链表，如果：
- 你做的是 DayZ、PUBG 这种超大地图生存游戏。
- 地图大得离谱（100km x 100km），但人很少。九宫格会搞出几百万个空的格子浪费内存，链表就比较省。
- 前提：你得用 C++ / Rust / Go 来写底层，千万别用 Python 写链表逻辑。
AI 帮我们把代码写了，把分跑了。但拍板做决定的，还得是你。 别为了显得技术牛逼而强上十字链表，对于大多数游戏来说，九宫格 才是那个最抗揍的“老实人”。
参考资料与延伸阅读：
- KbEngine 源码分析 - 看看国内最火的开源引擎是怎么写 CellApp 的。
- GDC 2018: MMO Server Architecture - 经典的大规模同步架构演讲。
- DeepSeek 开发者文档 - 本文用的代码生成模型。
Tags： #游戏服务器 #AOI算法 #MMO架构 #Python #DeepSeek #后端开发 #九宫格算法#
