[tc]魔兽3 1.21内存修改器 V4

　　由于Blood+缺了一集，一边等候下载，一边就写了这个V4版。有些代码写的实在垃圾，懒得改了，于是又贴了几个补丁。
　　这次除了补完上次说的“攻击力”、“攻击类型”、“防御类型”之外，“防御力”也被我“一不小心”改出来了。“智力”还是像以前一样，有找不到的几率，暂时还没有想到解决方案。

　　因为此次更新并不完全是一时兴起，所以那个修改金钱的难题是一定要解决的。
　　6F088E78: mov eax,[edx+78] 8b 42 78
　　金钱和智力一样，代码是公用的，有一定的几率会变成无用的地址，好在几率不大，大部分时间是在一个区域内不停的变动，[tc]仔细一看：edx的低16位居然是固定的！比如P1的金钱始终是[0190]，P2是[1410]，只有高16位是不固定的。这就好办了，取下上16位，补上我们自己的下16位即可！该问题完美解决！
　　编程的时候值得一提的是：这次[tc]决意尽可能少的修改原来游戏的代码。此前的修改存在冗余！比如“力量”、“敏捷”，我是分开搜索的。但是明眼人很快会发现，这两个地址是相关的，只要找到其中一个，另一个也能推算出来。这次修改金钱也是一样的道理。
　　[tc]修改了Player 1-10（注：魔兽最多可以有12个在线玩家，我一时偷懒只作了10个）的金、木、人口、最大人口，但是这些数据是相关的：对于同一个人而言，偏移地址是这样的：
　　　　金　　　　　　0x 0
　　　　木　　　　　　0x 80
　　　　最大人口　　　0x180
　　　　当前人口　　　0x200

　　不出意外的话，这是我最后一次更新这个修改器了。因为基本上能想到的东西都已经写了。

推箱子的求解

　　经过两周的折腾，白了头发无数，终于能算一些简单的地图了。15x15以内的地图基本上不超过5秒钟能有近似最优解。超过20x20的地图，10分钟之内没有结果，我也没耐心等下去。
　　整个算法看起来是这样的：首先选择可以移动的箱子的集合，选择一个深度优先遍历，当发现下一步有重复时，选择较短的路径；当树的深度超过一个限度时，把叶子节点送入一个链表；只要那个链表不空，那么设定新的最大深度，回到第一步。为了判定初始的深度，需要对箱子与目标点作一次匹配（我选择的是最大代价匹配）。
　　为了实现A*算法，使用了许多类来作支撑，比如：
　　　clsShortestPath　　　　　 专门求迷宫的最短路径，翻译自高中时候的程序
　　　clsGraph_MostMatching　　 二部图最大匹配
　　　clsMapData　　　　　　　　跟地图有关的操作在这里
　　　clsMapStatus　　　　　　　跟地图状态有关的操作在这里
　　　clsSolution　　　　　　　 求解的主程序，根据一个基本clsSolutionNode作为树根，展开所有解
　　　clsSolutionNode　　　　　 解的内容、保存下一个解的链状结构，当树的深度超过给定值时会调用制定的函数保存状态
　　　clsSolutionNodeHistory　　纪录解的历史，在重复的解中选择路径比较短的解

　　如果有人说这样写效率会不会很低？我认为不会，我没有使用virtual，不算真正的OO，在静态绑定的作用下，效率不会很低。
　　代码总共33k，没办法把源代码贴出来。下面是程序到目前为止的5个版本的What's New，从中可以说明一些问题。

V1
● 用链表实现广度优先
● 计算下一级时，回收上一级内存

V2
● 改进的内存回收，能快速回收同一层的内存
● 阻止嵌入角落
● 修改了过程保存的方式（不再是string），减小了内存使用
● 防止重复上一次的步骤的反过程（比如上一次是向左，那么这一次不会向右），用list实现


V3
● 下定决心，把广度优先改成深度优先，用树实现，保存下一步的是list
● 新建clsSolutionNodeHistory，加强了重复路径搜索能力，杜绝重复的搜索
● 明确了地图clsMap、地图数据clsMapData的不同（前者只有地形数据），减小了内存占用和构造时间
● 修正了图形显示的小Bug（箱子、目标位置的标记不能通过单次循环完成）
● 新增了一个小的地图编辑器（VB）

V4
● 地图优化：自动判定不能放置箱子的区域（不需要再在地图编辑器中作弊了）
● 改进的clsSolutionNodeHistory：情况相同时，如果上一次失败了，那么取消现在的尝试；如果上一个记录还没有计算过，那么选择路径比较短的一次
● 进一步改进了状态的保存，clsMapData改名为clsMapStatus、clsMap改名为clsMapData
● 追加了一个看似十分垃圾的评价函数，以箱子与目标的距离作为判定依据，这样就形成了一个简化的A*算法
● 强制限定了运算深度，由于不能自动追加深度，还不能看作是IDA*算法
● 为了得到初始的运算深度，用网络流实现了二部图的最优匹配
● 为了提供最优匹配的原始数据（目前是每个箱子到每个目标的距离），编写了最短路经搜索代码，代码用的是高中时写的VB程序，算法名字不记得了，只知道空间复杂度O(n^4)，时间复杂度O(n^2)

V5
● 题解程序将步数溢出的节点压入一个链表，IDA*得以实现
● 最优匹配从自小代价改为最大代价（也就是说，假定编地图的人让玩家总是把箱子推到最远的目标点，真是无语了）

用最大流实现二部图最大匹配

　　为了某个已经折腾了两周的程序，花了两天时间实现了二部图的最大匹配，现分享如下。

　　题目的简化版是这样的：ABCD四个节点要对应1234四个节点，每个字母对应一个数字、每个数字对应一个字母。已知每个字母与每个数字只见的对应代价是不一样的。现在求最佳的配对方案，使得总代价最大／最小。
　　这个问题属于二部的带权匹配问题，网上似乎有不少解法，基本上是用匈牙利算法解决的。但是考虑到带权问题的复杂性，以及日后扩充要求的可能性，[tc]决定还是用网络流来求解。

　　[tc]的参考书：《网络最优化》，刘家壮，高等教育出版社，1991年。
　　用网络流求解的思路是这样的。由于已知字母与数字的关系如下图所示（对应关系的弧略去），
　　　A \/ 1
　　　B \/ 2
　　　C /\ 3
　　　D /\ 4
　　可以在现有的关系基础上，增加一个只有出度的开始节点s，和一个只有入度的结束节点t。
　　　　/　A \/ 1 \
　　　S -　B \/ 2 - T
　　　　\　C /\ 3 /
　　　　\　D /\ 4 /
　　显然s到t的计算过程可以找到字母与数字的匹配。现在设网络内的容量全部为1，当前流量为0，那么容易证明匹配结束后，每个字母对应一个数字、每个数字对应一个字母。

　　既然思路确定了，程序也就简单了。下面的代码是用来测试的，实际使用时可以整理成类，整理成类的方法就不说了。
　　注意这个算法的时间复杂度大约是O(n^2*L)，n是矩阵度数，L是一个不确定的值，L < n，与匈牙利算法的O(n ^ 3)相比差不多，但是可以轻易的扩展成更复杂的程序。
　　另外为了功能需要，下面的代码包括了求最大最小值两个代码，是用宏定义来区分的，看代码时请特别小心。


#include "stdafx.h"
//////////////////////////////////////////////////////////////////
// 用最大流实现二分图最大匹配
// 网络最大流（容量1），添加了超级源、超级汇
#include < stdio.h >
#include < string.h >
/*
样例：
INPUT
3

3 5 2
3 2 8
7 5 8

OUTPUT
20
*/

// 如果是寻最大值，需要下面这句
// 如果是寻最小值，屏蔽下面这句
//#define __FIND_MAX

const int maxn=100;
const int maxint=32767;
struct stuAbutMatrixNode // 邻接矩阵
{
int weight, // 权重
flux, // 流量
capability; // 容量
};

struct stuGraphicNode
{
int value, // 值
fa; // 度
};
stuAbutMatrixNode iAbility[maxn+2+1][maxn+2+1]; // 0..maxn+2
stuGraphicNode best[maxn+2+1];
int numItems,
numMaxWork,
s,t; // s、t是始边、终边的下标

void init()
{
int i,j;
scanf("%d",&numItems);
memset(iAbility,0,sizeof(iAbility));
for(i=1;i<=numItems;i++)
for(j=numItems+1;j<=2*numItems;j++)
{
iAbility[i][j].capability=1;
int iInput;
scanf("%d",&iInput);
iAbility[i][j].weight=iInput;
iAbility[j][i].weight=-iInput;
}
s=2*numItems+1;
t=2*numItems+2;
for (i=1;i<=numItems;i++)
{
iAbility[s][i].capability=1;
iAbility[numItems+i][t].capability=1;
}
numMaxWork=0;
}

bool find()
{
int i,j;
bool quit;
#ifdef __FIND_MAX
memset(best,0,sizeof(best));
best[s].value=1;
#else
for(i=1;i<=2*numItems+2;i++)
best[i].value=maxint;
best[s].value=0;
#endif
do
{
quit=true;
for(i=1;i<=2*numItems+2;i++)
#ifdef __FIND_MAX
if(best[i].value>0)
#else
if(best[i].value!=maxint)
#endif
for(j=1;j<=2*numItems+2;j++)
if (iAbility[i][j].flux
#ifdef __FIND_MAX
if (best[i].value+iAbility[i][j].weight>best[j].value)
#else
if (best[i].value+iAbility[i][j].weight
#endif
{
best[j].value=best[i].value+iAbility[i][j].weight;
best[j].fa=i;
quit=false;
}
}while(!quit);

#ifdef __FIND_MAX
if(best[t].value>1)
return true;
else
return false;
#else
if(best[t].value
return true;
else
return false;
#endif
}

void add()
{
int i,j;
i=t;
while(i!=s)
{
j=best[i].fa;
iAbility[j][i].flux++;
iAbility[i][j].flux=-iAbility[j][i].flux;
i=j;
}

int x,y,value;
y=best[t].fa;
x=best[y].fa;
value=iAbility[x][y].weight;
printf("(%d,%d)=%d\n",x,y-numItems,value);

#ifdef __FIND_MAX
numMaxWork+=best[t].value-1;
#else
numMaxWork+=best[t].value;
#endif
}

int main()
{
init();

while(find())
add();


#ifdef __FIND_MAX
printf("Max=%d\n",numMaxWork);
#else
printf("Min=%d\n",numMaxWork);
#endif

return 0;
}

sprintf等C用法在C++的转换的小记

　　当我主张（在PC上）用C++的新用法替换C语言的旧式用法时，许多人问来一些奇怪的问题，这里收集了几个典型问题，探讨一下。

1、字符数组
　　别用这个了，string更好，也标准。同寝室有个同学更喜欢CString，好吧，这个我也没意见，我一般用string，因为我总觉得CString是MFC的东西（其实不是），有恐惧心理。
　　另一方面，string是一个模版类，如果需要宽字节（比如Windows程序），就要用wstring代替，关于这个问题我另外撰文说明好了。简单的说，如果要显示中文，应该使用国际化支持，例如：流.imbue(locale("chs"));
　　不过上面这段代码只能在Windows底下用，在Linux下要受到字体配置文件的影响。
　　
2、sprintf()，将printf的结果送入字符串，用于缓冲
　　其实这个问题挺难解决的。
　　首先sprinf有缓冲区溢出的危险，snprintf没有这个危险，但是只有C99容纳了这个函数，C++03似乎没这东西。
　　[tc]的建议是用stringstream，这东西总的说来好用，就是太慢。而且大家也知道，stream基本上没有解决二进制直接访问的问题，所以对效率要求非常高的话还使用指针。
　　好在哪里呢？比如你要把一个"13.2"的字符串转换成13.2的数字，那么可以这样：
　　stringstream ss;float fnum;
　　ss<<"13.2";ss>>fnum;

3、getch()
　　读一个字符本来就不是什么难事。更何况现在一般用这个函数只为了显示一行“Press Any Key To Continue...”，如果只是这样的话，一句“system(pause");”真是又简便又清楚。缺点就是不好移植。

4、动态数组
　　老生常谈了。STL里的容器肯定比你写得好！这里就再废话几句：
　　　数据规模小 选vector，使用之前记得reserve()
　　　数据规模大 选list
　　　随机存取 选vector
　　　用iterator遍历 差不多，用vector
　　　前、后部插入 首选deque、vector也快
　　　后部删除 deque、vector
　　　前部删除 deque、list
　　　中间插入 list、deque，我比较倾向list
　　　中间删除 vector、deque
　　　交换数据 vector
　　当然还有别的。
　　顺便，不要再问排序了，容器都有.sort()。

在ARM上演示uC/OS

　　在克服了一些困难之后，终于可以在ARM上直观的表演uC/OS了。（鼓掌）

　　下面两张图是原作者《嵌入式实时操作系统uC/OS-II第2版》的第一个范例。内容是这样的：建立10个任务，随机的在屏幕上显示本任务的编号，屏幕下方提示的数据分别是：任务数（10个任务+1个监视任务+2个系统任务）、CPU占用率、任务切换情况。

　　左边这张是uC/OS移植到WindowsXP之后的效果，为了兼容原作者的代码，在控制台下显示运行结果。因为刚刚开始运行，屏幕还没有占满。
　　右边的图是今天刚刚改写好的ARM版uC/OS，为了兼容PC下的代码，把PC机上特有的函数封装一层，以“字符模式”运行。值得注意的是CPU占用率将近100%，只要把uC时钟降低，那么CPU占用率也会降低，当然如果那样做的话，ARM有很多时间是空闲的。

　　在ARM平台上，干扰因素比PC多，加上机能限制，当外部中断出现时，你会看到“任务切换次数”下降，但是并没有挂掉。据说uC/OS被验证为是一个足够稳定的系统，可以用于军事、科研、紧急事务处理（医疗救护？）等领域。当然，我认为那是建立在程序不写错的基础上，实际上[tc]的这份uC只要破坏掉看门狗的运行，系统即刻会崩溃的。

　　还需要说明的两个问题：

　　一个是，[tc]很想知道，在CPU空闲的时候，ARM能不能迅速切换到省电模式，降低功耗？问题在于，[tc]分别试验了CPU在65%和98%的两个程序，结果65%的情况下，CPU温度比较低（这项测试是根据[tc]的触觉，不知道有没有心理因素），也就是说，ARM是自动降温的CPU。然而在官方的说明文本里面似乎没有出现相关介绍。

　　另一个问题是，这个程序中，[tc]使用的是自己编写的随机函数。似乎工作的还不错\ OoO /。


　

扫除

下午跑到宿舍去打扫卫生，阳台的地由于被雨水淋到，脏得够呛。好在是瓷砖地，清洗起来也容易。

3月4日就开学了，以后就算是这种水贴也只能以星期一篇了吧。不过，一想到这学期就要搬本部，我就……哈哈哈哈！

《I''s》系列

漫画：周刊《少年Jump》1997～2000连载的桂正和的作品。
15卷，累计1000万册销量。
[tc]我有收藏扫描版。

OVA：2002年12月，From I''s，《另一个夏天的故事》，全2话
这是一个仅在便利店贩卖的动画，销售量上、下两集合计7万张。

　　不管从画风还是配乐上看，OVA都难上档次。而且故事内容与原作几乎没有关系，几乎像是同人作品。围绕 濑户一贵、秋叶いっき、市村洋介 10年前重新见面的约定展开。和 葦月 伊织 似乎关系不大。另外OVA还聚集了一小帮声优方面的名家。自我感觉声优方面OVA比TV更强一些。

TV：2005年，全6话+5 SP。
　　桂正和本人也参加了这次动画化，绘画水平有了质的飞跃。故事本身基本上是按照原作情节，并且把YY内容专门转移到SP中，是相当成功的手法。

{
/*--------------------------------
* 最近的动画评论真是越来越短了...
--------------------------------*/
}

tcGUI.c

　　今天为ST2410做了一个图形库，完成了大约40%。一想到我今天的工作是八十年代的程序员经常做的事，我就 T_T

　　简单的说，这个图形库用于在没有文字显示BIOS的CPU上显示文字的。目前完成了以下工作：

英文8x12点阵的提取
宋体16x16点阵的提取（一个VB小程序），目前做了一级字库
LCD初始化（抄来的）
描点（抄来的）
描线（抄来的）
矩形（抄来的）
实心矩形（抄来的）
清屏（抄来的）
位图图片（抄来的）
英文显示
中文显示
更换颜色，前景/背景
文字透明

　　还需要加入的功能：
屏幕滚动（即翻页）
屏幕保存/恢复（用于实现双缓冲、视频缓冲、直接写屏）
绘制窗体
触摸笔（快成形了）

　　本来，[tc]以为这些代码很好找的，结果处处碰壁。在u龙那里，虽然得到一份差不多用途的东西，可惜是编译好的库文件，不提供代码。一气之下，[tc]自己写了这份代码，深感屏幕存取之效率低下，没有显卡的日子，难！

　　下面第一张图是昨天，为调试方便写的引导程序的图形界面部分。
　　第二张是刚刚实现的成果，似乎实际效果更好一些。不过我这样说也没人相信。
　　在这份成果上，只要将config.h中的#define CHINESE_SUPPORT 1去掉，就会变成第三幅图的样子，目标代码将会减小将近200K。