— AI分享站

Archive
Tag "技巧"

接上篇,我们接着聊。

分数系统的打分公式,是根据情况自己定义的,但也有一些方式来帮助构建出比较合理的公式来,公式的推导就是一个函数的拟合过程,我们可以先取几个样点,然后试着找到一条函数曲线,尽可能的去使样点落在我们的这条函数曲线上。在中学的时候的实验课上,大家应该都做过这种事情。在AI中,我们的打分公式,一般不会很复杂,可能是简单的直线,或者分段的折线,有时也会是二次,或三次的曲线。有了这样一个基本曲线,接着再用测试样例去修正,一般就可以得到一个比较符合需求的打分公式了。

在分数系统中,如果有多个因素需要考量,比如我们上个例子中的EC和HP,这就引出了分数如何组合的问题。就像我们先前对Retreat和Shoot的打分方式。常用的做法是,针对每个因素单独引入打分公式,并且归到[min, max]的分数区间中,然后再对所有的得分组合后,得到一个最终得分。对每个因素单独打分的好处是,我们可以跟专注于单个因素的影响,方便我们构建打分公式,并且可以方便的移除和添加新的因素,而且也能更好的复用我们的打分公式。分数的组合一般可以有两种:

1. 加权平均,s = (k1*s1 + k2 * s2 + ... + kn * sn)/(k1 + k2 + ... + kn)
2. 因子连乘,s = s1 * s2 * ... * sn ( 0 <= si <= 1.0 )

这两种方式有各自的适用范围,第一种方式,我们除了对打分公式要细心调整外,还需要对加权因子加以调整。第二种方式必须保证每个因子被归到[0,1]之间,因为用到了乘法的原因,所以体现了一种并且的关系,一旦有一个因子为0,则整个分数就会是0。

分数系统是一种模糊逻辑,他不像基于规则的系统那样逻辑非常清楚,所以,在分数系统中,有时会出现一种“意外点”,但对AI来说,出现一些意外点,也不是不可接受,有时这样也更显得AI很真实,AI也会犯错的嘛。一旦使用了分数系统,debug的过程就变成了不断调整公式和数值的过程。如果设计的好的话,AI程序员可以提供出一套调节分数的接口,这样design也可以参与其中了。

当然,有时分数系统是会和规则系统联合使用的,用来处理一些意外情况。我常觉得,在AI中,规则系统就是用来修bug的。

好了,就聊到这儿,欢迎大家留言

相关:

---> 基于分数系统(Scoring System)的AI设计(1)

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

最近在做的一个AI用到了分数系统,这次就来和大家聊聊这个话题。

先来设计一个场景,有一个单兵作战的士兵,在丛林中,他有一些基本的行为,比如射击(shoot),移动(move),撤退(retreat)。他必须结合很多因素来决定自己的行为,比如,敌人的数量,自身的情况,弹瑞脑消金兽药的情况,环境的情况等等,我们现在就来为这个士兵写AI来模拟他的行为。

AI常常用到一些if-else的逻辑判定(这种方式,在AI中叫基于规则的AI,Rule-Based System),对一些简单并且确定的逻辑,这种方式十分的便捷有效。但在上面这个场景中,如果单纯的用if-else,会使代码很快变的杂乱和难以维护,我们可以试着写一下,假设我们需要考虑以下两个个要素:

1. 敌人的数量(Enemy Count,EC)
2. 自己的负伤程度(Hit point,HP,用0~100来表示)

我们定义以下规则

规则1. 如果 EC = 0,那么 Move
规则2. 如果 HP < 30,那么 Retreat
规则3. 如果 EC > 4,那么Retreat
规则4. 如果 0< EC <= 2 并且 HP >= 30 那么 Shoot
规则5. 如果 2< EC <= 4 并且 HP > 70 那么 Shoot
规则6. 如果 2< EC <= 4 并且 HP <= 70 那么 Retreat

这些规则可以转换成相对应的if-else,但这样一个简单的情形(两个条件,三个结果),我们就需要6条规则来描述,如果我们需要其他一些考虑因素,比如,弹瑞脑消金兽药,环境,那用这样的结构就很难维护了。对这种多因素判定的情况,我们就可以尝试用分数系统来做。分数系统的一个基本思想,是为每个单独的行为打分,根据分数的高低来决定做哪个行为,而所有的因素就是打分的依据。上面这个场景中,我们有三个独立行为,在每次的AI选择中,我们来为这些行为打分,下面我们来试着把这个士兵的AI用分数系统来做:

假设我们的分数是从0~100,Clamp(v, l, h)是指如果v<l,则v=l,或者如果v>h,则v=h,Max值取两者较大的那个值

1. Move:   s = Clamp(100*(1 - EC), 0, 100)
2. Retreat:s1 = Clamp(100 - HP, 0, 100)
s2 = Clamp(25 * EC, 0, 100)
s = (s1 + s2)/2
3. Shoot: s1 = Clamp(HP, 0, 100)
s2 = Clamp(100 - 25 * Max(EC, 1), 0, 100)
s = (s1 + s2)/2

我们来做一些测试:

1. HP = 60, EC = 2
Move(0), Retreat(45), Shoot(55) --> Shoot
2. HP = 20, EC = 1
Move(0), Retreat(52.5), Shoot(47.5) --> Retreat
3. HP = 100,EC = 5
Move(0), Retreat(50), Shoot(50) --> Shoot or Retreat
4. HP = 70, EC = 0
Move(100), Retreat(15), Shoot(72.5) -->Move

有上面的测试可以看出,大部分还是能符合我们预先定义的一些规则……

(待续)

ps: 本来想一下写完了,可是太晚了,最近身体不是很好,要早点休息了,明天再补完

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

C/C++一般函数只能返回一个返回值,要返回多个返回值,比较常用的一个办法可以传指针或者引用的参数进去,通过参数返回,还有一个办法,其实也很简单,就是返回一个structure出来。

struct stRet
{
retValue1;
retValue2;
....
}

stRet ReturnMultipleValueFromFunction()
{
stRet r;
...
return r;
}

这种方式没什么技术含量,但可能会被忽视,好处是代码很清晰,不用跟一大堆的参数,不过在效率上会差一点,因为多了copy的过程。总得来说,也是值得一用的。
————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

AI结构中,有一种情况非常容易出现,就是程序员会非常希望有一块区域,大家可以读取,存储一些信息,并且这块区域是全局共享的。不管是写作看似丑陋的全局变量,还是有一定组织的Blackboard结构,或者作为参数一路传到底,这种结构可以被统称为共享数据(Share Data)。作用就是在不同的模块间传递变量。

共享数据的需求,从某种程度上说,源自程序员的一种”偷懒“(当然这里没有任何贬义),试想一下,一块可以非常方便,存我想存的,读我想读的结构,一块非常松散且容易理解的结构,一块非常容易架构(或者几乎不用架构)的结构,相信很多人都会作为第一选择吧。确实,共享数据的优势很大,很有吸引力,在开发中,可以作为很多问题的解决方案,几乎在所有的引擎中,都或多或少存在着一些共享数据的模块。

在网上的很多文章里,探讨了多种共享数据的结构,OO开发,使得这种结构多了更多的灵活性,不再是以前一个structure走天下了,比如前面说到黑板系统,这个可以说是现在AI中经常会用到的结构,在FEAR的GOAP里就用到了Blackboard,用作在Planner间作数据共享(以后可以写篇文章介绍一下GOAP,我非常喜欢的一个AI架构)。但不管这么样,共享数据的本质还是相同的。

共享数据是一种优点和缺点同样明显结构,下面我们来看看它的缺点

首先,就是共享数据很容易乱,这是伴随它的随意性而生的,共享数据的内容会随着开发进程不停的被修改,或添加新的变量(这种情况居多),或删除冗余的变量(由于开发过程是多人协作的,所以,非常有可能的一种情况就是存在两个作用完全相同的变量,只是因为是不同的人加的),如果没有好的维护和清理,共享数据就会逐渐变成”垃圾堆“ -- 随便说一句,这也是我对共享数据的昵称

其次,共享数据会比较难debug,因为修改和读取都是匿名的,也就是说,谁也不知道,谁会在什么时候修改什么变量!这会导致变量被莫名修改,当然,加数据断点,或者好的统一入口,会使情况有所改善。

还有,共享数据很容易造成程序员对他的依赖,会认为任何变量都可以存在其中,而忽视了对本身模块的架构,在某些情况下,它会成为解决问题的最后一棵稻草,问题是,共享数据可以是,但不能每次都是!

sharingdata-1

像我写的标题,”黄金屋“还是”垃圾堆“,不取决于共享数据本身,而是取决于,我们如何去实现,如何去维护,如何去规范,如何去使用。想到这个问题,也源自我最近一段时间的实践和体会,作为一个新的系列的开始吧,下一篇,写点我对架构共享数据模块的想法。

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

【游戏篇】

0. 我的游戏引擎核阅读心得:找到Update,就找到了一切!

1. 找到游戏主循环:游戏主循环是游戏的核心所在,所以找到主循环至关重要,有几个办法,如果代码是可运行的(一些时候,代码连编都编不过),那比较简单的就是加断点(其实很多时候,都可以用加断点的方式来辅助阅读),这样callstack一看就找到了。如果不能运行,一个办法是从Main函数开始找,还有一个办法,是先找到一个模块,比如input的update函数,然后再顺着往上找。还有一个讨巧的办法,就是搜关键字,比如MainLoop。

2. 熟悉游戏的模块:游戏引擎总有一些常见的模块,比如input,animation,AI,network,sound,render,physics等等,这些模块就是游戏引擎的核心,可以先在引擎里找到这些模块的Tick或者Update函数,由update开始逐渐深入到各个模块的具体运作。看游戏引擎,一般只会挑自己感兴趣的看,因为引擎的东西实在太多,太杂,不可能都去了解。所以一定要有所取舍。

3. 要不求甚解:游戏引擎里面包含了各种技术,每个部分都有很多精彩的东西,但在通篇阅读的时候,有些可以跳过,也就是,只要知道他干吗的就可以了。最好的例子就是math,一些引擎的math实现相当厉害,但对我们来说,只要知道,vector,matrix等等怎么用就可以了,其内部实现,优化方法等完全不用去了解(除非你想学习)。我想到一些游戏中可以不用去了解的部分:基本数据结构(array,list等),math,thread部分,time,memory(但如果要优化内存,或者有bug,就需要看),一些类型的封装(smartpointer等),ScriptSystem(游戏中有时会自己实现一套虚拟机,可以无视)等等

4. 数据的重要性:游戏中的数据十分重要,比如你看AI部分代码,很有可能很多定义都在数据中,如果单看代码会十分难以理解,比较好的就是结合引擎提供的editor来看,先用editor改一下数据,然后再在代码里看相应的代码。还有,现在的游戏引擎很多都用了Script,比如lua,或者游戏自己的Script,比如Unreal,这时候,就要在script和引擎两头转,如果引擎没有提供很好的工具,确实相当麻烦,我到现在还没找到一个很好的办法来解决这样的问题,

5. :阅读游戏引擎需要一点经验,经常会边猜边读,猜的过程,就是一个使用以往经验的过程。总的来说,游戏中用的技术有一定的通用性,虽然名字或叫法可能不同,但基本思想还是一样的,又要举一个我比较熟悉的AI的例子,比如,FSM,有限状态机,看到代码里有类似的名字,那我就能大致了猜到这段代码的实现方法了。

好啦,写了这么多,基本把我想到的,学到的都做了一个梳理,我一方面上班会看一些代码,现在在业余时间也在研究doom的源码(以后可以写个Doom阅读笔记系列,再次崇拜一下伟大的Carmack),还在维护一个游戏引擎(TsiU),可以说,对游戏引擎的积累也慢慢加深,这里share一些东西,也算一个总结,我也是个Game界的newbie,欢迎大家讨论,批评指正。

相关:

---> 阅读代码的一些心得(1)(工具篇)
---> 阅读代码的一些心得(2)(通用篇)

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

【通用篇】

0. 我的一句话心得:“看代码有时候和阅读外文文章一样,先泛读,了解文章大意,再精读,了解单词语法。”

1. 了解代码的命名规则:代码一般都有自己的命名规范,比如cl打头表示类,E打头表示枚举,函数名前会带返回值类型等等,掌握这些命名规则,可以很方便的知道这个变量或函数的信息,加快看代码的速度,另一方面,对再开发也有很多好处,因为再开发一定要遵守代码中原有的命名规范,我想这也是程序员不成文的准则之一吧

2. 遍历工程结构:在实际看代码前,最好先看看他的solution结构和工程属性,包括哪些工程是lib,哪个是startup proj,工程和工程间的关系是什么。另外,看工程结构也可以大致了解代码中包括了哪些部分,有的项目是以工程来分的,有些是在一个工程中,用folder filter来分的。

3. 以main函数为开始点:和程序运行一下,看代码也可以从main函数开始,一般main函数会分为几个部分:初始化,主逻辑,销毁。初始化可以快速的了解代码中有哪些模块,主逻辑为今后阅读重点,销毁部分基本可以不care。另外,一些库的源代码,可能没有main函数,那就可以结合lib提供的Sample逐渐深入。

4. 拆分代码:一般代码是一个有多个部件组成的,阅读时需要拆分,比如win32窗口程序,一般是控件驱动,大部分的feature代码都可以在处理控件的消息中找到相应的线索,所以就可以按照控件的功能来阅读,逐步到具体实现方法,再比如stl源码,因为本来各个部件就比较独立,就可以按照头文件的分类逐步阅读。

5. 关心值得关心的:代码中有很多无用的信息,比如打印debug消息,profile,assert等等,代码中可能还有很多被称之为guard的代码,就是保护代码,也可以无视。当然,要从一大堆代码中取其精华,去其糟粕,需要一定的经验积累。

6. 用写者的角度思考:阅读代码,必须一直想几个问题,“如果是我,我会怎么实现?”,“作者为什么要这样写”等等。因为看代码如同阅读别人的逻辑思维,只有投入和思考后,才能产生共鸣。

(待续)

相关:

---> 阅读代码的一些心得(1)(工具篇)

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

一般游戏代码的量都是相当惊人的,在开始做项目的时候,特别是porting项目,都会阅读引擎代码,所以阅读代码的能力确实不可或缺。在进公司后做的第一个项目,我看代码的能力有了很大的提高,记得第一个项目的引擎代码有180万行,我和一些新进的同事,足足研究的了3个月,收获颇丰,后来也陆陆续续的看了多种引擎的代码,有一些心得,和大家分享,有些有可能和游戏相关,不过大体都比较通用。我将分为工具篇,通用代码篇,游戏专用篇来写。

【工具篇】

0. 我选工具的宗旨:尽量使用开源或者免费的工具,工具尽量轻量化。

1. 找一个好的阅读代码的工具:好的工具的基本标准是可以支持类,函数,变量的跳转等,现在的项目大多都用VS创建,所以VS一般就是首选,2003的话需要辅助VAssist,2005本身功能就比较强,就不太需要另外的插件。如果有两个显示器,或者显示器比较大,可以推荐SourceInsight。

2. 找一个好的UML的工具:现在代码大多是OOP,很多类的层次结构相当复杂,所以画UML图的方式就可以非常方便的理清各个类之间的关系,UML有很多内容,我一般就画一下类图,UML的工具也很多,推荐starUML,这个是开源的,而且非常轻量化,相当好用,其他诸如,Visio,RationalRose,也都可以。很多人也许习惯用纸和笔来画,虽然这样很快,但我觉得,这种方法比较不利于文档化和共享。

3. 用wiki来记录:wiki对于阅读代码来说是一个非常好的share和文档化工具,特别是有很多人一起看一个代码时,优点尤其明显。在阅读代码的过程中,可以在wiki上写一点notes,这样其他人在看到这部分代码时,就不用重新去理解代码内容,而可以结合你写的notes来辅助阅读,这样就大大节省了时间,到最后,整个wiki里就成了这个项目的文档,一举两得啊。我在一个项目里用过这个方法,效果相当不错。推荐几个pmwiki(开源,并且不需要额外的数据库),mediawiki(开源)。

(待续)

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More