« 在文本模式下显示中文 | 返回首页 | X Window 的 Resize 处理 »

树结构的管理

要写过多少代码才能得到哪怕一点真谛？

多少年过来，我在潜意识的去追求复杂的东西。比如我自幼好玩游戏，从小到大，一直觉得玩过的游戏过于简单（无论是电子游戏还是桌面游戏），始终追寻更复杂规则的游戏，供我沉浸进去。或许是因为，有了更高的理解和控制复杂度的能力，就可以更为轻松的驾御复杂性。

这很好的解释了 2000 年到 2004 年我对 C++ 的痴迷。还有对设计模式的迷恋。

Eric S. Raymond 说：尽量不要去想一种语言或操作系统最多能做多少事情，而是尽量去想这种语言或操作系统最少能做的事情——不是带着假想行动，而是从零开始。禅称为“初心”（beginner's mind）或者叫“虚心”(empty mind) 。

代码写多了，问题见过了，甚至是同一问题解决多了。模式这种东西自在心底，不必拿出来。时时的从零去想，总能重新明白一些道理。

为什么说语言重要也不重要，算法和数据结构重要也不重要。对要解决的问题的领域的理解很重要（即明白真正要做什么）。理解了，我们才可以用面向对象，用模式去套问题；可理解了，我们又不真的需要这些繁杂的抽象。

闲话放一边，今天想谈谈树结构的管理。

这个问题来自游戏引擎里对对象的管理。有时也出现在 GUI 模块中。

我以前总结过，所谓面向对象，就是可以用统一的方法对不同的对象进行同样的操作。而这个过程，需要我们把对象的同质引用放到一个容器中。这个容器，绝大多数情况下，由一个集合结构即可胜任。

而有些复杂的问题领域中，我们又需要树型结构的容器。有时是为了优化（比如在 3d 引擎中，用树结构描述对象的位置相对关系，以及用于裁减），有时是为了分类（比如把所有 npc 放到一颗子树下，而把 item 放到另一颗下）。

本质上，容器的处理异于普通对象，而树结构即容器之容器。把容器之容器看成一个单体，有利于问题的简化。

处理这种复杂数据结构，动态语言相对于 C/C++ 这样的静态语言，有比较明显的优势。但是在性能方面又有明显的劣势。权衡之下，我们需要做的是采用 C 去实现底层细节，而动态语言做高层管理，并控制粒度，减少控制频率。

据我个人观察和实践，虽然最终游戏 engine 管理的树结构非常繁杂。但 C/C++ 部分运转起来之后，需要特别控制的节点层次并不多。

但是，若想充分利用动态语言的动态性，在子树构建阶段，又非常有可能触及比较复杂的树层次。只到构建子树完毕，大多数中间层次和节点永远都不会再被特别控制。

具体的例子有 3d 粒子系统，人物换装系统等等。如果用动态语言去描述那些小部件的搭建过程会比（在 C/C++ 里）较轻松。但是搭建完毕后，可能持续引用的节点并不多。大部分中间节点留在 C 层自我运转就足够了。

这就是我上面说的粒度问题。在构建的局部阶段，我们需要局部的细粒度。而在全局控制阶段，我们则需要全局的粗粒度。

如果一贯的保持细粒度，对于动态语言很可能发生性能问题。而增加动态语言和 C 底层的结合度，也更有对象生命期管理的麻烦事。如果只是麻烦倒也罢了，随之带来的 gc 的负担往往也不可小窥。

我现在的解决方案：

把树节点分为匿名和具名两类。匿名节点只在构建期对上下文可见。具名节点，可以以路径名（相对或绝对）方式引用。

如果以 lua 为实作，接口类似这个样子。

create()
with(function(self) 
  -- do something with self
end)

create("name")
with("name",function(self)
  -- do something with node "name"
end)

create 方法可以在当前的位置创建一个子节点，可以给这个子节点起名，也可以匿名。

with 方法可以引用一个节点（如果给出名字，则找到具名节点，如果不给名字，则引用最近创建的一个匿名节点），并执行一个代码块（以 closure 方式给出），在这个代码块中可以引用这个节点对象 self ，操作 self 的各种属性和方法。但是 self 不可以传递到代码块之外。即不能被外面引用。这点在运行期通过锁机制保证。如果想长期引用一个节点，必须通过节点名。

除此之外，提供两个销毁节点的方法：

clear (name) 清除具名节点下的所有子节点。匿名节点不提供清理方法。

delete (name) 删除具名节点本身以及其下的子树，同样对匿名节点无效。

不提供任何枚举子节点和遍历子树的接口。（那些是 C 层次的事情）

为什么这样设计？仅仅这几个接口足够了吗？

这样，我们保证了动态语言层和 C 层关系的足够简单。尤其是规避了复杂的生命期管理。所有的节点都通过 create 构建，到 clear/delete 消亡。动态语言层有能力得到所有生命期信息。

而动态语言层没有移动子树和直接的持久引用特定树节点对象的能力，这向 C 层担保了绝对不会有悬空指针。具体到使用 lua 做封装时，我们简单的用 lightuserdata 引用 C 对象即可。

为什么提供 clear 和 delete 两种销毁节点的形式？这是因为我们没有枚举和遍历的接口，没有这两个接口，可以方便维持动态语言层上的对象粒度。

clear 用于插槽(slot) ，比如人物换装。模型的手上就可以有一个叫 hand （或 left_hand）的 slot ，供我们把武器的模型插上去。更换武器时，clear hand 这个 slot ，然后在其上重新创建新对象即可。

名字相对路径的支持，使得在特定位置创建子树可以做为通用模块。

delete 用于动态生成的对象本身。比如我们可以把场景中的 npc 挂在 root.npc 的子树下。再为每个 npc 以 id 为名创建节点。销毁 npc 即 delete root.npc.xxx (xxx 为 id)

匿名节点的设计，可以把大量复杂的子树构建过程交给动态语言去完成。

with 方法可以为上层程序员提供一个安全屏障。最主要是节点有效的保障。

上周末有同事问我，要不要增加移动子树的接口。比如有时我们需要把主角模型从一个地图层移到另一个地图层（比如从高楼上跳下）。我觉得这可能是个伪需求。

显示上的约束条件（模型依附在那个位置），和场景树的管理应该分离。比如不可以因为人物围着桌子跑，就把人的模型挂在桌子的坐标系内。

但另一些时候，我们需要让人物跨场景，则完全可以在旧场景中删除，然后在新场景中创建。在显示的表现上也可以做到不让用户察觉。

当然，也可能因为优化需要，或是实现简化的需要，我们需要增加这样一个方法。

move (name, parent)

把一个具名节点移动到另一个具名节点之下。

这最后一个方法或许是个可选项。

今天写了 400 多行 lua 代码，始终没什么感觉。看来周末就是应该休息一下。

最近想提高一点团队的工作效率，大家开会决定，以后每天最晚到岗时间提前到上午 10:30 。对我还是有点痛苦的 :) 我这几年，一直都习惯于中午再起床了。不过坚持了一周，感觉还行。也自然而然的把自己的下班时间提前到了 1:00 左右，睡眠似乎没受太大影响。

另，为近期的工作安排花了日程图，大大的挂在墙上。好象花点时间搞点形式主义出来，还真有点效果。 :D

云风 提交于 May 10, 2009 09:13 PM |

Comments

云风老大 你好！最近又看了以前c++和c的比较，我觉得大多数维护c++的人都在抓C语言的弱点，而没有提出c++缺点的解决方法~~我想请问您：快要出来的c++0x不知道有没有解决譬如像 几年以后修改c++代码工作量很大 很麻烦的问题？？？？
还望您不吝赐教！！！
我的邮箱是 141042304@163.com

Posted by: 2b | (25) July 6, 2009 12:39 PM

做游戏程序员都这样？都这么玩命？是自己喜欢呢还是看到别人这样自己也这样？

Posted by: Diwayou | (24) June 23, 2009 10:15 AM

还好

Posted by: netman | (23) May 29, 2009 03:31 PM

写得非常的好，支持！

Posted by: 桂林旅游 | (22) May 19, 2009 06:35 PM

上午10:30上班，凌晨1:00下班？
在公司14个半小时吗？

Posted by: Anonymous | (21) May 19, 2009 11:21 AM

生活养成规律 也就不在乎了

Posted by: 股票行情 | (20) May 18, 2009 03:40 AM

云兄的境界高了，这代码就是为了解决问题的，搞了那么多设计模式，写了那么多代码，回过头来发现，原来都是一步步的解决遇到的问题而发明的方法。需求带动了设计模式的发展，任何设计模式都有从不成熟到成熟、不通用到通用扩展的过程，看设计模式，不仅是要会用会套它，更重要的是揣摩一个成熟的设计模式它的成长历程，揣摩最初设计的人是怎么想的，是为了解决什么问题，这才是魅力所在啊。

Posted by: xikema | (19) May 17, 2009 10:44 AM

云风看起来最近引擎的研发进入了快速轨道了，gxgx

Posted by: skillzero | (18) May 16, 2009 11:08 PM

嗯，做研究做得实在是郁闷的不行了，来这里稍微踢个场:D
template<int Dimension>
struct Vector
{
real a;
Vector<Dimension - 1> B;
Vector& operator += (const Vector& v) {a += v.a; B += v.B; retun *this;}
Vector operator +(const Vector& v) const {return Vector(*this) += v;}
real DotProduct(const Vector& v) const {return a * v.a + B.DotProduct(v.B);}
};
template <>
struct Vector<1>
{
real a;
Vector() {}
Vector(const real& a) : a(a) {}
operator real&() {return a;}
operator const real&() const {return a;}
};
--Realtime Radiosity, Impossible!
--Realtime Radiosity!I'm possible

Posted by: PaulJi | (17) May 15, 2009 10:01 AM

云风是卡马克的FANS，所以作息时间也克隆了一下。

Posted by: alioxp [TypeKey Profile Page] | (16) May 13, 2009 10:51 AM

13楼真是少见多怪呀，很多软件公司都是这种作息，弹性工作制嘛，很向往啊

Posted by: springhill | (15) May 13, 2009 10:16 AM

所谓面向对象，就是可以用统一的方法对不同的对象进行同样的操作。
---
这种理解不够深入。

Posted by: foo | (14) May 13, 2009 02:01 AM

真奇怪,你们在新疆吗?怎么这种作息?

Posted by: wg | (13) May 12, 2009 01:27 PM

追求完美本来就是一种病

Posted by: sunway | (12) May 12, 2009 08:50 AM

呵呵，所谓技术不过是一种手段，想来这些东西无非是建立在“假设”的基础之上，所谓模型无非是对经验世界的一种总结，凡是这些都是出自于人，和真实的世界又有多大关系呢？爱因斯坦说过一句话：“手段的完善和目标的混乱”，想想还是很有道理的，再多的困惑都源自于“为什么？”吧

Posted by: ajivacat | (11) May 11, 2009 11:12 PM

这里C层除了实现对树容器的基本操作之外，还会做什么吗？还是说是C层仅仅提供容器，对容器的操作全都在脚本里？

Posted by: sjinny | (10) May 11, 2009 05:07 PM

这个作息时间应该受到批评

Posted by: lbaby | (9) May 11, 2009 03:34 PM

如果有遍历节点的需求，在上一个层次做。即，在添加子节点的时候把信息（节点的名字）记录到节点的用户数据里。

至于编辑器，换一套封装层。编辑器的需求比游戏差异还是满大的。

Posted by: Cloud [TypeKey Profile Page] | (8) May 11, 2009 12:44 PM

遍历节点都不支持啊，那编辑器该怎么做呢？

至于节点生命管理的话，不需要用GC也不需要用RC，我的解法是引入一个handle的概念，外部通过handle间接引用节点对象，handle自身永不删除，删除节点的时候把对象delete掉并把handle置空。这样当再次引用已被删除的对象时，handle会抛出异常。

Posted by: analyst | (7) May 11, 2009 12:12 PM

——这个问题来至游戏引擎里对对象的管理（来自？）
——需要我们把对想的同质引用放到一个容器中（对象？拼音输入法的问题？）

Posted by: tangfl | (6) May 11, 2009 10:18 AM

写代码就像谈恋爱。

很多人问：要谈多少次才能找到真爱？

Posted by: joe wulf [TypeKey Profile Page] | (5) May 11, 2009 08:11 AM

这样的水平真是佩服哦。微软，看到了吗

Posted by: 贫贱程序员 | (4) May 11, 2009 04:44 AM

哇.真的是云风写的日记吗 ? 好崇拜你呀..能不能加我Q ? 550171612 我是新程序员呢 ...

Posted by: 新手.. | (3) May 11, 2009 12:19 AM

不过确实晚上写代码的状态最好。。我也最恨早上早起上班了。。

Posted by: bobo | (2) May 11, 2009 12:09 AM

大家都是这样的生活节奏？

如果有家庭的，会有很多麻烦。

保重身体。

Posted by: chinainvent | (1) May 10, 2009 11:37 PM

Post a comment

非这个主题相关的留言请到：留言本