(原创)基于目标的决策系统 1

基于目标的决策系统

　　　　　　　　　　　　　　　　　　　　　　白礼彬，蔡孝府，唐坤

一.    概述

基于目标的决策系统又称为规划体系结构，它以环境状态作为输入，通过需求分析和机会分析，最终根据形成的目标制定行为规划。然后角色通过执行这些行为来改变周围的环境。规划体系结构与人们思考问题的方式非常接近，使游戏开发者能很容易地利用规划构造AI ，并且该系统具有很多优点：能根据环境的变化主动地做出反应，可以有中期目标和长期目标，根据目标主动选择合适的行为。

为了实践该AI决策系统，我们模仿盛大的泡泡堂游戏构造了一个真实的游戏环境，游戏玩法与其基本相同（玩家可以通过键盘控制角色移动，放置炸弹，拣宝物等）。不同的是，这里增加了电脑对手，即基于目标决策系统的AI智能体。它们也能像人一样进攻，逃跑，躲避爆炸，拣物品等，甚至比人类玩家根据有挑战性。以下是游戏的相关截图：

二.    原理分析

图1 游戏截图

每个Agent都有一个任务队列，此队列是一个按照任务优先度从大到小排序的。和Windows操作系统不同，这里是数值越大优先级越高。但是每个Agent都有一个固定的任务EscapeTask()(逃跑任务)，在Agent初始化的时候就插入到了每个Agent的任务队列中，初始时设置的优先级为0。当仲裁器在制定的位置初始化了4个Agent后，便对其插入攻击任务。如图1。

Pa和Pb属于队伍1，Pc和Pd为队伍2,因此，促使化后Pa和Pb的任务队列里面就有(EscapeTask(),AttackTask(Pc),AttackTask(Pd))三个任务，Pc和Pd里面就有(EscapeTask(),AttackTask(Pa),AttackTask(Pb))三个任务。

当其中一Agent发生死亡的时候，仲裁器就通知所有的Agent这个消息。每个Agent对这个消息做相应的处理。如：Pc死亡。仲裁器就将消息发给Pa Pb Pd,其中Pd与Pa是同一队伍，因此Pd不受理这个消息，而Pa和Pb则将任务队列中的AttackTask(Pc)任务删除。

当一个物品产生或者物品消失的时候，仲裁器也将这个消息发给每个Agent。如：item1产生了，PaPbPcPd则相应的插入FeachItemTask(item1)这个任务。

在每一桢，每个Actor都会更新每个任务的优先级。如FeachItemTask的优先级计算公式是abs(100-(Agent.Pos.x+Agent.Pos.y))。也就是离item距离越近，FeachItemTask的优先级就越高。攻击任务的优先级也会随攻击对象的距离减小而增加。每一个游戏帧，Agent都会选优先级最高的任务来执行。

图2  A*搜索路径

程序中的A*，由于场景中有大量的障碍物，因此有必要对障碍物或者通路设定不同的代价，使得Agent能够选出一条代价相对较小的路径。如图2，中间那个Agent需要攻击右边那个对手。A*搜索出了红线的路径，这条路径只需要炸掉3个木箱。A*会优先考虑代价小的路径，即空旷的路径。然后再考虑代价稍微大些的木箱。由于通过石头的代价设得非常地大，所以A*的算法根本不会去考虑石头。A*的具体算法实现这里不作介绍。

图3 炸弹的爆炸范围及剩余时间

上图为爆炸范围,阴影区为剩余时间。当Agent处于爆炸范围中。如何计算该往哪里躲避呢？首先算法先做一个地图备份VirtualMap,这个地图只用于计算躲避路径，并为了算法的需要需要在VirtualMap上做很多的标记。在计算后就将其释放掉。为了在逃跑时找出一条最近的路径，这里使用BFS寻路算法。如果使用A*则很可能找出的路径不是最近的。而BFS算法能绝对找到一条最进的路径。BFS从Agent周围向外辐射方式搜索。同时每计算一圈，地图上的所有剩余时间就减一。如果扩展到的那点剩余时间已经减到零了，说明当走到那里的时候已经爆炸了。这点就丢弃。安全地点有两种，一种是爆炸无法涉及，并且可以安全到达的区域，称为安全点。另一种是相邻两个爆炸区域的剩余爆炸时间大于等于三，剩余时间大的那个点称为半安全点。

如何确定安全点与半安全点的安全系数呢？首先要保证所有的安全点的安全系数要大于半安全点的安全系数。因为在某些极端情况下，半安全点是非常不信的。然后就是离Agent越近的安全系数越大，对于半安全点，相邻两个区域的剩余时间差越大，越安全。

然后返回安全系数最大的点。作为将要逃离到的躲避点。

当然也有可能完全计算不出能够躲避的区域，这时假设附近有敌人就和敌人同归于尽。

在安炸弹之前首先要计算安了炸弹之后是否能安全逃离。否则如果安炸弹自己却跑不掉，这个AI就是非常失败的。这时还是要用到VirtualMap。1、首先将地图信息复制到VirtualMap中。2、在VirtualMap中的自身位置处插入一个炸弹（只是在VirtualMap中插入，不在实际地图中插入）。3、然后计算炸弹之间的关联。因为BombA炸弹的爆炸范围如果涉及到了BombB炸弹的爆炸范围，假设B要10帧才爆炸，A在2帧后就爆炸。那么A会引爆B，B也会在2帧时爆炸。4、按照上面计算安全地点的BFS方式搜索安全地点，如果找到安全地点则安置炸弹。半安全地点或者没有能够可能躲避的地点则不安置炸弹。因为半安全地点并不可靠。

三.    总体设计

该游戏主要分为驱动模块，图像模块，逻辑模块，控制模块，游戏模型模块等

驱动模块：驱动游戏的图像，逻辑，控制模块执行，对游戏进行总控制

图像模块：采用微软DirectX9.0 的ddraw进行绘制，负责游戏画面显示

逻辑模块：分为PlayerActor（人控制）和AIActor（AI控制）两个部分，负责游戏逻辑处理和AI决策系统运算等

控制模块：接受键盘和鼠标输入，用于控制PlayerActor的动作和菜单命令接受等

        游戏模型模块：包括游戏地图，炸弹，障碍物等，对Actor移动，炸弹爆炸等进行计算，修改地图等物理环境。

系统结构图：

四.    详细设计

1， 驱动模块：

这里为GameEngine类，负责游戏初始化，即图像，逻辑，控制等模块的执行。

//游戏主引擎类

class CGameEngine

{

public:

    CGameEngine();

    ~CGameEngine();

    void run();                                  //执行函数

    void init(HWND _hwnd,HINSTANCE _hinstance) ; //初始化

private:

    void runGraphic();                          //图像执行函数

    void runLogic();                            //逻辑执行函数

    void runPhysics();                          //物理执行函数

    CMessageManager* m_pMessageManager;        //消息管理器

    CModel*  m_pModel;                         //模型

    int m_CycleTime;                           //周期执行时间

    CGraphicEngine      m_graphicEngine;      //图像引擎

    CDisplayBackGroud   m_displayBackGroud;   //显示表面   

    DXSound::CDirectSound   m_soundwave;      //声音

};

2， 图像模块：

3， 逻辑模块：

分为PlayerActor(人控制)和AIActor(AI控制)两部分：

1）  PlayerActor

由玩家控制，将接受到的键盘消息（上，下，左，右，空格）进行处理，作出响应，更新相应的图片序列，安放炸弹等。

        //玩家控制角色

class CPlayerActor:public CLogicActor

{

public:

    CPlayerActor(CModel* _model, CMessageManager* _MsManager,int& _id,const Pos& _pos,int& _camp);

    ~CPlayerActor();

    void run(); //执行函数

    void initial();

private:

    void dealAction(); //处理动作消息

};

2）  AIActor

4， 控制模块：

负责处理鼠标和键盘输入消息，做出PlayerActor的相应动作及处理菜单消息。

/控制类

class CControl

{

public:

    CControl();

    void run(); //执行函数

    ENUM::ActionType getAction()const { return m_Action;} //取得移动消息

    bool getIsSetBomb()const { return m_isSetBomb; } //是否在安炸弹

    //复原

    void resetAction()

{

        m_Action = ENUM::NoAction;

        m_isSetBomb = false;    

    }

    void clearKeybroadMessage(); //清空多余的键盘消息

private:

    ENUM::ActionType m_Action; //玩家移动动作

    bool m_isSetBomb;          //是否在放炸弹

    int m_LastTime;        //上一次按键消息时间  

    void checkKeyborad();  //检测键盘消息

    bool checkDelatTime(); //检测是否到间隔时间

};

五.    结论

对游戏开发者而言，规划是一个功能强大的攻击，可以提高游戏质量，并增加游戏真实感程度。在游戏中使用基于目标的决策系统结构可以使AI具有更强的能力和适应力，这里展示的游戏已充分说明了这一点，不过要用于商业游戏还有很长的一段路要走。

    当然基于目标的决策系统也有自身的一些弱点，如需要游戏设计者全方位考虑游戏中的所有可能，相对于if else之类简单逻辑判断较为复杂和低效。

/**//////////////////////////////////////////////////
// Content:  角色控制类 函数定义
/**//////////////////////////////////////////////////
#include "exception.h"
#include "CActor.h"
#include "CPlayerActor.h"
#include "CAIActor.h"
#include "CMessageManager.h"
#include "CModel.h"
#include "CGraphicActor.h"
#include "CPropertyManager.h"
#include "CMap.h"

//构造函数
CActor::CActor(int _camp, int _ID, ENUM::ActorType _type, CModel* _model, CMessageManager* _MsManager,const Pos& _pos,
                    LPDIRECTDRAW7 _lpdd,LPDIRECTDRAWSURFACE7 _animDest,char *filename)
:m_Camp(_camp),m_ID(_ID),m_Pos(_pos),m_Type(_type),m_pMsManager(_MsManager),m_State(ENUM::Alive),m_pModel(_model),m_LastUpdateTime(0)
...{
    m_pGraphic = new CGraphicActor(_model,m_Pos);             //对图像BOB进行初始化
    m_pGraphic->BOBSurInition(_lpdd,_animDest,_type,filename,
              _model->m_pMap->getBOBDisplayWidth(),_model->m_pMap->getBOBDisplayHeight());

    if(_type == ENUM::PlayerActor)
        m_pLogic = new CPlayerActor(_model,_MsManager,m_ID,m_Pos,m_Camp);
    else
        m_pLogic = new CAIActor(_model,_MsManager,m_ID,m_Pos,m_Camp);    
}

//析构函数
CActor::~CActor()
...{
    if(m_pGraphic == 0 || m_pLogic == 0)
        throw Exception("~CActor(), m_pGraphic||m_pLogic ==0") ;

    delete m_pGraphic;
    delete m_pLogic;
}

//图像执行函数
void CActor::runGraphic()
...{
    m_pGraphic->run();
}

//逻辑执行函数
void CActor::runLogic()
...{
    m_LastUpdateTime++;

    if(m_LastUpdateTime == m_pLogic->getUpdateVelocity()) //检测是否到更新时间
    ...{
        m_pLogic->run();
        m_LastUpdateTime = 0;
    }
}

//处理消息
void CActor::dealMessage(MS::CMessage* _ms)
...{
    switch(_ms->m_MsType)
    ...{
    case ENUM::Move:
        ...{
            MS::CMessage_Move* ms = dynamic_cast<MS::CMessage_Move*>(_ms);
            m_Pos = ms->m_To; //修改坐标
            m_pGraphic->receiveMessage(_ms); //发给图像模块    

            //检测是否有物品
            if( m_pModel->m_pMap->judgeElem(m_Pos,ENUM::Property) )
            ...{                
                //取得物品
                const CProperty* pProperty = m_pModel->m_pPropertyManager->GetProperty(m_Pos);
                dealProperty(pProperty); //处理                
                m_pModel->m_pPropertyManager->DelProperty(m_Pos); //删除物品            
            }
            break;
        }
    case ENUM::SetBomb: //放炸弹
        ...{
            MS::CMessage_SetBomb* ms = dynamic_cast<MS::CMessage_SetBomb*>(_ms);
            m_pGraphic->receiveMessage(_ms); //发给图像模块                
            break;
        }
    case ENUM::BeBomb:
        ...{
            MS::CMessage_BeBomb* ms = dynamic_cast<MS::CMessage_BeBomb*>(_ms);
            m_State = ENUM::Besiege;  //被困            
            m_pGraphic->receiveMessage(ms); //发给图像模块
            //注册被困消息
            m_pMsManager->registerMessage(ENUM::ActorMessage,new MS::CMessage_Besiege(this) );
            m_pModel->m_pMap->addElem(ms->m_Pos,ENUM::BesiegeActor); //修改地图
            m_pModel->m_pMap->addElem(ms->m_Pos,ENUM::Access);
            
            break;
        }
    case ENUM::msBesiege: //有人被困
        ...{                        
            m_pLogic->receiveMessage(_ms); //发给逻辑模块
            break;
        }
    case ENUM::Die: //死亡
        ...{                        
            m_pLogic->receiveMessage(_ms); //发给逻辑模块
            break;
        }
    case ENUM::AppearProperty: //道具出现
        ...{                        
            m_pLogic->receiveMessage(_ms); //发给逻辑模块
            break;
        }
    default:
        break;
    }
}

//处理吃物品
void CActor::dealProperty(const CProperty* pProperty)
...{
    m_pLogic->dealProperty(pProperty);
}