儿时想搞明白的闪电生成算法, 今天终于想起来并且看明白了.
算法很简单.
把起点和终点不断二分, 直到一个极限值, 然后再全部连接.
1 void drawLightning(HDC hdc, const POINT &start, const POINT &end, float diff)
2 {
3 if (diff < s_minDiff)
4 {
5 MoveToEx(hdc, start.x, start.y, nullptr);
6 LineTo(hdc, end.x, end.y);
7 }
8 else
9 {
10 POINT mid = {
11 (start.x + end.x) / 2,
12 (start.y + end.y) / 2,
13 };
14 mid.x += LONG((random() - 0.5f) * diff);
15 mid.y += LONG((random() - 0.5f) * diff);
16 drawLightning(hdc, start, mid, diff / 2);
17 drawLightning(hdc, end, mid, diff / 2);
18 }
19 }
第三个参数 diff 控制闪电的曲折程度,
内部变量 s_minDiff 是极限值.
这两个变量决定闪电有多少个关键点.
假设 diff == 10, s_minDiff = 5
已知, 每次递归 diff / 2, 因此最终 diff 会小于 s_minDiff, 也就是2.5.
为了方便理解, 可以用二叉树来形象标识.
0
0 0
0 0 0 0
二叉树有3层, 每层都是一次递归.
第一层递归 diff / 2 => 10 / 2.
第二层递归 diff / 2 => 5 / 2.
第三层递归 diff < s_minDiff.
所有节点相加就是总共调用次数.
所有画线的操作, 都在叶子节点中.
通过以上, 可以计算以下
递归层数 => diff / s_minDiff + 1
画线次数 => 2 ^ (递归层数 - 1)
调用次数 => 2 ^ (递归层数) - 1