Maxice

Game Development and Design

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  10 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

2010年2月24日 #

     摘要: 阅读: 13 评论: 0 作者: Maxice 发表于 2010-02-24 10:53 原文链接介绍  自Doom游戏时代以来我们已经走了很远。 DOOM不只是一款伟大的游戏,它同时也开创了一种新的游戏编程模式: 游戏 "引擎"。 这种模块化,可伸缩和扩展的设计观念可以让游戏玩家和程序设计者深入到游戏核心,用新的模型,场景和声音创造新的游戏, 或向已有的游戏素材中添加新的东西。大量的新游戏根据已...  阅读全文
posted @ 2010-02-24 10:53 Maxice 阅读(232) | 评论 (0)编辑 收藏

阅读: 4 评论: 0 作者: Maxice 发表于 2010-02-24 10:47 原文链接

介绍

  很多游戏都允许玩家捡取、携带、使用、买卖、丢弃、饮用,穿戴各种物品。这绝对是个庞大的系统,里面有太多需要关联的东西。在这篇文章中,会展现一个基础的物件管理系统给大家。


系统构架

  面对的第一个问题是如何将物品信息对应到各自的身上:比如血瓶有它的名字、外观以及属性;某些物品拥有特定属性,如数量、魔法属性、个性名字,磨损度等等,而且这些属性有可能是在稍后被添加的。

  那么,我们用类cItem来表示某一个物品。这个类包含了一个可以表示物品类型的标示。如果我们需要获得某个物品的属性,可通过cItemDatabase来获得,这是个物品数据库,它中包含所有物品的信息。

  因为物品会出现在不同的地方,,比如在地上,在交易中,或是玩家的背包里,我们要展现这些物品,就需要一个集合来统一表现,类cItemPack就是物品的集合,我把它翻译成物品包,你可以遍历这包中的物品,添加或移除他们。


物品

  第一步,我们来实现物品类,这是我们所用功夫最多的地方。首先考虑物品属性,他应该拥有如下属性:
可以设置到另一个物品上
和另外一个物品对比(看他们是否一样)
物品的指针
可以返回其唯一的ID
可以创建一个拥有唯一ID的物品
根据ID排序

现在我们得出了如下类定义:
class
cItem {
   
unsigned long
type;

public
:
    cItem(
unsigned long
);
    cItem &
operator= ( const
cItem & );
   
bool operator== ( const cItem & ) const
;
   
bool operator< ( const cItem & ) const
;
   
unsigned long getID( ) const;
};

上面的类有一个构造函数(参数ID),指针,比较操作,获取ID的函数。私有成员变量是物品的ID,通过这个ID可以从数据库中得到该物品的属性。

  这里要注意的是,const关键字出现在很多地方,在编程中要养成这种好习惯(具体作用大家都知道,呵呵)。通过const修饰,当cItem变得很大的时候,可以增加更多的安全性。

下面是实现:
cItem::cItem( unsigned long
t ) : type( t ) { }
cItem &cItem::
operator =( const cItem & o) { type = copy.type; return( *this
); }

unsigned long cItem::getID( void ) const { return
( type ); }
bool cItem::operator ==( const cItem & i ) const { return
( type == i.type ); }
bool cItem::operator <( const cItem &i ) const { return( type < i.type ); }

这个类的基础工作就做完了,可以在上面添加自己所需要的东西。接下来我们来谈谈cItemPack


物品包

用户希望物品包拥有如下属性:
将一个物品放入一个包中
创建一个空包
从一个包中将所有物品移除
添加某一物品到包中
从包中移除某一类物品
计算物品的某种类型
将两个包合并成为一个包

  包中有列表存放物品的类型。以后我们就可以通过列表容器来访问集合中的物品。不过这里的时间消耗为O(n)。

  也可以使用vector来实现,只需要O(1)的访问时间。但如果包中只存在一个物品,那就有点浪费。另外,如果物品很复杂,包含很多属性,或是两个物品有相同类型但不同属性,那么,依靠类型来获得物品,就会出问题,所以我们用map,下面是类定义:

cItemPack类:
class
cItemPack {
    std::map< cItem,
unsigned long
> contents;

public
:
    cItemPack( cItem & ,
unsigned long
);
   
void
clear( );
   
unsigned long add( const cItem & , const unsigned long
);
   
unsigned long remove( const cItem & , const unsigned long
);
   
unsigned long getAmount( const cItem & ) const
;
   
const std::map< cItem, unsigned long > & getItems( ) const
;
    cItemPack &
operator= ( const
cItemPack & );
    cItemPack &
operator+= ( const
cItemPack & );
    cItemPack
operator+ ( const cItemPack & ) const
;
};

  通过getAmount()接口获取物品的数量,可以很方便的展现商品清单等功能。通常cItemPack会表示一个实体,所以获取物品数量的接口是非常重要的。下面是cItemPack实现部分:

cItemPack::cItemPack( cItem & i, unsigned long
a ) { contents[i] = a; }
void cItemPack::clear( void
) { contents.clear( ); }
cItemPack & cItemPack::
operator=( const
cItemPack & o ) {
    contents = o.contents;
   
return
( *this );
}

两个构造函数,一个清除函数,一个=操作:这里没有具体的初始化,构造是依靠传进来的物品。接下来的函数可以向集合中添加某种物品。

unsigned long cItemPack::add( const cItem & i, const unsigned long
a )
{
   
return
( contents[i] += a );
}


下面的函数会返回某一种类型物品的数量,注意,因为map中的[]操作符并不是const,而这个函数的参数却是const,所以必须用map 的const iterator。
unsigned long cItemPack::getAmount( const cItem & i ) const

{
    std::map< cItem,
unsigned long
>::const_iterator j;
   
j = contents.find( i );
    if( j == contents.end( ) ) { return
( 0 ); }
    else { return
( j->second ); }
}


这里我们还需要一个移除函数,代码如下:
unsigned long cItemPack::remove( const cItem & i, const unsigned long
a )
{
   
unsigned long
t = contents[i];
   
if( a > t ) { contents[i] = 0; return
( a-t ); }
   
else { contents[i] = t-a; return
( 0 ); }
}


接下来是两个联合集合的函数:
cItemPack & cItemPack::operator+=( const
cItemPack & o )
{
    std::map< cItem,
unsigned long
>::const_iterator i;
   
for
( i = o.contents.begin( ); i != o.contents.end( ); ++i )
    {
        add( i->first, i->second );
    }
   
return
( *this );
}

cItemPack cItemPack::
operator+( const cItemPack & o ) const

{
   
return( cItemPack(*this) += o );
}


最后,将map的接口提供出来:
const std::map< cItem,unsigned long > & cItemPack::getItems( void ) { return( contents ); }


物品数据库

  我们在这里制定的物品都有名字,有简短的描述,以及值和重量,他们保存在下面的结构中:

struct sItemData {
    std::string name, description;
   
unsigned long
value, weight;
};


  我们使用monostate来表现这个数据库,这个对象类似单件,只存在一份,不过不能直接进行全局访问。

下面是该对象的定义:
namespace
cItemDatabase {
   
const sItemData & getData( const
cItem & );
    cItem create(
const
std::string & );
   
void initialize( const
std::string & );
   
void unload( void
);
};


第一个函数是获得物品数据
第二个是创建一个物品,参数是该物品的名字

  不过这里需要注意的是,用这些函数操作物品的时候,都必要要保证被操作的物品是已经被初始化的。不过要注意的是,如果操作失败的话,这里并没有一个返回错误的机制。第二,创建函数在创建物品的时候,并没有判断穿过来的物品名是否有效;第三,用户在获取某一个物品时,如果该物品并不存在于数据库中,同样没有一个返回错误的机制来通知用户。那么我们现在来创建一个返回错误的机制:

enum
eDatabaseError {
    IDBERR_NOT_INITIALIZED,
    IDBERR_INVALID_NAME,
    IDBERR_INVALID_ITEM
};


这是数据库的定义:
namespace
cItemDatabase {
    std::deque< sItemData > item_database_entries;
   
bool item_database_initialized = false
;
};


Deque用在这里的好处就用不着再讲了。呵呵,看老外一大段都是废话我就懒得翻译了。接下来是实现:

void cItemDatabase::initialize( const
std::string & s ) {
    item_database_entries.clear( );
   
//FILE LOADING SEQUENCE

    item_database_initialized =
true;
}

void cItemDatabase::unload( void
) {
    item_database_entries.clear( );
    item_database_initialized =
false
;
}


这里并没有具体的调用数据文件的代码,大家都会有自己的一套机制。本文提供的源代码里有作者的一套调用系统,大家可以参考。

getData函数的实现:
const sItemData & cItemDatabase::getData( const
cItem & i ) {
   
if
( item_database_initialized ) {
      
 unsigned long
type = i.getID( );
       
if
( type >= item_database_entries.size( ) )
        { throw IDBERR_INVALID_ITEM; }
       
else { return
( item_database_entries[type] ); }
    }
   
else
{ throw IDBERR_NOT_INITIALIZED; }
}


创建函数的实现:
cItem cItemDatabase::create( const std::string & s ) {
    if( !item_database_initialized ) { throw IDBERR_NOT_INITIALIZED; }
    long i;
    for( i = item_database_entries.size( )-1; i >= 0; --i ) {
        if( item_database_entries[i].name == s ) { return( cItem(i) ); }
    }
    throw IDBERR_INVALID_NAME;
}

评论: 0 查看评论 发表评论

找优秀程序员,就在博客园


最新新闻:
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报:QQ的平台化价值是如何创造的?(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐:史上最强女游戏程序员

网站导航:博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

posted @ 2010-02-24 10:47 Maxice 阅读(282) | 评论 (0)编辑 收藏

阅读: 15 评论: 0 作者: Maxice 发表于 2010-02-24 10:45 原文链接

摘要:
制作一个3-D游戏引擎并不是一件很简单的任务,因为现在的游戏玩家常常要求在游戏中有着高性能和高质量的输出。在这篇文章中,我们向大家展示了多种实时渲染的算法如何用来在一个实际的3-D游戏引擎中提高性能。我们探究了一个通用的3-D游戏引擎的结构并且讨论了在3-D游戏引擎中的视景图像的任务。我们将从软件工程的角度来研究视景图像,我们将向你展示一种面向对象的和可以方便的通过不同渲染引擎来设计的视景图像。接下来,我们解释了在我们的3-D游戏引擎中用来提高引擎性能的算法。我们在视景图像和物体几何层面上对我们的3-D游戏引擎进行了优化。我们提出的算法在静态和动态的场景中表现的都是相当的好。最后,我们用多处理器在视景图像方面用并行处理的方式来建立个3-D游戏引擎方面作了一下简单的展望。

一、介绍:

在过去的十年里面,计算机游戏行业经历了巨大的增长的黄金时期。在过去的几年里,随着3-D加速硬件设备的飞快的进步,游戏制造行业都将焦点集中在用创新的思想来生产交互式的3-D游戏。3-D游戏引擎是驱动这些游戏的核心技术。简单的来讲,一个3-D擎获得游戏中的3-D物体的几何数据并将这些数据展示在显示设备上,典型的显示设备就是显示器。这个过程就是我们通常所知的渲染。3-D物体的几何数据通常通过一系列的顶点来定义,物体的具体特性(象漫射的颜色,镜面反射以及发射出的颜色等),纹理图,纹理匹配以及一些常用的向量。所有的这些数据在3-D游戏引擎处理途径中经历不同的阶段来决定着这些3-D 物体的最终显示的效果。

图1 一个完整的3-D引擎的处理过程。高层的视景图像给用户一种直觉的方式来模拟一个场景,优化的场景保证了场景对于渲染的高效率。
高层视景图像规定了在游戏中的物体之间的关系,它对于游戏开发者来讲也是在游戏中操纵这些物体的一个应用程序接口(API)。在一个场景被渲染之前,视景图像必须为了渲染而被优化。这种优化处理就是典型的将高层视景图像转变成(编译成)优化的视景图像,这种被优化的视景图像就是用了一种非常适用于渲染的数据结构。这就要求开发者去详细的确定每个物体的“线索”:比如这个物体是静止的还是移动的,物体的结构是否随着时间的变化而变化等等。视景物体剔除就是将观察者不能看到的物体丢弃掉的处理过程,尽管细节层次控制可以将相对于观察着者比较远的一些无关紧要的物体给删除掉。所有这些思想的背后就是减少渲染那些你看不见的东西以及减少远端物体几何数据,为了是将送往最终渲染管线的数据减到最少,这些将会明显的提高渲染性能。这些就是一个3-D游戏引擎为了提高它的性能而所要完成的主要任务。
后续的任务,诸如灯光,视角转换,裁减,投影变换以及光栅化,都是渲染引擎为了完成渲染流程所需要承担的任务。渲染引擎,就是经常提及的立即模式渲染引擎,往往都可以被3-D加速硬件支持。两种主要的适用于PC机的渲染引擎就是微软的Direct3D和Silicon Graphics 公司的 OpenGL。在这种渲染引擎上开发游戏往往是枯燥和耗费时间的,这些引擎所给的程序接口都是些程序性的和面向硬件的。在接下来的部分,我们将在集中在建立3-D游戏引擎的三个主要的模块:(1)为我们的3-D引擎建立高层场景图像;(2)为了建立优化的场景图像的算法;(3)如何丢弃不在观察者视野范围内的物体,并且适当的控制细节层次控制物体。
2.在3-D引擎中的设计问题
视景图像设计由于它直接牵扯到整个3-D引擎的性能所以显得非常重要。它定义了一种让程序员来模拟视景的方式。一个好的视景图像设计应该允许程序员将更多的视景(诸如物体和它们的排列)包含在视景中,并且想到用最好的方式来展现它们,并且可以忽略掉渲染管线的复杂的控制。程序员将通过视景图像的API来设计3-D引擎。
视景图像设计
在视景图像设计中的第一个问题就是要考虑物体的表现。就像我们上面提到的一样,象Direct3D和OpenGl这样的立即模式的渲染引擎均倾向于拥有自己的面向图形硬件的渲染程序功能函数。很显然,这种面向渲染的设计并不适合于完成我们的视景图像的设计的目标。一个面向对象的视景图像设计明显的是一种比较好的程序模式,在这种模式中允许程序员在视景中用对象的概念来设计3-D游戏。我们将所有的游戏对象都当作视景中的3-D对象来对待。Strauss和 Carey已经介绍了完全面向对象的视景图像框架。这个框架的基本的思想就是将3-D视景描述为物体的图像,这种图像成为节点。有很多种类型的节点并且每一个节点都有不同的相关属性。比如说,圆柱形状的节点包含两个参数:半径和高度,但是球状物体仅仅包含一个参数,那就是半径。有一些特定的节点可以包含属于它们的子节点的一些参数。例如,在图2中,描绘了一个汽车的一部分的视景图像。节点组命名为“Body”,它拥有4个子节点来组成汽车的车身。纹理节点包含了定义汽车车身纹理图像的参数。这些参数同样会被命名为“门”的一组节点继承,这些节点用来组成汽车车身的车门。因此,汽车车门将会拥有和车身一样的纹理。通过应用这种方式,我们不仅可以增加资源的可重复利用度,而且也是简单的模拟场景的方式,尤其当我们处理一些视景物体的相对位置时,这种方式显得更有效。变换节点用来描述在父节点下的对象的位置和方向的变换。这些都是相对于父节点的变换。为了得到这些节点的绝对变换(相对于整个场景的变换),当前的这些节点将和它们的父节点的变换相结合(通过矩阵相乘)起来。这样就可以很轻松和简单的一个对象相对与父节点的位置和方向了。这种模型就是通常我们所说的等级场景模型并且是骨骼动画的基础,这种模型通常用来在游戏中的动画的运动部分。

2.2 可移植的视景图形
为了保证我们的游戏能满足尽可能多的玩家的要求,我们必须保证我们的3-D游戏引擎可以在不同的平台和不同的操作系统上运行。因此可移植性是我们设计视景图形的另外一个问题。一个视景图形必须能够在各种目标平台上运行渲染引擎,而且游戏的代码还不能做任何的改动。一个可移植的视景图形必须设计成为不依赖于特殊的渲染引擎才能运行。D鰈lner and Hinrichs 已经讨论了一些实用的方法来归纳不同渲染引擎的特性,并且提议一种可以支持这些系统的通用的视景图形结构。他们确信通过应用一种通用的视景图形,大多数的实时渲染设备都能被整合为单一的不会被凌驾于或是受到一些特殊的渲染引擎的视景图形表示方法。可移植性通过分离的渲染对象和渲染引擎来共同完成。图3就是一个用来证明这种观点简化了的原始的视景图形结构。和前面我们讨论的 Strauss and Carey的工作相类似,一个渲染对象就是在视景图形中的一个节点。多个渲染对象在视景中组织起来就形成了一个完整的视景。D鰈 lner and Hinrichs 将渲染对象扩展到包括不被任何渲染函数支持的2-D和3-D几何对象,除了它们的几何描述;属性包括外观属性(颜色,材质,纹理),变换属性(方向和位置),以及光照属性(不同的光源),这些都是要渲染的细节。在渲染的过程中,渲染引擎将会研究和解释视景图形的内容,计算每个被渲染对象的属性并且将它们转换为与目标渲染引擎相匹配的算法。因此,渲染引擎是唯一的能包含细化一个可移植渲染系统的代码的地方,这些渲染引擎的特殊的算法在整个执行过程中被称为句柄,即每个属性的特例。在渲染的时候渲染引擎将会调用这些句柄的方法。特殊的渲染引擎可以提供优化的引擎执行方法用来扩展底层渲染引擎的特殊的功能函数。在一张大的图片、一些视景图形被描述为可以满足特定规范的参数化的视景。一个视景结构紧紧能为给定的渲染引擎而计算。它的内容可以被不同的渲染引擎解释为不同的目的。
3.在3-D引擎中的优化技术
在这一章中的优化专门的是指用来加速我们3-D引擎的渲染速度的加速技术。优化技术获得视景图形中的对象,并且构建一种特别有利于渲染的数据结构来存储物体的几何数据。这个过程就是通常所说的视景图形编辑。一个完整的优化视景图形应该能够提供对于感光输出结果。Sudarsky and Gotsman 定义了一个在每一祯的运行时间为O(n+f (N))的条件下的感光输出算法,在这里N是在场景里所有对象,n是所有的可见物体,而且f(N)远远小于N。举个简单的例子, 也就是说一个光敏感输出算法的运行时间和可见物体的数量成线性正比关系,而不是和场景中的所有物体成正比。目前共有两种技术能达到这个目的。在物体的几何层次,细节层次控制试图在越远的物体上渲染的越少的数据(也就是物体包含越少的数据)。然而,越靠近观察者的物体越会清晰的呈现它们的完整特性,反之越远的物体看起来越粗糙因为很多精细的细节数据被移除掉了。在场景结构层次,可见性删除技术可以避免渲染观察着看不见的部分。这些物体在渲染之前就被丢弃掉了以便于不把这些数据送到渲染硬件中去。可见性删除技术可以更深层次的分成背面剔除法,视锥体剔除法和遮挡剔除法。简单的讲,背面剔除法就是将背对于观察者的物体的表面被丢弃;视锥体剔除法就是将观察者视角外的物体忽略掉;遮挡剔除法就是试图将从观察者视线内的被其他物体完全遮挡的物体丢弃掉(如图4)。
图4(a)视锥体剔除法将观察者视线外的物体丢弃掉。
    (b)遮挡剔除法将被其他物体挡住的物体丢弃掉。

3.1场景结构优化

为了实现在可见性剔除算法的光敏感输出,它们不能简单的重复计算整个场景中的物体并且决定哪一个是可见的。我们应用一种特定的数据结构来将场景中的物体分组,这样的话,用一个简单的查询,算法就可以一下子决定是接受还是丢弃一组物体。我们还可以建议使用分等级的数据结构来根据物体的位置来将场景中的物体归成几个区域。通过这种方式,如果一个特定的区域被发现是相对于观察者来讲是不可见的或是隐藏的那么大部分的物体将不会被渲染。为了得到这些分级的数据结构场景必须要被预处理。假设这个预处理是非常耗费时间的,那么它必须在初始化阶段被完成。
我们应用混合式八叉树作为空间数据结构来存储3-D引擎中的物体。我们选择八叉树的主要原因是基于我们回顾其他的优化技术,我们优化的场景结构的可适应性可以扩展到不同的算法。八叉树模型用一个立方体顺着三个纬度来一次性的划分空间物体。在每一个阶段,用八个相等的立方体沿着三个轴面上均匀的划分整个场景(xz,xy和yz面)。图5证明在2维视角上验证了这个过程。

图5 一个二维版本的八叉树的四方块的构建。每个面上再递归的划分为四个相等的小的相等的四方块,直到里面的物体为空或是一整个物体。
这样就可以创建一个每个节点都包含有八个字节点的树。通过划分每个物体都会和它所嵌套子节点的的相应的立方体相关联。如果一个物体恰好被一个面所划分(图5 的c),那么这个物体就可以用几种方法来处理。一种方法就是根据与划分面的关系来划分物体,根据物体在他的子节点的所关联的立方体的空间尺度来关联部分物体。分裂算法有点复杂并且这种方法同时也会增加场景中物体的数量。另外一种方法就是将原始的物体既可以与它的父节点相关联也可以与它的装入的子节点相关联。当立方体为空时,或是一整个物体都包含在立方体时就停止向下划分(图5的d)。当算法结束时,实际的物体都会包含在八叉树的叶节点内,每个叶节点会包含少于或是等于指定的物体的数量。

3.2物体的可见性剔除

视锥体剔除法是通过执行观察者视角与装入最大立方体的一系列物体的交集测试来运行的,如果测试失败则将这些物体在最初的阶段裁减掉,否则进行与最小的立方体进行一次最终的测试。八叉树不仅可以很好的应用在静态的场景,同时它也可以方便的应用于动态的场景中。遮挡剔除法算法可以紧接着应用于丢弃掉其他的一大部分不在观察者视线内的物体,尤其对于场景内物体密度比较大的情况更加有效。张提出了一种比较新颖的应用分级的空间图形遮挡地图的遮挡剔除算法。这个算法有两部分测试组成:一个在Z轴方向上的一维度深度测试和两维度的空间图形的交迭测试来共同决定一个物体是否被遮挡住。
对于两维度的交迭测试,一个遮挡表示就是被渲染一系列潜在的很好的遮光板而构建的,这个遮挡在场景结构完成时就被确定了。张还建议一些大的或比较靠近观察者的物体当作比较好的遮光板。这些遮光板被渲染成没有纹理,灯光和开启Z-buffering的一块在黑背景下的一块白颜色的脱离屏幕的图形缓冲。这些操作允许将一些列小的遮光板拼成一块大的遮光板。这个被渲染过的图像就是最高分辨率的遮挡地图,这个方案是基于分级的遮挡地图的。这个层级是通过从最高分辨率向下到最小分辨率一层层递归取样形成的,象图6所示。图形硬件可以用缩小倍率的过滤的双线性插补的纹理映射来加速这个过程。

图6  a 接近建立一个遮挡图的遮光板
(b)在不同级别的分层次的遮挡图
交集测试是通过测试物体是否投影在屏幕空间的范围内,这一点和分层次的遮挡图形的同尺寸的像素对应于相同尺度的边框内的尺寸是不一样的。如果边框内所有的元素与映射的交集为不透明(全白),那么这个算法就认为这个物体是被遮挡的。然而,这个算法会递归的检查比它低一层次的不透明的像素。这个算法独特的一点是比较接近可见性剔除,也就是忽略掉对那些仅通过小洞或是透过遮光物体才能见到的物体的渲染。对于这点,在遮挡映射里像素并不完全等同于全部透明,而是相对于一个透明的阈值(灰度)。这个值越小那么这个算法就越接近于剔除,场景内物体会由于被忽略渲染而导致部分可见。张已经得出了一个计算在层次中的不同等级的阈值的公式。这个特征就好像是增加剔除率,当场景不需要物体被看见事可以通过一些遮挡物的一些小的和一些不是特别清醒的图来代替这个物体。
一维度的Z-depth 是用来检查一个物体是否在遮挡物体的后面。张提议用深度估计缓冲来将屏幕分成一系列的小的矩形区域。对于每个区域,所有的遮挡物体的视线内的最远的顶点的z-value被加入缓冲。深度估计缓冲在每一帧祯都需要建立。在渲染是,如果一个物体的所占的体积的最近的顶点的Z-value要比这个物体所能覆盖的区域的所存储的Z-value都大的话,这个物体才会通过深度测试。为了使一个物体被遮挡,这个物体必须同时能通过用分级的遮挡映射的交集测试和用深度估计缓冲的深度测试才行。

3.3动态物体的优化
为了处理八叉树内的动态物体,最直接的方法就是每次当物体运动是,就在八叉树内把它删除掉,接下来通过插入它的新位置。这并不是最佳的处理方法,因为这样会使我们陷入到频繁修改八叉树的结构。举个例子来说,删除八叉树的节点有时会合并刚刚分开的节点,就像图7所示。另外,它还经常需要一个很长的路径来寻找物体的相对于根节点的插入的新节点。为了避免因为删除和建立节点而频繁更新八叉树,Sudarsky建议仅更新那些具有最少共同祖先的子树的物体的新老位置。(图8)对于一个八叉树很深的大场景,这种方法会很明显的减少更新八叉树的时间,因为LCA要比根节点更加接近叶节点。
为了避免对每个动态物体的每一帧都要更新八叉树的结构,Sudarsky用了一个懒惰计算技术,即我们在一个物体是绝对需要的之前不计算任何事情。这就需要一个与每个动态物体相关联的临时的边界体(TBV)。这个TBV是一个保证在某些特定时间内能包含一个动态物体的边界体。这段时间就是指TBV的有效时间,失效其就是这个时间的最后时刻。现在比较流行的TBV的构建方法往往基于一些物体运动和行为的前期知识。举个例子,sweep曲面可以用作TBV的物体上的边界;如果最大的速度和加速度已知的话,球形也是可以用的。应用这种技术,动态物体的TBV可以用在上述视锥体剔除法的交集测试中。在下列情况下一个运动的物体可以被认为是个隐藏的或是不可见的:(1)它的TBV是可见的,也就意味着物体本身可能是可见的;(2)它的TBV过期了,意味着这个TBV不再保证包含一个物体了。一个优先队列用来存储所有的TBV的过期的数据。为了得到更适宜的性能,我们所关心的有效期必须被关闭。一个适当的算法在大多数环境下都能很好的应对这种情况。如果一个物体在确实被看见之前它的TBV就过期了,也就意味着它的有效期太短并且在下一个TBV中将赋予它更长的有效期。相比之下,如果一个 TBV在它过期之前就被看见了,那么在下一个TBV中将赋予它更短的有效期。


图8)当动态物体被更新是八叉树的节点经常被删掉和建立。
   (a)最初有两个物体的八叉树
(b)一个动态物体从八叉树内被删除
(c)动态物体又被重新插入到新的位置

3.4物体的几何优化
场景物体的几何数据可以通过试图产生代表从不同观察者的距离的物体的不同层次细节(LOD)进一步的优化。这种情况的背后的原因是我们不需要展现所有的完整的物体的数据因为物体距离我们比较远并且在图形上看起来很小。我们只需要展现那些距离观察者比较近的物体的完整数据,这些物体的精细的数据都可以被展现出来。这样就可以明显的减少物体的数据,因为我们只需要发送那些最需要物体到渲染引擎里去。图9证明了一个Stanford兔子在LOD控制下在两个相对于观察者不同的距离下的显示情况。

图9(a)最高细节的原始的兔子模型(35947个顶点,69451个三角形)
(b)相对于观察者比较远的距离情况下同样的减少了LOD的兔子模型
(c)一个扩大(b)的版本,展示给我们一个粗糟的兔子模型(359个顶点,508个三角形)
通过简化物体的LOD控制是一种为了提高我们3-D引擎性能的必须的技术。LOD两个比较出名的简化技术是分数倍采样和聚类方法。分数被采样是在分类的基础上减少顶点、边或是三角形。那些对于整个显示贡献比较少的顶点将被标注为候选顶点。当一个最不重要的顶点被刈除后,剩下的漏洞将被补上。这个过程一直到达到预期的目的后才会结束。在聚类方法中,一组高权重的顶点将被预决定了。靠近这些顶点的周围的一些顶点将被聚类。只有那些权重高的顶点被送到渲染引擎中去,这些顶点都关联着网格的形成。这种方法非常快但是这种简化的方法的质量比较差。
简化算法的保真度可以通过在简化过程中瞄准那些小的共面的网格来得以提高。为了得到这些网格,可以用长度,面积,体积,角度等,来测量每个顶点的其他临近的顶点。当这些共面的顶点被刈除或是被大的三角形代替,多边形的数量减少了,但是物体的形状仍和原来物体相差不多。这样原来的物体将被尽可能多的保留下来。

4.将来3-D游戏引擎

上面我们讨论的所有的算法都是串行的,都是设计运行在一个处理器的计算机上。尽管今天主流的游戏者都在用这种配置,多处理器的计算机是未来工业的一种趋势。现在在多处理器上的3-D引擎算法方面作了很多的研究工作。Rohlf and Helman解释了3-D引擎的不同构件之间如何用不同的并行散发进行优化。他们研究的3-D引擎用多处理技术来划分多个处理器之间的工作,并且用管道来管理数据。他们同时也证明了处理器如何同步在不同环境下它们之间的操作。
Igehy介绍了一个感兴趣的方向将OpenGL程序接口扩展到并行处理上。他的扩展允许多个绘图设备同时来画一张图。最初所包括的同步化是允许并行横行一个明确的有序的场景。在一个24处理器的系统上应用这个程序接口的运行证明了它的有效性。

5.总结
我们已经介绍了一些主要的方面来执行一个实际的3-D游戏引擎。这个引擎的设计是轻便的和有效的,因为它允许游戏程序有效的构建和控制场景对象。我们也强调了很多3-D引擎应用的优化技术。光敏感输出是我们在3-D引擎中所用算法的必要部分。在场景和物体层面为了将对静态和动态物体的渲染性能提高到最大优化是必须要做的。最后,简单讨论了一些额外的用来提高并行处理的3-D引擎性能的源码。

 

评论: 0 查看评论 发表评论

找优秀程序员,就在博客园


最新新闻:
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报:QQ的平台化价值是如何创造的?(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐:史上最强女游戏程序员

网站导航:博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

posted @ 2010-02-24 10:45 Maxice 阅读(78) | 评论 (0)编辑 收藏

阅读: 4 评论: 0 作者: Maxice 发表于 2010-02-24 10:43 原文链接

by Kylinx

一个游戏引擎做好了,最重要的是缺什么?脚本。打个比方,游戏引擎是一部电脑,则脚本就是电脑的软件。既然脚本这么重要,那该怎样实现呢?下面我就来说说我的做法。

首先理解一下消息循环
一个好的游戏离不开好的消息循环。它是游戏实现很重要的一部分。下面我就来说说我的游戏《宿命传说》的做法。

首先,我定义了一个全局变量extern int GameState;
在游戏中定义了许多当前的游戏状态例如

#define GAME_STATE_CUSTOM 0 //这代表在战斗中玩家可以控制游戏
#define GAME_STATE_TALKING 1

等等。
好了,下面在WinMain里面的while(1)循环中有个UpdateScreen()函数

原型为
void UpdateScreen()
{
    延时
    switch(GameState)
    {
        case GAME_STATE_CUSTOM:
            画出地图
            画出所有精灵
            画出天气(如果有的话)
            如果玩家选中了敌人的话(打个比方DrawFlag=DrawEnemyState)就显示敌人的移动范围和敌人状态
        break;
        case GAME_STATE_TALKING:
            GameDialogProc();
        break;
        case GAME_STATE_SCRIPTCONTROLLING:
            ScriptControlProc();
        break;
        ….//其他的消息在这里处理
    }
    将缓冲表面的图象显示到屏幕;
}

每个游戏状态都需要一个独立的函数来写。这样在每次切换游戏状态时都不会出现无法处理的情况。
在处理键盘消息的时候我也用一个个独立的函数来写
如处理回车键我用了 KeyReturnProc()来控制
在这个函数里同样也少不了switch(GameState)这一句,为什么?
答案很简单,比如说在精灵行走时回车键就没有用,这是我没有处理精灵行走这个状态的键盘消息。而在战斗场景里按下回车键,如果有精灵在选择框里的话,就会处理相应的东西。
例如选择了敌人则使DrawFlag=DrawEnemyState;这样在更新屏幕时就会画出敌人的移动范围和状态。
明白了吗?好了,如果你明白了消息循环的原理,下面的东西就很容易理解了。

下面谈谈脚本控制
要实现这个,就必须在UpdataScreen()这个函数中拦截一个“脚本控制”的消息,并调用相应的处理函数:ScriptControlProc();
那么怎样得到“脚本控制”这个消息呢?
我是这样约定的:新游戏->调用脚本
"战斗结束"->调用脚本
“前往下一个地点”->调用脚本
好了,就只有这几种情况下才调用,调用脚本的函数为BeginScriptControl();
这个函数做了三个工作:
1.首先读取舞台(场景)角色的数据(没一关都是一个不同的舞台)
2.打开脚本文件(注意要用全局的文件指针)(虽然我在源程序中没直接打开,但是原理是一样的)
3.将游戏状态设定为“脚本控制”以便在下一次UpdateScreen()中调用的是ScriptControlProc();(怎么样?知道消息循环的作用了吧?)
ScriptControlProc()这个函数其实也很简单:
读取脚本文件中的参数直到文件结束

读取脚本文件需要一个解释脚本的函数LoadParam(FILE*fp);
这个函数负责解释脚本中的东西:是函数调用还是函数参数
然后找到相应的函数执行即可
比如说脚本里有一段代码MovePlayerTo(1,1,1);
意思就是把第1个玩家移动到1,1处
怎样做呢?
我是按照以下几步做的
1.保存当前的游戏状态
2.把当前游戏状态设定为“移动精灵”
当引擎得到“移动精灵”这个函数后,在UpdataScreen()中调用的是
MoveRoleProc()这个函数
当移动结束后,MoveRoleProc()调用EndMoveRole(),这个函数的作用就是
读取先前的游戏状态

怎么样?又回到读脚本了吧?记住在移动角色的时候脚本文件的指针没有改变,
所以回到读脚本的这个函数后不是重新读取而是继续读取!
同理其他的脚本指令如LoadDialog也是一样的道理!
当文件要结束的时候,别忘了告诉引擎该停止了,这时候我们必须更新游戏状态
脚本里的SetGameState就是负责这项工作的。

评论: 0 查看评论 发表评论

找优秀程序员,就在博客园


最新新闻:
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报:QQ的平台化价值是如何创造的?(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐:史上最强女游戏程序员

网站导航:博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

posted @ 2010-02-24 10:43 Maxice 阅读(154) | 评论 (0)编辑 收藏

     摘要: 阅读: 5 评论: 0 作者: Maxice 发表于 2010-02-24 10:42 原文链接就像修房子一样,别管你用多贵的砖头,它只是一块砖头而已,并不是你想要的房子。砖头可以在开发的时候随时换,但是结构一旦定下来,就不好修改了。 那么一个基本,却又efficient的结构究竟是什么样的呢?很简单。所有你所需要的就是引擎,无限状态机和内存池。这三个东西一点都不复杂,你可以从头开始写:首先是你...  阅读全文
posted @ 2010-02-24 10:42 Maxice 阅读(76) | 评论 (0)编辑 收藏

阅读: 8 评论: 0 作者: Maxice 发表于 2010-02-24 10:39 原文链接

Introduction To DirectPlay
翻译:杨冰(源代码之光)
E-Mail:iceryeah2000@163.com
创建时间:2002-9-11
最后修改时间:2002-10-1
备注:此章节是在翻译完Using DirectPlay章节后翻译的,对很多术语的翻译都经过了很长时间的考虑,可能还有不妥之处,会在以后更正。

目录:
  Creating and Managing Sessions
  DirectPlay Network Communication
  DirectPlay Transport Protocol
  Communicating with DirectPlay Objects
  DirectPlay Lobby Support
  
正文:

Microsoft? DirectPlay? API为开发者提供了开发诸如多人游戏或聊天程序的工具。一个多人游戏有两个基本特性:
1 两个或更多的独立用户,每个用户都拥有客户端游戏程序
2 网络连接了用户的电脑(通过中央电脑服务器连接)
DirectPlay提供了一个额外的层,使你的游戏和网络底层相隔。并且,你的游戏可以非常简单的使用DirectPlay API,并使用DirectPlay管理网络通讯。DirectPlay提供的特性,使多人游戏在开发中得到了很多简化。其中包括:
1 创建和管理点对点,客户/服务会话(Session)
2 在一个会话中管理用户(User)和组(Group)
3 管理在不同网络平台上进行会话的成员之间发送的消息
4 使游戏在大厅(Lobby)中互动
5 使用户可以进行语音互动

  这部分的文档(Introduction To DirectPlay)高度概括了DirectPlay的功能。随后的章节将告诉你DirectPlay的细节和如何在你的游戏中使用DirectPlay。

Creating and Managing Sessions
  游戏会话是一个特殊的多人游戏。会话中会有两个或者更多的用户同时在线,用户彼此拥有相同的游戏客户端。角色(Player)在游戏中是一个实体,它被游戏所定制。每个用户可以拥有多个角色。不过,游戏必须自己管理这些角色,使用DirectPlay接口对象来管理这些角色。

创建会话的第一步就是收集一组用户的信息。有两种方式:
1 大多数游戏会话都被一个运行在远程计算机上大厅程序(lobby application)所管理。大多数基于Internet的游戏都用这种方式。
2 各个用户自己相互进行联系。这种方式一般用在小型的局域网中。并且游戏不是很大。

会话被管理后,游戏就可以被连接。在会话过程中,角色可能从会话中退出,或者新的角色被加入。

  在多人游戏中,同一会话中的用户UI应该进行同步。管理多人游戏会话应该反复发送消息流给每个用户。比如,每当角色移动,一个消息就应该被发送,以便在所有其他游戏客户端更新角色的位置。DirectPlay的核心就是为所有在一个会话中的计算机发送高效安全的消息。

有两种基本方式来组织会话消息,一种是点对点,一种是客户/服务模式。讲这两种模式的资料很多,这里就不再复述。

DirectPlay Network Communication
   DirectPlay的主要功能是使游戏和网络底层分开。如果你需要发送状态更新的消息,你可以很简单的调用DirectPlay API,不必在意复杂的网络连接情况。DirectPlay网络服务提供了多种网络连接支持:TCP/IP, IPX, modem, 和 serial links。

DirectPlay Transport Protocol
   DirectPlay网络核心是DirectPlay协议。这个传输层协议在DirectPlay8中完全重写,现在已经被用在所有的消息中。DirectPlay协议重点放在让你可以很简单的发送消息。协议为多人游戏提供了很多量身定制的特性,包括:
1 可靠和不可靠的消息传递。可靠传递的消息是不断的发送,直到目标程序确信接收了他们。你可以根据你的情况分配消息的具体发送方法。
2 连续和非连续消息传递。连续消息被一个个传送到目标程序中。
3 消息分割和打包。当消息的大小超过网络的许可,DirectPlay将自动进行分割和重组打包。
4 阻塞控制。DirectPlay会自动控制(throttles)你传出消息的速度,使目标程序能够执行和接收消息。
5 发送顺序。要确保重要的消息被首先发送,DirectPlay可以设置消息的发送级别,其中包括low, medium, 和 high priority。High priority(最高优先发送)消息被最先送上消息队列的前端,然后是medium和low。
6 消息超时处理。防止消息队列被阻塞,DirectPlay允许你分派每个消息一个超时值,当这个消息超时后,便从消息队列中移除。 DirectPlay Addresses

为了传送消息,每个加入多人游戏的人都要有一个唯一的地址。运行游戏客户端的电脑提供设备地址,而游戏主机将提供主机地址。

DirectPlay的地址是一个URL字符串。这些字符串由如下格式构成:
x-directplay:/[data string]
在不同的网络连接上,它包含发送消息方和接收方这样的元素。
DirectPlay地址对象会生成URL字符串。依你的熟练程度,你可以直接使用URL地址或者通过DirectPlay地址对象来管理URL。(using the methods exposed by the address object to handle each element of the data string separately)

Communicating with DirectPlay Objects
   DirectPlay其实是基于COM的。各个组件管理各个不同的方面。比如,DirectPlay点(peer)对象(CLSID_DirectPlay8Peer),就是负责管理点对点游戏的。

你通过组件的接口来和它通讯。比如,在点对点游戏中,你发送给另外用户数据时,使用IDirectPlay8Peer::SendTo。DirectPlay会发送消息到目标。

DirectPlay通过很多callback functions(回调函数)进行联系。在原理上,这些函数和windows程序使用得回调函数一样。游戏执行这些callback function,在DirectPlay初始化期间传送函数指针。当DirectPlay需要通讯时,它调用callback function,并且传递两个重要信息:
1 鉴定消息类别ID。
2 一个数据块指针,一般是一个结构体。

比如,当一个消息发送上面的信息到目标,目标程序的callback function将接收到DPNMSGID_RECEIVE消息ID,指出那个消息已经到达。并伴随着包含数据的结构。

因为大多数的DirectPlay消息是多线程的,其中关键就是callback function如何被恰当的执行。

DirectPlay Lobby Support
  大厅(Lobby)主要的任务是安排角色会面和安排游戏。大厅服务器(Lobby servers)一般还有其他功能,比如主持聊天室,发送新闻和信息,主持商业买卖。大厅服务器可以便利的使用和安排多人游戏工作,但它不是必需的。多人游戏也可以直接在大厅客户端之间进行通讯(lobby clients)。

一个具有大厅的多人游戏,由三个部分组成:
1 大厅服务器
2 大厅客户端
3 支持大厅的游戏(A lobbyable game)

DirectPlay没有具体的告诉大厅服务器如何工作,你可以自己安排。DirectPlay提供了对大厅客户端的支持。一个大厅客户端通过大厅服务器连接程序(vendor)进行工作,连接程序被安装到用户的系统上。它就像一个链,来连接用户和大厅。当你要直接进行通讯,你必须知道每个大厅的工作细节。

大厅客户端游戏接收大厅服务器的通讯细节,使用恰当的通讯协议。大厅客户端进行用户和游戏程序之间的通讯。游戏也能使用接口传送消息给大厅客户端。

大厅实际可以连接任何程序。不过,游戏必须有某些具体的大厅支持组件(lobby-aware components)。一般的,一个支持大厅的游戏可以通过会话和大厅客户端进行联系。如果游戏被注册成支持大厅,大厅客户端能自动的接收更新信息,并在游戏里进行相应的更新。诸如host migration。

 

评论: 0 查看评论 发表评论

找优秀程序员,就在博客园


最新新闻:
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报:QQ的平台化价值是如何创造的?(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐:史上最强女游戏程序员

网站导航:博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

posted @ 2010-02-24 10:39 Maxice 阅读(124) | 评论 (0)编辑 收藏

阅读: 8 评论: 0 作者: Maxice 发表于 2010-02-24 10:37 原文链接

这是GAMEGEMS中的第三章的第一部分,番的不好。你可以直接阅读原文。原本以为这是人工智能的部分,看到一半才发现只是一个简单的框架。如果你想学人工智能,这里没有,就不要浪费时间了。由于本人水平有限,其中难免会出现原则性的错误,希望指正。
关键字:有限状态机、状态、输入、状态转换、输出状态当前状态
一个有限状态机类
在这篇文章中,我们创建了一个通用的有限状态机(FSM)的C++类。有限状态机是计算机科学和数学理论的抽象,它在许多的方面是很有用处的。这里我们不去讲解有限状态机的理论上的知识。而是讲如何实现一个“有限状态机”,“有限状态机”在游戏的人工智能方面是很有用处的。
“有限状态机”是由有限的状态组成的一个机制。一个“状态”就是一个状况。你考虑一下门;它的“状态”有“开”或“关”以及“锁”与“未锁”。
对于一个“有限状态机”,它应该有一个“输入”。这个“输入”可以影响“状态转换”。“有限状态机”应该有一个简单(或复杂)的状态转换函数,这个函数可以决定什么状态可以变成“当前状态”。
这个当前的新状态被称为“有限状态机”的“状态转换”的“输出状态”。如果你对这个概念有些迷惑,就把“门”做为理解“有限状态机”的例子。当一个“门”处于“关闭”状态和“锁”状态,当你输入了“使用钥匙”时,门的状态可以变成“未锁”状态(即“状态转换”的输出状态,也就是门的当前状态)。当你输入了“使用手”时,门的状态可以转换成“开”的状态。当门处于“开”的状态时,我们输入“使用手”时,会使门的状态重新回到“关”的状态。当“门”处于“关”的状态时,我们输入“使用钥匙”时,这将会使门重新回到“锁”的状态。当门处于“锁”的状态,我们输入“使用手”,就不能把门的状态转换到“开”的状态,门仍然会保持“锁”的状态。还有,当门处于“开”的状态时,我们输入“使用钥匙”是不能把门的状态转换成“锁”的状态的。
总之,“有限状态机”是一个有限的状态组成的,其中的一个状态是“当前状态”。“有限状态机”可以接受一个“输入”,这个“输入”的结果将导致一个“状态转换”的发生(即从“当前状态”转换到“输出”状态)。这个“状态转换”是基于“状态转换函数”的。状态转换完成之后,“输出状态”即变成了“当前状态”。
输入 状态转换函数
当前状态-----》状态转换-------------》输出状态(当前状态)
那么,人们是如何将这个概念应用到游戏的AI系统中的呢?有限状态机的功能很多:管理游戏世界、模拟NPC的思维、维护游戏状态、分析玩游戏的人的输入,或者管理一个对象的状态。
假如在一个冒险游戏中有一个NPC,名字可以叫MONSTER。我们可以先假设这个MONSTER在游戏中有如下的状态:BERSERK、RAGE、MAD、ANNOYED以及UNCARING。(前几个状态不好分别)。假设,MONSTER对于不同的状态可以执行不同的操作,并且假设你已经有了这些不同操作的代码。我们这时可以使用“有限状态机”来模拟这个MONSTER的行为了。只要我们给出不同的“输入”,MONSTER就会做出不同的反应。我们再来指出这些“输入”是什么:PLAYER SEEN、PLAYER ATTACKS、PLAYERGONE、MONSTER HURT、MONSTER HEALED。这样我们可以得到一个状态转换的表格,如下:游戏状态转换表:
当前状态 输入 输出状态
UNCARING PLAYER SEEN ANNOYED
UNCARING PLAYER ATTACKS MAD
MAD MONSTER HURT RAGE
MAD MONSTER HEALED UNCARING
RAGE MONSTER HURT BERSERK
RAGE MONSTER HEALED ANNOYED
BERSERK MONSTER HURT BERSERK
BERSERK MONSTER HEALED RAGE
ANNOYED PLAYER GONE UNCARING
ANNOYED PLAYER ATTACKS RAGE
ANNOYED MONSTER HEALED UNCARING
根据上面的这个表格,我们可以很容易的画出一个MONSTER的“状态转换图”,MONSTER的每一个状态就是图中的顶点。
因此,根据当前状态和对FSM的输入,MONSTER的状态将被改变。这时根据MONSTER的状态执行相应操作的代码(假设已经实现)将被执行,这时MONSTER好像是具备了人工智能。显然,我们可以定义更多的“状态”,写出更多的“输入”,写出更多的“状态转换”,这样,MONSTER可以表现的更真实,生动,当然,这些游戏的规则问题应该是策划制定的。
FSMclass以及FSMstate
现在,我们如何把这些方法变成现实?使用FSMclass和它的组成部分FSMstate可以实现这些想法。
定义FSMstate
class FSMstate
{
    unsigned m_usNumberOfTransition; //状态的最大数
    int* m_piInputs; //为了转换而使用的输入数组
    int* m_piOutputState; //输出状态数组
    int m_iStateID; //这个状态的唯一标识符
public:
    //一个构造函数,可以接受这个状态的ID和它支持的转换数目
    FSMstate(int iStateID,unsigned usTransitions);
    //析构函数,清除分配的数组
    ~FSMstate();
    //取这个状态的ID
    int GetID(){return m_iStateID;}
    //向数组中增加状态转换
    void AddTransition(int iInput,int iOutputID);
    //从数组中删除一个状态转换
    void DeleteTransition(int iOutputID);
    //进行状态转换并得到输出状态
    int GetOutput(int iInput);
};
对这个类的分析:
功能:主要是实现与一个状态相关的各种操作。我们前面假设了MONSTER的各种状态:
#define STATE_ID_UNCARING 1
#define STATE_ID_MAD 2
#define STATE_ID_RAGE 3
#define STATE_ID_BERSERK 4
#define STATE_ID_ANNOYED 5
状态转换所需的输入有:
#define INPUT_ID_PLAYER_SEEN 1
#define INPUT_ID_PLAYER_ATTACK 2
#define INPUT_ID_PLAYER_GONE 3
#define INPUT_ID_MONSTER_HURT 4
#define INPUT_ID_MONSTER_HEALED 5
以上是五个状态的标识符。
我们就要声明5个FSMstate的实例,每一个实例代表一个状态和与之有关的操作。假设我们先处理状态STATE_ID_MAD
类成员变量m_iStateID就等于STATE_ID_MAD类成员变量m_usNumberOfTransition就是可由这个状态转换成的状态的个数,前面有一个表,其中有两个状态可以由这个状态产生,它们分别是STATE_ID_UNCARING和STATE_ID_RAGE。
这时,m_usNumberOfTransition等于2。
m_piInputs是一个指针变量,它保存与这个状态相关的输入,在前面的表中我们知道与STATE_ID_MAD相关的输入为
INPUT_ID_MONSTER_HURT和INPUT_ID_MONSTER_HEALED,因此m_piInputs中存放的是这两个数据。
而m_piOutputState存放的是与STATE_ID_MAD相关的状态,即STATE_ID_RAGE和STATE_ID_UNCARING,这样,m_piOutputState中存放的数据便是这两个值。
以上是对成员变量的解释,下面解释成员函数:
构造函数
FSMstate::FSMstate(int iStateID,unsigned usTransitions)
{
    if(!usTransitions) //如果给出的转换数量为0,就算为1
        m_usNumberOfTransitions=1;
    else
        m_usNumberOfTransitions=usTransitions;
    //将状态的ID保存起来
    m_iStateID=iStateID;
    //分配内存空间
    try
    {
        m_piInputs=new int[m_usNumberOfTransitions];
        for(int i=0;i<m_usNumberOfTransitions;++i)
            m_piInputs[i]=0;
    }
    catch(...)
    {
        throw;
    }
    try
    {
        m_piOutputState=new int[m_usNumberOfTransition];
        for(int i=0;i<m_usNumberOfTransitions;++i)
            m_piOutputState[i]=0;
    }
    catch(...)
    {
        delete [] m_piInputs;
        throw;
    }
}
这就是构造函数,在FSMstate类中共有四个成员变量,在这个函数中全部被初始化了。FSMstate是一个类,是否还记得MONSTER的状态(如MAD、UNCARING)。这个类就是实现对MONSTER的一个状态的管理的。假如这个状态是STATE_ID_MAD, 与这个状态相关的状态有两个,上面已经讲过了。这时我们给成员变量赋值,在这个具体例子中它们的值如下:
m_usNumberOfTransition=2
m_piInput[0]=0;
m_piInput[1]=0;
m_piOutputState[0]=0;
m_piOutputState[1]=0;
m_iStateID=STATE_ID_MAD;
析构函数:
FSMState::~FSMState()
{
    delete [] m_piInputs;
    delete [] m_piOutputState;
}
析构函数将动态分配的存储空间释放了。
void FSMstate::AddTransition(int iInput,int iOutputID)
{
    for(int i=0;i<m_usNumberOfTransitions;++i)
        if(!m_piOutputState[i]) break;
            if(i<m_usNumberOfTransition)
            {
                m_piOutputState[i]=iOutputID;
                m_piInputs[i]=iInput;
            }
}
这个函数给两个前面构造函数动态分配的空间加入数据,首先要找到两个数组中找到适当的位置,之后,如果位置是合法的
我们就可以把数据加入这两个数组中。因为STATE_ID_MAD与两个状态有关,因此,我们可以调用两次这个函数,把这两个状态加入到类中:
AddTransition(INPUT_ID_MONSTER_HURT,STATE_ID_RAGE);
AddTransition(INPUT_ID_MONSTER_HEALED,STATE_ID_UNCARING)
这样,与状态STATE_ID_MAD相关的“状态”和“输入”也加入了。
void FSMstate::DeleteTransition(int iOutputID)
{
    // 遍历每一个输出状态
    for(int i=0;i<m_usNumberOfTransitions;++i)
    {
        //如果找到输出状态,退出循环
        if(m_piOutputState[i]==iOutputID)
            break;
    }
    //如果没有找到输出状态,返回
    if(i>=m_usNumberOfTransitions)
        return;
    //将输出状态的内容置0
    m_piInputs[i]=0;
    m_piOutputState[i]=0;
    //被删除的输出状态的后面的输出状态前移
    for(;i<(m_usNumberOfTransition-1);++i)
    {
        if(!m_piOUtputState[i])
            break;
        m_piInputs[i]=m_piInputs[i+1];
        m_piOutputState[i]=m_piOutputState[i+1];
    }
    //最后面的输出状态置0
    m_piInputs[i]=0;
    m_piOutputState[i]=0;
}
这个函数是要删除与一个状态相关的输出状态。设一个状态STATE_ID_MAD,与之相关的状态有两个STATE_ID_RAGE,STATE_ID_UNCARING,当然这是经过初始化以及前面的添加状态函数之后,产生了这两个相关的状态。你想删除哪一个?如果你想删除相关的输出状态,只要在删除函数中指出那个状态即可,例如:
DeleteTransition(STATE_ID_RAGE);
你就可以删除输出状态STATE_ID_RAGE了。
int FSMstate::GetOutput(int iInput)
{
    //先给输出状态赋值(如果未找到与输入对应的输出状态时,返回这个值)
    int iOutputID=m_iStateID;
    //遍历输出状态
    for(int i=0;i<m_usNumberOfTransitions;++i)
    {
        //如果没找到,退出循环
        if(!m_piOutputState[i])
            break;
        //如果找到了与“输入”相对应的“输出状态”,进行赋值。
        if(iInput==m_piInputs[i])
        {
            iOutputID=m_piOutputState[i];
            break;
        }
    }
    //返回“输出状态”
    return(iOutputID);
}
这个函数功能是返回与“输入”相对应的“输出状态”的标识。如果没有与“输入”相对应的“输出状态”,返回原来的状态,如果有与之对应的“输出状态”,返回这个状态的ID。
下面定义的是FSMclass,这个类用于维护FSMstate对象集合。
class FSMclass
{
    State_Map m_map; //包括了状态机的所有状态
    int m_iCurrentState; //当前状态的ID
public:
    FSMclass(int iStateID); //初始化状态
    ~FSMclass()
    //返回当前状态ID
    int GetCurrentState() {return m_iCurrentState;}
    //设置当前状态ID
    void SetCurrentState(int iStateID) {m_iCurrentState=iStateID;}
    //返回FSMstate对象指针
    FSMstate* GetState(int iStateID);
    //增加状态对象指针
    void AddState(FSMstate* pState);
    //删除状态对象指针
    void DeleteState(int iStateID);
    //根据“当前状态”和“输入”完成“状态”的转换。
    int StateTransition(int iInput);
};
FSMclass::m_map是FSMstate对象的集合,是从STL<map>中实现的。
FSMclass::m_iCurrentState是FSMstate对象的状态标识,是“有限状态机”的当前状态。
FSMclass::GetCurrentState()可以用之访问当前的FSMstate对象的状态的标识符。
FSMclass::SetCurrentState()可以设置当前FSMstate对象的状态的标识符。
FSMclass::GetState()可以取得有限状态机中的任何FSMstate对象的指针。
FSMclass::AddState()增加有限状态机中的FSMstate对象。
FSMclass::DeleteState()删除有限状态机中的FSMstate对象
FSMclass::StateTransition()初始化状态转换,根据输入返回输出状态。
这个类使用了STL,我不知道它怎么用:)。听说是高人才使用它,高人起码要写过上万行的代码。因此不能详细介绍这个类了
总之,可以这么理解这两个类FSMstate,FSMclass.FSMstate代表了一个状态以及和状态相关的数据和操作。如在MONSTER中有五个状态,我们就要声明五个类的对象,每个对象中包括了与这个状态相关的状态,输入和各种转换函数。可以说FSMstate是对每一个状态的封装(包括相关数据和操作),游戏中的对象有多少状态,就要声明多少个FSMstate对象。而FSMclass则是对这若干个FSMstate对象(这个例子中MONSTER有五个状态)进行的封装。在FSMclass中指明了若干个FSMstate中哪一个是当前的MONSTER拥有的状态并且可以设置,得到以及删除状态,并且可以进行状态间的转换。
总之:游戏中的MONSTER有多少状态,游戏中就要声明多少的FSMstate对象,每一个FSMstate对象包括了与特定的状态相关的数据和操作。而FSMclass只有一个,它用于协调若干个FSMstate之间的关系和操作。
下面是如何在游戏中使用两个类的例子:
首先是创建FSMstate对象(若干个),有多少状态就要循环多少次,下面是增加STATE_ID_UNCARING状态的例子:
FSMstate* pFSMstate=NULL;
//创建状态
try
{
    //第一个参数是增加状态的标识,第二个参数指明了与这个
    //状态相关的状态的个数。
    pFSMstate=new FSMstate(STATE_ID_UNCARING,2);
}
catch(...)
{
    throw;
}
//之后给这个状态加入相关的“输入”和“输出状态”
pFSMstate->AddTransition(INPUT_ID_PLAYER_SEEN,STATE_ID_ANNOYED);
pFSMstate->AddTransition(INPUT_ID_PLAYER_ATTACKS,STATE_ID_MAD);
这个函数指明了与特定状态相关的“输入”和“输出状态”
比如第一个函数,它表明如果我要输入一个INPUT_ID_PLAYER_SEEN,这时就会产生一个输出状态,STATE_ID_ANNOYED。
我们应该为每一个状态做上面的事情,这里就略过了。之后我们要声明一个FSMclass对象,用于协调上面的FSMstate对象之间的关系。
try
{
    m_pFSMclass=new FSMclass(STATE_ID_UNCARING);
}
catch(...)
{
    throw;
}
上面指明了MONSTER的当前状态是STATE_ID_UNCARING最后将FSMstate对象分别加入到FSMclass中。
下面介绍如何使用FSMclass
使用十分简单,只要我们给出一个“输入”,之后,我们便可以得到一个“输出状态”,根据这个“输出状态”我们执行相应的操作,最后,把这个“输出状态”变成MONSTER的当前状态。
在游戏中发生了一些事情,如玩游戏的人指出他控制的人进攻MONSTER(用鼠标点击了MONSTER),这时会产生一个“输入”iInputID=INPUT_ID_PLAYER_ATTACK;
这时,我们调用状态转换函数:
m_iOutputState=m_pFSMclass->StateTransition(iInputID);
这时,我们的“输入”对MONSTER产生了刺激,产生了一个“输出状态”。这时我们根据这个输出状态调用相应的代码执行就可以了,这时的MONSTER好像有应反了,我们说它有了简单的智能。
if(m_iOutputState==STATE_ID_MAD)
{
    //some code for the monster to act mad
}
当然,我们也应该把其它状态执行的操作也写出来,但只写一个就可以了。使用这个状态机就是这么简单。总之,FSMclass不是全部的人工智能,相反,它只是一个框架,一个开始智能需要的还很多。只要你可以分出“状态”,并且知道什么“输入”产生什么“输出状态”就可以了,当然这是一个游戏的规则,策划应当完成这个部分?

评论: 0 查看评论 发表评论

找优秀程序员,就在博客园


最新新闻:
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报:QQ的平台化价值是如何创造的?(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐:史上最强女游戏程序员

网站导航:博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

posted @ 2010-02-24 10:37 Maxice 阅读(660) | 评论 (0)编辑 收藏

阅读: 6 评论: 0 作者: Maxice 发表于 2010-02-24 10:35 原文链接

不想让ime显示默认的窗口,只想用它的转换和选字功能,看过拿铁游戏论坛上的一个兄弟的一些代码,修正了一些我认为的bug,加入了一组控制函数,使得程序中可以显示一些button,玩家可以不必用热键就能切换输入法、全角/半角,中/英文标点。

//不知道这个能不能解决缩进的问题


下载演示例子

#pragma comment ( lib, "imm32.lib" )
#include <windows.h>
#include <imm.h>

class CIme{
    bool g_bIme; //ime允许标志
    char g_szCompStr[ MAX_PATH ]; //存储转换后的串
    char g_szCompReadStr[ MAX_PATH ];//存储输入的串
    char g_szCandList[ MAX_PATH ]; //存储整理成字符串选字表
    int g_nImeCursor; //存储转换后的串中的光标位置
    CANDIDATELIST *g_lpCandList; //存储标准的选字表
    char g_szImeName[ 64 ]; //存储输入法的名字
    bool g_bImeSharp; //全角标志
    bool g_bImeSymbol; //中文标点标志
    void ConvertCandList( CANDIDATELIST *pCandList, char *pszCandList ); //将选字表整理成串

public:
    CIme() : g_lpCandList( NULL ){ DisableIme(); } //通过DisableIme初始化一些数据
    ~CIme()
    {

        DisableIme();
        if( g_lpCandList )
        {
            GlobalFree( (HANDLE)g_lpCandList );
            g_lpCandList = NULL;
        }
    }

    //控制函数
    void DisableIme(); //关闭并禁止输入法,如ime已经打开则关闭,此后玩家不能用热键呼出ime
    void EnableIme(); //允许输入法,此后玩家可以用热键呼出ime
    void NextIme(); //切换到下一种输入法,必须EnableIme后才有效
    void SharpIme( HWND hWnd ); //切换全角/半角
    void SymbolIme( HWND hWnd );//切换中/英文标点

    //状态函数
    char* GetImeName(); //得到输入法名字,如果当前是英文则返回NULL
    bool IfImeSharp(); //是否全角
    bool IfImeSymbol(); //是否中文标点
    void GetImeInput( char **pszCompStr, char **pszCompReadStr, int *pnImeCursor, char **pszCandList );

    //得到输入法状态,四个指针任意可为NULL则此状态不回返回
    //在pszCompStr中返回转换后的串
    //在pszCompReadStr中返回键盘直接输入的串
    //在pnImeCursor中返回szCompStr的光标位置
    //在pszCandList中返回选字表,每项之间以\t分隔

    //必须在消息中调用的函数,如果返回是true,则窗口函数应直接返回0,否则应传递给DefWindowProc
    bool OnWM_INPUTLANGCHANGEREQUEST();
    bool OnWM_INPUTLANGCHANGE( HWND hWnd );
    bool OnWM_IME_SETCONTEXT(){ return true; }
    bool OnWM_IME_STARTCOMPOSITION(){ return true; }
    bool OnWM_IME_ENDCOMPOSITION(){ return true; }
    bool OnWM_IME_NOTIFY( HWND hWnd, WPARAM wParam );
    bool OnWM_IME_COMPOSITION( HWND hWnd, LPARAM lParam );
};

void CIme::DisableIme()
{
    while( ImmIsIME( GetKeyboardLayout( 0 )))
        ActivateKeyboardLayout(( HKL )HKL_NEXT, 0 );//如果ime打开通过循环切换到下一个关闭

    g_bIme = false;
    g_szCompStr[ 0 ] = 0;
    g_szCompReadStr[ 0 ] = 0;
    g_nImeCursor = 0;
    g_szImeName[ 0 ] = 0;
    g_szCandList[ 0 ] = 0;
}

void CIme::EnableIme()
{
    g_bIme = true;
}

void CIme::NextIme()
{
    if( !g_bIme )
        return;
    ActivateKeyboardLayout(( HKL )HKL_NEXT, 0 );
}

void CIme::SharpIme( HWND hWnd )
{
    ImmSimulateHotKey( hWnd, IME_CHOTKEY_SHAPE_TOGGLE );
}

void CIme::SymbolIme( HWND hWnd )
{
    ImmSimulateHotKey( hWnd, IME_CHOTKEY_SYMBOL_TOGGLE );
}

void CIme::ConvertCandList( CANDIDATELIST *pCandList, char *pszCandList ) //转换CandidateList到一个串,\t分隔每一项
{
    unsigned int i;
    if( pCandList->dwCount < pCandList->dwSelection )
    {
        pszCandList[ 0 ] = 0;
        return;
    }

    //待选字序号超出总数,微软拼音第二次到选字表最后一页后再按PageDown会出现这种情况,并且会退出选字状态,开始一个新的输入
    //但微软拼音自己的ime窗口可以解决这个问题,估计微软拼音实现了更多的接口,所以使用了这种不太标准的数据
    //我现在无法解决这个问题,而且实际使用中也很少遇到这种事,而且其它标准输入法不会引起这种bug
    //非标准输入法估计实现的接口比较少,所以应该也不会引起这种bug

    for( i = 0; ( i < pCandList->dwCount - pCandList->dwSelection )&&( i < pCandList->dwPageSize ); i++ )
    {
        *pszCandList++ = ( i % 10 != 9 )? i % 10 + '1' : '0';//每项对应的数字键
        *pszCandList++ = '.';//'.'分隔
        strcpy( pszCandList, (char*)pCandList + pCandList->dwOffset[ pCandList->dwSelection + i ] );//每项实际的内容
        pszCandList += strlen( pszCandList );
        *pszCandList++ = '\t';//项之间以'\t'分隔
    }
    *( pszCandList - 1 )= 0;//串尾,并覆盖最后一个'\t'
}

bool CIme::OnWM_INPUTLANGCHANGEREQUEST()
{
    return !g_bIme;//如果禁止ime则返回false,此时窗口函数应返回0,否则DefWindowProc会打开输入法
}

bool CIme::OnWM_INPUTLANGCHANGE( HWND hWnd ) //ime改变
{
    HKL hKL = GetKeyboardLayout( 0 );
    if( ImmIsIME( hKL ))
    {
        HIMC hIMC = ImmGetContext( hWnd );
        ImmEscape( hKL, hIMC, IME_ESC_IME_NAME, g_szImeName );//取得新输入法名字
        DWORD dwConversion, dwSentence;
        ImmGetConversionStatus( hIMC, &dwConversion, &dwSentence );
        g_bImeSharp = ( dwConversion & IME_CMODE_FULLSHAPE )? true : false;//取得全角标志
        g_bImeSymbol = ( dwConversion & IME_CMODE_SYMBOL )? true : false;//取得中文标点标志
        ImmReleaseContext( hWnd, hIMC );
    }
    else//英文输入
        g_szImeName[ 0 ] = 0;

    return false;//总是返回false,因为需要窗口函数调用DefWindowProc继续处理
}

bool CIme::OnWM_IME_NOTIFY( HWND hWnd, WPARAM wParam )
{
    HIMC hIMC;
    DWORD dwSize;
    DWORD dwConversion, dwSentence;
    switch( wParam )
    {
    case IMN_SETCONVERSIONMODE://全角/半角,中/英文标点改变
        hIMC = ImmGetContext( hWnd );
        ImmGetConversionStatus( hIMC, &dwConversion, &dwSentence );
        g_bImeSharp = ( dwConversion & IME_CMODE_FULLSHAPE )? true : false;
        g_bImeSymbol = ( dwConversion & IME_CMODE_SYMBOL )? true : false;
        ImmReleaseContext( hWnd, hIMC );
        break;

    case IMN_OPENCANDIDATE://进入选字状态
    case IMN_CHANGECANDIDATE://选字表翻页
        hIMC = ImmGetContext( hWnd );
        if( g_lpCandList )
        {
            GlobalFree( (HANDLE)g_lpCandList );
            g_lpCandList = NULL;
        } //释放以前的选字表
        if( dwSize = ImmGetCandidateList( hIMC, 0, NULL, 0 ))
        {
            g_lpCandList = (LPCANDIDATELIST)GlobalAlloc( GPTR, dwSize );
            if( g_lpCandList )
                ImmGetCandidateList( hIMC, 0, g_lpCandList, dwSize );
        } //得到新的选字表
        ImmReleaseContext( hWnd, hIMC );
        if( g_lpCandList )ConvertCandList( g_lpCandList, g_szCandList );//选字表整理成串
        break;

    case IMN_CLOSECANDIDATE://关闭选字表
        if( g_lpCandList )
        {
            GlobalFree( (HANDLE)g_lpCandList );
            g_lpCandList = NULL;
        }//释放
        g_szCandList[ 0 ] = 0;
        break;
    }

    return true;//总是返回true,防止ime窗口打开
}

bool CIme::OnWM_IME_COMPOSITION( HWND hWnd, LPARAM lParam ) //输入改变
{
    HIMC hIMC;
    DWORD dwSize;
    hIMC = ImmGetContext( hWnd );
    if( lParam & GCS_COMPSTR )
    {
        dwSize = ImmGetCompositionString( hIMC, GCS_COMPSTR, (void*)g_szCompStr, sizeof( g_szCompStr ));
        g_szCompStr[ dwSize ] = 0;
    }//取得szCompStr

    if( lParam & GCS_COMPREADSTR )
    {
        dwSize = ImmGetCompositionString( hIMC, GCS_COMPREADSTR, (void*)g_szCompReadStr, sizeof( g_szCompReadStr ));
        g_szCompReadStr[ dwSize ] = 0;
    }//取得szCompReadStr

    if( lParam & GCS_CURSORPOS )
    {
        g_nImeCursor = 0xffff & ImmGetCompositionString( hIMC, GCS_CURSORPOS, NULL, 0 );
    }//取得nImeCursor

    if( lParam & GCS_RESULTSTR )
    {
        unsigned char str[ MAX_PATH ];
        dwSize = ImmGetCompositionString( hIMC, GCS_RESULTSTR, (void*)str, sizeof( str ));//取得汉字输入串
        str[ dwSize ] = 0;
        unsigned char *p = str;
        while( *p )PostMessage( hWnd, WM_CHAR, (WPARAM)(*p++), 1 );//转成WM_CHAR消息
    }

    ImmReleaseContext( hWnd, hIMC );
    return true;//总是返回true,防止ime窗口打开
}

char* CIme::GetImeName()
{
    return g_szImeName[ 0 ]? g_szImeName : NULL;
}

bool CIme::IfImeSharp() //是否全角
{
    return g_bImeSharp;
}

bool CIme::IfImeSymbol() //是否中文标点
{
    return g_bImeSymbol;
}

void CIme::GetImeInput( char **pszCompStr, char **pszCompReadStr, int *pnImeCursor, char **pszCandList )
{
    if( pszCompStr )
        *pszCompStr = g_szCompStr;
    if( pszCompReadStr )
        *pszCompReadStr = g_szCompReadStr;
    if( pnImeCursor )
        *pnImeCursor = g_nImeCursor;
    if( pszCandList )
        *pszCandList = g_szCandList;
}

//由于微软拼音实现了很多自己的东西,CIme和它的兼容性有些问题
//1、在函数ConvertCandList中所说的选字表的问题
//2、函数GetImeInput返回的szCompReadStr显然经过了加工而不是最初的键盘输入
// 它的每个可组合的输入占以空格补足的8byte,且新的不可组合的输入存为0xa1
// 我们可以在输入法名字中有子串"微软拼音"时,只显示末尾的一组8byte,如果有0xa1就什么都不显示,也可以直接用TextOut显示所有的

评论: 0 查看评论 发表评论

找优秀程序员,就在博客园


最新新闻:
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报:QQ的平台化价值是如何创造的?(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐:史上最强女游戏程序员

网站导航:博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

posted @ 2010-02-24 10:35 Maxice 阅读(247) | 评论 (0)编辑 收藏

阅读: 6 评论: 0 作者: Maxice 发表于 2010-02-24 10:28 原文链接

在这一节中就要向大家介绍另外一个重要的部分,并且也是最头疼的部分:线程同步和数据保护。

  关于线程的概念我在前面的章节中已经介绍过了,也就在这里不累赘—“重复再重复”了。有一定线程基础的人都知道,线程只要创建后就如同脱缰的野马,对于这样的一匹野马我们怎么来进行控制和处理呢?简单的说,我们没有办法进行控制。因为我们更本就没有办法知道CPU什么时候来执行他们,执行他们的次序又是什么?

  有人要问没有办法控制那我们如何是好呢?这个问题也正是我这里要向大家进行解释和说明的,虽然我们不能够控制他们的运行,但我们可以做一些手脚来达到我们自己的意志。

  这里我们的做手脚也就是对线程进行同步,关于同步的概念大家在《操作系统》中应该都看过吧!不了解的话,我简单说说:读和写的关系(我读书的时候,请你不要在书上乱写,否则我就没有办法继续阅读了。)

处理有两种:用户方式内核方式
用户方式的线程同步由于有好几种:原子访问,关键代码段等。

  在这里主要向大家介绍关键代码段的处理(我个人用的比较多,简单实用)。先介绍一下它的一些函数,随后提供关键代码段的处理类供大家参考(比较小,我就直接贴上来了)

VOID InitializeCriticalSection( //初始化互斥体
    LPCRITICAL_SECTION lpCriticalSection // critical section
);

VOID DeleteCriticalSection( //清除互斥体
    LPCRITICAL_SECTION lpCriticalSection // critical section
);

VOID EnterCriticalSection( //进入等待
    LPCRITICAL_SECTION lpCriticalSection // critical section
);

VOID LeaveCriticalSection( //释放离开
    LPCRITICAL_SECTION lpCriticalSection // critical section
);

以上就是关于关键代码段的基本API了。介绍就不必了(MSDN)。而我的处理类只是将这几个函数进行了组织,也就是让大家能够更加理解关键代码端

.h
class CCriticalSection //共享变量区类
{
public:
    CCriticalSection();
    virtual ~CCriticalSection();
    void Enter(); //进入互斥体
    void Leave(); //离开互斥体释放资源
private:
    CRITICAL_SECTION g_CritSect;
};

.cpp
CCriticalSection::CCriticalSection()
{
    InitializeCriticalSection(&g_CritSect);
}

CCriticalSection::~CCriticalSection()
{
    DeleteCriticalSection(&g_CritSect);
}

void CCriticalSection::Enter()
{
    EnterCriticalSection(&g_CritSect);
}

void CCriticalSection::Leave()
{
    LeaveCriticalSection(&g_CritSect);
}

由于篇幅有限关键代码段就说到这里,接下来向大家简单介绍一下内核方式下的同步处理。

  哎呀!这下可就惨了,这可是要说好多的哦!书上的罗罗嗦嗦我就不说了,我就说一些我平时的运用吧。首先内核对象和一般的我们使用的对象是不一样的,这样的一些对象我们可以简单理解为特殊对象。而我们内核方式的同步就是利用这样的一些特殊对象进行处理我们的同步,其中包括:事件对象,互斥对象,信号量等。对于这些内核对象我只向大家说明两点:
1.内核对象的创建和销毁
2.内核对象的等待处理和等待副作用

第一:内核对象的创建方式基本上而言都没有什么太大的差别,例如:创建事件就用HANDLE CreateEvent(…..),创建互斥对象 HANDLE CreateMutex(…….)。而大家注意的也是这三个内核对象在创建的过程中是有一定的差异的。对于事件对象我们必须明确指明对象是人工对象还是自动对象,而这种对象的等待处理方式是完全不同的。什么不同下面说(呵呵)。互斥对象比较简单没什么说的,信号量我们创建必须注意我们要定义的最大使用数量和初始化量。最大数量>初始化量。再有如果我们为我们的内核对象起名字,我们就可以在整个进程中共用,也可以被其他进程使用,只需要OPEN就可以了。也就不多说了。

第二:内核对象的等待一般情况下我们使用两个API:
DWORD WaitForSingleObject( //单个内核对象的等待
            HANDLE hHandle, // handle to object
            DWORD dwMilliseconds // time-out interval
);

DWORD WaitForMultipleObjects( //多个内核对象的等待
            DWORD nCount, // number of handles in array
            CONST HANDLE *lpHandles, // object-handle array
            BOOL fWaitAll, // wait option
            DWORD dwMilliseconds // time-out interval
);

具体怎么用查MSDN了。

  具体我们来说等待副作用,主要说事件对象。首先事件对象是分两种的:人工的,自动的。人工的等待是没有什么副作用的(也就是说等待成功后,要和其他的对象一样要进行手动释放)。而自动的就不一样,但激发事件后,返回后自动设置为未激发状态。这样造成的等待结果也不一样,如果有多个线程在进行等待事件的话,如果是人工事件,被激活后所有等待线程成执行状态,而自动事件只能有其中一个线程可以返回继续执行。所以说在使用这些内核对象的时候,要充分分析我们的使用目的,再来设定我们创建时候的初始化。简单的同步我就说到这里了。下面我就将将我们一般情况下处理游戏服务器处理过程中的数据保护问题分析:

首先向大家说说服务器方面的数据保护的重要性,图例如下:

用户列表

    用户删除

    用户数据修改

    使用数据

加入队列

  对于上面的图例大家应该也能够看出在我们的游戏服务器之中,我们要对于我们用户的操作是多么的频繁。如此频繁的操作我们如果不进行处理的话,后果将是悲惨和可怕的,举例:如果我们在一个线程删除用户的一瞬间,有线程在使用,那么我们的错误将是不可难以预料的。我们将用到了错误的数据,可能会导致服务器崩溃。再者我们多个线程在修改用户数据我们用户数据将是没有办法保持正确性的。等等情况都可能发生。怎么样杜绝这样的一些情况的发生呢?我们就必须要进行服务器数据的保护。而我们如何正确的保护好数据,才能够保持服务器的稳定运行呢?下面说一下一些实际处理中的一些经验之谈。

1.我们必须充分的判断和估计我们服务器中有那些数据要进行数据保护,这些就需要设计者和规划者要根据自己的经验进行合理的分析。例如:在线用户信息列表,在线用户数据信息,消息列表等。。。。。

2.正确和十分小心的保护数据和正确的分析要保护的数据。大家知道我们要在很多地方实现我们的保护措施,也就是说我们必须非常小心谨慎的来书写我们的保护,不正确的保护会造成系统死锁,服务器将无法进行下去(我在处理的过程中就曾经遇到过,头都大了)。正确的分析要保护的数据,也就是说,我们必须要估计到我们要保护的部分的处理能够比较快的结束。否则我们必须要想办法解决这个问题:例如:

DATA_STRUCT g_data;
CRITICAL_SECTION g_cs;

EnterCriticalSection(&g_cs);
SendMessage(hWnd,WM_ONEMSG,&g_data,0);
LeaveCriticalSection(&g_cs);

以上处理就有问题了,因为我们不知道SendMessage()什么时候完成,可能是1/1000豪秒,也可能是1000年,那我们其他的线程也就不用活了。所以我们必须改正这种情况。

DATA_STRUCT g_data;
CRITICAL_SECTION g_cs;

EnterCriticalSection(&g_cs);
PostMessage(hWnd,WM_ONEMSG,&g_data,0);
LeaveCriticalSection(&g_cs);

或者 DATA_STRUCT temp_data;

EnterCriticalSection(&g_cs);
temp_data = g_cs;
LeaveCriticalSection(&g_cs);
SendMessage(hWnd,WM_ONEMSG,& temp_data,0);

3.最好不要复合保护用户数据,这样可能会出现一些潜在的死锁。

  简而言之,服务器的用户数据是一定需要进行保护,但我们在保护的过程中就一定需要万分的小心和谨慎。这篇我就说到这里了,具体的还是需要从实践中来进行学习,下节想和大家讲讲服务器的场景处理部分。

评论: 0 查看评论 发表评论

找优秀程序员,就在博客园


最新新闻:
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报:QQ的平台化价值是如何创造的?(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐:史上最强女游戏程序员

网站导航:博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

posted @ 2010-02-24 10:28 Maxice 阅读(157) | 评论 (0)编辑 收藏

阅读: 9 评论: 0 作者: Maxice 发表于 2010-02-24 10:26 原文链接

  在游戏的编写中,不可避免的出现很多应用数据结构的地方,有些简单的游戏,只是由几个数据结构的组合,所以说,数据结构在游戏编程中扮演着很重要的角色。
  本文主要讲述数据结构在游戏中的应用,其中包括对链表、顺序表、栈、队列、二叉树及图的介绍。读者在阅读本文以前,应对数据结构有所了解,并且熟悉C/C++语言的各种功用。好了,现在我们由链表开始吧!

1、链表
  在这一节中,我们将通过一个类似雷电的飞机射击游戏来讲解链表在游戏中的应用。在飞机游戏中,链表主要应用在发弹模块上。首先,飞机的子弹是要频繁的出现,消除,其个数也是难以预料的。链表主要的优点就是可以方便的进行插入,删除操作。我们便将链表这一数据结构引入其中。首先,分析下面的源代码,在其中我们定义了坐标结构和子弹链表。

  
struct CPOINT
  {
    int x;
  
// X轴坐标
    int y;  
// Y轴坐标
  
};

  struct BULLET
  {
    struct BULLE* next;
  
// 指向下一个子弹
    CPOINT bulletpos;   
// 子弹的坐标
    int m_ispeed;     
// 子弹的速度
  
};

  接下来的代码清单是飞机类中关于子弹的定义:

  
class CMYPLANE
  {
  public:
    void AddBullet(struct BULLET*);
  
// 加入子弹的函数,每隔一定时间加弹
    void RefreshBullet();       
// 刷新子弹
  
privated:
    struct BULLET *st_llMyBullet;
   
// 声明飞机的子弹链表
  
};

  在void AddBullet(struct BULLET*)中,我们要做的操作只是将一个结点插入链表中,并且每隔一段时间加入,就会产生连续发弹的效果。
  这是加弹函数主要的源代码:

  
void AddBullet(struct BULLET*)
  {
    struct BULLET *st_llNew,*st_llTemp;
  
// 定义临时链表
    st_llNew=_StrucHead;         
// 链表头(已初始化)
    st_llNew->(BULLET st_llMyBullet *)malloc(sizeof(st_llMyBullet));  
// 分配内存
    st_llTemp= =_NewBullet;        
// 临时存值
    
st_llNew->next=st_llTemp->next; st_llTemp->next=st_llNew;
  }

  函数Void RefreshBullet()中,我们只要将链表历遍一次就行,将子弹的各种数据更新,其中主要的源代码如下:

  
while(st_llMyBullet->next!=NULL)
  {

    
// 查找
    st_llMyBullet->bulletpos.x-=m_ispeed;  
// 更新子弹数据
    
………
    st_llMyBullet=st_llMyBullet->next;
   
// 查找运算
  }

  经过上面的分析,在游戏中,链表主要应用在有大规模删除,添加的应用上。不过,它也有相应的缺点,就是查询是顺序查找,比较耗费时间,并且存储密度较小,对空间的需求较大。
  如果通过对游戏数据的一些控制,限定大规模的添加,也就是确定了内存需求的上限,可以应用顺序表来代替链表,在某些情况下,顺序表可以弥补链表时间性能上的损失。当然,应用链表,顺序表还是主要依靠当时的具体情况。那么,现在,进入我们的下一节,游戏中应用最广的数据结构 — 顺序表。

2、顺序表
  本节中,我们主要投入到RPG地图的建设中,听起来很吓人,但是在RPG地图系统中(特指砖块地图系统),却主要使用数据结构中最简单的成员 — 顺序表。
  我们规定一个最简单的砖块地图系统,视角为俯视90度,并由许多个顺序连接的图块拼成,早期RPG的地图系统大概就是这样。我们这样定义每个图块:

  struct TILE  
// 定义图块结构
  
{
    int m_iAcesse;
  
// 纪录此图块是否可以通过
    ……       
// 其中有每个图块的图片指针等纪录
  };

  当m_iAcesse=0,表示此图块不可通过,为1表示能通过。
  我们生成如下地图:

  
TILE TheMapTile[10][5];

  并且我们在其中添入此图块是否可以通过,可用循环将数值加入其中,进行地图初始化。
  如图表示:

0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 1 1 1 0
2 0 0 0 0 0 1 1 1 1 0
3 0 0 0 0 0 1 1 1 1 0
4 1 1 1 1 1 1 1 1 1 1

图1


  从上图看到这个地图用顺序表表示非常直接,当我们控制人物在其中走动时,把人物将要走到的下一个图块进行判断,看其是否能通过。比如,当人物要走到(1,0)这个图块,我们用如下代码判断这个图块是否能通过:

  
int IsAcesse(x,y)
  {
    return TheMapTile[x,y].m_iAcesse;
  
// 返回图块是否通过的值
  
}

  上述只是简单的地图例子,通过顺序表,我们可以表示更复杂的砖块地图,并且,现在流行的整幅地图中也要用到大量的顺序表,在整幅中进行分块。
  好了,现在我们进入下一节:

3、栈和队列
  栈和队列是两种特殊的线性结构,在游戏当中,一般应用在脚本引擎,操作界面,数据判定当中。在这一节中,主要通过一个简单的脚本引擎函数来介绍栈,队列和栈的用法很相似,便不再举例。
  我们在设置脚本文件的时候,通常会规定一些基本语法,这就需要一个解读语法的编译程序。这里列出的是一个语法检查函数,主要功能是检查“()”是否配对。实现思想:我们规定在脚本语句中可以使用“()”嵌套,那么,便有如下的规律,左括号和右括号配对一定是先有左括号,后有右括号,并且,在嵌套使用中,左括号允许单个或连续出现,并与将要出现的有括号配对销解,左括号在等待右括号出现的过程中可以暂时保存起来。当右括号出现后,找不到左括号,则发生不配对现象。从程序实现角度讲,左括号连续出现,则后出现的左括号应与最先到来的右括号配对销解。左括号的这种保存和与右括号的配对销解的过程和栈中后进先出原则是一致的。我们可以将读到的左括号压入设定的栈中,当读到右括号时就和栈中的左括号销解,如果在栈顶弹不出左括号,则表示配对出错,或者,当括号串读完,栈中仍有左括号存在,也表示配对出错。
  大致思想便是这样,请看代码片断:

  struct  
// 定义栈结构
  
{
    int m_iData[100];
  
// 数据段
    int m_iTop;     
// 通常规定栈底位置在向量低端
  
}SeqStack;

  int Check(SeqStack *stack)  
// 语法检查函数
  
{
    char sz_ch;
    int boolean; Push(stack,'# ');
  
// 压栈,#为判断数据
    sz_ch=getchar();         
// 取值
    
boolean=1;
    while(sz_ch!='\n'&&boolean)
    {
      if(sz_ch= ='(')
        Push(stack,ch);
      if(sz_ch= =')')
        if(gettop(stack)= ='#')
 
// 读栈顶
          
boolean=0;
        else
          Pop(stack);
     
// 出栈
      
sz_ch=getchar();
    }
    if(gettop(stack)!='#') boolean=0;
    if(boolean) cout<<"right";
   
// 输出判断信息
    
else
      cout<<"error";

  这里只是介绍脚本的读取,以后,我们在图的介绍中,会对脚本结构进行深入的研究。
  总之,凡在游戏中出现先进后出(栈),先进先出(队列)的情况,就可以运用这两种数据结构,例如,《帝国时代》中地表中间的过渡带。

4、二叉树
  树应用及其广泛,二叉树是树中的一个重要类型。在这里,我们主要研究二叉树的一种应用方式:判定树。其主要应用在描述分类过程和处理判定优化等方面上。
  在人工智能中,通常有很多分类判断。现在有这样一个例子:设主角的生命值d,在省略其他条件后,有这样的条件判定:当怪物碰到主角后,怪物的反应遵从下规则:
 

表1

  根据条件,我们可以用如下普通算法来判定怪物的反应:

  
if(d<100) state=嘲笑,单挑;
  else if(d<200) state=单挑;
    else if(d<300) state=嗜血魔法;
      else if(d<400) state=呼唤同伴;
        else state=逃跑;


  上面的算法适用大多数情况,但其时间性能不高,我们可以通过判定树来提高其时间性能。首先,分析主角生命值通常的特点,即预测出每种条件占总条件的百分比,将这些比值作为权值来构造最优二叉树(哈夫曼树),作为判定树来设定算法。假设这些百分比为:

表2

  构造好的哈夫曼树为:

图2

  对应算法如下:

  
if(d>=200)&&(d<300) state=嗜血魔法;
  else if(d>=300)&&(d<500) state=呼唤同伴;
    else if(d>=100)&&(d<200) state=单挑;
      else if(d<100) state=嘲笑,单挑;
        else state=逃跑;


  通过计算,两种算法的效率大约是2:3,很明显,改进的算法在时间性能上提高不少。
  一般,在即时战略游戏中,对此类判定算法会有较高的时间性能要求,大家可以对二叉树进行更深入的研究。现在,我们进入本文的最后一节:图的介绍,终于快要完事了。

5、图
  在游戏中,大多数应用图的地方是路径搜索,即关于A*算法的讨论。由于介绍A*算法及路径搜索的文章很多,这里介绍图的另一种应用:在情节脚本中,描述各个情节之间的关系。
  在一个游戏中,可能包含很多分支情节,在这些分支情节之间,会存在着一定的先决条件约束,即有些分支情节必须在其他分支情节完成后方可开始发展,而有些分支情节没有这样的约束。
  通过分析,我们可以用有向图中AOV网(Activity On Vertex Network)来描述这些分支情节之间的先后关系。好了,现在假如我们手头有这样的情节:

情节编号 情节 先决条件
C1 遭遇强盗
C2 受伤 C1
C3 买药 C2
C4 看医生 C2
C5 治愈 C3,C4


  注意:在AOV网中,不应该出现有向环路,否则,顶点的先后关系就会进入死循环。即情节将不能正确发展。我们可以采取拓扑派序来检测图中是否存在环路,拓扑排序在一般介绍数据结构的书中,都有介绍,这里便不再叙述。
  那么以上情节用图的形式表现为(此图为有向图,先后关系在上面表格显示):
 

图3

  现在我们用邻接矩阵表示此有向图,请看下面代码片断:

  
struct MGRAPH
  {
    int Vexs[MaxVex];
      
// 顶点信息
    int Arcs[MaxLen][MaxLen];  
// 邻接矩阵
    
……
  };


  顶点信息都存储在情节文件中。
  将给出的情节表示成邻接矩阵:

0 1 0 0 0
0 0 1 1 0
0 0 0 0 1
0 0 0 0 1
0 0 0 0 0

图4


  我们规定,各个情节之间有先后关系,但没有被玩家发展的,用1表示。当情节被发展的话,就用2表示,比如,我们已经发展了遭遇强盗的情节,那么,C1与C2顶点之间的关系就可以用2表示,注意,并不表示C2已经发展,只是表示C2可以被发展了。
  请看下面的代码:

  
class CRelation
  {
  public:
    CRelation(char *filename);
        // 构造函数,将情节信息文件读入到缓存中
    void SetRelation(int ActionRelation);  // 设定此情节已经发展
    BOOL SearchRelation(int ActionRelation); // 寻找此情节是否已发展
    BOOL SaveBuf(char *filename);      
// 保存缓存到文件中
    
……
  privated:
    char* buf;
                // 邻接矩阵的内存缓冲
    
……
  };


  在这里,我们将表示情节先后关系的邻接矩阵放到缓冲内,通过接口函数进行情节关系的修改,在BOOL SearchRelation(int ActionRelation)函数中,我们可以利用广度优先搜索方法进行搜索,介绍这方面的书籍很多,代码也很长,在这里我就不再举例了。
  我们也可以用邻接链表来表示这个图,不过,用链表表示会占用更多的内存,邻接链表主要的优点是表示动态的图,在这里并不适合。
  另外,图的另一个应用是在寻路上,著名的A*算法就是以此数据结构为基础,人工智能,也需要它的基础。好了,本节结束。

评论: 0 查看评论 发表评论

找优秀程序员,就在博客园


最新新闻:
· 诺基亚两款概念手机Stealth/Dragonfly曝光(2010-03-09 09:45)
· IE6必须死 却没人做得到(2010-03-09 09:41)
· 南方日报:QQ的平台化价值是如何创造的?(2010-03-09 09:29)
· 报告称SNS网站功能趋于同质化(2010-03-09 09:26)
· 迫于压力 微软将修改浏览器选择界面算法(2010-03-09 09:09)

编辑推荐:史上最强女游戏程序员

网站导航:博客园首页  个人主页  新闻  闪存  小组  博问  社区  知识库

posted @ 2010-02-24 10:26 Maxice 阅读(242) | 评论 (0)编辑 收藏