“主包你的数据结构已经入门了是时候开发原神了。”这句弹幕式调侃看似只是直播间的玩笑实际上戳中了很多开发者真实的状态数组、链表、栈、队列、树、图的概念都背过时间复杂度也能默写可是一旦离开课本面对一个具体的项目需求时还是不知道这些数据结构该往哪里放。这篇文章就用“原神”这个梗认真聊一件很落地的事数据结构入门之后怎么把它变成真正能跑起来的项目能力。我会以开发一个简化版开放世界游戏的核心系统为例用手写 C# 代码实现背包、任务依赖图、怪物刷新调度、A* 寻路四个模块每一块都会明确对应到一种数据结构并解释为什么选它、不选它的下场是什么。如果你正好学完了数据结构又苦于找不到练手场景这篇文章就是写给你的。1. 为什么“学完数据结构”和“能做项目”之间存在一条鸿沟数据结构教材通常会按知识点组织数组、链表、栈、队列、树、图、排序、查找、哈希表。每章都在讲“这种结构长什么样”“增删改查复杂度是多少”。这种方式能帮你建立知识体系却很难帮你建立“选型意识”。真实项目里的需求从来不是“请用哈希表插入一条数据”而是角色背包里上千种物品如何快速查找和排序任务线之间的前置关系怎么表示才能自动推出可接任务顺序地图上的怪物需要在不同时间点刷新怎样保证事件按时间顺序触发主角从一个点走到另一个点怎么绕过障碍物找到最短路径这些问题都有一个共同点摆在面前的不是“数据结构”而是原始、混杂、有约束的业务数据。你需要先抽象出数据之间的关系再决定用什么结构组织最后还要考虑性能和后续维护。游戏开发所以非常适合用来串联数据结构是因为它足够具象。你不会再问“树有什么用”而是直接看到场景管理里每个节点就是一个区域你不会再问“优先队列有什么用”而是直接看到怪物刷新事件被按时间排序的瞬间。换句话说数据结构入门解决的是“认识工具”的问题做项目解决的是“会用工具解决问题”的问题。这篇篇文章里我们贴着“原神”这样的开放世界游戏场景把学过的东西全部用一遍。2. 游戏开发中到底会用到哪些数据结构开放世界游戏看起来复杂核心系统拆开之后背后的数据结构并没有超出教材范围。下表是典型开放世界游戏中会大量使用的结构游戏系统核心数据结构解决的核心问题地图场景管理四叉树、网格、空间哈希确定哪些物体出现在视野范围减少碰撞和渲染计算角色/怪物实体池数组、对象池控制对象生成销毁开销避免 GC 抖动背包/道具系统哈希表 链表快速按 ID 查找物品同时维护槽位顺序任务系统有向无环图 拓扑排序表达任务前置依赖自动推导可接任务顺序寻路系统图 最小堆A* 算法在障碍地图上找最短路径战斗技能/状态机栈、队列、状态集合技能连招、Buff 生命周期、动作状态的切换消息/日志/网络包循环队列、阻塞队列解耦生产者和消费者按顺序处理数据抽卡/掉落数组 权重前缀和按概率随机获得物品排行榜跳表、堆维护大量玩家的实时排名这里面值得注意的一点是同一个业务系统往往不止用一种结构。比如背包系统既需要哈希表支持 O(1) 的按 ID 查询又需要链表或数组来维持展示顺序任务系统是图结构但真正跑“现在能接哪些任务”的时候又依赖队列做拓扑排序。所以学数据结构不能只背单一结构的 API更重要的是理解“数据量多大、查询多频繁、顺序重不重要”这三个问题。下面我们直接进入一个简化版项目看看这些结构到底怎么协作。3. 一个“简化原神”的项目框架设计我们要做的不是真的复刻米哈游那款大作而是摘出开放世界游戏中几个最典型、也最能考验数据结构功底的子系统背包系统物品注册、添加、移除、展示。任务系统多个任务之间存在前置依赖。怪物刷新不同怪物在指定时间刷新。寻路系统在网格地图上从一个点走到另一个点。为了让代码能直接在自己电脑上跑这里不依赖 Unity、Unreal 等游戏引擎而是用.NET 6 的控制台程序实现。这样你只要装了 .NET SDK 就能验证结果不需要额外安装任何大型软件。先建立工程dotnet new console -n GenshinLike cd GenshinLike然后按功能拆分文件。最终项目结构如下GenshinLike/ ├── GenshinLike.csproj ├── Program.cs # 入口 ├── InventorySystem.cs # 背包系统 ├── QuestGraph.cs # 任务依赖图 ├── MonsterSpawner.cs # 怪物刷新调度 └── AStarPathfinding.cs # A* 寻路每个文件只负责一个模块模块之间通过公开类和方法交互。这种组织方式本身就是工程实践的一部分数据结构是模块内部的实现细节对外只暴露业务含义清晰的方法。后续如果要换一种数据结构只要模块内部不改变 API调用方完全不用动。4. 环境准备与前置条件本文示例基于 C# 和 .NET。具体版本不需要卡得太死核心功能在 .NET 6、.NET 7、.NET 8 中都可以运行。建议使用 LTS 版本比如 .NET 6 或 .NET 8。检查本机环境dotnet --version如果还没有安装去 .NET 官方网站下载对应 SDK 安装即可。安装完成后进入刚才创建的GenshinLike目录。这里有一点需要提醒下面的示例会用到PriorityQueueTElement, TPriority它是.NET 6 才引入的集合类型。如果你用的是老旧的 .NET Framework这个类型不存在需要自己手写最小堆或者升级项目版本。从工程角度说能用标准库新特性就优先用但实际公司项目里还要考虑团队的 SDK 版本约束。5. 完整示例代码实现5.1 背包系统哈希表 列表维护槽位背包系统最常见的需求是按物品 ID 快速查询物品信息同时要按获取顺序展示背包。只用一个ListItem虽然简单但查找某个物品时要遍历物品多了性能就差了。更合理的设计是“双结构”一个Dictionaryint, Item保存物品静态信息一个ListItemSlot保存运行时数量槽位。名称GenshinLike/InventorySystem.cs的代码// 文件路径GenshinLike/InventorySystem.cs using System; using System.Collections.Generic; using System.Linq; namespace GenshinLike; public enum ItemType { Material, Weapon, Artifact } public class Item { public int Id { get; init; } public string Name { get; init; } public ItemType Type { get; init; } public int MaxStack { get; init; } } public class ItemSlot { public int ItemId { get; set; } public int Count { get; set; } } public class Inventory { private readonly Dictionaryint, Item _itemDict new(); private readonly ListItemSlot _slots new(); public void RegisterItem(Item item) { _itemDict[item.Id] item; } public bool AddItem(int itemId, int count) { if (!_itemDict.TryGetValue(itemId, out var item)) { Console.WriteLine($物品 {itemId} 未注册); return false; } var slot _slots.FirstOrDefault(s s.ItemId itemId); if (slot null) { _slots.Add(new ItemSlot { ItemId itemId, Count count }); } else { slot.Count count; } Console.WriteLine($获得 {item.Name} x{count}); return true; } public bool RemoveItem(int itemId, int count) { var slot _slots.FirstOrDefault(s s.ItemId itemId); if (slot null || slot.Count count) { return false; } slot.Count - count; if (slot.Count 0) { _slots.Remove(slot); } return true; } public void Print() { Console.WriteLine(当前背包); foreach (var slot in _slots) { var item _itemDict[slot.ItemId]; Console.WriteLine($- {item.Name} x{slot.Count}); } } }代码里值得注意的点Item的属性用了init创建后不可修改符合配置数据只读的习惯。AddItem先用TryGetValue检查物品是否已注册避免脏数据。_slots负责维持顺序_itemDict负责按 ID 快速查找物品描述。这里真正的坑在于“背包格子是否叠堆”。真实游戏里同一种物品会叠堆但格子数有上限需要维护Count MaxStack的逻辑。上面是最小演示版工程里还要加“检查 MaxStack”“分割堆叠”“排序物品”等逻辑。这些逻辑本质上还是在操作列表和字典数据结构选型并没有变化。5.2 怪物刷新调度优先队列怪物刷新可以抽象成“按时间顺序触发的事件集合”。如果用一个普通 List每次 Tick 都要遍历所有事件判断是否到时间复杂度很高。这里用PriorityQueue它会自动让最小触发时间的事件排在队首每次只需要检查队首事件。文件GenshinLike/MonsterSpawner.cs// 文件路径GenshinLike/MonsterSpawner.cs using System; using System.Collections.Generic; namespace GenshinLike; public class Monster { public int Id { get; init; } public string Name { get; init; } public int Level { get; init; } } public class SpawnEvent { public Monster Monster { get; init; } public int TriggerTime { get; init; } } public class MonsterSpawner { private readonly PriorityQueueSpawnEvent, int _queue new(); public void Schedule(Monster monster, int triggerTime) { _queue.Enqueue(new SpawnEvent { Monster monster, TriggerTime triggerTime }, triggerTime); } public void Tick(int currentSecond) { while (_queue.Count 0 _queue.Peek().TriggerTime currentSecond) { var evt _queue.Dequeue(); Console.WriteLine($[t{currentSecond}s] 刷新怪物{evt.Monster.Name} Lv.{evt.Monster.Level}); } } }PriorityQueueSpawnEvent, int的第一个泛型参数是元素类型第二个是优先级类型。这里直接用触发时间作为优先级时间越小的优先级越高。Peek()只查看队首不弹出只有满足触发时间条件时才Dequeue()。这种设计非常契合游戏主循环每一帧或每一秒调用一次Tick不需要扫描全部怪物时间复杂度为 O(log n)。如果用 List 存储并每次排序也能实现但插入和移除都要承担额外开销。数据量小的时候无所谓当地图上同时存在几千个待刷新事件时优先队列的优势就很明显了。5.3 任务依赖图邻接表 拓扑排序原神类的任务线通常存在严格的前置关系。例如“前往风龙废墟”必须先完成“迎风点火”“击败特瓦林”必须先完成“前往风龙废墟”。这种关系可以用有向图表示每个任务是一个节点A 指向 B 表示“A 是 B 的前置任务”。图的存储方式主要有邻接矩阵和邻接表。任务数量可能很多但每个任务的前置任务很少所以用Dictionaryint, Listint这种邻接表更节省空间。文件GenshinLike/QuestGraph.cs// 文件路径GenshinLike/QuestGraph.cs using System; using System.Collections.Generic; namespace GenshinLike; public class Quest { public int Id { get; init; } public string Name { get; init; } } public class QuestGraph { private readonly Dictionaryint, Quest _quests new(); private readonly Dictionaryint, Listint _adjacencies new(); public void AddQuest(Quest quest) { _quests[quest.Id] quest; _adjacencies[quest.Id] new Listint(); } public void AddDependency(int from, int to) { if (!_adjacencies.ContainsKey(from) || !_adjacencies.ContainsKey(to)) { throw new InvalidOperationException(任务节点未注册); } _adjacencies[from].Add(to); } public Listint TopologicalOrder() { var inDegree new Dictionaryint, int(); foreach (var id in _quests.Keys) { inDegree[id] 0; } foreach (var edges in _adjacencies.Values) { foreach (var to in edges) { inDegree[to]; } } var queue new Queueint(); foreach (var (id, degree) in inDegree) { if (degree 0) { queue.Enqueue(id); } } var result new Listint(); while (queue.Count 0) { var current queue.Dequeue(); result.Add(current); foreach (var next in _adjacencies[current]) { inDegree[next]--; if (inDegree[next] 0) { queue.Enqueue(next); } } } return result; } }TopologicalOrder返回一个任务列表列表中任何一个任务出现时它的所有前置任务都已经排在前面。这是一个标准的 Kahn 算法先计算每个节点的入度把入度为 0 的节点入队然后依次处理并更新相邻节点入度。如果任务图里存在循环依赖最终返回列表的长度会小于任务总数。使用时要判断if (order.Count ! questGraph.GetQuestCount()) { Console.WriteLine(任务依赖存在环请检查配置); }这里的环检测非常重要。真实项目的任务表经常由策划配置开发无法保证配置永远合法所以一定在加载时校验。5.4 A* 寻路图搜索 最小堆开放世界角色移动绕不开寻路。A* 是一种启发式搜索算法它在 Dijkstra 的基础上增加了“当前点到目标点的估计距离”从而更快找到目标。这里用网格地图演示0 代表可走1 代表障碍物。每个格子可以上下左右移动移动代价为 1。文件GenshinLike/AStarPathfinding.cs// 文件路径GenshinLike/AStarPathfinding.cs using System; using System.Collections.Generic; namespace GenshinLike; public class AStarPathfinding { private readonly int[,] _grid; private readonly int _width; private readonly int _height; public AStarPathfinding(int[,] grid) { _grid grid; _width grid.GetLength(0); _height grid.GetLength(1); } public List(int x, int y) FindPath((int x, int y) start, (int x, int y) end) { var open new PriorityQueue(int x, int y, int f), int(); var gScore new Dictionary(int, int), int(); var cameFrom new Dictionary(int, int), (int, int)(); open.Enqueue((start.x, start.y, Heuristic(start, end)), 0); gScore[(start.x, start.y)] 0; while (open.Count 0) { var current open.Dequeue(); int cx current.x; int cy current.y; if (cx end.x cy end.y) { return ReconstructPath(cameFrom, start, end); } foreach (var (nx, ny) in Neighbors(cx, cy)) { if (!IsWalkable(nx, ny)) { continue; } int tentativeG gScore.GetValueOrDefault((cx, cy)) 1; if (!gScore.ContainsKey((nx, ny)) || tentativeG gScore[(nx, ny)]) { cameFrom[(nx, ny)] (cx, cy); gScore[(nx, ny)] tentativeG; int f tentativeG Heuristic((nx, ny), end); open.Enqueue((nx, ny, f), f); } } } return new List(int x, int y)(); } private int Heuristic((int x, int y) a, (int x, int y) b) { return Math.Abs(a.x - b.x) Math.Abs(a.y - b.y); } private List(int x, int y) Neighbors(int x, int y) { var result new List(int x, int y)(); if (x 0) result.Add((x - 1, y)); if (x _width - 1) result.Add((x 1, y)); if (y 0) result.Add((x, y - 1)); if (y _height - 1) result.Add((x, y 1)); return result; } private bool IsWalkable(int x, int y) { return x 0 x _width y 0 y _height _grid[x, y] 0; } private List(int x, int y) ReconstructPath( Dictionary(int, int), (int, int) cameFrom, (int x, int y) start, (int x, int y) end) { var path new List(int x, int y)(); var current end; while (current ! start) { path.Add(current); current cameFrom[current]; } path.Add(start); path.Reverse(); return path; } }这里的open使用最小堆每次能高效取出 f 值最小的节点。gScore记录起点到每个节点的实际代价cameFrom记录路径前驱用于最后回溯路径。启发函数使用曼哈顿距离适合“只允许上下左右移动”的网格地图。如果你的游戏地图允许斜向移动启发函数就要改成欧几里得距离否则寻路结果可能不是最优路径。这是 A* 使用中最经典的调整项。6. 运行结果与效果验证现在我们把四个模块串到Program.cs中跑一个完整演示。文件GenshinLike/Program.cs// 文件路径GenshinLike/Program.cs using System; using System.Collections.Generic; using GenshinLike; // 1. 背包系统 var inventory new Inventory(); inventory.RegisterItem(new Item { Id 101, Name 摩拉, Type ItemType.Material, MaxStack 9999 }); inventory.RegisterItem(new Item { Id 102, Name 风车菊, Type ItemType.Material, MaxStack 99 }); inventory.AddItem(101, 500); inventory.AddItem(102, 3); inventory.AddItem(101, 200); inventory.RemoveItem(101, 100); inventory.Print(); Console.WriteLine(); // 2. 怪物刷新系统 var spawner new MonsterSpawner(); spawner.Schedule(new Monster { Id 1, Name 丘丘人, Level 5 }, 1); spawner.Schedule(new Monster { Id 2, Name 史莱姆, Level 3 }, 2); spawner.Schedule(new Monster { Id 3, Name 深渊法师, Level 10 }, 0); Console.WriteLine(怪物刷新调度); for (int t 0; t 2; t) { spawner.Tick(t); } Console.WriteLine(); // 3. 任务依赖图 var questGraph new QuestGraph(); questGraph.AddQuest(new Quest { Id 1, Name 迎风点火 }); questGraph.AddQuest(new Quest { Id 2, Name 前往风龙废墟 }); questGraph.AddQuest(new Quest { Id 3, Name 击败特瓦林 }); questGraph.AddQuest(new Quest { Id 4, Name 探查深渊教团 }); questGraph.AddDependency(1, 2); questGraph.AddDependency(2, 3); questGraph.AddDependency(1, 4); var order questGraph.TopologicalOrder(); Console.WriteLine(任务推荐顺序 string.Join( - , order)); Console.WriteLine(); // 4. A* 寻路 var grid new int[,] { { 0, 0, 0, 0, 0 }, { 0, 1, 1, 0, 0 }, { 0, 0, 0, 1, 0 }, { 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 0 } }; var pathfinder new AStarPathfinding(grid); var path pathfinder.FindPath((0, 0), (4, 4)); Console.WriteLine(A* 寻路结果); Console.WriteLine(string.Join( - , path));在项目目录执行dotnet run预期会看到类似下面的输出获得 摩拉 x500 获得 风车菊 x3 获得 摩拉 x200 当前背包 - 摩拉 x600 - 风车菊 x3 怪物刷新调度 [t0s] 刷新怪物深渊法师 Lv.10 [t1s] 刷新怪物丘丘人 Lv.5 [t2s] 刷新怪物史莱姆 Lv.3 任务推荐顺序1 - 2 - 4 - 3 A* 寻路结果 (0, 0) - (1, 0) - (2, 0) - (2, 1) - (2, 2) - (3, 2) - (4, 2) - (4, 3) - (4, 4)任务推荐顺序未必是唯一的只要满足先完成前置任务的条件即可。寻路结果只要是一串连续、不穿障碍物的格子坐标就说明 A* 逻辑正确。如果运行报错优先检查 SDK 版本是否支持PriorityQueue以及项目文件是否包含所有.cs文件。7. 数据结构实战中的常见问题与排查方法写纯数据结构题和写游戏系统最大的区别在于数据是动态的、有边界的还会出错。下面列几个实际项目中容易踩的坑。问题现象可能原因排查方式解决方案Dictionary 遍历顺序与添加顺序不一致Dictionary 底层是哈希表不保证顺序观察输出顺序与预期差异需要保序时使用 List 或 OrderedDictionary 配合维护老项目没有 PriorityQueue.NET Framework / 早期版本 SDK 不包含该类dotnet --version检查运行库版本升级 SDK或自实现最小堆任务图返回顺序数量不够图中有环导致部分任务入度永远不为 0打印 result.Count 与总任务数比较在加载阶段做环检测给出具体环路径A* 找不到路径返回空列表起点或终点是障碍物或终点被完全包围打印地图上一个点 IsWalkable 的值寻路前校验起点和终点合法性不合法时给出回退策略游戏实体频繁 new 导致 GC 卡顿怪物/掉落物大量创建销毁 class 对象使用 Profiler 查看 GC Alloc用对象池复用实体或改用 struct 存储纯数据背包物品数量错误添加和移除时没有检查堆叠上限/下限单测覆盖叠堆边界封装 Add 和 Remove统一校验 MaxStack 与 Count这些坑在教科书里很少出现但在真实开发中非常常见。尤其是“用 Dictionary 却期望它保持插入顺序”这是新手最容易犯的错误。哈希表的优势是查找快代价就是内部顺序由哈希值决定不能当列表用。8. 数据结构实战的最佳实践与工程建议从上面的代码可以提炼出一套适用性很强的实践方法。先确认数据规模再决定数据结构。如果背包最多只有 10 个格子用 List 遍历也没问题如果可能放 10000 件装备就必须考虑哈希表或索引结构。数据结构不是越复杂越好而是匹配真实规模。能用数组/连续内存解决就不要盲目上链表。现代 CPU 对连续内存的预读非常友好。链表虽然插入删除是 O(1)但每个节点分布在堆上遍历时缓存命中率低。游戏里的对象池、实体列表经常用数组。哈希表的键不要用可变对象。如果用一个自定义类作为DictionaryMyClass, T的 key而它的GetHashCode依赖某个可变字段一旦字段被修改查询就会失败。要么只读属性要么用 ID 这类稳定值。图结构一定要在初始化阶段检测环。任务图、技能图、依赖关系图只要由人配置就存在环的可能。不要等运行时死循环了才发现。本文的拓扑排序可以直接扩展为环检测工具。优先队列适合所有“按优先级/时间取任务”的场景。除了怪物刷新技能冷却、战斗事件调度、网络消息重传甚至工作流引擎都会用到类似结构。掌握PriorityQueue之后很多定时调度代码都可以简化。A的改进空间很大。* 本文的网格地图只是最基础版本。真实游戏可能使用 Navigation Mesh或者对地图做分层分区管理。不要把算法封装得太死应该把“代价计算”“邻居获取”抽象成接口这样后续换地图类型不用重写整套寻路。生产项目要配合 Profiler 做验证。数据结构选型不能只靠理论分析要在真实数据量和真实设备上跑一遍。Unity 里的 Profiler、.NET 的 dotnet-trace、以及各种内存分析工具都能帮你确认瓶颈到底在查找、排序还是 GC。9. 总结与下一步数据结构入门之后真正的分水岭不是会不会背复杂度和定义而是能不能在真实项目里识别出“这里需要一个哈希表”“那里应该用优先队列”“任务系统本质上是一张图”。这篇文章通过一个简化版开放世界游戏项目把背包、怪物刷新、任务依赖、寻路四个系统分别落到哈希表列表、优先队列、邻接表拓扑排序、A* 四类经典数据结构上。你可以先复制代码把每个模块跑起来再试着改一改比如给背包增加格子容量上限或者给任务图加一个环检测方法再或者把 A* 的启发函数改成欧几里得距离看看路径效果有什么变化。这些改动都不大但能让你真正理解“数据结构是服务于需求的”。如果想继续深入下一步可以研究 Unity DOTS/ECS 里的结构 SoA 设计、四叉树/空间哈希在大世界场景中的用法、以及网络同步时环形缓冲区的应用。这些方向都是把数据结构从“会做”推向“会优化”的必经之路。现在先打开编辑器从背包和地图模块开始吧。 用C#手写原神核心系统：数据结构实战指南
“主包你的数据结构已经入门了是时候开发原神了。”这句弹幕式调侃看似只是直播间的玩笑实际上戳中了很多开发者真实的状态数组、链表、栈、队列、树、图的概念都背过时间复杂度也能默写可是一旦离开课本面对一个具体的项目需求时还是不知道这些数据结构该往哪里放。这篇文章就用“原神”这个梗认真聊一件很落地的事数据结构入门之后怎么把它变成真正能跑起来的项目能力。我会以开发一个简化版开放世界游戏的核心系统为例用手写 C# 代码实现背包、任务依赖图、怪物刷新调度、A* 寻路四个模块每一块都会明确对应到一种数据结构并解释为什么选它、不选它的下场是什么。如果你正好学完了数据结构又苦于找不到练手场景这篇文章就是写给你的。1. 为什么“学完数据结构”和“能做项目”之间存在一条鸿沟数据结构教材通常会按知识点组织数组、链表、栈、队列、树、图、排序、查找、哈希表。每章都在讲“这种结构长什么样”“增删改查复杂度是多少”。这种方式能帮你建立知识体系却很难帮你建立“选型意识”。真实项目里的需求从来不是“请用哈希表插入一条数据”而是角色背包里上千种物品如何快速查找和排序任务线之间的前置关系怎么表示才能自动推出可接任务顺序地图上的怪物需要在不同时间点刷新怎样保证事件按时间顺序触发主角从一个点走到另一个点怎么绕过障碍物找到最短路径这些问题都有一个共同点摆在面前的不是“数据结构”而是原始、混杂、有约束的业务数据。你需要先抽象出数据之间的关系再决定用什么结构组织最后还要考虑性能和后续维护。游戏开发所以非常适合用来串联数据结构是因为它足够具象。你不会再问“树有什么用”而是直接看到场景管理里每个节点就是一个区域你不会再问“优先队列有什么用”而是直接看到怪物刷新事件被按时间排序的瞬间。换句话说数据结构入门解决的是“认识工具”的问题做项目解决的是“会用工具解决问题”的问题。这篇篇文章里我们贴着“原神”这样的开放世界游戏场景把学过的东西全部用一遍。2. 游戏开发中到底会用到哪些数据结构开放世界游戏看起来复杂核心系统拆开之后背后的数据结构并没有超出教材范围。下表是典型开放世界游戏中会大量使用的结构游戏系统核心数据结构解决的核心问题地图场景管理四叉树、网格、空间哈希确定哪些物体出现在视野范围减少碰撞和渲染计算角色/怪物实体池数组、对象池控制对象生成销毁开销避免 GC 抖动背包/道具系统哈希表 链表快速按 ID 查找物品同时维护槽位顺序任务系统有向无环图 拓扑排序表达任务前置依赖自动推导可接任务顺序寻路系统图 最小堆A* 算法在障碍地图上找最短路径战斗技能/状态机栈、队列、状态集合技能连招、Buff 生命周期、动作状态的切换消息/日志/网络包循环队列、阻塞队列解耦生产者和消费者按顺序处理数据抽卡/掉落数组 权重前缀和按概率随机获得物品排行榜跳表、堆维护大量玩家的实时排名这里面值得注意的一点是同一个业务系统往往不止用一种结构。比如背包系统既需要哈希表支持 O(1) 的按 ID 查询又需要链表或数组来维持展示顺序任务系统是图结构但真正跑“现在能接哪些任务”的时候又依赖队列做拓扑排序。所以学数据结构不能只背单一结构的 API更重要的是理解“数据量多大、查询多频繁、顺序重不重要”这三个问题。下面我们直接进入一个简化版项目看看这些结构到底怎么协作。3. 一个“简化原神”的项目框架设计我们要做的不是真的复刻米哈游那款大作而是摘出开放世界游戏中几个最典型、也最能考验数据结构功底的子系统背包系统物品注册、添加、移除、展示。任务系统多个任务之间存在前置依赖。怪物刷新不同怪物在指定时间刷新。寻路系统在网格地图上从一个点走到另一个点。为了让代码能直接在自己电脑上跑这里不依赖 Unity、Unreal 等游戏引擎而是用.NET 6 的控制台程序实现。这样你只要装了 .NET SDK 就能验证结果不需要额外安装任何大型软件。先建立工程dotnet new console -n GenshinLike cd GenshinLike然后按功能拆分文件。最终项目结构如下GenshinLike/ ├── GenshinLike.csproj ├── Program.cs # 入口 ├── InventorySystem.cs # 背包系统 ├── QuestGraph.cs # 任务依赖图 ├── MonsterSpawner.cs # 怪物刷新调度 └── AStarPathfinding.cs # A* 寻路每个文件只负责一个模块模块之间通过公开类和方法交互。这种组织方式本身就是工程实践的一部分数据结构是模块内部的实现细节对外只暴露业务含义清晰的方法。后续如果要换一种数据结构只要模块内部不改变 API调用方完全不用动。4. 环境准备与前置条件本文示例基于 C# 和 .NET。具体版本不需要卡得太死核心功能在 .NET 6、.NET 7、.NET 8 中都可以运行。建议使用 LTS 版本比如 .NET 6 或 .NET 8。检查本机环境dotnet --version如果还没有安装去 .NET 官方网站下载对应 SDK 安装即可。安装完成后进入刚才创建的GenshinLike目录。这里有一点需要提醒下面的示例会用到PriorityQueueTElement, TPriority它是.NET 6 才引入的集合类型。如果你用的是老旧的 .NET Framework这个类型不存在需要自己手写最小堆或者升级项目版本。从工程角度说能用标准库新特性就优先用但实际公司项目里还要考虑团队的 SDK 版本约束。5. 完整示例代码实现5.1 背包系统哈希表 列表维护槽位背包系统最常见的需求是按物品 ID 快速查询物品信息同时要按获取顺序展示背包。只用一个ListItem虽然简单但查找某个物品时要遍历物品多了性能就差了。更合理的设计是“双结构”一个Dictionaryint, Item保存物品静态信息一个ListItemSlot保存运行时数量槽位。名称GenshinLike/InventorySystem.cs的代码// 文件路径GenshinLike/InventorySystem.cs using System; using System.Collections.Generic; using System.Linq; namespace GenshinLike; public enum ItemType { Material, Weapon, Artifact } public class Item { public int Id { get; init; } public string Name { get; init; } public ItemType Type { get; init; } public int MaxStack { get; init; } } public class ItemSlot { public int ItemId { get; set; } public int Count { get; set; } } public class Inventory { private readonly Dictionaryint, Item _itemDict new(); private readonly ListItemSlot _slots new(); public void RegisterItem(Item item) { _itemDict[item.Id] item; } public bool AddItem(int itemId, int count) { if (!_itemDict.TryGetValue(itemId, out var item)) { Console.WriteLine($物品 {itemId} 未注册); return false; } var slot _slots.FirstOrDefault(s s.ItemId itemId); if (slot null) { _slots.Add(new ItemSlot { ItemId itemId, Count count }); } else { slot.Count count; } Console.WriteLine($获得 {item.Name} x{count}); return true; } public bool RemoveItem(int itemId, int count) { var slot _slots.FirstOrDefault(s s.ItemId itemId); if (slot null || slot.Count count) { return false; } slot.Count - count; if (slot.Count 0) { _slots.Remove(slot); } return true; } public void Print() { Console.WriteLine(当前背包); foreach (var slot in _slots) { var item _itemDict[slot.ItemId]; Console.WriteLine($- {item.Name} x{slot.Count}); } } }代码里值得注意的点Item的属性用了init创建后不可修改符合配置数据只读的习惯。AddItem先用TryGetValue检查物品是否已注册避免脏数据。_slots负责维持顺序_itemDict负责按 ID 快速查找物品描述。这里真正的坑在于“背包格子是否叠堆”。真实游戏里同一种物品会叠堆但格子数有上限需要维护Count MaxStack的逻辑。上面是最小演示版工程里还要加“检查 MaxStack”“分割堆叠”“排序物品”等逻辑。这些逻辑本质上还是在操作列表和字典数据结构选型并没有变化。5.2 怪物刷新调度优先队列怪物刷新可以抽象成“按时间顺序触发的事件集合”。如果用一个普通 List每次 Tick 都要遍历所有事件判断是否到时间复杂度很高。这里用PriorityQueue它会自动让最小触发时间的事件排在队首每次只需要检查队首事件。文件GenshinLike/MonsterSpawner.cs// 文件路径GenshinLike/MonsterSpawner.cs using System; using System.Collections.Generic; namespace GenshinLike; public class Monster { public int Id { get; init; } public string Name { get; init; } public int Level { get; init; } } public class SpawnEvent { public Monster Monster { get; init; } public int TriggerTime { get; init; } } public class MonsterSpawner { private readonly PriorityQueueSpawnEvent, int _queue new(); public void Schedule(Monster monster, int triggerTime) { _queue.Enqueue(new SpawnEvent { Monster monster, TriggerTime triggerTime }, triggerTime); } public void Tick(int currentSecond) { while (_queue.Count 0 _queue.Peek().TriggerTime currentSecond) { var evt _queue.Dequeue(); Console.WriteLine($[t{currentSecond}s] 刷新怪物{evt.Monster.Name} Lv.{evt.Monster.Level}); } } }PriorityQueueSpawnEvent, int的第一个泛型参数是元素类型第二个是优先级类型。这里直接用触发时间作为优先级时间越小的优先级越高。Peek()只查看队首不弹出只有满足触发时间条件时才Dequeue()。这种设计非常契合游戏主循环每一帧或每一秒调用一次Tick不需要扫描全部怪物时间复杂度为 O(log n)。如果用 List 存储并每次排序也能实现但插入和移除都要承担额外开销。数据量小的时候无所谓当地图上同时存在几千个待刷新事件时优先队列的优势就很明显了。5.3 任务依赖图邻接表 拓扑排序原神类的任务线通常存在严格的前置关系。例如“前往风龙废墟”必须先完成“迎风点火”“击败特瓦林”必须先完成“前往风龙废墟”。这种关系可以用有向图表示每个任务是一个节点A 指向 B 表示“A 是 B 的前置任务”。图的存储方式主要有邻接矩阵和邻接表。任务数量可能很多但每个任务的前置任务很少所以用Dictionaryint, Listint这种邻接表更节省空间。文件GenshinLike/QuestGraph.cs// 文件路径GenshinLike/QuestGraph.cs using System; using System.Collections.Generic; namespace GenshinLike; public class Quest { public int Id { get; init; } public string Name { get; init; } } public class QuestGraph { private readonly Dictionaryint, Quest _quests new(); private readonly Dictionaryint, Listint _adjacencies new(); public void AddQuest(Quest quest) { _quests[quest.Id] quest; _adjacencies[quest.Id] new Listint(); } public void AddDependency(int from, int to) { if (!_adjacencies.ContainsKey(from) || !_adjacencies.ContainsKey(to)) { throw new InvalidOperationException(任务节点未注册); } _adjacencies[from].Add(to); } public Listint TopologicalOrder() { var inDegree new Dictionaryint, int(); foreach (var id in _quests.Keys) { inDegree[id] 0; } foreach (var edges in _adjacencies.Values) { foreach (var to in edges) { inDegree[to]; } } var queue new Queueint(); foreach (var (id, degree) in inDegree) { if (degree 0) { queue.Enqueue(id); } } var result new Listint(); while (queue.Count 0) { var current queue.Dequeue(); result.Add(current); foreach (var next in _adjacencies[current]) { inDegree[next]--; if (inDegree[next] 0) { queue.Enqueue(next); } } } return result; } }TopologicalOrder返回一个任务列表列表中任何一个任务出现时它的所有前置任务都已经排在前面。这是一个标准的 Kahn 算法先计算每个节点的入度把入度为 0 的节点入队然后依次处理并更新相邻节点入度。如果任务图里存在循环依赖最终返回列表的长度会小于任务总数。使用时要判断if (order.Count ! questGraph.GetQuestCount()) { Console.WriteLine(任务依赖存在环请检查配置); }这里的环检测非常重要。真实项目的任务表经常由策划配置开发无法保证配置永远合法所以一定在加载时校验。5.4 A* 寻路图搜索 最小堆开放世界角色移动绕不开寻路。A* 是一种启发式搜索算法它在 Dijkstra 的基础上增加了“当前点到目标点的估计距离”从而更快找到目标。这里用网格地图演示0 代表可走1 代表障碍物。每个格子可以上下左右移动移动代价为 1。文件GenshinLike/AStarPathfinding.cs// 文件路径GenshinLike/AStarPathfinding.cs using System; using System.Collections.Generic; namespace GenshinLike; public class AStarPathfinding { private readonly int[,] _grid; private readonly int _width; private readonly int _height; public AStarPathfinding(int[,] grid) { _grid grid; _width grid.GetLength(0); _height grid.GetLength(1); } public List(int x, int y) FindPath((int x, int y) start, (int x, int y) end) { var open new PriorityQueue(int x, int y, int f), int(); var gScore new Dictionary(int, int), int(); var cameFrom new Dictionary(int, int), (int, int)(); open.Enqueue((start.x, start.y, Heuristic(start, end)), 0); gScore[(start.x, start.y)] 0; while (open.Count 0) { var current open.Dequeue(); int cx current.x; int cy current.y; if (cx end.x cy end.y) { return ReconstructPath(cameFrom, start, end); } foreach (var (nx, ny) in Neighbors(cx, cy)) { if (!IsWalkable(nx, ny)) { continue; } int tentativeG gScore.GetValueOrDefault((cx, cy)) 1; if (!gScore.ContainsKey((nx, ny)) || tentativeG gScore[(nx, ny)]) { cameFrom[(nx, ny)] (cx, cy); gScore[(nx, ny)] tentativeG; int f tentativeG Heuristic((nx, ny), end); open.Enqueue((nx, ny, f), f); } } } return new List(int x, int y)(); } private int Heuristic((int x, int y) a, (int x, int y) b) { return Math.Abs(a.x - b.x) Math.Abs(a.y - b.y); } private List(int x, int y) Neighbors(int x, int y) { var result new List(int x, int y)(); if (x 0) result.Add((x - 1, y)); if (x _width - 1) result.Add((x 1, y)); if (y 0) result.Add((x, y - 1)); if (y _height - 1) result.Add((x, y 1)); return result; } private bool IsWalkable(int x, int y) { return x 0 x _width y 0 y _height _grid[x, y] 0; } private List(int x, int y) ReconstructPath( Dictionary(int, int), (int, int) cameFrom, (int x, int y) start, (int x, int y) end) { var path new List(int x, int y)(); var current end; while (current ! start) { path.Add(current); current cameFrom[current]; } path.Add(start); path.Reverse(); return path; } }这里的open使用最小堆每次能高效取出 f 值最小的节点。gScore记录起点到每个节点的实际代价cameFrom记录路径前驱用于最后回溯路径。启发函数使用曼哈顿距离适合“只允许上下左右移动”的网格地图。如果你的游戏地图允许斜向移动启发函数就要改成欧几里得距离否则寻路结果可能不是最优路径。这是 A* 使用中最经典的调整项。6. 运行结果与效果验证现在我们把四个模块串到Program.cs中跑一个完整演示。文件GenshinLike/Program.cs// 文件路径GenshinLike/Program.cs using System; using System.Collections.Generic; using GenshinLike; // 1. 背包系统 var inventory new Inventory(); inventory.RegisterItem(new Item { Id 101, Name 摩拉, Type ItemType.Material, MaxStack 9999 }); inventory.RegisterItem(new Item { Id 102, Name 风车菊, Type ItemType.Material, MaxStack 99 }); inventory.AddItem(101, 500); inventory.AddItem(102, 3); inventory.AddItem(101, 200); inventory.RemoveItem(101, 100); inventory.Print(); Console.WriteLine(); // 2. 怪物刷新系统 var spawner new MonsterSpawner(); spawner.Schedule(new Monster { Id 1, Name 丘丘人, Level 5 }, 1); spawner.Schedule(new Monster { Id 2, Name 史莱姆, Level 3 }, 2); spawner.Schedule(new Monster { Id 3, Name 深渊法师, Level 10 }, 0); Console.WriteLine(怪物刷新调度); for (int t 0; t 2; t) { spawner.Tick(t); } Console.WriteLine(); // 3. 任务依赖图 var questGraph new QuestGraph(); questGraph.AddQuest(new Quest { Id 1, Name 迎风点火 }); questGraph.AddQuest(new Quest { Id 2, Name 前往风龙废墟 }); questGraph.AddQuest(new Quest { Id 3, Name 击败特瓦林 }); questGraph.AddQuest(new Quest { Id 4, Name 探查深渊教团 }); questGraph.AddDependency(1, 2); questGraph.AddDependency(2, 3); questGraph.AddDependency(1, 4); var order questGraph.TopologicalOrder(); Console.WriteLine(任务推荐顺序 string.Join( - , order)); Console.WriteLine(); // 4. A* 寻路 var grid new int[,] { { 0, 0, 0, 0, 0 }, { 0, 1, 1, 0, 0 }, { 0, 0, 0, 1, 0 }, { 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 0 } }; var pathfinder new AStarPathfinding(grid); var path pathfinder.FindPath((0, 0), (4, 4)); Console.WriteLine(A* 寻路结果); Console.WriteLine(string.Join( - , path));在项目目录执行dotnet run预期会看到类似下面的输出获得 摩拉 x500 获得 风车菊 x3 获得 摩拉 x200 当前背包 - 摩拉 x600 - 风车菊 x3 怪物刷新调度 [t0s] 刷新怪物深渊法师 Lv.10 [t1s] 刷新怪物丘丘人 Lv.5 [t2s] 刷新怪物史莱姆 Lv.3 任务推荐顺序1 - 2 - 4 - 3 A* 寻路结果 (0, 0) - (1, 0) - (2, 0) - (2, 1) - (2, 2) - (3, 2) - (4, 2) - (4, 3) - (4, 4)任务推荐顺序未必是唯一的只要满足先完成前置任务的条件即可。寻路结果只要是一串连续、不穿障碍物的格子坐标就说明 A* 逻辑正确。如果运行报错优先检查 SDK 版本是否支持PriorityQueue以及项目文件是否包含所有.cs文件。7. 数据结构实战中的常见问题与排查方法写纯数据结构题和写游戏系统最大的区别在于数据是动态的、有边界的还会出错。下面列几个实际项目中容易踩的坑。问题现象可能原因排查方式解决方案Dictionary 遍历顺序与添加顺序不一致Dictionary 底层是哈希表不保证顺序观察输出顺序与预期差异需要保序时使用 List 或 OrderedDictionary 配合维护老项目没有 PriorityQueue.NET Framework / 早期版本 SDK 不包含该类dotnet --version检查运行库版本升级 SDK或自实现最小堆任务图返回顺序数量不够图中有环导致部分任务入度永远不为 0打印 result.Count 与总任务数比较在加载阶段做环检测给出具体环路径A* 找不到路径返回空列表起点或终点是障碍物或终点被完全包围打印地图上一个点 IsWalkable 的值寻路前校验起点和终点合法性不合法时给出回退策略游戏实体频繁 new 导致 GC 卡顿怪物/掉落物大量创建销毁 class 对象使用 Profiler 查看 GC Alloc用对象池复用实体或改用 struct 存储纯数据背包物品数量错误添加和移除时没有检查堆叠上限/下限单测覆盖叠堆边界封装 Add 和 Remove统一校验 MaxStack 与 Count这些坑在教科书里很少出现但在真实开发中非常常见。尤其是“用 Dictionary 却期望它保持插入顺序”这是新手最容易犯的错误。哈希表的优势是查找快代价就是内部顺序由哈希值决定不能当列表用。8. 数据结构实战的最佳实践与工程建议从上面的代码可以提炼出一套适用性很强的实践方法。先确认数据规模再决定数据结构。如果背包最多只有 10 个格子用 List 遍历也没问题如果可能放 10000 件装备就必须考虑哈希表或索引结构。数据结构不是越复杂越好而是匹配真实规模。能用数组/连续内存解决就不要盲目上链表。现代 CPU 对连续内存的预读非常友好。链表虽然插入删除是 O(1)但每个节点分布在堆上遍历时缓存命中率低。游戏里的对象池、实体列表经常用数组。哈希表的键不要用可变对象。如果用一个自定义类作为DictionaryMyClass, T的 key而它的GetHashCode依赖某个可变字段一旦字段被修改查询就会失败。要么只读属性要么用 ID 这类稳定值。图结构一定要在初始化阶段检测环。任务图、技能图、依赖关系图只要由人配置就存在环的可能。不要等运行时死循环了才发现。本文的拓扑排序可以直接扩展为环检测工具。优先队列适合所有“按优先级/时间取任务”的场景。除了怪物刷新技能冷却、战斗事件调度、网络消息重传甚至工作流引擎都会用到类似结构。掌握PriorityQueue之后很多定时调度代码都可以简化。A的改进空间很大。* 本文的网格地图只是最基础版本。真实游戏可能使用 Navigation Mesh或者对地图做分层分区管理。不要把算法封装得太死应该把“代价计算”“邻居获取”抽象成接口这样后续换地图类型不用重写整套寻路。生产项目要配合 Profiler 做验证。数据结构选型不能只靠理论分析要在真实数据量和真实设备上跑一遍。Unity 里的 Profiler、.NET 的 dotnet-trace、以及各种内存分析工具都能帮你确认瓶颈到底在查找、排序还是 GC。9. 总结与下一步数据结构入门之后真正的分水岭不是会不会背复杂度和定义而是能不能在真实项目里识别出“这里需要一个哈希表”“那里应该用优先队列”“任务系统本质上是一张图”。这篇文章通过一个简化版开放世界游戏项目把背包、怪物刷新、任务依赖、寻路四个系统分别落到哈希表列表、优先队列、邻接表拓扑排序、A* 四类经典数据结构上。你可以先复制代码把每个模块跑起来再试着改一改比如给背包增加格子容量上限或者给任务图加一个环检测方法再或者把 A* 的启发函数改成欧几里得距离看看路径效果有什么变化。这些改动都不大但能让你真正理解“数据结构是服务于需求的”。如果想继续深入下一步可以研究 Unity DOTS/ECS 里的结构 SoA 设计、四叉树/空间哈希在大世界场景中的用法、以及网络同步时环形缓冲区的应用。这些方向都是把数据结构从“会做”推向“会优化”的必经之路。现在先打开编辑器从背包和地图模块开始吧。