国庆放假了

似乎前一段时间精力养的比较足，但是杂事太多，看看假期能不能动手作一些东西出来。10月7号回来看看。

关于MYSQL INSERT命令的两点用法

INSERT指令的ON DUPLICATE KEY UPDATE...可以在插入时发现有重复的记录自动转为UPDATE。（4.1以后的版本才支持）

另外INSERT .... values (...), (...), ... 可以一次插入多条记录。

这两点今天才知道，对优化效率确有帮助。

关于狭小地图的大量NPC寻路算法

在 GameRes 上，看到这个问题：如果很多NPC同时在一个场景寻路，又不能互相穿透，那么很容易导致卡死，这种情况如何解脱？

基本上，“规则 + 限制”就有可能陷入锁死，寻路是一种规则，碰撞则是是一种限制。有时候，特殊的场景和恰好的时序会导致系统到达一个稳定的状态而无法继续。看上去可能比较难这么巧合，但是实际上这几乎是必然的，因为稳定状态随着限制增多（比如地方狭小之处，又或是存在大量人物），而系统一旦到了稳定状态就会停滞不前。所以规则中必须有一种可靠的打破平衡的方法。

一个比较简单的思路正如论坛上有人提到的，参考 ethernet 的数据发送碰撞检测退让算法 CDMA/CD（每次冲突退让 random(min(2^n, LIMIT)) 个时间片，n 为冲突次数，LIMIT 为最大退让时间，如果 n 到达最大值则丢弃数据）。这个方法容易想到，但是实际上并不是那么有效，因为：

1. 以太网在发送数据节点较多、通讯负载高的网络下效率会下降，而且随着负载高下降得很快。根据经验，
传统的以太网带宽利用率是 1/e，大概是 30% 左右，也就是说 10M 的以太网在在负荷较高时只能维持 3M 左右的通讯数据带宽。（现代普遍采用的是交换式的网络了，可以大量减少冲突，才能保证 1G 以上的应用）

2. 以太网的表现是机器越少，通讯越少越实用反之则不实用。而我们的目标是在高负载的时候还能够继续的工作而不陷入一种稳定状态，随机退让的思路刚好不符合我们的要求。

举一个具体的例子：

------------------
XXXYYY
XXXYYY
------------------

如果 X 往右，Y 往左，那么显然的，不论 X、Y 怎么退让（等待一段时间寻路），那么这个系统都是不会脱离稳定状态的。

关于打破平衡的方法很多，这些都和具体的情况有关，如果我们考虑的是游戏中的自动寻路，那么我们可以借鉴一下真实世界的方法：

如果很多人在一个拥挤的空间朝各个方向前进，那么可以想象的是，这些人会陷入混乱，甚至会导致悲剧发生（比如球场骚乱导致践踏事件，实际上，大家争先恐后的脱离危险地区的方法效率是不高的，所以才导致了更多的人遭到不幸）。真实世界真正能够有效的维持交通秩序，是因为大家有一套限制比较严格的规则，避免出现这种情况发生。比如，靠右行走；排成纵队而非横列。如果你试图建立一个这样的系统，大家随意行走，只遵守物理规则（不能飞，不能穿透），遇到瓶颈自动恢复，基本上这是无解的。

所以，综合上面分析的结果，如果你期望游戏中 AI 看起来不那么傻，那么就需要从以下几个方面完善你的寻路算法：

1. 一个区域内，如果寻路人员的空间密度小于一定数值，自由寻路。
2. 如果密度较高，则靠右行走，限制队列宽度。

那么这时，问题的关键就在于第二点如何实现，如果采用的是 A* 类的算法，那么我们可以简单的在地图上做一些标记来辅助我们解决这些问题，例如：

---------------------
RRRRRRRRRRRRRRRRRRRRR
SSSSSSSSSSSSSSSSSSSSS
TTTTTTTTTTTTTTTTTTTTT
UUUUUUUUUUUUUUUUUUUUU
---------------------

R、S、T、U 表示不同的四元组：
R - (1, 10, -, 3)
S - (1, 10, 3, 12)
T - (10, 1, 12, 3)
U - (10, 1, 3, -)

四元组的含义是，（向左走开销，向右走开销，向上走开销，向下走开销，-表示不可能），这样，我们寻路时，根据寻路的下一步方向，可以估算一个符合我们期望的开销成本，促使选择一条靠右走，宽度为 2 的道路。在较为拥堵的时候，禁止选择走 > 10 的节点，如果寻路失败，则原地等待一段时间。这样，发生完全堵死的情况就很不容易了（实际设计算法中，还需要考虑一些更复杂的具体情况）。

最后，我们是否需要在所有场景一点一点的去描述这个四元组？这是不必要的，除非非常特殊的地图，可能需要人为的设置（好像划分单行线一样），一般来说，这些数据可以由程序根据我们的规则自动预先生成。

由“谁证明了庞加莱猜想”想开的

前不久，看到了丘成桐宣布最后完证了庞加莱猜想，似乎是一个能让中国数学界振奋的消息。
然后随后引起了不少质疑，最近又看到丁伟岳在其BLOG上提了最新的质疑，包括以下内容：

1. 佩雷尔曼（俄）已经解决了庞加莱猜想（8月22日国际数学界大会的开幕式上，国际数学家联盟宣布授予佩雷尔曼菲尔兹奖，但其本人已经拒绝）。
2. 称国外媒体（包括华尔街日报发表署名文章、美国数学会的会刊《Notices》两个出处）都谴责了国内这些关于猜想的不实报道。
3. 杨乐，曹怀东、媒体就中国数学家在猜想上贡献的说法上有出入。

在这里，未经详细的考证，我无从知道事情的真相并发表评论，我也没有足够的时间去一一核对这些说法，并且分析各类旁证（仅分析一个人提供的说法显然是不够的，即使国外的杂志上也可能有不同说法的文章，贸然的将国外杂志的一两片文章当作圣经一样作为佐证显然也是不足的），我只是很疑惑：

1. 中国数学界已经多年没有出过像样的成果了。
2. 中国数学界多年内很少出有分量的数学家了，即使加上所有华裔，其数量依然不足以称道。
3. 中国人口占世界的1/5，并且基础教育还可以，几乎所有的有数学潜质的人都有受到足够基础教育的机会。

我很遗憾的是，我没怎么听说过国内的数学界就数学问题本身进行广泛的争论，而是就人品、道德问题进行不断的攻击。不论是丘，还是丁。然而，就道德问题而言似乎并没有改善，纵观这二十年来，中国整个学术界都在滑向道德败坏的深渊。