定时器的实现:从逐帧计时到最小堆与时间轮

2230 字
11 分钟
定时器的实现:从逐帧计时到最小堆与时间轮

一、需求#

定时器在游戏中无处不在:

  • 延迟执行:3 秒后刷新怪物;
  • 重复执行:每秒恢复 1 点体力,每 0.5 秒造成一次持续伤害;
  • 倒计时:技能冷却、Buff 持续时间、活动剩余时间;
  • 超时:网络请求 10 秒没有响应就重试。

需要支持:添加、取消、暂停;回调中可以再添加新的定时器;数量从几个到成千上万(服务器上更多)。

二、基础做法#

做法实现问题
各自在 Update 中计时每个对象维护自己的计时变量,每帧减去 deltaTime逻辑分散;对象多时 Update 调用本身就有开销(见 减少 Update 的数量)
协程 / 异步yield return new WaitForSeconds(3),或 await UniTask.Delay(3000)简单方便;取消需要额外处理;大量使用时有分配(见 Unity 异步编程)
统一管理器 + 列表所有定时器放在一个列表中,每帧遍历,到时间的触发集中管理了,但每帧都要检查所有定时器,O(n)

数量不多(几十个)时,统一管理器 + 列表完全够用。数量很大时,问题在于每帧检查了大量还远没到时间的定时器。下面两种结构正是为了解决这个问题。

三、最小堆#

按触发时间把定时器放进最小堆,堆顶永远是最早触发的那个:

每帧:
while 堆顶的触发时间 <= 当前时间:
取出堆顶,执行回调
如果是重复定时器,更新触发时间后重新放回堆中
  • 添加:O(log n);
  • 每帧检查:只看堆顶,没到时间就立即结束,不再关心其他定时器;
  • 取消:在堆中查找并删除比较麻烦。常用延迟删除:只把定时器标记为已取消,等它到达堆顶时直接丢弃。
public class TimerManager
{
class Timer { public double Time; public double Interval; public Action Callback; public bool Cancelled; }
readonly List<Timer> _heap = new();
double _now;
public object Add(double delay, Action callback, double interval = 0)
{
var t = new Timer { Time = _now + delay, Interval = interval, Callback = callback };
Push(t);
return t; // 作为句柄,用于取消
}
public void Cancel(object handle) => ((Timer)handle).Cancelled = true;
public void Update(double deltaTime)
{
_now += deltaTime;
while (_heap.Count > 0 && _heap[0].Time <= _now)
{
var t = Pop();
if (t.Cancelled) continue; // 延迟删除
t.Callback();
if (t.Interval > 0 && !t.Cancelled) // 重复定时器重新入堆
{
t.Time += t.Interval;
Push(t);
}
}
}
void Push(Timer t)
{
_heap.Add(t);
int i = _heap.Count - 1;
while (i > 0)
{
int p = (i - 1) / 2;
if (_heap[p].Time <= _heap[i].Time) break;
(_heap[p], _heap[i]) = (_heap[i], _heap[p]);
i = p;
}
}
Timer Pop()
{
var top = _heap[0];
int last = _heap.Count - 1;
_heap[0] = _heap[last];
_heap.RemoveAt(last);
int i = 0;
while (true)
{
int l = i * 2 + 1, r = l + 1, m = i;
if (l < _heap.Count && _heap[l].Time < _heap[m].Time) m = l;
if (r < _heap.Count && _heap[r].Time < _heap[m].Time) m = r;
if (m == i) break;
(_heap[m], _heap[i]) = (_heap[i], _heap[m]);
i = m;
}
return top;
}
}

重复定时器用 t.Time += t.Interval 而不是 _now + Interval:这样即使某一帧卡顿导致处理晚了,下一次触发的时间也不会被推后,长期不会产生累积误差。

四、时间轮#

原理#

时间轮像一个钟表:一个环形数组,每个格子(槽)代表一个时间刻度(比如 100 毫秒),格子里存放在这个时刻到期的定时器。一个指针每过一个刻度前进一格,执行当前格子中的定时器。

槽数 8,刻度 100ms,指针当前在第 2 格
[0] [1] [2] [3] [4] [5] [6] [7]
↑
指针
添加一个 300ms 后触发的定时器:需要 3 个刻度 → 放进第 (2 + 3) % 8 = 5 格
  • 添加:直接算出槽的位置,O(1);
  • 每个刻度:只处理当前槽中的定时器;
  • 非常适合大量定时器、频繁添加和取消的场景,服务器、网络框架中被广泛使用。

超出一圈:轮数#

延迟超过一圈(8 格 × 100ms = 800ms)怎么办?给定时器记录一个剩余轮数:

延迟 n 个刻度:
槽位 = (当前指针 + n) % 槽数
轮数 = (n - 1) / 槽数 ← 指针还要经过这个槽多少次之后才真正触发
指针每次经过时:轮数 > 0 就减一跳过,轮数为 0 才触发
public class TimingWheel
{
class Timer { public int Rounds; public Action Callback; public bool Cancelled; }
readonly List<Timer>[] _slots;
readonly double _tick;
int _cursor;
double _accumulated;
public TimingWheel(int slotCount, double tick)
{
_slots = new List<Timer>[slotCount];
for (int i = 0; i < slotCount; i++) _slots[i] = new List<Timer>();
_tick = tick;
}
public object Add(double delay, Action callback)
{
int ticks = Math.Max(1, (int)Math.Ceiling(delay / _tick));
var t = new Timer { Rounds = (ticks - 1) / _slots.Length, Callback = callback };
_slots[(_cursor + ticks) % _slots.Length].Add(t);
return t;
}
public void Cancel(object handle) => ((Timer)handle).Cancelled = true;
public void Update(double deltaTime)
{
_accumulated += deltaTime;
while (_accumulated >= _tick)
{
_accumulated -= _tick;
_cursor = (_cursor + 1) % _slots.Length;
var slot = _slots[_cursor];
for (int i = slot.Count - 1; i >= 0; i--) // 倒序遍历,回调中新加入的定时器不会在本轮被处理
{
var t = slot[i];
if (t.Cancelled) { slot.RemoveAt(i); continue; }
if (t.Rounds > 0) { t.Rounds--; continue; }
slot.RemoveAt(i);
t.Callback();
}
}
}
}

分层时间轮#

只有一层时,延迟很长的定时器会在每一圈都被检查一次(只是减少轮数)。分层时间轮像钟表的时、分、秒三根针:

秒轮:60 格,每格 1 秒
分轮:60 格,每格 1 分钟
时轮:24 格,每格 1 小时
2 小时 5 分钟后触发的定时器 → 先放进时轮
时轮转到它所在的格子时 → 把它降级放进分轮的对应位置
分轮转到时 → 再降级到秒轮
秒轮转到时 → 触发

每个定时器在整个生命周期中只会被移动很少的几次。

精度#

时间轮的精度就是一个刻度。刻度为 100 毫秒时,定时器最多会晚约 100 毫秒触发。刻度越小越精确,但空转的次数越多。客户端游戏中对精度要求高的定时(技能、Buff),刻度可以和逻辑帧对齐。

五、最小堆与时间轮对比#

列表最小堆时间轮
添加O(1)O(log n)O(1)
每帧检查O(n)O(1)(只看堆顶)只处理当前槽
取消O(n) 或标记标记,延迟删除标记,或 O(1) 从槽中移除
精度精确精确一个刻度
适合数量少客户端中等数量、需要精确时间大量定时器,服务器、网络超时

六、时间源与其他注意事项#

用哪个时间驱动,决定了定时器在暂停、切后台时的行为:

时间源暂停(timeScale = 0)时适合
Time.deltaTime停止战斗中的技能冷却、Buff
Time.unscaledDeltaTime继续UI 动画、暂停菜单中的计时
服务器时间继续,且不受修改手机时间影响体力恢复、活动倒计时(见 倒计时)

其他注意事项:

  • 回调中添加或取消定时器:要确保遍历过程不会因此出错(上面的实现中用了倒序遍历和延迟删除)。
  • 回调中的异常:一个回调抛出异常,不应该中断其他定时器的执行,可以在调用回调时捕获异常并记录日志。
  • 对象销毁:定时器的回调引用了已经销毁的对象,到时间时就会出错。对象销毁时要取消它创建的定时器,或者在回调中检查对象是否还存在。
  • 卡顿后的补偿:一帧卡了很久,重复定时器可能一次需要触发多次。需要根据业务决定是全部补上(持续伤害),还是只触发一次(刷新显示)。

常见追问#

大量定时器怎么高效管理? 最小堆:按触发时间排序,每帧只检查堆顶;时间轮:环形数组,添加 O(1),每个刻度只处理当前槽。

时间轮的原理是什么? 环形数组,每格代表一个时间刻度,指针按刻度前进,执行当前格子中的定时器。添加时直接计算出目标槽位,超过一圈的记录剩余轮数。

延迟超过一圈怎么办? 记录轮数,指针经过时轮数减一,为零才触发;或者使用分层时间轮,长延迟的定时器先放在粗粒度的轮中,逐级下放。

最小堆和时间轮怎么选? 需要精确时间、数量中等用最小堆;数量巨大、频繁增删、可以接受一个刻度误差用时间轮。

定时器的取消怎么实现? 标记为已取消,到期时直接丢弃(延迟删除),避免在堆或槽中查找。

重复定时器怎么避免误差累积? 下一次触发时间在上一次的计划时间上加间隔,而不是在当前时间上加。

定时器用哪个时间驱动? 战斗相关用缩放时间,UI 和暂停菜单用真实时间,体力、活动等用服务器时间。

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

定时器的实现:从逐帧计时到最小堆与时间轮
https://xslab.cloud/posts/algorithms/timers/
作者
LuxFire
发布于
2026-10-14
许可协议
CC BY-NC-SA 4.0
相关文章 智能推荐
1
游戏中的随机:随机数生成器、权重随机、洗牌、伪随机分布与均匀采样
游戏算法 Unity 与 .NET 随机数生成器的区别、种子与可复现;权重随机的三种实现(线性、二分、别名法);Fisher-Yates 洗牌及其常见错误;洗牌袋;Dota 式的伪随机分布;在圆内、球面上均匀取点;正态分布与噪声;以及随机相关的服务器权威问题。
2
绳子与鱼竿的模拟:Verlet 积分、距离约束、关节链与贝塞尔曲线
游戏算法 实现绳子的四种方式(关节链、弹簧质点、Verlet 加约束、纯曲线)及其取舍;Verlet 积分与距离约束迭代的原理和完整代码;碰撞、收放线与张力计算;鱼竿弯曲的几种做法;鱼线的渲染;以及一个钓鱼系统中物理与表现的整体设计。
3
寻路算法:BFS、Dijkstra、A*、JPS、NavMesh 与流场
游戏算法 寻路问题的建模(网格、路点图、导航网格);BFS、Dijkstra、贪心与 A* 的区别;A* 的原理、启发函数的选择与可采纳性、完整实现;JPS 跳点搜索;Unity NavMesh、拐角算法与局部避障;大量单位的流场寻路;分层寻路;以及路径平滑和性能优化。
4
游戏 AI 决策:状态机、分层状态机、行为树、效用 AI 与 GOAP
游戏算法 游戏 AI 要解决什么问题;有限状态机的实现与状态爆炸;分层状态机;行为树的节点类型、执行状态、Tick 机制、黑板与中断,以及一个最小实现;效用 AI 的打分机制;GOAP 的目标、动作与规划;各种方案的对比与选择。
5
曲线与缓动:贝塞尔、Catmull-Rom、弧长参数化与缓动函数
游戏算法 游戏中曲线的用途;二次与三次贝塞尔曲线的公式、性质与德卡斯特里奥算法;经过所有点的 Catmull-Rom 样条与向心参数化;曲线上匀速运动的弧长参数化;沿曲线运动时的朝向;常用缓动函数与 AnimationCurve;以及 Unity Splines。
随机文章 随机推荐
Profile Image of the Author
LuxFire
Hello, I'm LuxFire.
公告
欢迎来到我的博客!这是一则示例公告。
音乐
封面

音乐

暂未播放

0:00 0:00
暂无歌词
分类
标签
站点统计
文章
60
分类
6
标签
164
总字数
171,869
运行时长
0 天
最后活动
0 天前

文章目录