第1篇 概述
第1章 架构,性能和游戏 (已看)
第2篇 再探设计模式
第2章 命令模式 (已看)
第3章 享元模式 (已看)
第4章 观察者模式 (已看)
第5章 原型模式 (已看)
第6章 单例模式 (已看)
第7章 状态模式 (已看)
第3篇 序列型模式
第8章 双缓冲 (已看)
第9章 游戏循环 (已看)
第10章 更新方法 (已看)
第4篇 行为型模式
第11章 字节码 (已看)
第12章 子类沙盒 (已看)
第13章 类型对象 (已看)
第5篇 解耦型模式
第14章 组件模式 (已看)
第15章 事件队列 (已看)
第16章 服务定位器 (已看)
第6篇 优化型模式
第17章 数据局部性 (已看)
第18章 脏标记模式 (已看)
第19章 对象池 (已看)
第20章 空间分区 (已看)
第1章 架构,性能和游戏
1.1 什么是软件架构
这本书关于代码的组织方式
1.1.1 什么是好的软件架构
第一个关键部分是,架构意味着变化.衡量一个设计好坏的方法就是看它应对变化的灵活性
1.1.2 你如何做出改变
一旦你理解了问题和它涉及的代码,则实际的编码有时是微不足道的
1.1.3 我们如何从解耦中受益
你可以用一堆方式来定义"解耦",但我认为如果两块代码耦合,意味着你必须同时了解这两块代码.如果你让它们解耦,那么你只需了解其一.
当然,对解耦的另一个定义就是当改变了一块代码时不必更改另外一块代码.很明显,我们需要更改一些东西,但是耦合得越低,更改所波及得范围就越小
1.2 有什么代价
良好的架构需要很大的努力及一系列准则.每当你做出一个改变或者实现一个功能时,你必须很优雅地将它们融入到程序的其余部分.你必须非常谨慎地组织代码并保证其在开发周期中经过数以千计的小变化之后仍然具有良好的组织性
1.3 性能和速度
没有人可以在纸上设计出一个平衡的游戏.这需要迭代和实验.
1.4 坏代码中的好代码
原型(把那些仅仅在功能上满足一个设计问题的代码融合在一起)是一个完全正确的编程实践
1.5 寻求平衡
开发中我们有几个因素需要考虑
1. 我们想获得一个良好的架构,这样在项目的生命周期中便会更容易理解代码
2. 我们希望获得快速的运行时性能
3. 我们希望快速完成今天的功能
这些目标至少部分是相冲突的.好的架构从长远来看,改进了生产力,但维护一个良好的架构就意味着每一个变化都需要更多的努力来保持代码的干净
最快编写的代码实现却很少是运行最快的.相反,优化需要消耗工程时间.一旦完成,也会使代码库僵化:高度优化过的代码缺乏灵活性,很难改变
完成今日的工作并担心明天的一切总伴随着压力.但是,如果我们尽可能快的完成功能,我们的代码库就会充满了补丁,bug和不一致的混乱,会一点点地消磨掉我们未来的生产力
这里没有简单的答案,只有权衡
1.6 简单性
1.7 准备出发
抽象和解耦能够使得你的程序开发变得更快和更简单.但不要浪费时间来做这件事,除非你确信存在问题的代码需要这种灵活性
在你的开发周期中要对性能进行思考和设计,但是要推迟那些降低灵活性的,底层的,详尽的优化,能晚则晚
尽快地探索你的游戏的设计空间,但是不要走得太快留下一个烂摊子给自己.毕竟你将不得不面对它
如果你将要删除代码,那么不要浪费时间将它整理得很整洁.摇滚明星把酒店房间弄得很乱是因为他们知道第二天就要结账走人.
但是,最重要得是,若要做一些有趣得玩意,那就乐在其中地做吧
第2章 命令模式
"将一个请求(request)封装成一个对象,从而允许你使用不同的请求,队列或日志将客户端参数化,同时支持请求操作的撤销和恢复"
我想你也和我一样觉得这句话晦涩难懂.
首先,它的比喻不够形象.在软件界之外,一词往往多义."客户(client)"指代同你有着某种业务往来的一类人.据我查证,人类(human beings)是不可"参数化"的
其次,句子的剩余部分只是列举了这个模式可能的使用场景.而万一你遇到的用例不在其中,那么上面的阐述就不太明朗了.
我对命令模式的精炼概括如下: 命令就是一个对象化(实例化)的方法调用(A command is a reified(具象化) method call)
这个术语意味着,将某个概念(concept)转化为一块数据(data),一个对象,或者你可以认为是传入函数的变量等.
GOF后面这样补充到: 命令就是面向对象化的回调(Commands are an object-oriented replacement for callbacks)
一些语言的反射系统(Reflection system)可以让你在运行时命令式地处理系统中的类型.你可以获取到一个对象,它代表着某些其他对象的类,你可以通过它试试看这个类型能做些什么.话句话说,反射是一个对象化的类型系统
2.1 配置输入
简单实现
void InputHandler::handleInput() {
if (isPressed(BUTTON_X)) jump();
else if (isPressed(BUTTON_Y)) fireGun();
else if (isPressed(BUTTON_A)) swapWeapon():
else if (isPressed(BUTTON_B)) lurchIneffectively();
}
class Command {
public:
;
virtual ~Command() {}
};
class JumpCommand: public Command {
public:
virtual void execute() { jump(); }
};
class FireCommand: public Command {
public:
virtual void execute() { fireGun(); }
};
class InputHandler {
public:
void handleInput();
// Methods to bind commands...
private:
Command * buttonX_;
Command * buttonY_;
Command * buttonA_;
Command * buttonB_;
};
void InputHandler::handleInput() {
if (isPressed(BUTTON_X)) buttonX_->execute();
else if (isPressed(BUTTON_Y)) buttonY_->execute();
else if (isPressed(BUTTON_A)) buttonA_->execute();
else if (isPressed(BUTTON_B)) buttonB_->execute();
}
2.2 关于角色的说明
控制任意游戏角色
class Command {
public:
;
virtual void ~Command() {}
};
class JumpCommand: public Command {
public:
virtual void execute(GameActor & actor) {
actor.jump();
}
};
Command * InputHandler::handleInput() {
if (isPressed(BUTTON_X)) return buttonX_;
if (isPressed(BUTTON_Y)) return buttonY_;
if (isPressed(BUTTON_A)) return buttonA_;
if (isPressed(BUTTON_B)) return buttonB_;
return NULL;
}
Command * command = inputHandler.handleInput();
if (command) {
command->execute(actor);
}
2.3 撤销和重做
在上个例子中,我们想要从被操控的角色中抽象出命令,以便将角色和命令解耦.在这个例子中,我们特别希望将命令绑定到被移动的单位上.这个命令的实例不是一般性质的"移动某些物体"这样适用于很多情境下的操作,在游戏的回合次序中,它是一个特定具体的移动
这凸显了命令模式在实现时的一个变化.在某些情况下,像我们第一对的例子,一个命令代表了一个可重用的对象,表示一件可完成的事情(a thing that can be done).
这里,这些命令更加具体.他们表示一些可在特定时间点完成的事情.
class MoveUnitCommand: public Command {
public:
MoveUnitCommand(Unit * unit, int x, int y) : unit_(unit),x_(x),y_(y) {}
virtual void execute() {
unit_->moveTo(x_, y_);
}
private:
Unit * unit_;
int x_;
int y_;
};
Command * handleInput() {
Unit * unit = getSelectedUnit();
if (isPressed(BUTTON_UP)) {
;
return new MoveUnitCommand(unit, unit->x(), destY);
}
if (isPressed(BUTTON_DOWN)) {
;
return new MoveUnitComand(unit, unit->x(), destY);
}
return NULL;
}
可撤销的命令
class Command {
public:
;
;
virtual ~Command() {}
};
class MoveUnitCommand: public Command {
public:
MoveUnitCommand(Unit * unit, ), yBefore() {}
virtual void execute() {
xBefore_ = unit_->x();
yBefore_ = unit_->y();
unit_->moveTo(x_, y_);
}
virtual void undo() {
unit_>moveTo(xBefore_, yBefore_);
}
private:
Unit * unit_;
int x_, y_;
int xBefore_, yBefore_;
};
2.4 类风格化还是函数风格化
function makeMoveUnitCommand(unit, x, y) {
// This function here is the command object;
return function() {
unit.move(x, y);
}
}
function makeMoveUnitCommand(unit, x, y) {
var xBefore, yBefore;
return {
execute: function() {
xBefore = unit.x();
yBefore = unit.y();
unit.moveTo(x, y);
},
undo: function() {
unit.moveTo(xBefore, yBefore);
}
};
}
2.5 参考
1. 你可能最终会有很多不同的命令类.为了更容易地实现这些类,可以定义一个具体的基类,里面有着一些实用的高层次的方法,这样便可以通过对派生出来的命令组合来定义其行为,这么做通常是有帮助的.它会将命令的主要方法execute()变成子类沙盒
2. 在我们的例子中,我们明确地选择了那些会执行命令的角色.在某些情况下,尤其是在对象模型分层的情况下,它可能没有这么直观.一个对象可以响应一个命令,而它也可以决定将命令下放给其从属对象.如果你这样做,你需要了解下责任链
3. 一些命令如第一个例子中的JumpCommand是无状态的纯行为的代码块.在类似这样的情况下,拥有不止一个这样命令类的实例会浪费内存,因为所有的实例是等价的.享元模式就是解决这个问题的.
第3章 享元模式
使用共享以高效地支持大量的细粒度对象
3.1 森林之树
用代码来表示一颗树
class Tree {
private:
Mesh mesh_;
Texture bark_;
Texutre leaves_;
Vector position_;
double height_;
double thickness_;
Color barkTinit_;
Color leafTinit_;
};
要让GPU在每帧都显示成千上万的树数据量会很大,尤其是网格和纹理.
我们可以将对象分割成两个独立的类,游戏中每一颗树的实例都有一个指向共享的TreeModel的引用
class TreeModel {
private:
Mesh mesh_;
Texture bark_;
Texture leaves_;
};
class Tree {
private:
TreeModel * model_;
Vector position_;
double height_;
double thickness_;
Color barkTint_;
Color leafTint_;
};
3.2 一千个实例
3.3 享元模式
享元(Flyweight),顾名思义,一般来说当你有太多对象并考虑对其进行轻量化时它便能派上用场
享元模式通过将对象数据切分成两种类型来解决问题.
第一种类型数据是那些不属于单一实例对象并且能够被所有对象共享的数据.GoF将其称为内部状态(the intrinsic state),但我更喜欢将它认为是"上下文无关"的状态.在本例中,这指的便是数木的几何形状和纹理数据等.
其他数据便是外部状态(the extrinsic state), 对于每一个实例它们都是唯一的.在本例中,指的是每颗树的位置,缩放比例和颜色.
3.4 扎根之地
简陋的实现
enum Terrain {
TERRAIN_GRASS,
TERRAIN_HILL,
TERRAIN_RIVER
// Other terrains...
};
class World {
private:
Terrain tiles_[WIDTH][HEIGHT];
};
int World::getMovementCost(int x, int y) {
switch (tiles_[x][y]) {
;
;
;
// Other terrains...
}
}
bool World::isWater(int x, int y) {
switch (tiles_[x][y]) {
case TERRAIN_GRASS: return false;
case TERRAIN_HILL: return false;
case TERRAIN_RIVER: return true;
// Other terrains...
}
}
使用享元
class Terrain {
public:
Terrain(int movementCost, bool isWater, Texture texture): moveCost_(moveCost), isWater_(isWater), texture_(texture) {}
int getMoveCost() const { return moveCost_; }
bool isWater() const { return isWater_; }
const Texture & getTexture() const {
return texture_;
}
private:
int moveCost_;
bool isWater_;
Texture texture_;
};
class World {
public:
World() : grassTerrain_(, , , true, RIVER_TEXTURE) {}
private:
Terrain grassTerrain_;
Terrain hillTerrain_;
Terrain riverTerrain_;
// Other stuff...
};
void World::generateTerrain() {
; x < WIDTH; x++) {
; y < HEIGHT; y++) {
) == ) {
tiles_[x][y] = &hillTerrain_;
} else {
tiles_[x][y] = &grassTerrain_;
}
}
}
int x = random(WIDTH);
; y < HEIGHT; y++) {
tiles_[x][y] = &riverTerrain_;
}
}
3.5 性能表现如何
3.6 参考
1. 在上面草地瓦片的例子中,我们只是匆忙地为每个地形类型创建一个实例然后将之存储到World中.这使得查找和重用共享实例变得很简单.然而在许多情况下,你并不会在一开始便创建所有的享元.如果你不能预测哪些是你真正需要的,则最好按需创建它们.为了获得共享优势,当你需要一个对象时,你要先看看你是否已经创建了一个相同的对象.如果是,则只需返回这个实例.这通常意味着在一些用来查找现有对象的接口背后,你必须做些结构上的封装.像这样隐藏构造函数,其中一个例子就是工厂方法模式
2. 为了找到以前创建的享元,你必须追踪哪些你已经实例化过的对象的池(pool).正如其名,这意味着,对象池模式对于存储它们会很有用
3. 在使用状态模式时,你经常会拥有一些"状态"对象,对于状态所处的状态机而言它们没有特定的字段.状态的标识和方法也足够有用.在这种情况下,你可以同时在多个状态机中始使用这种模式,并且重用这个相同的状态实例并不会带来任何问题
第4章 观察者模式
在对象间定义一种一对多的依赖关系,以便当某对象的状态改变时,与它存在依赖关系的所有对象都能收到通知并自动进行更新
在计算机上随便打开一个应用,它就很有可能就是采用Model-View-Controller架构开发,而其底层就是观察者模式.观察者模式应用十分广泛,Java甚至直接把它集成到了系统库里面(java.util.Observer),C#更是直接将它集成在了语言层面(event关键字)
4.1 解锁成就
简陋实现
void Physics::updateEntity(Entity & entity) {
bool wasOnSurface = entity.isOnSurface();
entity.accelerate(GRAVITY);
entity.update();
if (wasOnSurface && !entity.isOnSurface()) {
notify(entity, EVENT_START_FAILE);
}
}
4.2 这一切是怎么工作的
4.2.1 观察者
class Observer {
public:
;
virtual void ~Observer() {}
};
class Achievements: public Observer {
public:
virtual void onNotify(const Entity & entity, Event event) {
switch( event) {
case EVENT_ENTITY_FELL:
if (entity.isHero() && heroIsOnBridge_) {
unlock(ACHIEVEMENT_FELL_OFF_BRIDGE);
}
break;
// Handle other events...
// Update heroIsOnBridge...
}
}
private:
void unlock(Achievement achievenment) {
// Unlock if not already unlocked...
}
bool heroIsOnBridge_;
};
4.2.2 被观察者
通知方法会被正在被观察的对象调用.在GoF的术语里,这个对象被称为"被观察对象(Subject)".它有两个职责.首先,它拥有观察者的一个列表,这些观察者在随时候命接收各种各样的通知,其次就是发送通知
class Subject {
private:
Observer * observers_[MAX_OBSERVERS];
int numObservers_;
};
class Subject {
public:
void addObserver(Observer * observer) {
// Add to array...
}
void removeObserver(Observer * observer) {
// Remove from array...
}
protected:
void notify(const Entity & entity, Event event) {
; i < numObservers_; i++) {
observers_[i]->onNotify(entity, event);
}
}
// Other stuff...
};
允许外部的代码来控制谁可以接收通知.这个被观察者对象负责和观察者对象进行沟通,但是,它并不与它们耦合
同时,被观察者对象拥有一个观察者对象的集合,而不是单个观察者,这也是很重要的.它保证了观察者们并不会隐式地耦合在一起.例如,声音引擎也注册了落水事件,这样在该成就达成的时候,就可以播放一个合适的声音.如果被观察者对象不支持多个观察者的话,当声音引擎注册这个事件的时候,成就系统就无法注册该事件了
这意味着,两个系统会相互干扰对方----而且是以一种很不恰当的方式,因为第二个观察者使第一个观察者失效了.观察者集合的存在,可以让每一个观察者都互相不干扰.在它们各自的眼里,都认为被观察者对象眼里只有它自己
4.2.3 可被观察的物理模块
class Physics: public Subject {
public:
void updateEntity(Entity & entity);
};
在实际代码中,我会尽量避免使用继承.取而代之的是,我们让Physics系统有一个Subject实例.与观察物理引擎相反,我们的被观察者对象会是一个单独的"下落事件"对象.观察者会使用下面的代码 physics.entityFell().addObserver(this);
对我而言,这就是"观察者"系统和"事件"系统的区别.前者,你观察一个事情,它做了一些你感兴趣的事.后者,你观察一个对象,这个对象代表了已经发生的有趣的事情.
4.3 它太慢了
发送一个通知,只不过需要遍历一个列表,然后调用一些虚函数.老实讲,它比普通的函数调用会慢一些,但是虚函数带来的开销几乎可以忽略不计,除了对性能要求极其高的程序
4.4 太多的动态内存分配
4.4.1 链式观察者
class Subject {
Subject(): head_(NULL) {}
// Methods...
private:
Observer * head_;
};
void Subject::addObserver(Observer * observer) {
observer->next_ = head_;
head_ = observer;
}
void Subject::removeObserver(Observer * observer) {
if (head_ == observer) {
head_ = observer->next_;
observer->next_ = NULL;
return;
}
Observer * current = head_;
while (current != NULL) {
if (current->next_ == observer) {
current->next_ = observer->next_;
observer->next_ = NULL;
return;
}
current = current->next_;
}
}
void Subject::notify(const Entity & entity, Event event) {
Observer * observer = head_;
while (observer != NULL) {
observer->onNotify(entity, event);
observer = observer->next_;
}
}
class Observer {
friend class Subject;
public:
Observer(): next_(NULL) {}
// Other stuff...
private:
Observer * next_;
};
4.4.2 链表节点池
4.5 余下的问题
设计模式会遭人诟病,大部分是由于人们用一个好的设计模式去处理错误的问题,所以事情变得更加糟糕了
4.5.1 销毁被观察者和观察者
当一个被观察者对象被删除时,观察者本身应该负责把它自己从被观察者对象中移除.通常情况下,观察者都知道它在观察着哪些被观察者,所以需要做的只是在析构器中添加一个removeObserver()方法
当一个被观察者对象被删除时,如果不我们不想让观察者来处理问题,则可以修改以下做法.我们只需要在被观察者对象被删除之前,给所有的观察者发送一个"死亡通知"就可以了.这样,所有已注册的观察者都可以收到通知并进行相应的处理
4.5.2 不用担心,我们有GC
4.5.3 接下来呢
观察者模式非常适合于一些不相关的模块之间的通信问题.它不适合于单个紧凑的模块内部的通信.
这也是为什么它适合我们的例子: 成就系统和物理系统是完全不相关的领域,而且很有可能是由不同的人实现的.我们想让它们的通信尽可能地减少,这样任何一个模块都不用依赖另一个模块就可以工作
4.6 观察者模式的现状
4.7 观察者模式的未来
第5章 原型模式
使用特定原型实例来创建特定种类的对象,并且通过拷贝原型来创建新的对象.
5.1 原型设计模式
初始实现
class Monster {
// Stuff...
};
class Ghost: public Monster {};
class Demon: public Monster {};
class Sorcerer: public Monster {};
class Spawner {
public:
;
virtual ~Spawner() {}
};
class GhostSpawner: public Spawner {
public:
virtual Monster * spawnMonster() {
return new Ghost();
}
};
class DemonSpawner: public Spawner {
public:
virtual Monster * spawnMonster() {
return new Demo();
}
};
// Other
原型模式提供了一种解决方案.其核心思想是一个对象可以生成与自身相似的其他对象.如果你有一个幽灵,则你可以通过这个幽灵制作出更多的幽灵,如果你有一个魔鬼,那你就能制作出其他魔鬼.任何怪物都能被看作是一个原型,用这个原型就可以复制出更多不同版本的怪物
class Monster {
public:
;
virtual ~Monster() {}
// Other stuff...
};
class Ghost: public Monster {
public:
Ghost(int health, int speed): health_(health), speed_(speed) {}
virtual Monster * clone() {
return new Ghost(health_, speed_);
}
private:
int health_;
int speed_;
};
class Spawner {
public:
Spawner(Monster * prototype): prototype_(prototype) {}
Monster * spawnMonster() {
return prototype_->clone();
}
private:
Monster * prototype_;
};
Monster * ghostPrototype = , );
Spawner * ghostSpawner = new Spawner(ghostPrototype);
关于这个模式,有点比较优雅的是,它不仅克隆原型类,而且它也克隆了对象的状态.
5.1.1 原型模式效果如何
5.1.2 生成器函数
Monster * spawnGhost() {
return new Ghost();
}
typedef Monster * (*SpawnCallback)();
class Spawner {
public:
Spawner(SpawnCallback spawn): spawn_(spawn) {}
Monster * spawnMonster() { return spawn_(); }
private:
SpawnCallback spawn_;
};
Spawner * ghostSpawner = new Spawner(spawnGhost);
5.1.3 模板
class Spawner {
public:
;
virtual ~Spawner() {}
};
template <class T>
class SpawnerFor: public Spawner {
public:
virtual Monster * spawnMonster() { return new T(); }
};
Spawner * ghostSpawner = new SpawnerFor<Ghost>();
5.1.4 头等公民类型(First-class types)
5.2 原型语言范式
5.2.1 Self语言
5.2.2 结果如何
5.2.3 JavaScript如何
function Weapon(range, damage) {
this.range = range;
this.damage = damage;
}
, );
Weapon.prototype.attack = function(target) {
if (distanceTo(target) > this.range) {
console.log("Out of range!");
} else {
target.health -= this.damage;
}
}
5.3 原型数据建模
第6章 单例模式
确保一个类只有一个实例,并为其提供一个全局访问入口 http://wiki.c2.com/?SingletonPattern
6.1 单例模式
6.1.1 确保一个类只有一个实例
在有些情况下,一个类如果有多个实例就不能正常运作.最常见的就是,这个类与一个维持着自身全局状态的外部系统进行交互的情况.
6.1.2 提供一个全局指针以访问唯一实例
class FileSystem {
public:
static FileSystem & instance() {
// Lazy initialize
if (instance_ == NULL) {
instance_ = new FileSystem();
}
return *instance_;
}
private:
FileSystem() {}
static FileSystem * instance_;
};
// 更现代的版本
class FileSystem {
public:
static FileSystem & instance() {
static FileSystem * instance = new FileSystem();
return *instance;
}
private:
FileSystem() {}
};
6.2 使用情境
优点
1. 如果我们不使用它,就不会创建实例
2. 它在运行时初始化
3. 你可以继承单例,这是一个强大但是经常被忽视的特性
class FileSystem {
public:
static FileSystem & instance();
;
;
virtual ~FileSystem() {}
protected:
FileSystem() {}
};
class PS3FileSystem: public FileSystem {
public:
virtual char * read(char * path) {
// Use Sony file IO API...
}
virtual void write(char * path, char * text) {
// Use sony file IO API...
}
}；
class WiiFileSystem: public FileSystem {
public:
virtual char * read(char * path) {
// Use Nintendo file IO API...
}
virtual void write(char * path, char * text) {
// Use Nintendo file IO API...
}
};
FileSystem & FileSystem::instance() {
#if PLATFORM == PLAYSTATION3
static FileSystem * instance = new PS3FileSystem();
#elif PLATFORM == WII
static FileSystem * instance = new WiiFileSystem();
#endif
return *instance;
}
6.3 后悔使用单例的原因
6.3.1 它是一个全局变量
我们学到的一个教训就是,全局变量是有害的,理由如下
1. 它们令代码晦涩难懂
2. 全局变量促进了耦合
3. 它对并发不友好
6.3.2 它是个画蛇添足的解决方案
6.3.3 延迟初始化剥离了你的控制
6.4 那么我们该怎么做
6.4.1 看你究竟是否需要类
我见过的游戏中的许多单例类都是"managers"----这些保姆类只是为了管理其他对象.我见识过一个代码库,里面好像每个类都有一个管理者: Monster, MonsterManager, Particle, ParticleManager, Sound, SoundManager, ManagerManager.有时为了区别,它们叫做"System"或“Engine",不过只是改了名字而已
尽管保姆类有时是有用的,不过这通常反映出它们对OOP不熟悉.比如下面这两个虚构的类
class Bullet {
public:
int getX() const { return x_; }
int getY() const { return y_; }
void setX(int x) { x_ = x; }
void setY(int y) { y_ = y; }
private:
int x_;
int y_;
};
class BulletManager {
public:
Bullet * create(int x, int y) {
Bullet * bullet = new Bullet();
Bullet->setX(x);
Bullet->setY(y);
return bullet;
}
bool isOnScreen(Bullet & bullet) {
&&
bullet.getY() >= &&
bullet.getX() < SCREEN_WIDTH &&
bullet.getY() < SCREEN_HEIGHT;
}
void move(Bullet & bullet) {
bullet.setX(bullet.getX() + );
}
};
或许这个例子有点蠢,但是我见过很多代码在剥离了外部细节之后,所暴露出来的设计就是这样的.如果你查看这段代码,那你自然会想,BulletManager应该是个单例.毕竟任何包含Bullet的对象都需要这个管理器,而你需要有多少个BulletManager实例呢?
事实上,这里的答案是零.我们是这样解决管理类的"单例"问题的:
class Bullet {
public:
Bullet(int x, int y): x_(x), y_(y) {}
bool isOnScreen() {
&& x_ < SCREEN_WIDTH &&
y_ >= && y_ < SCREEN_HEIGHT;
}
; }
private:
int x_, y_;
};
就这样.没有管理器也没有问题.设计糟糕的单例通常会"帮助"你往其他类中添加功能.如果可以,你只需要将这些功能移动到它所帮助的类中去就可以了.毕竟,面向对象就是让对象自己管理自己
6.4.2 将类限制为单一实例
一个assert()意味着"我确保这个应该始终为true,如果不是,这就是一个bug,并且我想立刻停止以便你能修复它".这可以让你在代码域之间定义约定.如果一个函数断言它的某个参数不为NULL,那么就是说"函数和调用者之间约定不能够传递NULL".
6.4.3 为实例提供便捷的访问方式
通用的原则是,在保证功能的情况下将变量限制在一个狭窄的范围内.对象的作用越小,我们需要记住它的地方就越少.在我们盲目地采用具有全局作用域的单例对象之前,让我们考虑下代码库访问一个对象的其他途径
传递进去: 最简的解决方式,通常也是最好的方式,就是将这个对象当作一个参数传递给需要它的函数
在基类中获取它: 许多游戏架构有浅层次但是有宽度的继承体系,通常只有一层继承 面向切面编程
class GameObject {
protected:
Log & Log() { return log_; }
private:
static Log & log_;
};
class Enemy: public GameObject {
void doSomething() {
getLog().write("I can log!");
}
};
通过其他全局对象访问它: 我们可以通过将全局对象类包装到现有类里面来减少它们的数量.那么除了依次创建Log, FileSystem和AudioPlayer单例外,我们可以:
class Game {
public:
static Game & instance() { return instance_; }
Log & log() { return *log_; }
FileSystem & fileSystem() { return *file_; }
AudioPlayer & audioPlayer() { return *audio_; }
// Functions to set log_, et. al. ...
private:
static Game instance_;
Log *log_;
FileSystem *files_;
AudioPlayer *audio_;
};
通过服务定位器来访问: 到现在为止, 我们假设全局类就是像Game那样的具体类.另外一个选择就是定义一个类专门用来给对象做全局访问. 这个模式被称为服务定位器模式
6.5 剩下的问题
还有一个问题,我们应该在什么情况下使用真正的单例呢?老实说,我没有在任何游戏中使用GoF实现版本的单例.为了确保只实例化一次,我通常只是简单地使用一个静态类.如果那不起作用,我就会用一个静态的标识位在运行时检查是否只有一个类实例被创建
第7章 状态模式
允许一个对象在其内部状态改变时改变自身的行为.对象看起来好像是在修改自身类. https://en.wikipedia.org/wiki/State_pattern
7.1 我们曾经相遇过
void Heroine::handleInput(Input input) {
if (input == PRESS_B) {
if (!isJumping_ && !isDucking_) {
// Jump...
}
} else if (input == PRESS_DOWN) {
if (!isJumping_) {
isDucking_ = true;
setGraphics(IMAGE_DUCK);
} else {
isJumping_= false;
setGraphics(IMAGE_DIVE);
}
} else if (input == RELEASE_DOWN) {
if (isDucking_) {
// Stand...
}
}
}
7.2 救星: 有限状态机
有限状态机(FSM)可以看作最简单的图灵机
整个状态机可以分为: 状态,输入和转换
你拥有一组状态,并且可以在这组状态之间进行切换
状态机同一时刻智能处于一种状态
状态机会接收一组输入或者事件
每一个状态有一组转换,每一个转换都关联着一个输入并指向另外一个状态
7.3 枚举和分支
enum State {
STATE_STANDING,
STATE_JUMPING,
STATE_DUCKING,
STATE_DIVING
};
void Heroine::handleInput(Input input) {
switch(state_) {
case STATE_STANDING:
if (input == PRESS_B) {
state_ = STATE_JUMPING;
yVelocity_ = JUMP_VELOCITY;
setGraphics(IMAGE_JUMP);
} else if (input == PRESS_DOWN) {
state_ = STATE_DUCKING;
setGraphics(IMAGE_DUCK);
}
break;
// Other states...
}
}
void Heroine::update() {
if (state_ == STATE_DUCKING) {
chargeTime_++;
if (chargeTime_ > MAX_CHARGE) {
superBomb();
}
}
}
7.4 状态模式
7.4.1 一个状态接口
class HeroineState {
public:
virtual void handleInput(Heroine & heroine, Input input) {}
virtual void update(Heroine & heroine) {}
virtual ~HeroineState() {}
};
7.4.2 为每一个状态定义一个类
class DuckingState: public HeroineState {
public:
DuckingState(): chargeTime_() {}
virtual void handleInput(Heroine & heroine, Input input) {
if (input == RELEASE_DOWN) {
// Change to standing state...
heroine.setGraphics(IMAGE_STAND);
}
}
virtual void update(Heroine & heroine) {
chargeTime++;
if (chargeTime_ > MAX_CHARGE) {
heroine.superBomb();
}
}
private:
int chargeTime_;
};
7.4.3 状态委托
class Heroine {
public:
virtual void handleInput(Input input) {
state_->handleInput(*this, input);
}
virtual void update() { state_->update(*this); }
// Other methods...
private:
HeroineState * state_;
};
7.5 状态对象应该放在哪里呢
7.5.1 静态状态
class HeroineState {
public:
static StandingState standing;
static DuckingState ducking;
static JumpingState jumping;
static DivingState diving;
// Other code...
};
if (input == PRESS_B) {
heroine.state_ = &HeroineState::jumping;
heroine.setGraphics(IMAGE_JUMP);
}
7.5.2 实例化状态
void Heroine::handleInput(Input input) {
HeroineState * state = state_->handleInput(*this, input);
if (state != NULL) {
delete state_;
state_ = state;
}
}
HeroineState * StandingState::handleInput(Heroine & heroine, Input input) {
if (input == PRESS_DOWN) {
// Other code...
return new DuckingState();
}
// Stay in this state.
return NULL;
}
7.6 进入状态和退出状态的行为
HeroineState * DuckingState::handleInput(Heroine & heroine, Input input) {
if (input == RELEASE_DOWN) {
heroine.setGraphics(IMAGE_STAND);
return new StandingState();
}
// Other code...
}
class StandingState: public HeroineState {
public:
virtual void enter(Heroine & heroine) {
heroine.setGraphics(IMAGE_STAND);
}
// Other code...
};
void Heroine::handleInput(Input input) {
HeroineState * state = state_->handleInput(*this, input);
if (state != NULL) {
delete state_;
state_ = state;
// Call the enter action on the new state
state_->enter(*this);
}
}
HeroineState * DuckingState::handleInput(Heroine & heroine, Input input) {
if (input == RELEASE_DOWN) {
return new StandingState();
}
// Other code...
}
7.7 有什么收获吗
7.8 并发状态机
class Heroine {
// Other code...
private:
HeroineState * state_;
HeroineState * equipment_;
};
void Heroine::handleInput(Input input) {
state_->handleInput(*this, input);
equipment_->handleInput(*this, input);
}
7.9 层次状态机
层次状态机:一个状态有一个父状态.当有一个事件进来的时候,如果子状态不处理它,那么沿着继承链传给它的父状态来处理.换句话说,它有点像覆盖继承的方法
class OnGroundState: public HeroineState {
public:
virtual void handleInput(Heroine & heroine, Input input) {
if (input == PRESS_B) {
// Jump...
} else if (input == PRESS_DOWN) {
// Duck...
}
}
};
class DuckingState: public OnGroundState {
public:
virtual void handleInput(Heroine & heroine, Input input) {
if (input == RELEASE_DOWN) {
// Stand up...
} else {
// Didn't handle input, so walk up hierarchy
OnGroundState::handleInput(heroine, input);
}
}
};
7.10 下推自动机
下推自动机(pushdown automata)
你可以把新的状态放入栈里面.当前的状态永远存在栈顶,所以你总能转换到当前状态.但是当前状态会将前一个状态压在栈中自身的下面而不是抛弃掉它
你可以弹出栈顶的状态,改状态将被抛弃.与此同时,上一个状态就变成了新的栈顶状态了
7.11 现在知道它们有多有用了吧
即使有了这些通用的状态机扩展,它们的使用范围仍然是有限的.在游戏的AI领域,最近的趋势是越来越倾向于行为树和规划系统.
但是这并不意味着有限状态机,下推自动机和其他简单的状态机没有用.它们对于解决某些特定的问题是一个很好的建模工具.当你的问题满足以下几点要求的时候,有限状态机将会非常有用
你有一个游戏实体,它的行为基于它的内部状态而改变
这些状态被严格划分为相对数目较少的小集合
游戏实体随着时间的变化会响应用户输入和一些游戏事件
第8章 双缓冲
8.1 动机
8.1.1 计算机图形系统是如何工作的(概述)
诸如计算机显示器的显示设备在每一时刻仅绘制一个像素.显示设备从左至右地扫描屏幕屏幕每行中的像素,并如此从上至下地扫描屏幕上的每一行.当它扫描至屏幕的右下角时,它将重定位至屏幕的左上角并如前述那样地重复扫描屏幕.这一扫描过程是如此地快速(大概每秒60次),以至于我们的眼睛无法察觉这一过程.对于我们而言,扫描的结果就是屏幕一块彩色像素组成的静态区域,即一张图片
我们的程序一次只渲染一个像素,同时我们要求显示器一次性显示所有的像素----可能这一帧看不到任何东西,但下一帧显示的就是完整的笑脸.双缓冲模式解决了这一问题
8.1.2 第一幕,第一场
8.1.3 回到图形上
双缓冲中的一个缓存用于展示当前帧,于此同时,渲染代码正在另一个缓冲区中写入数据.当渲染代码完成时,通过交换缓冲区,使得显卡驱动开始从第一个缓冲区转向第二个缓冲区以读取其数据进行渲染.只要它掌握好时机在每次刷新显示器结束时进行切换,我们就不会看到任何衔接的裂隙,且整个场景能一次性的瞬间显示出来
8.2 模式
定义一个缓冲区类来封装一个缓冲区:一块能被修改的状态区域.这块缓冲区能被逐步地修改,但我们希望任何外部的代码将对该缓冲区的修改都视为原子操作.为实现这一点,此类中维护两个缓冲区实例:后台缓冲区和当前缓冲区
当要从缓冲区读取信息时,总是从当前缓冲区读取.当要往缓冲区中写入数据时,则总在后台缓冲区上进行.当改动完成后,则执行"交换"操作来将当前缓冲区与后台缓冲区进行瞬时的交换,以便让新的缓冲区为我们所见,同时刚被换下来的当前缓冲区则成为现在的后台缓冲区以供复用
8.3 使用情境
当下面这些条件都成立时,使用双缓冲模式:
我们需要维护一些被逐步改变着的状态量
同个状态可能会在其被修改的同时被访问到
我们希望避免访问状态的代码能看到具体的工作过程
我们希望能够读取状态但不希望等待写入操作的完成
8.4 注意事项
不像那些较大的架构模式,双缓冲模式处于一个实现层次相对底层的位置.因此,它对代码库的影响较小----甚至多数游戏都不会察觉到这些差别
8.4.1 交换本身需要时间
双缓冲模式需要在状态写入完成后进行一次交换操作,操作必须是原子性的:也就是说任何代码都无法在这个交换期间对缓冲区内的任何状态进行访问.通常这个交换过程和分配一个指针的速度差不多,但如果交换用去了比修改初始状态更多的时间,那这样模式就毫无助益了
8.4.2 我们必须有两份缓冲区
这个模式的另外一个后果就是增加了内存使用.
8.5 示例代码
class Framebuffer {
public:
// Constructor and methods...
private:
;
;
char pixels_[WIDTH * HEIGHT];
};
void Framebuffer::clear() {
; i < WIDTH * HEIHGT; i++) {
pixels_[i] = WHITE;
}
}
void Framebuffer::draw(int x, int y) {
pixels_[(WIDTH * y) + x] = BLACK;
}
const char * Framebuffer::getPixels() {
return pixels_;
}
class Scene {
public:
void draw() {
buffer_.clear();
buffer_.draw(, );
buffer_.draw(, );
buffer_.draw(, );
buffer_.draw(, );
buffer_.draw(, );
buffer_.draw(, );
}
Framebuffer & getBuffer() { return buffer_; }
private:
Framebuffer buffer_;
};
buffer_.draw(, );
buffer_.draw(, );
// <- Video driver reads pixels here!
buffer_.draw(, );
buffer_.draw(, );
buffer_.draw(, );
buffer_.draw(, );
class Scene {
public:
Scene(): current_(&buffer_[]), next_(&buffer_[]) {}
void draw() {
next_->clear();
next_->draw(,);
// ...
next_->draw(, );
swap();
}
Framebuffer & getBuffer() { return *current_; }
private:
void swap() {
// Just switch the pointers.
Framebuffer * temp = current_;
current_ = next_;
next_ = current_;
}
Framebuffer buffers_[];
Framebuffer * current_;
Framebuffer * next_;
};
8.5.1 并非只针对图形
双缓冲模式所解决的核心问题就是对状态同时进行修改与访问的冲突.造成此问题的原因通常有两个,我们已经通过上述图形示例描述了第一种情况----状态直接被另一个线程或中断的代码所直接访问
而另一种情况同样很常见:进行状态修改的代码访问到了其正在修改的那个状态.这会在很多地方发生:尤其是实体的AI和物理部分,在它与其他实体进行交互时会发生这样的情况,双缓冲模式往往能在此情形下奏效
8.5.2 人工非智能
class Actor {
public:
Actor(): slapped_(false) {}
;
virtual ~Actor() {}
void reset() { slapped_ = false; }
void slap() { slapped_ = true; }
bool wasSlapped() { return slapped_; }
private:
bool slapped_;
};
class Stage {
public:
vodi add(Actor * actor, int index) {
actors_[index] = actor;
}
void update() {
; i < NUM_ACTORS; i++) {
actors_[i]->update();
actors_[i]->reset();
}
}
private:
;
Actor * actors_[NUM_ACTORS];
};
// 对于用户而言,角色开始同步地各自移动,但从内部看,一个时刻仅有一个角色被更新
class Comedian: public Actor {
public:
void face(Actor * actor) { facing_ = actor; }
virtual void update() {
if (wasSlapped()) { facing_->slap() };
}
private:
Actor * facing_;
};
Stage stage;
Comedian * harry = new Comedian();
Comedian * baldy = new Comedian();
Comedian * chump = new Comedian();
harry->face(baldy);
harry->face(chump);
harry->face(harry);
stage.add(harry, );
stage.add(baldy, );
stage.add(chump, );
harry->slap();
stage.update();
8.5.3 缓存这些巴掌
class Actor {
public:
Actor(): currentSlapped_(false) {}
;
virtual ~Actor() {}
void swap() {
currentSlapped_ = nextSlapped_;
nextSlapped_ = false;
}
void lap() { nextSlapped_ = true; }
bool wasSlapped() { return currentSlapped_; }
private:
bool currentSlapped_;
bool nextSlapped_;
};
void Stage::update() {
; i < NUM_ACTORS; i++) {
actors_[i]->update();
}
; i < NUM_ACTROS; i++) {
actors_[i]->swap();
}
}
8.6 设计决策
8.6.1 缓冲区如何交换
交换缓冲区指针或者引用
在两个缓冲区之间进行数据的拷贝
8.6.2 缓冲区的粒度如何
8.7 参考
你几乎能在任何一个图形API种找到双缓冲模式的应用.例如,OpenGL种的swapBuffers()函数,Direct3D种的"swap chains",微软XNA框架在endDraw()方法种也使用了帧缓冲区的交换
第9章 游戏循环
实现用户输入和处理器速度在游戏行进时间上的解耦
9.1 动机
假如有哪个模式是本书最无法删减的,那么非游戏循环模式莫属.游戏循环模式是游戏编程模式种的精髓.几乎所有的游戏都包含着它,无一雷同,相比而言那些非游戏程序中却难见它的身影
9.1.1 CPU探秘
while (true) {
char * command = readCommand();
handleCommand(command);
}
9.1.2 事件循环
如果剥去现代的图形应用程序UI的外衣,你将发现它们和旧得冒险游戏是如此相似
while (true) {
Event * event = waitForEvent();
dispatchEvent(event);
}
不同于其他大多数软件,游戏即便在用户不提供任何输入时也一直在运行.加入你坐下来盯着屏幕,游戏也不会卡住.动画依旧在播放,各种效果也在闪动跳跃
这是真实的游戏循环的第一个关键点:它处理用户输入,但并不等待输入.游戏循环始终在运转:
while (true) {
processInput();
update();
render();
}
9.1.3 时间之外的世界
假如用现实时间来衡量游戏循环的速度,我们就得到了游戏的"帧率(FPS,frames per second)".
两个因素决定了帧率.
第一个是循环每一帧要处理的信息量.复杂的物理运算,一堆对象的数据更新,许多图形细节等都将让你的CPU和GPU忙个不停,这都会让一帧消耗更多的时间
第二个是底层平台的速度.速度越快的芯片相同时间内能够处理更多的代码.多核,多GPU,专用声卡以及操作系统的调度器都会影响着你的一帧中所能处理的代码量
9.1.4 秒的长短
游戏循环模式的另一个要点:这一模式让游戏在一个与硬件无关的速度常量下运行.
9.2 模式
一个游戏循环会在游戏过程中持续地运转.每循环一次,它非阻塞地处理用户输入,更新游戏状态,并渲染游戏.它跟踪流逝的时间并控制游戏的速率
9.3 使用情境
9.4 使用须知
9.5 示例代码
9.5.1 跑,能跑多快就跑多快
while (true) {
processInput();
update();
render();
}
它的问题在于你无法控制游戏运转的快慢.在较快的机器上游戏循环可能会快得令玩家看不清楚游戏在做什么,在慢的机器上游戏则会变慢变卡
9.5.2 小睡一会儿
你希望游戏运行在60帧,假如你确定每16ms甚至更短的时间就能处理所有的信息
while (true) {
double start = getCurrentTime();
processInput();
update();
render();
sleep(start + MS_PER_FRAME - getCurrentTime());
}
对于超过16ms时间的处理时间,则无能为力
9.5.3 小改动,大进步
double lastTime = getCurrentTime();
while (true) {
double current = getCurrentTime();
double elapsed = current - lastTime;
processInput();
update(elapsed);
render();
lastTime = current;
}
9.5.4 把时间追回来
double previous = getCurrentTime();
double lag = 0.0;
while (true) {
double current = getCurrentTime();
double elapsed = current - previous;
previous = current;
lag += elapsed;
processInput();
while (lag >= MS_PER_UPDATE) {
update();
lag -= MS_PER_UPDATE;
}
render();
}
9.5.5 留在两帧之间
9.6 设计决策
9.6.1 谁来控制游戏循环,你还是平台
使用平台的事件循环
使用游戏引擎的游戏循环
自己编写游戏循环
9.6.2 你如何解决能量耗损
限制帧率
9.6.3 如何控制游戏速度
非同步的固定时间步长
同步的固定时长
变时时长
定时更新迭代,变时渲染
9.7 参考
讲述游戏循环模式的一篇经典文章是来自 Glenn Fiedler 的 "Fix Your Timestep". 没有这篇文章,这一章就没法写成现在这样
Witters的文章 game loops 也值得一看
Unity 的框架具有一个复杂的游戏循环,这里有一个对其很详尽的阐述
第10章 更新方法
通过对所有对象实例同时进行帧更新来模拟一系列相互独立的游戏对象
10.1 动机
// Skeleton variables...
Entity skeleton;
bool patrollingLeft = false;
Entity leftStatue;
Entity rightStatue;
;
;
// Main game loop
while (true) {
if (patrollingLeft) {
x--;
) patrollingLeft = false;
} else {
x++;
) patrollingLeft = true;
}
skeleton.setX(x);
) {
leftStatueFrames = ;
leftStatue.shootLightning();
}
) {
rightStatueFrames = ;
rightStatue.shootLightning();
}
// Handle user input and render game...
}
你会发现这代码的可维护性不高.我们维护着一堆其值不断增长的变量,并不可避免地将所有代码都塞进游戏循环里,每段代码处理一个游戏中特殊的实体.为达到让所有实体同时运行的目的,我们把它们杂糅在一起了.
你可能猜到我们所要运用的设计模式该干些什么了;它要为游戏中的每个实体封装其自身的行为.这将使得游戏循环保持整洁并便于往循环中增加或移除实体
为了做到这一点,我们需要一个抽象层,为此定义一个update()的抽象方法.游戏循环维护对象集合,但它并不关心这些对象的具体类型.它只是更新它们.这将每个对象的行为从游戏循环以及其他对象那里分离了出来
每一帧,游戏循环遍历游戏对象集合并调用它们的update().这在每帧都给与每个对象一次更新自己行为的机会.通过逐帧调用update方法,使得这些对象的表现得到同步
游戏循环维护一个动态对象集合,这使得向关卡里添加或者移除对象十分便捷----只要往集合里增加或移除就好
10.2 模式
游戏世界维护一个对象集合.每个对象实现一个更新方法以在每帧模拟自己的行为.而游戏循环在每帧对集合中所有的对象调用其更新方法,以实现和游戏世界同步更新
10.3 使用情境
假如把游戏循环比作有史以来最好的东西,那么更新方法模式就会让它锦上添花.
更新方法模式在如下情境最为适用:
你的游戏中含有一系列对象或系统需要同步地运转
各个对象之间的行为几乎是相互独立的
对象的行为与时间相关
10.4 使用须知
10.4.1 将代码划分至单帧之中使其变得更加复杂
10.4.2 你需要在每帧结束前存储游戏状态以便下一帧继续
10.4.3 所有对象都在每帧进行模拟,但并非真正同步
在本设计模式中,游戏循环在每帧遍历对象集并逐个更新对象.在update()的调用中,多数对象能够访问到游戏世界的其他部分,包括那些正在更新的其他对象.这意味着,游戏循环遍历更新对象的顺序意义重大
10.4.4 在更新期间修改对象列表时必须谨慎
不在本帧处理新添加的对象
int numObjectsThisTurn = numObjects_;
; i < numObjectsThisTurn; i++) {
objects_[i]->update();
}
在迭代时移除对象
一种方法是小心地移除对象并在更新任何计数器时把被移除的对象也算在内.还有一个办法是将移除操作推迟到本次循环遍历结束之后.将要被移除的对象标记为"死亡",但并不从列表中移除它.在更新期间,确保跳过那些被标记死亡的对象接着等到遍历更新结束,再次遍历列表来移除这些"尸体"
10.5 示例代码
class Entity {
public:
Entity(): x_(), y_() {}
;
virtual ~Entity() {}
double x() const { return x_; }
double y() const { return y_; }
void setX(double x) { x_ = x; }
void setY(double y) { y_ = y; }
private:
double x_, y_;
};
class World {
public:
World(): numEntities_() {}
void gameLoop();
private:
Entity * entities_[MAX_ENTITIES];
int numEntities_;
};
void World::gameLoop() {
while (true) {
// Handle user input...
// Update each entity
; i < numEntities_; i++) {
entities_[i]->update();
}
// Physics and rendering...
}
}
10.5.1 子类化实体
10.5.2 定义实体
class Skeleton: public Entity {
public:
Skeleton(): patrollingLeft_(false) {}
virtual void update() {
if (patrollingLeft_) {
setX(x() - );
) patrollingLeft_ = false;
} else {
setX(x() + );
) patrollingLeft_ = true;
}
}
private:
bool patrollingLeft_;
};
class Statue: public Entity {
public:
Statue(), delay_(delay) {}
virtual void update() {
if (++frames_ == delay_) {
shootLightning();
// Reset the timer.
frames_ = ;
}
}
private:
int frames_;
int delay_;
void shootLightning() {
// Shoot the lightning...
}
};
10.5.3 逝去的时间
void Skeleton::update(double elapsed) {
if (patrollingLeft_) {
x -= elapsed;
) {
patrollingLeft_ = false;
x = -x;
}
} else {
x += elapsed;
) {
patrollingLeft_ = true;
x = - (x - );
}
}
}
10.6 设计决策
10.6.1 update方法依存于何类中
你显然必须决定好该把update()方法放在哪一个类中
实体类中 假如你已经创建了实体类,那么这是最简单的选项.因为这不会往游戏中增加额外的类.假如你不需要很多种类的实体,那么这种方法可行,但实际项目中很少这么做
组件类中 更新方法模式与组件模式享有相同的功能----让实体/组件独立更新,它们都使得每个实体/组件在游戏世界中能够独立于其他实体/组件.渲染,物理,AI都仅需专注于自己
代理类中 将一个类的行为代理给另一个类,设计了其他几种设计模式.状态模式可以让你通过改变一个对象的代理来改变其行为.对象类型模式可以让你在多个相同类型的实体之间共享行为
假如你适用上述射击模式,那么自然而然地需要将update()方法至于代理类中.这么一来,你可能在主类中仍保留update()方法,但它会成为非虚的方法并简单地指向代理类对象的update()方法
void Entity::update() {
state_->update();
}
10.6.2 那些未被利用的对象该如何处理
你常需要在游戏中维护这样一些对象:不论处于何种原因,它们暂时无需被更新.一种方法是单独维护一个需要被更新的"存活"对象表.
10.7 参考
这一模式与游戏循环和组件模式共同构成了多数游戏引擎的核心部分
当你开始考虑实体集合或循环中组件在更新时的缓存功能,并希望它们更快地运转时,数据局部性模式将会有所帮助
Unity 的引擎框架在许多类模块中使用了本模式,包括Monobehaviour类
微软的XNA平台在Game和GameComponent类中均使用了这一模式
Quintus 是基于JavaScript的游戏引擎,在其主要的Sprite类中使用了这一模式
第11章 字节码
通过将行为编码成虚拟机指令,而使其具备数据的灵活性
11.1 动机
11.1.1 魔法大战
11.1.2 先数据后编码
class Expression {
public:
;
virtual ~Expression();
};
class NumberExpression: public Expression {
public:
NumberExpression(double value): value_(value) {}
virtual double evaluate() { return value_; }
private:
double value_;
};
class AdditionExpression: public Expression {
public:
AdditionExpression(Expression * left, Expression * right): left_(left), right_(right) {}
virtual double evaluate() {
// Evaluate the operands
double left = left_->evaluate();
double right = right_->evaluate();
// Add them.
return left + right;
}
private:
Expression * left_;
Expression * right_;
};
11.1.4 虚拟机器码
11.2 字节码模式
指令集定义了一套可以执行的底层操作.一系列指令被编码为字节序列.虚拟机逐条执行指令栈上这些指令.通过组合指令,既可完成很多高级行为
11.3 使用情境
这是本书中最复杂的模式,它可不是轻易就能放进你的游戏里的,仅当你的游戏中需要定义大量行为,而且实现游戏的语言出现下列情况才应该使用:
编程语言太底层了,编写起来繁琐易错
因编译时间太长或工具问题,导致迭代缓慢
它的安全性太依赖编码者.你想确保定义的行为不会让程序崩溃,就得把它们从代码库转移至安全沙箱中
当然,这个列表复合大多数游戏的情况.谁不想提高迭代速度,让程序更安全?但那是有代价的,字节码比本地码要慢,所以它并不适合用作对性能要求极高的核心部分
11.4 使用须知
11.4.1 你需要个前端界面
11.4.2 你会想念调试器的
11.5 示例
11.5.1 法术API
void setHealth(int wizard, int amount); void setWisdom(int wizard, int amount); void setAgility(int wizard, int amount); void playSound(int soundId); void spawnParticles(int particleType);
11.5.2 法术指令集
enum Instruction {
INST_SET_HEALTH = 0x00,
INST_SET_WISDOM = 0x01,
INST_SET_AGILITY = 0x02,
INST_PLAY_SOUND = 0x03,
INST_SPAWN_PARTICLES = 0x04
};
swtich (instruction) {
case INST_SET_HEALTH:
setHealth(, );
break;
case INST_SET_WISDOM:
setWisdom(, );
break;
case INST_SET_AGILITY:
setAgility(, );
break;
case INST_PLAY_SOUND:
playSound(SOUND_BANG);
break;
case INST_SPAWN_PARTICLES:
spawnParticles(PARTICLE_FLAME);
break;
}
class VM {
public:
void interpret(char bytecode[], int size) {
; i < size; i++) {
char instruction = bytecode[i];
switch (instruction) {
// Case for each instruction...
}
}
}
};
11.5.3 栈机
class VM {
public:
VM(): stackSize_() {}
// Other stuff...
private:
;
int stackSize_;
int stack_[MAX_STACK];
};
class VM {
private:
void push(int value) {
// Check for stack overflow.
assert(stackSize_ < MAX_STACK);
stack_[stackSize_++] = value;
}
int pop() {
// Make sure the stack isn't empty.
assert(stackSize_ > );
return stack_[--stackSize_];
}
// Other stuff...
};
switch (instruction) {
case INST_SET_HEALTH:
int amount = pop();
int wizard = pop();
setHealth(wizard, amount);
break;
// Similar for SET_WISDOM and SET_AGILITY...
case INST_PLAY_SOUND:
playSound(pop());
break;
case INST_SPAWN_PARTICLES:
spawnParticles(pop());
break;
}
switch (instruction) {
// Other instruction cases...
case INST_LITERAL:
// Read the next byte from the bytecode.
int value = bytecode[++i];
push(value);
break;
}
毫无疑问,这个架构就是所谓的栈机.例如Forth, PostScript和Factor这类编程语言将这个模型直接暴露给了用户
11.5.4 组合就能得到行为
case INST_GET_HEALTH:
int wizard = pop();
push(getHealth(wizard));
break;
case INST_GET_WISDOM:
case INST_GET_AGILITY:
// You get the iead...
case INST_ADD:
int b = pop();
int a = pop();
push(a + b);
break;
setHealth(, getHealth() + (getAgilit() + getWisdom()) / );
LITERAL [] # Wizard index
LITERAL [, ] # Wizard index
GET_HEALTH [, ] #getHealth()
LITERAL [, , ] # Wizard index
GET_AGILITY [, , ] # getAgility()
LITERAL [, , , ] # Wizard index
GET_WISDOM [, , , ] getWisdom()
ADD [, , ] # Add agility and wisdom
LITERAL [, , , ] # Divisor
DIVIDE [, , ] # Average them
ADD [, ] # Add average to health
SET_HEALTH [] #Set health to result
11.5.5 一个虚拟机
11.5.6 语法转换工具
11.6 设计决策
11.6.1 指令如何访问堆栈
字节码虚拟机有两种大风格: 基于栈和基于寄存器.在基于栈的虚拟机中,指令总是操作栈顶,正如我们的实例代码一样.例如, "INST_ADD"出栈两个值,将它们相加,然后将结果入栈
基于寄存器的虚拟机也有一个堆栈.唯一的区别是指令可以从栈的更深层次中读取输入.不像"INST_ADD" 那样总是出栈操作数,它在字节码中存储两个索引来表示应该从堆栈的哪个位置读取操作数
基于栈的虚拟机
指令很小
代码生成更简单
指令数更多
基于寄存器的虚拟机
指令更大
指令更小
11.6.2 应该有哪些指令
外部基本操作
内部基本操作
控制流
抽象化
11.6.3 值应当如何表示
单一数据类型
它很简单
你无法使用不同的数据类型
标签的一个变体
enum ValueType {
TYPE_INT,
TYPE_DOUBLE,
TYPE_STRING
};
struct Value {
ValueType type;
union {
int intValue;
double doubleValue;
char * stringValue;
}
};
值存储了自身的类型信息
占用更多内存
不带标签的联合体
紧凑
快速
不安全
一个接口
class Value {
public:
virtual ~Value() {}
;
virtual int asInt() {
// Can only call this on ints
assert(false));
;
}
// Other conversion methods...
};
class IntValue: public Value {
public:
IntValue(int value): value_(value) {}
virtual ValueType type() { return TYPE_INT; }
virtual int asInt() { return value_; }
private:
int value_;
};
开放式
面向对象
累赘
低效
11.6.4 如何生成字节码
如果你一定了一种基于文本的语言
你得定义一种语法
你要实现一个分析器
你必须处理语法错误
对非技术人员没有亲和力
如果你设计了一个图形化编辑器
你要实现一个用户界面
不易出错
可移植性差
11.7 参考
这个模式是Gof解释器模式的姊妹版.它们都会为你提供一种用数据组合行为的方法.事实上,你经常会将两个模式一起使用.你用来生成字节码的工具通常会有一个内部对象树来表达代码.这正是解释器模式能做的事情.为了将它编译成字节码,你需要递归遍历整棵树,正如你在解释器模式中解析它那样.唯一的不同是你并不是直接执行一段代码而是将它们输出成字节码指令并在以后执行它们
Lua编程语言是游戏中广泛使用的编程语言.它内部实现了一个紧凑的基于寄存器的字节码虚拟机
Kismet是内置在UnrealEd(Unreal Engine的编辑器)中的图形化脚本工具
我自己的小型脚本语言,Wren,是一个简单的基于堆栈的字节码解释器
第12章 子类沙盒
使用基类提供的操作集合来定义子类中的行为
12.1 动机
这个设计模式会催生一种扁平的类层次架构.你的继承链不会太深,但是会有大量的类与Superpower挂钩.通过使一个类派生大量的直接子类,我们限制了该代码在代码库里的影响范围.游戏中大量的类都会获益于我们精心射击的Superpower类
12.2 沙盒模式
一个基类定义了一个抽象的沙盒模式方法和一些预定义的操作集合.通过将它们设置为受保护的状态以确保它们仅供子类使用.每个派生出的沙盒子类根据父类提供的操作来实现沙盒函数
12.3 使用情境
沙盒模式适用于以下情况
你有一个带有大量子类的函数
基类能够提供所有子类可能需要执行的操作集合
在子类之间有重叠的代码,你希望在它们之间更简便地共享代码
你希望使这些继承类与程序其他代码之间的耦合最小化
12.4 使用须知
12.5 示例
class Superpower {
public:
virtual ~Superpower() {}
protected:
// 沙盒函数
;
// 与其他系统耦合
void move(double x, double y, double z) {
// Code here...
}
// 与其他系统耦合
void playSound(SoundId sound) {
// Code here...
}
// 与其他系统耦合
void spawnParticles(ParticleType type, int count) {
// Code here...
}
double getHeroX() {}
double getHeroY() {}
double getHeroZ() {}
};
class SkyLaunch: public Superpower {
protected:
virtual void activate() {
) {
move(, , );
playSound(SOUND_SPROING);
spawnParticles(PARTICLE_DUST, );
} else if (getHeorZ() < 10.0f) {
playSound(SOUND_SWOOP);
move(, , getHeroZ() - );
} else {
playSound(SOUND_DIVE);
spawnParticles(PARTICLE_SPARKLES, );
move(, , -getHeroZ());
}
}
};
起初,我建议对power类采用数据驱动的方式.此处就是一个你决定不采用它的原因.如果你的行为是复杂的,命令式的,那么用数据定义它们会更加困难
12.6 设计决策
12.6.1 需要提供什么操作
经验法则
如果所提供的操作仅仅被一个或者少数的子类所使用,那么不必将它加入基类.这只会给基类增加复杂度,同时将影响每个子类,而仅有少数子类从中受益.将该操作与其他提供的操作保持一致或许值得,但让这些特殊子类直接调用外部系统或许更为简单和清晰
当你在游戏的其他模块进行某个方法调用时,如果它不修改任何状态,那么它就不具备侵入性.它仍然产生了耦合,但这是个"安全"的耦合,因为在游戏中它不带来任何破坏.而另一方面,如果这些调用确实改变了状态,则将与代码库产生更大的耦合,你需要对这些耦合更上心.因此此时这些方法更适合由更可视化的基类提供
如果提供的操作,其实现仅仅是对一些外部系统调用的二次封装,那么它并没有带来多少价值.在这种情况下,直接调用外部系统更为简单.然而,极其简单的转向调用也仍有用----这些函数通常访问基类不像直接暴露给子类的状态
12.6.2 是直接提供函数,还是由包含它们的对象提供
class SoundPlayer {
void playSound(SoundId sound) { }
void stopSound(SoundId sound) {}
void setVolume(SoundId sound) {}
};
class Superpower {
protected:
SoundPlayer & getSoundPlayer() {
return soundPlayer_;
}
// Sandbox method and other operations...
private:
Soundplayer soundPlayer_;
};
把提供的操作分流到一个像这样的辅助类中能给你带来些好处
减少了基类的函数数量.
在辅助类中的代码通常更容易维护
降低了基类和其他系统之间的耦合
12.6.3 基类如何获取其所需的状态
把它传递给基类构造函数
class Superpower {
public:
Superpower(ParticleSystem * particles): particles_(particles) {}
// Sandbox method and other operations...
private:
ParticleSystem * particles_;
};
class SkyLaunch: public Superpower {
public:
SkyLaunch(ParticleSystem * particles): Superpower(particles) {}
};
进行分段初始化
Superpower * power = new Superpower();
power->init(particles);
Superpower * createSkyLaunch((ParticleSystem * particles) {
Superpower * power = new SkyLaunch();
power->init(particles);
return power;
}
将状态静态化
class Superpower {
public:
static void init(ParticleSystem * particles) {
particles_ = particles;
}
// Sandbox method and other operations...
private:
static ParticleSystem* particles_;
};
使用服务定位器
class Superpower {
protected:
void spawnParticles(ParticleType type, int count) {
ParticleSystem & particles = Locator::getParticles();
particles.spawn(type, count);
}
// Sandbox method and other operations...
};
12.7 参考
当你采用更新方法模式的时候,你的更新函数通常也是一个沙盒函数
模板方法模式正好与本模式相反.在这两个模式中,你都使用一系列操作原语来实现一个函数.使用子类沙盒模式时,函数在继承类中,原语操作则在基类中.使用模板方法时,基类定义函数骨架,而原语操作被继承类实现
你可以将这个模式看作是在外观模式上的一个变种.外观模式将许多不同的系统隐藏在了一个简化的API之下.在子类沙盒模式中,基类对于子类来说充当着隐藏游戏引擎实现细节的角色
第13章 类型对象
通过创建一个类来支持新类型的灵活创建,其每个实例都代表一个不同的对象类型
13.1 动机
13.1.1 经典的面向对象方案
class Monster {
public:
;
virtual ~Monster() {}
protected:
Monster(int startingHealth): health_(startingHealth) {}
private:
int health_;
};
class Dragon: public Monster {
public:
Dragon(): Monster() {}
virtual const char * getAttach() {
return "The dragon breathes fire!" ;
}
};
class Troll: public Monster {
public:
Troll(): Monster() {}
virtual const char * getAttack() {
return "The troll clubs you!";
}
};
13.1.2 一种类型一个类
为了将怪物与种族关联起来,我们让每个Monster实例化一个包含了其种族信息的Bread对象引用.Breed类本质上定义了怪物的"类型".每个种族实例都是一个对象,代表着不同的概念类型,而这个模式的名字就是: 类型对象
13.2 类型对象模式
定义一个类型对象类和一个持有类型对象类.每个类型对象的实例表示一个不同的逻辑类型.每个持有类型对象类的实例引用一个描述其类型的类型对象
实例数据被存储在持有类型对象的实例中,而所有同概念类型所共享的数据和行为被存储在类型对象中.引用同一个类型的对象之间能表现出"同类"的性状.这让我们可以在相似对象集合*享数据和行为,这与类派生的作用有几分相似,但却无需硬编码出一批派生类
13.3 使用情境
当你需要定义一系列不同"种类"的东西,但又不想把那些种类硬编码进你的类型系统时,本模式都适用.尤其是当下面任何一项成立的时候:
你不知道将来会有什么类型
你需要在不重新编译或修改代码的情况下,修改或添加新的类型
13.4 使用须知
13.4.1 类型对象必须手动跟踪
13.4.2 为每个类型定义行为更困难
通过类型对象去定义类型相关的数据非常容易,但是定义数据类型相关的行为却很难.
有几种方法可以跨越这个限制.
一个简单的方法是创建一个固定的预定义行为集合,让类型对象中的数据从中任选其一
另一个更强大,更彻底的解决方案是支持在数据中定义行为.如果我们能读取数据文件并提供给上述任意一种模式来实现,行为定义就完全从代码中脱离出来,而被放进数据文件内容中.
13.5 示例
class Breed {
public:
Breed(int health, const char * attack): health_(health), attack_(attack) {}
int getHealth() { return health_; }
const char * getAttack() { return attack_; }
private:
int health_;
const char * attack_;
};
class Monster{
public:
Monster(Breed & breed): health(breed.getHealth()), breed_(breed) {}
const char * getAttack() {
return breed_.getAttack();
}
private:
int health_;
Breed & breed_;
};
13.5.1 构造函数: 让类型对象更加像类型
class Breed {
public:
Monster * newMonster() {
return new Monster(*this);
}
// Previous Breed code...
};
class Monster {
friend class Bread;
public:
const char * getAttack() {
return breed_.getAttack();
}
private:
Monster(Breed & breed): health_(breed.getHealth()), breed_(breed) {}
int health_;
Breed & bread_;
};
13.5.2 通过继承共享数据
仿照多个怪物通过种族共享特性的方式,让种族之间也能够共享特性.我们不采用语言本身的派生机制,而是自己在类型对象里实现它
class Breed {
public:
Breed(Breed * parent, int health, const char * attack): parent_(parent), health_(health), attack_(attack) {}
int getHealth();
const char * getAttack();
private:
Breed * parent_;
int health_;
const char * attack_;
};
在属性每次被请求的时候执行代理调用
int Breed::getHealth() {
// Override
|| parent_ == NULL) {
return health_;
}
// Inherit
return parent->getHealth();
}
const char * Breed::getAttack() {
// Override
if (attack_ != NULL || parent_ == NULL) {
return attack_;
}
// Inherit
return parent->getAttack();
}
如果我们能确保基种族的属性不会改变.那么一个更快的解决方案是在构造时采用继承.这也被称为"复制"代理,因为我们在创建一个类型时把继承的特性复制到了这个类型内部
Breed(Breed * parent, int health, const char * attack): health_(health), attack_(attack) {
// Inherit non-overridden attribute
if (parent != NULL) {
) health_ = parent->getHealth();
if (attack == NULL) {
attack_ = parent->getAttack();
}
}
}
int getHealth() { return health_; }
const char * getAttack() { return attack_; }
假设游戏引擎从JSON文件创建种族
{
"Troll": {
,
"attack": "The troll hits you!"
},
"Troll Archer": {
"parent": "Troll",
,
"attack": "The troll archer fires an arrow!"
},
"Troll Wizard": {
"parent": "Troll",
,
"attack": "The troll wizard casts a spell"
}
}
13.6 设计决策
13.6.1 类型对象应该封装还是暴露
如果类型对象被封装
类型对象模式的复杂性对代码库的其他部分不可见.它成为了持有类型对象才需关心的实现细节
持有类型对象的类可以有选择性地重写类型对象的行为
如果类型对象被公开
外部代码在没有持有类型对象类实例的情况下就能访问类型对象
类型对象现在是对象公共API的一部分
13.6.2 持有类型对象如何创建
通过这种模式,每个"对象"现在都成了一对对象:主对象以及它所使用的类型对象.那么我们如何创建并将它们绑定起来呢?
构造对象并传入类型对象
在类型对象上调用"构造"函数
13.6.3 类型能否改变
类型不变
无论编码还是理解起来都更简单
易于调试
类型可变
减少对象创建
做约束时要更加小心
13.6.4 支持何种类型的派生
没有派生
简单
可能会导致重复劳动
单继承
仍然相对简单
属性查找会更慢
多重派生
能避免绝大多数的数据重复
复杂
13.7 参考
这个模式所围绕的高级问题是如何在不同对象之间共享数据.从另一个不同角度尝试解决这个问题的是原型模式
类型对象与享元模式很接近.它们都让你在实例间共享数据.享元模式倾向于节约内存,并且共享的数据可能不会以实际的"类型"呈现.类型对象模式的重点在于组织性和灵活性
这个模式与状态模式也有诸多相似性.它们都把对象的部分定义工作交给另一个代理对象实现.在类型对象中,我们通常代理的对象是:宽泛地描述对象的静态数据.在状态模式中,我们代理的是对象当前的状态,即描述对象当前配置的临时数据.当我们讨论到可改变类型对象的时候,你可以认为是类型对象在状态模式的基础上身兼二职
第14章 组件模式
允许一个单一的实体跨越多个不同域而不会导致耦合
14.1 动机
14.1.1 难题
14.1.2 解决难题
将独立的Bjorn类根据域边界切分成相互独立的部分.举个例子,我们将所有用来处理用户输入的代码放到一个单独的类InputComponent中.而Bjorn将拥有整个类的一个实例.我们将重复对Bjorn类包含的所有域做相同的工作
当我们完成工作后,我们几乎将Bjorn类中的所有东西都清理了出去.剩下的便是一个将所有组件绑定在一起的外壳.我们通过简单地将代码分割成多个更小类的方式解决了整个超大类的问题,但完成这项工作所达到的效果远远不止这些
14.1.3 宽松的末端
14.1.4 捆绑在一起
继承有它的用户,但是对某些代码重用来说实现起来太麻烦了.相反,软件设计的趋势应该是尽可能地使用组合而不是继承.为实现两个类之间的代码共享,我们应该让它们拥有同一个类的实例而不是继承同一个类
14.2 模式
单一实体跨越了多个域.为了能保持域之间相互隔离,每个域的代码都独立地放在自己的组件类中.实体本身则可以简化为这些组件的容器
14.3 使用情境
组件最常见于游戏中定义实体的核心类,但是它们也能够用在别的地方.当如下条件成立时,组件模式就能够发挥它的作用
你有一个涉及多个域的类,但是你希望让这些域保持相互解耦
一个类越来越庞大,越来越难以开发
你希望定义许多共享不同能力的对象,但采用继承的办法却无法令你精确地重用代码
14.4 注意事项
组件模式相较直接在类中编码的方式为类本身引入了更多的复杂性.每个概念上的"对象"成为一系列必须被同时实例化,初始化,并正确关联的对象的集群.不同组件之间的通信变得更具挑战性,而且对它们所占用内存的管理将更复杂
使用组件的另外一个后果是你经常需要通过一系列间接引用来处理问题,考虑容器对象,首先你必须得到你需要的组件,然后你才可以做你需要做的事情,在一些性能要求较高的内部循环代码中,这个组件指针可能会导致低劣的性能
14.5 示例代码
14.5.1 一个庞大的类
class Bjorn {
public:
Bjorn(): velocity_(), x_(), y_() {}
void update(World & world, Graphics & graphics);
private:
;
int velocity_;
int x_, y_;
Volume volume_;
Sprite spriteStand_;
Sprite spriteWalkLeft_;
Sprite spriteWalkRight_;
};
void Bjorn::update(World & world, Graphics & graphics) {
switch (Controller::getJoystickDirection()) {
case DIR_LEFT:
velocity_ -= WALK_ACCELERATION;
break;
case DIR_RIGHT:
velocity_ += WALK_ACCELERATION;
break;
}
x_ += velocity_;
world.resolveCollision(volume_, x_, y_, velocity_);
Sprite * sprite = &spriteStand_;
) sprite = &spriteWalkLeft_;
) sprite = &spriteWalkRight_;
graphics.draw(*sprite, x_, y_);
}
14.5.2 分割域
class InputComponent {
public:
void update(Bjorn & bjorn) {
switch(Controller::getJoystickDirection()) {
case DIR_LEFT:
bjorn.velocity -= WALK_ACCELERATION;
break;
case DIR_RIGHT:
bjorn.velocity += WALK_ACCELERATION;
break;
}
}
private:
;
};
class Bjorn {
public:
int velocity;
int x, y;
void update(World & world, Graphics & graphics) {
input_.update(*this);
x += velocity;
world.resolveCollision(volume_, x, y, velocity);
Sprite * sprite = &spriteStand_;
) {
sprite = &spriteWalkLeft_;
} ) {
sprite = &spriteWalkRight_;
}
graphics.draw(*sprite, x, y);
}
private:
InputComponent input_;
Volume volume_;
Sprite spriteStand_;
Sprite sptireWalkLeft_;
Sprite spriteWalkRight_;
};
14.5.3 分割其余部分
class PhysicsComponent {
public:
void update(Bjorn & bjorn, World & world) {
bjorn.x += bjorn.velocity;
world.resolveCollision(volume_, bjorn.x, bjorn.y, bjorn.velocity);
}
private:
Volume volume_;
};
class GraphicsComponent {
public:
void update(Bjorn & bjorn, Graphics & graphics) {
Sprite * sprite = &spriteStand_;
) {
sprite = &spriteWalkLeft_;
} ) {
sprite = &spriteWalkRight_;
}
graphics.draw(*sprite, bjorn.x, bjorn.y);
}
private:
Sprite spriteStand_;
Sprite spriteWalkLeft_;
Sprite spriteWalkRight_;
};
class Bjorn {
public:
int velocity;
int x, y;
void update(World & world, Graphics & graphics) {
input_.update(*this);
physics_.update(*this);
graphics_.update(*this);
}
private:
InputComponent input_;
PhysicsComponent inpiut_;
GraphicsComponent input_;
};
现在Bjorn类基本只做两件事:持有一些真正定义了Bjorn的组件,并持有这些域所共享的那些状态量.位置和速度的信息之所以还保留在Bjorn类中主要有两个原因
首先他们是"泛域"(pan-domain)状态,几乎所有的组件都会使用它们,所以如果将它们放到组件中是不明智的
第二点也是最重要的一点就是,将位置和速度这两个状态信息保留在Bjorn类中使得我们能够轻松地在组件之间传递信息而不需要耦合它们.
14.5.4 重构Bjorn
到目前为止,我们已经将行为封装到单独的组件类中,但是我们没有将这些行为从核心类中抽象化.Bjorn仍然精确地知道行为是在哪个类中被定义的.
我们将处理用户输入的组件隐藏到一个接口下,这样就能够将输入组件变成一个抽象的基类
class InputComponent {
public:
;
virtual ~InputComponent() {}
};
class PlayerInputComponent: public InputComponent {
public:
virtual void update(Bjorn & bjorn) {
switch (Controller::getJoystickDirection()) {
case DIR_LEFT:
bjorn.velocity -= WALK_ACCELERATION;
break;
case DIR_RIGHT:
bjorn.velocity += WALK_ACCELERATION;
break;
}
}
private:
;
};
class Bjorn {
public:
int velocity;
int x, y;
Bjorn(InputComponent * input): input_(input) {}
void update(World & world, Graphics & graphics) {
input_->update(*this);
physics_.update(*this, world);
graphics_.update(*this, graphics);
}
private:
InputComponent * input_;
PhysicsComponent physics_;
GraphicsComponent graphics_;
};
Bjorn * bjorn = new Bjorn(new PlayerInputComponent());
class DemoInputComponent: public InputComponent {
public:
virtual void update(Bjorn & bjorn) {
// AI to automatically control Bjorn...
}
};
现在,仅仅只是交换了一个组件,我们就得到了一个功能完备的完全由电脑控制的演示模式.我们能够重用Bjorn的所有其他代码,包括物理以及图形,甚至不需要了解这两者之间有什么区别
14.5.5 删掉Bjorn
现在让我们看看Bjorn类,你会发现基本上没有Bjorn独有的代码,它更像是个组件包.事实上,它是一个能够用到游戏中所有对象身上的游戏基本类的最佳候选
class PhysicsComponent {
public:
;
virtual ~PhysicsComponent() {}
};
class GraphicsComponent {
public:
;
virtual ~GraphicsComponent() {}
};
class GameObject {
public:
int velocity;
int x, y;
GameObject(InputComponent * input, PhysicsComponent * physics, GraphicsComponent * graphics): input_(input), physics_(physics), graphics_(graphics) {}
void update(World & world, Graphics & graphics) {
input_->update(*this);
physics_->update(*this, world);
graphics_->update(*this, graphics);
}
private:
InputComponent * input_;
PhysicsComponent * physics_;
GraphicsComponet * graphics_;
};
class BjornPhysicsComponent: public PhysicsComponent {
public:
virtual void update(GameObject & obj, World & world) {
// Physics code...
}
};
class BjornGraphicsComponent: public GraphicsComponent {
public:
virtual void update(GameObject & object, Graphics & graphics) {
// Graphics code...
}
};
GameObject * createBjorn() {
return new GameObject(new PlayerInputComponent(), new BjornPhysicsComponent(), new BjornGraphicsComponent());
}
14.6 设计决策
关于这个设计模式的最重要的问题是:你需要的组件集合是什么?答案取决于你的游戏需求与风格.引擎越大越复杂,你就越想要将组件切分得更细
14.6.1 对象如何获得组件
如果这个类创建了自己的组件
它确保了这个类一定有它所需要的组件
但是这么做将导致重新配置这个类变得困难
如果由外部代码提供组件
对象将变得灵活.我们完全可以通过添加不同的组件来改变类的行为
对象可以从具体的组件类型中解耦出来
14.6.2 组件之间如何传递信息
完美地将组件互相解耦并且保证功能隔离是个很好的想法,但这通常是不现实的.这些组件同属于一个对象的事实暗示了它们都是整体的一部分因此需要相互协作----亦即通信
所以组件之间又是如何传递信息的呢?有好几个选择
通过修改容器对象的状态
它使得组件间保持解耦
它要求组件间任何需要共享的数据都由容器对象进行共享
这使得信息传递变得隐秘,同时对组件执行的顺序产生依赖
直接互相引用
class BjornGraphicsComponent {
public:
BjornGraphicsComponent(BjornPhysicsComponent * physics): physics_(physics) {}
void Update(GameObject & obj, Graphics & graphics) {
Sprite * sprite;
if (!physics_->isOnGround()) {
sprite = &spriteJump_;
} else {
// Existing graphics code...
}
graphics.draw(*sprite, obj.x, obj.y);
}
private:
BjornPhysicsComponent * physics_;
Sprite spriteStand_;
Sprite spriteWalkLeft_;
Sprite spriteWalkRight_;
Sprite spriteJump_;
};
这简单且快捷
组件之间紧密耦合.缺点就是会变得相当混乱.
通过传递信息的方式
这是选项中最复杂的一个.我们可以在容器类中建立一个小的消息传递系统,让需要传递信息的组件通过广播的方式去建立组件间的联系.GoF称之为中介模式,两个或者两个以上的对象通过将信息传递到一个中介的方法来取得相互之间的联系.而本章节中,容器类则充当了中间的角色
class Component {
public:
;
virtual ~Component() {}
};
class ContainerObject {
public:
void send(int message) {
; i < MAX_COMPONENTS; i++) {
if (components_[i] != NULL) {
components_[i]->receive(message);
}
}
}
private:
;
Component * components_[MAX_COMPONENTS];
};
兄弟组件之间是解耦的
容器对象十分简单
意料之外的是,没有哪个选择是最好的.你最终有可能将上述所说的三种方法都使用到
14.7 参考
Unity框架的核心GameObject类完全围绕组件来设计
开源引擎Delta3D有一个GameActor基类,该基类使用一个名叫ActorComponent的基类实现了组件模式
微软的XNA游戏框架附带了一个核心游戏类.它拥有一系列游戏组件对象.本文中的举例是在单个游戏层面上使用组件,而XNA则实现了主要游戏对象的设计模式,但是本质是一样的
这种设计模式与GoF中的策略模式很类似.都是将对象的行为委托给一个独立的从对象.不同的是策略模式的"策略"对象通常都是无状态的,它封装了一个算法,但是没有数据.它定义了一个对象的行为方式,而不是对象本身
组件本身具有一定的功能性.它们经常会持有描述对象以及定义对象实际标识的状态.然而,这个界限可能有点模糊.你可能有一些不需要任何状态的组件.在这种情况下,你可以在跨多个容器对象的情况下使用相同的组件实例.在这一点上,它的确表现得像是一个策略对象
第15章 事件队列
对消息或事件的发送与受理进行时间上的解耦
15.1 动机
15.1.1 用户图形界面的事件循环
15.1.2 中心事件总线
15.1.3 说些什么好呢
class Audio {
public:
static void playSound(SoundId id, int volume);
};
void Audio::playSound(SoundId id, int volume) {
ResourceId resource = loadSound(id);
int channel = findOpenChannel();
) return;
startSound(resource, channel, volume);
}
class Menu {
public:
void onSelect(int index) {
Audio::playSound(SOUND_BLOOP, VOL_MAX);
// Other sutff...
}
};
问题1: 在音效引擎完全处理完播放请求前,API的调用一直阻塞着调用者
问题2: 不能批量地处理请求
问题3: 请求在错误的线程被处理
15.2 事件队列模式
事件队列是一个按照先进先出顺序存储一系列通知或请求的队列.发出通知时系统会将该请求置入队列并随即返回,请求处理器随后从事件队列中获取并处理这些请求.请求可由处理器直接处理或转交给对其感兴趣的模块.这一模式对消息的发送者与受理者进行了解耦,使消息的处理变得动态且非实时
15.3 使用情境
如果你只想对一条消息的发送者和接收者进行解耦,那么诸如观察者模式和命令模式都能以更低的复杂度满足你.需要在某个问题上对时间进行解耦时,一个队列往往足矣
按照推送和拉取的方式思考:代码A希望另一个代码块B做一些事情.A发起这一请求最自然的方式就是将它推送给B
同时,B在其自身的循环中适时地拉取该请求并进行处理也是十分自然的.当你具备推送端和拉取端之后,在两者之间需要一个缓冲.这正是缓冲队列比简单的解耦模式多出来的优势
队列提供给拉取请求的代码块一些控制权:接收者可以延迟处理,聚合请求或者完全废弃它们.但这是通过"剥夺"发送者对队列的控制来实现的.所有的发送端能做的就是往队列里投递消息.这使得队列在发送端需要实时反馈时显得很不适用
15.4 使用须知
不像本书中其他更简单的模式,事件队列会更复杂一些并且对你的游戏框架产生广泛而深远的影响.这意味着你在决定如何使用,是否适用本模式时须三思
15.4.1 中心事件队列是个全局变量
该模式的一种普遍用法被称为"*枢纽站",游戏中所有模块的消息都可以通过它来传递.它是游戏中强大的基础设施,然而强大并不总意味着好用
关于"全局变量是糟糕的"这点,大多数人在走过不少弯路后才恍然大悟.当你有一些系统的任何部分都能访问的状态时,各种细小部分不知不觉地产生了相互依赖.本模式将这些状态封装成为一种不错的小协议,但让然是全局性的,故仍具有任何全局变量所包含的危险性da
15.4.2 游戏世界的状态任你掌控
当你接收到一个事件,你要十分谨慎,不可认为当前世界的状态反映的是消息发出时世界的状态.这就意味着队列事件视图比同步系统中的事件具有更重量级的数据结构.后者只需通知"某事发生了"然后接收者可以检查系统环境来深入细节,而适用队列时,这些细节必须在事件发生时被记录以便稍后处理消息时适用
15.4.3 你会在反馈系统循环中绕圈子
任何一个事件或消息系统都得留意循环
1. A发送了一个事件
2. B接收它,之后发送一个响应事件
3. 这个响应事件恰巧是A关心的,所以接收它.作为反馈A也会发送一个响应事件...
4. 回到2
当你的消息系统是同步的,你很块就能发现死循环----它们会导致栈溢出并造成游戏崩溃.对于队列来说,异步的放开栈处理会适这些伪事件在系统中来回徘徊,但游戏可能会保持运行.一个常用的规避法则是避免在处理事件末端代码中发送事件
15.5 示例代码
struct PlayMessage {
SoundId id;
int volume;
};
class Audio {
public:
; }
// Other stuff...
private:
;
static PlayMessage pending_[MAX_PENDING];
static int numPending_;
};
void Audio::playSound(SoundId id, int volume) {
assert(numPending_ < MAX_PENDING);
pending_[numPending_].id = id;
pending_[numPending_].volume = volume;
numPending_++;
}
class Audio {
public:
static void update() {
; i < numPending_; i++) {
ResourceId resource = loadSound(pending_[i].id);
int channel = findOpenChannel();
) return;
startSound(resource, channel, pending_[i].volume);
}
numPending_ = ;
}
// Other stuff...
};
15.5.1 环状缓冲区
class Audio {
pubic:
static void init() {
head_ = ;
tail_ = ;
}
// Methods...
private:
static int head_;
static int tail_;
// Array...
};
void Audio::playSound(SoundId id, int volume) {
assert((tail_ + ) % MAX_PENDING != head_);
// Add to the end of the list
pending_[tail_].id = id;
pending_[tail_].volume = volume;
tail_ = (tail_ + ) % MAX_PENDING;
}
void Audio::update() {
// If there are no pending requests, do nothing
if (head_ == tail_) return;
ResourceId resource = loadSound(pending_[head_].id);
int channel = findOpenChannel();
) return;
startSound(resource, channel, pending_[head_].volume);
head_ = (head_ + ) % MAX_PENDING;
}
15.5.2 汇总请求
15.5.3 跨越线程
15.6 设计决策
许多游戏将事件队列作为通讯架构的一个关键部分,你可以花大量的时间来设计各种复杂的路由和消息过滤机制.但在你准备建立类似于洛杉矶电话交换机系统那样的东西之前,我建议你开始要简单点.下面是入门时要考虑的一些问题
15.6.1 入队的是什么
迄今为止,"事件"和"消息"总是被我替换着使用,因为这无伤大雅.无论你往队列里塞什么,它都具备相同的解耦与聚合能力,但二者仍然有一些概念上的不同
如果队列中是事件
一个"事件"或"通知"描述已经发生的事情,比如"怪物死亡".你将它入队,所以其他对象可以响应事件,有几分像一个异步的观察者模式
你可能会允许多个监听器.由于队列包含的事件已经发生.因此发送者不关心谁会接收到它.从这个角度来看,这个事件已经过去并且已经被忘记了
可访问队列的域往往更广.事件队列经常用于给任何和所有感兴趣的部分广播事件.为了允许感兴趣的部分有更大的灵活性,这些队列往往有更多的全局可见性
如果队列中是消息
一个"消息"或"请求"描述一种"我们期望"发生在"将来"的行为,类似于"播放音乐".你可以认为这是一个异步API服务
你更可能只有单一的监听器.示例中,队列中的消息专门向音频API请求播放声音.如果游戏的其他任何部分开始从队列中偷窃消息,那并不会起到好的作用
15.6.2 谁能从队列中读取
单播队列 当一个队列是一个类的API本身的一部分时,单播再合适不过了.类似我们的声音示例,站在调用者的角度,它们能调用的只是一个"playSound()"方法
队列成为读取者的实现细节.
队列被更多地封装
你不必担心多个监听器竞争的情况
广播队列 这是大多数"事件"系统所做的事情.当一个事件进来时,如果你有十个监听器,则它们都能看见该事件
事件可以被删除
可能需要过滤事件
工作队列 类似于一个广播队列,此时你也有多个监听器.不同的是队列中的每一项只会被投递到一个监听器中.这是一种对于并发线程支持不好的系统中常见的工作分配模式
你必须做好规划
15.6.3 谁可以写入队列
一个写入者 这种风格尤其类似于同步式观察者模式.你拥有一个可以生成事件的特权对象,以供其他模块接收
你隐式地知道事件的来源
通常允许多个读取者.你可以创造一对一接收者的队列,但是,这样不太像通信系统,而更像是一个普通的队列数据结构
多个写入者 这是我们的音频引擎例子的工作原理.因为"playSound()"函数是一个公共方法,所以任何代码库部分都可以为队列添加一个请求,"全局"或"*"事件总线工作原理类似
你必须小心反馈循环
你可能会想要一些发送方在事件本身的引用
15.6.4 队列中对象的生命周期是什么
转移所有权 这是手动管理内存时的一种传统方法.当一个消息排队时,队列声明它,发送者不再拥有它.当消息处理时,接收者取走所有权并负责释放它
共享所有权 当前,虽然C++程序员能更舒服地进行垃圾回收了,但分享所有权会容易接受.这样一来,只要任何事情对它有一个引用,消息就依然存在.当被忘记时它就会自动释放
队列拥有它 另一个观点是消息总是存在于队列中.不用自己释放消息,发送者会从队列中请求一个新的消息.队列返回一个已经存在于队列内存中的消息引用,接着发送者会填充队列.消息处理时,接收者参考队列中相同消息的操作.
15.7 参考
我已经提到事件队列许多次了,但在很多方面,这个模式可以看成是我们所熟知的观察者模式的异步版本
和很多模式一样,事件队列有过一些其他别名.其中一个概念叫做"消息队列",它通常是指一个更高层面的概念.当事件队列应用于应用程序内部时,消息队列通常用于消息之间的通信
另一个术语是"发布/订阅",有时缩写为"订阅".类似于"消息队列",它通常在大型分布式系统中被提及,而不专用于像我们例子这阿姨那个简陋的编码模式中
一个有限状态机,类似于GoF的状态模式,需要一个输入流.如果你想要异步地响应它们,把它们入列就好.当你有一堆状态机互相发送消息的时候,每个状态机都一个小的队列等待输入(称为邮箱),于是你就重新发明出了计算角色模型
Go编程语言内置的"通道"类型,本质上就是一个事件队列或者消息队列
第16章 服务定位器
为某服务提供一个全局访问入口来避免使用者与该服务具体实现类之间产生耦合
16.1 动机
在游戏编程中,某些对象或者系统几乎出现在程序的每个角落.在某些时刻,你很难找到一个不需要内存分配,日志记录或者随机数生成的游戏.我们通常认为类似这样的系统是在整个游戏中需要被随时访问的服务
// Use a static class? AudioSystem::playSound(VERY_LOUD_BANG); // Or maybe a singleton? AudioSystem::instance()->playSound(VERY_LOUD_BANG);
尽管我们实现了想要的目的,但整个过程却带来了很多耦合.游戏中每一处调用音频系统的地方,都直接引用了具体的AudioSystem类和访问AudioSystem类的机制----使用静态类或者单例
这些调用音频系统的地方,的确需要耦合到某些东西上以便播放声音,但直接耦合到音频具体实现类上就好像让一百个陌生人知道你家的地址,而仅仅是因为需要它们投递信件.这不仅是隐私问题,而且当你搬家时必须告诉每个人你的新地址,这实在是太痛苦了
这里有个更好的解决办法:电话簿.每一个想要联系我们的人能够通过查找名字来得到我们当前的地址.当我们搬家时,我们告诉电话公司,它们更新电话簿,这样每个人都能得到新的地址了.实际上,我们甚至不必给出我们真正的地址.我们能够列出一个邮政信箱,或者其他能够"代表"我们的东西.通过让访问者查询电话簿来找到我们,我们便有了一个方便的可以控制如何查找我们的地方
这就是服务定位器模式的简单介绍----它将一个服务的"是什么(具体实现类型)"和"在什么地方(我们如何得到它的实例)"与需要使用整个服务的代码解耦了
16.2 服务定位器模式
一个服务类为一系列操作定义了一个抽象的接口.一个具体的服务提供器实现了这个接口.一个单独的服务定位器通过查找一个合适的提供器来提供这个服务的访问,它同时屏蔽了提供器的具体类型和定位这个服务的过程.
16.3 使用情境
每当你将东西变得全局都能访问的时候,你就是在自找麻烦.这就是单例模式存在的主要问题,而这个模式存在的问题也没有什么不同.对于何时使用服务定位器,我的简单建议就是: 谨慎使用
与其给需要使用的地方提供一个全局机制来访问一个对象,不如首先考虑将这个对象传递进去.这极其简单易用,而且将耦合变得直观.这可以满足绝大部分需求
但是,有时手动地将一个对象传来传去显得毫无理由或者使得代码难以阅读.有些系统,比如日志系统或内存管理系统,不应该是某个模块公开API的一部分.渲染代码的参数应该必须和渲染相关,而不是像日志系统那样的东西
同样地,它也适用于一些类似功能的单一系统.你的游戏可能只有一个音频设备或者显示系统让玩家与之打交道.传递的参数是一项环境属性,所以将它传递10层函数以便让一个底层的函数能够访问,为代码增加了毫无意义的复杂度
在这些情况下,这个模式能够起到作用.它用起来像一个更灵活,更可配置的单例模式.当被合理地使用时,它能够让你的代码更有弹性,而且几乎没有运行时的损失.
16.4 使用须知
服务定位器的关键困难在于,它要有所依赖(连接两份代码),并且在运行时才连接起来.这给与了你弹性,但付出的代价就是阅读代码时比较难以理解依赖的是什么.
16.4.1 服务必须被定位
当使用单例或者一个静态类时,我们需要的实例不可能变得不可用.但是,既然这个模式需要定位服务,那么我们可能需要处理定位失败的情况
16.4.2 服务不知道被谁定位
既然定位器是全局可访问的,那么游戏中的任何代码都有可能请求一个服务然后操作它.这意味着这个服务在任何情况下都必须能正确工作.
16.5 示例代码
16.5.1 服务
class Audio {
public:
;
;
;
virtual ~Audio() {}
};
16.5.2 服务提供器
class ConsoleAudio: public Audio {
public:
virtual void playSound(int soundID) {
// Play sound using console audio api...
}
virtual void stopSound(int soundID) {
// Stop sound using console audio api...
}
virtual void stopAllSounds() {
// Stop all sounds using console audio api...
}
};
16.5.3 简单的定位器
class Locator {
public:
static Audio * getAudio() { return service_; }
static void provide(Audio * service) {
service_ = service;
}
private:
static Audio * service_;
};
ConsoleAudio * audio = new ConsoleAudio();
Locator::provide(audio);
Audio * audio = Locator::getAudio();
audio->playSound(VERY_LOUD_BANG);
静态函数getAudio()负责定位工作.我们能在代码的任何地方调用它,它能返回一个Audio服务的实例提供我们使用
它"定位"的方法十分简单----在使用这个服务之前它依赖一些外部代码来注册一个服务提供器.
这里使用的技术叫做依赖注入,这个术语表示了一个基本的思想.假设你有一个类,依赖另外一个类.在我们的例子中,我们的Locator类需要Audio服务的一个实例.通常,这个定位器应该负责为自己构建这个实例.依赖注入却说外部代码应该负责为这个对象注入它所需要的这个依赖实例
这里关键需要注意的地方是调用playSound()的代码对ConsoleAudio具体实现毫不知情.它只知道Audio的抽象接口,同样重要的是,甚至是定位器本身和具体服务提供器也没有耦合.代码中唯一知道具体实现类的地方,是提供这个服务的初始化代码
这里还有更深一层的解耦----通过服务定位器,Audio接口在绝大多数地方并不知道自己正在被访问.一旦它知道了,它就是一个普通的抽象基类了.这十分有用,因为这意味着我们可以将这个模式应用到一些已经存在的但并不是围绕这个来设计的类上.这和单例有个对比,后者影响了"服务"类本身的设计
16.5.4 空服务
“时序解耦”----两份单独的代码必须按正确的顺序调用来保证程序正确工作.每个状态软件都有不同程度的"时序耦合",但是就像其他耦合那样,消除时序耦合会使得代码易于管理
class NullAudio: public Audio {
public:
virtual void playSound(int soundID);
virtual void stopSound(int soundID);
virtual void stopAllSounds();
};
class Locator {
public:
static void initialize() {
service_ = &nullService_;
}
static Audio & getAudio() { return *service_; }
static void provide(Audio * service) {
// Revert to null service.
if (service == NULL) service = &nullService_;
service_ = service;
}
private:
static Audio * service_;
static NullAudio nullService_;
};
16.5.5 日志装饰器
class LoggedAudio: public Audio {
public:
LoggedAudio(Audio & wrapped): wrapped_(wrapped) {}
virtual void playSound(int soundID) {
log("play sound");
wrapped_.playSound(soundID);
}
virtual void stopSound(int soundID) {
log("stop sound");
wrapped_.stopSound(soundID);
}
virtual void stopAllSounds() {
log("stop all sounds");
wrapped_.stopAllSounds();
}
private:
void log(const char * message) {
// Code to log message...
}
Audio & wrapped_;
};
void enableAudioLogging() {
// Decorate the existing service.
Audio * service = new LoggedAudio(Locator::getAudio())；
// Swap it in.
Locator::provide(service);
}
16.6 设计决策
16.6.1 服务是如何被定位的
外部代码注册
它简单快捷
我们控制提供器如何被构建
我们可以在游戏运行的时候更换服务提供器
定位器依赖外部代码
在编译时绑定
class Locator {
public:
static Audio & getAudio() { return service_; }
private:
#if DEBUG
static DebugAudio service_;
#else
static ReleaseAudio service_;
#endif
};
它十分快速
你能保证服务可用
你不能方便地更改服务提供器
在运行时配置
我们不需重编译就能切换服务提供器
非程序员能够更换服务提供器
一份代码库能够同时支持多份配置
不像前几个解决方案,这方案比较复杂且十分重量级
定位服务需要时间
16.6.2 当服务不能被定位时发生了什么
让使用者处理
它让使用者决定如何处理查找失败
服务使用者必须处理查找失败
终止游戏
使用者不需要处理一个丢失的服务
如果服务没有被找到,游戏将会中断
返回一个空服务
使用者不需要处理丢失的服务
当服务不可用时,游戏还能继续
16.6.3 服务的作用域多大
如果是全局访问
它鼓励整个代码库使用同一个服务
我们对何时何地使用服务完全失去了控制
如果访问被限制到类中
我们控制了耦合.
它可能导致重复的工作
我的一般原则是,如果服务被限制在游戏的一个单独域中,那么就把服务的作用域限制到类中.比如,获取网络访问的服务就可能被限制在联网的类中.而更广泛使用的服务,比如日志服务应该是全局的
16.7 其他参考
服务定位器模式在很多方面和单例模式非常相近,所以值得考虑两者来决定哪一个更适合你的需求
Unity框架把这个模式和组件模式结合起来,并使用在了GetComponent()方法中
Microsoft的XNA游戏开发框架将这个模式内嵌到它的核心Game类中.每个实例有一个GameService对象,能够用来注册和定位任何类型的服务
第17章 数据局部性
通过合理组织数据利用CPU的缓存机制来加快内存访问速度
17.1 动机
RAM的存取速度远远跟不上CPU的速度
17.1.1 数据仓库
对刚访问数据的邻近数据进行访问的术语叫做访问局部性(locality of reference)
17.1.2 CPU的托盘
当代计算机有多级缓存,也就是你所听到的那些"L1", "L2", "L3"等.它们的大小按照其等级递增,但速度却随等级递减
17.1.3 等下,数据即性能
17.2 数据局部性模式
当代CPU带有多级缓存以提高内存访问速度.这一机制加快了对最近访问过的数据的邻近内存的访问速度.通过增加数据局部性并利用这一点可以提高性能----保持数据位于连续的内存中以提供程序进行处理
17.3 使用情境
如果多数优化措施,知道我们使用数据局部性模式的第一条准则就是找到出现性能问题的地方.不要在那些代码库里非频繁执行的部分浪费时间,它们不需要本模式.对那些非必要的代码进行优化将使你的人生变得艰难----因为结果总是更加复杂且笨拙.由于此模式的特殊性,因此你可能还希望确定你的性能问题是否是由缓存未命中引起的,如果不是,那么这个模式也帮不上忙
17.4 使用须知
为了做到缓存友好,你可能需要牺牲一些之前所做的抽象化.你越是在程序的数据局部性上下工夫,你就越要牺牲继承,接口以及这些手段所带来的好处.这里并没有高招,只有利弊权衡的挑战.而乐趣便在这里
17.5 示例代码
17.5.1 连续的数组
class GameEntity {
public:
GameEntity(AIComponent * ai, PhysicsComponent * physics, RenderComponent * render): ai_(ai), physics_(physics), render_(render) {}
AIComponent * ai() { return ai_; }
PhysicsComponent * physics() { return physics_; }
RenderComponent* render() { return render_; }
private:
AIComponent * ai_;
PhysicsComponent * physics_;
RenderComponent * render_;
};
class AIComponent {
public:
void update() {
// Work with and modify state
}
private:
// Goals, mood, etc, ...
};
class PhysicsComponent {
public:
void update() {
// Work with and modify state...
}
private:
// Rigid body, velocity, mass, etc, ...
};
class RenderComponent {
public:
void render() {
// Work with and modify state...
}
private:
// Mesh, textures, shaders, etc. ...
};
while (!gameOver) {
; i < numEntities; i++) {
entities[i]->ai()->update();
}
; i < numEntities; i++) {
entities[i]->physics()->update();
}
; i < numEntities; i++) {
entities[i]->render()->update();
}
// Other game loop machinery for timing...
}
while (!gameOver) {
// Process AI
; i < numEntities; i++) {
aiComponents[i].update();
}
// Update Physics
; i < numEntites; i++) {
physicsComponents[i].update();
}
// Draw to screen
; i < numEntities; i++) {
renderComponents[i].render();
}
// Other game loop machinery for timing...
}
17.5.2 包装数据
class Particle {
public:
void update() { /* Gravity, etc. ... */ }
// Position, velocity, etc. ...
};
class ParticleSystem {
public:
ParticleSystem(): numParticles_() {}
void update();
private:
;
int numParticles_;
Particle particles_[MAX_PARTICLES];
};
void ParticlesSystem::update() {
; i < numParticles_; i++) {
particles_[i].update();
}
}
; i < numParticles_; i++) {
if (particles_[i].isActive()) {
particles_[i].update();
}
}
void ParticleSystem::activateParticle(int index) {
// Shouldn't already be active!
assert(index >= numActive_);
// Swap it with the first inactive particle right
// after the active ones.
Particle temp = particels_[numActive_];
particles_[numActive_] = particles_[index];
particles_[index] = temp;
numActive_++;
}
void ParticleSystem::deactivateParticle(int index) {
// Shouldn't already be inactive!
assert(index < numActive);
numActive_--;
// Swap it with the last active particle right
// before the inactive ones.
Particle temp = particles_[numActive_];
particles_[numActive_] = particles_[index];
particles_[index] = temp;
}
17.5.3 热/冷分解
class AIComponent {
public:
void update() { /* ... */ }
private:
Animation * animation_;
double energy_;
Vector goalPos_;
};
class AIComponent {
public:
void update() { /* ... */ }
private:
// Previous fields ...
LootType drop_;
int minDrops_;
int maxDrops_;
double chanceOfDrop_;
};
class AIComponent {
public:
// Methods...
private:
Animation * animation_;
double energy_;
Vector goalPos_;
LootDrop * loot_;
};
class LootDrop {
friend class AIComponent;
LootType drop_;
int minDrops_;
int maxDrops_;
double chanceOfDrop_;
};
17.6 设计决策
这种设计模式更适合叫做一种思维模式.它提醒着你,数据的组织方式是游戏性能的一个关键部分.这一块的实际拓展空间很大,你可以让你的数据局部性影响到游戏的整个架构,又或者它只是应用在一些核心模块的数据结构上.对这一模式的应用,你最需要关心的就是该何时何地使用它.而随着这个问题我们也会看到一些新的顾虑
17.6.1 你如何处理多态
避开继承
安全而容易
速度更快
灵活性差
为不同的对象类型使用相互独立的数组
这样的一系列集合让对象紧密地封包
你可以进行静态地调用分发
你必须时刻追踪这些集合
你必须注意每一个类型
使用指针集合
这样做灵活性高
这样做并不缓存友好
17.6.2 游戏实体是如何定义的
假如游戏实体通过类中的指针来索引其组件
你可以将组件存于相邻的数组中
对于给定实体,你可以很容易地获取它的组件
在内存中移动组件很困难
假如游戏实体通过一系列ID来索引其组件
这更加复杂
这样做更慢
你需要访问组件管理器
假如游戏实体本身就只是个ID
你的游戏实体类完全消失了,取而代之的是一个优雅的数值包装
实体类本身是空的
你无须管理其生命周期
检索一个实体的所有组件会很慢
17.7 参考
本章节的许多内容涉及到组件模式,而组件模式中的数据结构是在优化缓存使用时几乎最常用的.事实上,使用组件模式使得这一优化变得更加简单.因为实体一次只是更新它们的一个域(AI模块和物理模块等),所以将这些模块划分为组件使得你可以将一系列实体合理地划为缓存友好的几部分.但这并不意味着你只能选择组件模式实现本模式!不论何时你遇到涉及大量数据的性能问题,考虑数据的局部性都是很重要的
Tony Albrecht写作的<<Pitfalls of Object-Oriented Programmi9ng>>一书被广泛阅读,这本书介绍了如何通过游戏的数据结构设计来实现缓存友好性.它使得许多人(包括我!)意识到数据结构的设计对性能有多么地重要
与此同时,Noel Lopis就同一个话题撰写了一篇广为流传的博客
本设计模式几乎完全地利用了同类型对象的连续数组的优点.随着时间推移,你将会往这个数组中添加和移除对象.对象池模式恰恰阐释了这一内容
Artemis游戏引擎是首个也是最为知名的对游戏实体使用简单ID的框架
第18章 脏标记模式
18.1 动机
许多游戏都有一个称之为场景图的东西.这是一个庞大的数据结构,包含了游戏世界中所有的物体.渲染引擎使用它来决定将物体绘制到屏幕的什么地方
就最简单的来说,一个场景图只是包含多个物体的列表.每个物体都含有一个模型(或其他图元)和一个"变换".变换描述了物体在世界中的位置,旋转角度和缩放大小.想要移动或者旋转物体,我们可以简单地修改它的变换
当渲染器绘制一个物体时,它将这个物体的变换作用到这个物体的模型上,然后将它渲染出来.如果我们有的是一个场景"袋"而不是场景"图"的话,事情会变得简单很多
然而,许多场景图是分层的.场景中的一个物体会绑定在一个父物体上.在这种情况下,它的变换就依赖于其父物体的位置,而不是游戏世界中的一个绝对位置.
举个例子,想象我们的游戏中有一艘海盗船在海上.桅杆的顶部是一个瞭望塔,一个海盗靠在这个瞭望塔上,抓在海盗肩膀上的是只鹦鹉.这艘船的局部变换标记了它在海中的位置,瞭望塔的变换标记了它在船上的位置,等等
鹦鹉->海盗->瞭望塔->海盗船
这样,当一个父物体移动时,它的子物体也会自动地跟着移动.如果我们修改船的局部变换,瞭望塔,海盗,鹦鹉也会随之变动.如果在船移动时我们必须手动调整船上所有物体的变换来防止相对滑动,那会是一件很头疼的事情
18.1.1 局部变换和世界变换
计算一个物体的世界变换是相当直观的----只要从根节点沿着它的父链将变换组合起来就行.也就是说鹦鹉的世界变换就是
鹦鹉世界变换 = 船的局部变换 x 瞭望塔的局部变换 x 海盗的局部变换 x 鹦鹉的局部变换
我们每帧都需要世界中每个物体的世界变换.所以即使每个模型中只有少数的几个矩阵相乘,却也是代码中影响性能的关键所在.保持它们及时更新是棘手的,因为当一个父物体移动,这会影响它自己和它所有的子物体,以及子物体的子物体等的世界变换
最简单的途径是在渲染的过程中计算变换.每一帧中,我们从顶层开始递归地遍历场景图.对每个物体,我们计算它们的世界变换并立刻绘制它
但是这对我们宝贵的CPU资源是一种可怕的浪费.许多物体并不是每一帧都移动.想想关卡中那些静止的几何体,它们没有移动,但每一帧都要重计算它们的世界变换是一种多么大的浪费
18.1.2 缓存世界变换
一个明显的解决方法是将它"缓存"起来.在每个物体中,我们保存它的局部变换和它派生物体的世界变换.当我们渲染时,我们只使用预先计算好的世界变换.如果物体从不移动,那么缓存的变换始终是最新的,一切都很美好
当一个物体缺失移动了,简单的方法就是立即刷新它的世界变换.但是不要忘了继承连!当一个父物体移动时,我们需要重计算它的世界变换并递归地计算它所有子物体的世界变换
想象某些比较繁重的游戏场景.在一个单独帧中,船被扔进海里,瞭望塔在风中晃动,海盗斜靠在边上,鹦鹉跳到他的头上.我们修改了4个局部变换.如果我们在每个局部变换变动时都匆忙地重新计算世界变换,结果会发生什么
我们只移动了4个物体,但是我们做了10次世界变换计算.这6次无意义的计算在渲染器使用之前就被扔掉了.我们计算了4次鹦鹉的世界变换,但是只渲染了一次
问题的关键是一个世界变换可能依赖于好几个局部变换.由于我们在每个这些变换变化时都立刻重计算,所以最后当一帧内有好几个关联的局部变换改变时,我们就将这个变换重新计算了好多遍
->Move Ship
* Recalc Ship
* Recalc Nest
* Recalc Pirate
* Recalc Parrot
->Move Nest
* Recalc Nest
* Recalc Pirate
* Recalc Parrot
->Move Pirate
* Recalc Pirate
* Recalc Parrot
->Move Parrot
* Recalc Parrot
18.1.3 延时重算
我们通过将修改局部变换和更新世界变换解耦来解决这个问题.这让我们在单次渲染中修改多个局部变换,然后在所有变动完成之后,在实际渲染器使用之前仅需要计算一次世界变换
要做到这点,我们为图中每个物体添加一个"flag"."flag"和"bit"在编程中是同义词----它们都表示单个小单元数据,能够存储两种状态中的一个.我们称之为"true"和"false",有时也叫"set"和"cleared".
我们在局部变换改动时设置它.当我们需要这个物体的世界变换时,我们检查这个flag.如果它被标记为"set"了,我们计算这个世界变换,然后将这个flag置为"clear".这个flag代表,"这个世界变换是不是过期了?"由于某些原因,传统上这个"过期的"被称作"脏的".也就是"脏标记","Dirty bit"也是这个模式常见的名字.但是我想我会坚持使用那种看起来每那么"污秽"的名字
如果我们运用这个模式,然后将我们上个例子中的所有物体都移动,那么游戏看起来如下:
->Move Ship
->Move Nest
->Move Pirate
->Move Parrot
Render
* Recalc Ship
* Recalc Nest
* Recalc Pirate
* Recalc Parrot
这是你能期望的最好的办法.每个被影响的物体的世界变换只需要计算一次.只需要一个简单的位数据,这个模式位我们做了不少事：
它将父链上物体的多个局部变换的改动分解为每个物体的一次重计算
它避免了没有移动的物体的重计算
一个额外的好处: 如果一个物体在渲染之前移除了,那就根本不用计算它的世界变换
18.2 脏标记模式
一组原始数据随时间变化.一组衍生数据经过一些代价昂贵的操作由这些数据确定.一个脏标记跟踪这个衍生数据是否和原始数据同步.它在原始数据改变时被设置.如果它被设置了,那么当需要衍生数据时,它们就会被重新计算并且标记被清除.否则就使用缓存的数据
18.3 使用情境
脏位标记设计两个关键词:"计算"和"同步".在这两种情况下,处理原始数据到衍生数据的过程在时间或其他方面会有很大的开销
这里也有些其他的要求:
原始数据的修改次数比衍生数据的使用次数多
递增地更新数据十分困难
18.4 使用须知
18.4.1 延时太长会有代价
这个模式把某些耗时的工作推迟到真正需要时才进行,而到有需要时,往往刻不容缓.
18.4.2 必须保证每次状态改动时都设置脏标记
既然衍生数据是通过原始数据计算而来,那它本质上就是一份缓存.当你获取缓存数据时,棘手的问题是缓存失效----当缓存和原始数据不同步时,什么都不正确了.在这个模式中,它意味着当任何原始数据变动时,都要设置脏标记
18.4.3 必须在内存中保存上次的衍生数据
18.5 示例代码
class Transform {
public:
static Transform origin();
Transform combine(Transform & other);
};
class GraphNode {
public:
GraphNode(Mesh * mesh): mesh_(mesh), local_(Transform::origin() ) {}
private:
Transform local_;
Mesh * mesh_;
GraphNode * children_[MAX_CHILDREN];
Int numChildren_;
};
GraphNode * graph_ = new GraphNode(NULL);
// Add children to root graph node...
void renderMesh(Mesh * mesh, Transform transform);
18.5.1 未优化的遍历
void GraphNode::render(Transform parentWorld) {
Transform world = local_.combine(parentWorld);
if (mesh_) renderMesh(mesh_, world);
; i < numChildren_; i++) {
children_[i]->render(world);
}
}
graph->render(Transform::origin());
18.5.2 让我们"脏"起来
class GraphNode {
public:
GraphNode(Mesh * mesh): mesh_(mesh), local_(Transform::origin()), dirty_(true) {}
// Other methods...
private:
Transform world_;
bool dirty_;
// Other fields...
};
void GraphNode::render(Transform parentWorld, bool dirty) {
dirty != dirty_;
if (dirty) {
world_ = local_.combine(parentWorld);
dirty_ = false;
}
if (mesh_) renderMesh(mesh_, world_);
; i < numChildren_; i++) {
children_[i]->render(world_, dirty);
}
}
18.6 设计抉择
18.6.1 何时清除脏标记
当需要计算结果时
当计算结果从不使用时,它完全避免了计算
如果计算十分耗时,会造成明显的卡顿
在精心设定的检查点
这些工作并不影响用户体验.
当工作执行时,你失去了控制权
在后台
你可以调整工作执行的频率
你可以做更多冗余的工作
需要支持异步操作
18.6.2 脏标记追踪的粒度多大
更精细的粒度
你只需要处理真正变动了的数据,你将船的真正变动的木块数据发送给服务器
更粗糙的粒度
你最终需要处理未变动的数据
存储脏标记消耗更少的内存
固定开销花费的时间要更少
18.7 参考
这种模式在游戏外的领域也是常见的,比如在Angular这种BS(browser-side)框架中,它利用脏标记来跟踪浏览器中有变动并需要提交到服务端的数据
物理引擎跟踪着物体的运动和空闲状态.一个空闲的物体直到受到力的作用才会移动,它在受力之前不需要处理.这个"是否在移动"就是一个脏标记,用来标记哪些物体收到了力的作用并需要计算它们的物理状态
第19章 对象池
使用固定的对象池重用对象,取代单独地分配和释放对象,以此来达到提升性能和优化内存使用的目的
19.1 动机
19.1.1 碎片化的害处
19.1.2 二者兼顾
19.2 对象池模式
定义一个保持着可重用对象集合的对象池类.其中的每个对象支持对其"使用(in use)"状态的访问,以确定这一对象目前是否"存活(alive)".在对象池初始化时,它预先创建整个对象的集合(通常为一块连续堆区域),并将它们都置为"未使用(not in use)"状态
当你想要创建一个新对象时就向对象池请求.它将搜索到一个可用的对象,将其初始化未"使用中(in use)"状态并返回给你.当该对象不再被使用时,它将被置回"未使用(not in use)"状态.使用该方法,对象便可以在无需进行内存或其他资源分配的情况下进行任意的创建和销毁
19.3 使用情境
这一设计模式被广泛地应用于游戏中的可见物体,如游戏实体对象,各种视觉特效,但同时也被使用于非可见的数据结构中,如当前播放的声音.我们在以下情况使用对象池:
当你需要频繁地创建和销毁对象时
对象的大小一致时
在堆上进行对象内存分配较慢或者会产生内存碎片时
每个对象封装着获取代价昂贵且可重用的资源,如数据库,网络的连接
19.4 使用须知
19.4.1 对象池可能在闲置的对象上浪费内存
19.4.2 任意时刻处于存活状态的对象数目恒定
19.4.3 每个对象的内存大小是固定的
19.4.4 重用对象不会被自动清理
19.4.5 未使用的对象将占用内存
19.5 示例代码
class Particle {
public:
Particle(): framesLeft_() {}
void init(double x, double y, double xVel, double yVel, int lifetime);
void animate();
; }
private:
int framesLeft_;
double x_, y_;
double xVel_, yVel_;
};
void Particle::init(double x, double y, double xVel, double yVel, int lifetime) {
x_ = x;
y_ = y;
xVel_ = xVel;
yVel_ = yVel;
frameLeft_ = lifetime;
}
void Particle::animate() {
if (!inUse()) return;
framesLeft_;
x_ += xVel_;
y_ += yVel_;
}
class ParticlePool {
public:
void create(double x, double y, double xVel, double yVel, int lifetime);
void animate();
private:
;
Particle particles_[POOL_SIZE];
};
void ParticlePool::animate() {
; i < POOL_SIZE; i++) {
particles_[i].animate();
}
}
void ParticlePool::create(double x, double y, double xVel, double yVel, int lifetime) {
; i < POOL_SIZE; i++) {
if (!particles_[i].inUse()) {
particles_[i].init(x, y, xVel, yVel, lifetime);
return;
}
}
}
class Particle {
public:
// Previous stuff...
Particle * getNext() const { return state_.next; }
void setNext(Particle * next) {
state_.next = next;
}
private:
int framesLeft_;
union {
// State when it's in use
struct {
double x, y, xVel, yVel;
} live;
// State when it's available.
Particle * next;
} state_;
};
class ParticlePool {
// Previous stuff...
private:
Particle * firstAvailable_;
};
ParticlePool::ParticlePool() {
// The first one is available.
firstAvailable_ = &particles_[];
// Each particle points to the next.
; i < POOL_SIZE - ; i++) {
particles_[i].setNext(&particles_[i + ]);
}
// The last one terminates the list
particles_[POOL_SIZE - ].setNext(NULL);
}
void ParticlePool::create(double x, double y, double xVel, double yVel, int lifetime) {
// Make sure the pool isn't full.
assert(firstAvailable_ != NULL);
// Remove it from the available list.
Particle * newParticle = firstAvailable_;
firstAvailable_ = new Particle->getNext();
newParticle->init(x, y, xVel, yVel, lifetime);
}
bool Particle::animate() {
if (!inUse()) return false;
framesLeft_;
x_ += xVel_;
y_ += yVel_;
;
}
void ParticlePool::animate() {
; i < POOL_SIZE; i++) {
if (particles_[i].animate()) {
// Add this particle to the front of the list.
particles_[i].setNext(firstAvailable_);
firstAvailable_ = &particles_[i];
}
}
}
19.6 设计决策
19.6.1 对象是否被加入对象池
假如对象与对象池耦合
实现很简单,你可以简单地为那些池中的对象增加一个"使用中"的标志位或者函数,这就能解决问题了
你可以保证对象只能通过对象池创建.在C++中,只需简单地将对象池类作为对象类的友元类,并将对象的构造函数私有化即可
class Particle {
friend class ParticlePool;
private:
Particle(): inUse_(false) {}
bool inUse_;
};
class ParticlePool {
Particle pool_[];
};
你可以避免存储一个"使用中"的标志位,许多对象已经维护了可以表示自身是否仍然存活的状态
假如对象独立于对象池
任意类型的对象可以被置入池中.这是个巨大的优点.通过对象与对象池的解绑,你将能够实现一个通用,可重用的对象池类
"使用中"状态必须能够在对象外部被追踪.最简单的做法是在对象池中额外创建一块独立的空间:
template <class TObject>
class GenericPool {
private:
;
TObject pool_[POOL_SIZE];
bool inUse_[POOL_SIZE];
};
19.6.2 谁来初始化那些被重用的对象
假如在对象池内部初始化重用对象
对象池可以完全封装它管理的对象
对象池与对象如何被初始化密切相关
class Particle {
public:
// Multiple ways to initialize
void Init(double x, double y);
void Init(double x, double y, double angle);
void Init(double x, double y, double xVel, double yVel);
};
class ParticlePool {
public:
void create(double x, double y);
void create(double x, double y, double angle);
void create(double x, double y, double xVel, double yVel);
};
假如对象在外部被初始化
此时对象池的接口会简单一些
class Particle {
public:
void init(double x, double y);
void init(double x, double y, double angle);
void init(double x, double y, double xVel, double yVel);
};
class ParticlePool {
public:
Particle * create() {
}
private:
Particle pool_[];
};
ParticlePool pool;
pool.create()->init(, );
pool.create()->init(, , 0.3);
pool.create()->init(, , 3.3, 4.4);
外部编码可能需要处理新对象创建失败的情况
Particle * particle = pool.create(); , );
19.7 参考
对象池模式与享元模式看起来很相似.它们都管理着一系列可重用对象.其差异在于"重用"的含义.享元模式中的对象通过在多个持有者中并发地共享相同的实例以实现重用.它避免了因在不同上下文中使用相同对象而导致的重复内存使用.对象池的对象也被重用,但此"重用"意味着在原对象持有者使用完对象之后,将其内存回收.对象池里的对象在其生命周期中不存在着因为被共享而引致的异常
将那些类型相同的对象在内存上整合,能够帮助你在遍历这些对象时利用好CPU的缓存区.数据局部性设计模式阐释了这一点
第20章 空间分区
20.1 动机
将对象存储在根据位置组织的数据结构中来高效地定位它们
20.1.1 战场上的部队
假设我们在制作一款即时策略游戏.对立阵营的上百个单位将在战场上相互厮杀.勇士们需要知道该攻击他们附近的哪个敌人,简单的方式处理就是查看每一对单位看看他们彼此距离的远近
void handleMelle(Unit * units[], int numUnits) {
; a < numUnits - ; a++) {
; b < numUnits; b++) {
if (units[a]->position() == units[b]->position()) {
handleAttack(units[a], units[b]);
}
}
}
}
这里我们用一个双重循环,每层循环都遍历了战场上的所有单位.这意味着我们每一帧对检验的次数随着单位个数的平方增加.每增加一个额外的单位,都要与前面的所有单位进行比较.当单位数目非常大时,局面便会失控
20.1.2 绘制战线
20.2 空间分区模式
对于一组对象而言,每一个对象在空间都有一个位置.将对象存储在一个根据对象的位置来组织的数据结构中,该数据结构可以让你高效地查询位于或靠近某处的对象.当对象的位置变化时,应更新该空间数据结构以便可以继续这样查找对象
20.3 使用情境
这是一个用来存储活跃的,移动的对象以及静态图像和游戏世界的几何形状等对象的常见模式.复杂的游戏常常有多个空间分区来应对不同类型的存储内容
该模式的基本要求是你有一组对象,每个对象都具备某种位置信息,而你因为要根据位置做大量的查询来查找对象从而遇到了性能问题
20.4 使用须知
空间分区将O(n)或者O(n2)复杂度的操作拆解为更易于管理的结构.对象越多,模式的价值就越大.相反,如果你的n值很小,则可能不值得使用该模式.由于该模式要根据对象的位置来组织对象,故对象位置的改变就变得难以处理了.你必须重新组织数据结构来跟踪物体的新位置,这会增加代码的复杂性并产生额外的CPU周期开销.你必须确保这么做是值得的
空间分区会使用额外的内存来保存数据结构.就像许多的优化一样,它是以空间换取速度的.如果你的内存比时钟周期更吃紧的话,这可能是个亏本生意
20.5 示例代码
20.5.1 一张方格纸
设想一下战场的整个区域.现在,往上铺一张方格大小固定的网,就像盖张方格纸那样.我们用这些网格中的单元格来取代一维数组以存储单位.每个单元格存储那些处于其边界之内的单位列表.我们在处理战斗时,只考虑在同一个单元格内的单位.我们不会将每个单位与游戏中的其他单位一一比较,取而代之的是,我们已经将战场划分为一堆更小的小型战斗,每一个小战场里的单位要少很多
20.5.2 相连单位的网格
class Unit {
friend class Grid;
public:
Unit(Grid * grid, double x, double y): grid_(grid), x_(x), y_(y) {}
void move(double x, double y);
private:
double x_, y_;
Grid * grid_;
};
class Grid {
public:
Grid() {
// Clear the grid
; x < NUM_CELLS; x++) {
; y < NUM_CELLS; y++) {
cells_[x][y] = NULL;
}
}
}
;
;
private:
Unti * cells_[NUM_CELLS][NUM_CELLS];
};
class Unit {
// Previous code...
private:
Unit * prev_;
Unit * next_;
};
20.5.3 进入战场
Unit::Unit(Grid * grid, double x, double y): grid_(grid), x_(x), y_(y), prev_(NULL), next_(NULL) {
grid_->add(this);
}
void Grid::add(Unit * unit) {
// Determin which grid cell it's in
int cellX = (int)(unit->x_ / Grid::CELL_SIZE);
int cellY = (int)(unit->y_ / Grid::CELL_SIZE);
// Add to the front of list for the cell it's in
unit->prev_ = NULL;
unit->next_ = cells_[cellX][cellY];
cells_[cellX][cellY] = unit;
if (unit->next_ != NULL) {
unit->next_->prev_ = unit;
}
}
20.5.4 刀光剑影的战斗
void Grid::handeMelee() {
; x < NUM_CELLS; x++) {
; y < NUM_CELLS; y++) {
handelCell(cells_[x][y]);
}
}
}
void Grid::handleCell(Unit * unit) {
while (unit != NULL) {
Unit * other = unit->next_;
while (other != NULL) {
if (unit->x_ == other->x_ && unit->y_ == other->y) {
handleAttack(unit, other);
}
other = other->next_;
}
unit = unit->next_;
}
}
20.5.5 冲锋陷阵
void Unit::move(double x, double y) {
grid_->move(this, x, y);
}
void Grid::move(Unit * unit, double x, double y) {
// See which cell it was in.
int oldCellX = (int)(unit->x_ / Grid::CELL_SIZE);
int oldCellY = (int)(unit->y_ / Grid::CELL_SIZE);
// See which cell it's moving to
int cellX = (int)(x / Grid::CELL_SIZE);
int cellY = (int)(y / Grid::CELL_SIZE);
unit->x_ = x;
unit->y_ = y;
// If it didn't change cells, we're done.
if (oldCellX == cellX && oldCellY == cellY) return;
// Unlink it from the list of its old cell.
if (unit->prev_ != NULL) {
unit->prev_->next_ = unit->next_;
}
// If it's the head of a list, remove it
if (cells_[oldCellX][oldCellY] == unit) {
cells_[oldCellX][oldCellY] = unit->next_;
}
// Add it back to the grid at its new cell.
add(unit);
}
20.5.6 近在咫尺,短兵相接
if (distance(unit, other) < ATTACK_DISTANCE) {
handleAttack(unit, other);
}
void Grid::handleUnit(Unit * unit, Unit * other) {
while (other != NULL) {
if (distance(unit, other) < ATTACK_DISTANCE) {
handleAttack(unit, other);
}
other = other->next_;
}
}
void Grid::handleCell(int x, int y) {
Unit * unit = cells_[x][y];
while (unit != NULL) {
// Handle other units in this cell
handelUnit(unit, unit->next_);
unit = unit->next_;
}
}
void Grid::handleCell(int x, int y) {
Unit * unit = cells_[x][y];
while (unit != NULL) {
// Handle other units in this cell
handleUnit(unit, unit->next_);
// Also try the neighboring cells
) handleUnit(unit, cells_[x - ][y]);
) handleUnit(unit, cells_[x][y - ]);
&& y > )
handelUnit(unit, cells_[x - ][y - ]);
&& y < NUM_CELLS - )
handleUnit(unit, cells_[x - ][y + ]);
unit = unit->next_;
}
}
20.6 设计决策
20.6.1 分区是层级的还是扁平的
在网格例子中,我们将网格划分成了一个单一扁平的单元格集合.与此相反,层级空间分区则是将空间划分成几个区域.然后,如果这些区域中仍然包含着许多的对象,就会继续划分.整个递归过程持续到每个区域的对象数目都少于某个约定的最大对象数量为止
如果它是一个扁平的分区
相对简单
内存使用量恒定
当对象改变位置时可以更为快速地更新
如果它是一个层级的分区
它可以更有效地处理空白的空间
它在处理对象稠密区域时更为有效
20.6.2 分区依赖于对象集合吗
如果分区依赖于对象
对象可以被逐步地添加
对象可以快速地移动
分区可以不平衡
如果分区自适应于对象集合
你可以确保分区间的平衡
对整个对象集合进行一次性的分区时更为高效
如果分区不依赖于对象,而层级却依赖于对象
可以逐步地增加对象
对象可以快速地移动
分区是平衡的
20.6.3 对象只存储在分区中吗
如果它是对象唯一存储的地方
这避免了两个集合的内存开销和复杂性
如果存在存储对象的另外一个集合
遍历所有的对象会更为快速
20.7 参考
在这章中我避开对具体空间分区结构的详细讨论,以保持章节的高层次概括性(并且也不会太长),但是下一步你应该要去了解一些常见的结构.尽管它们的名字吓人,但却出奇的简单明了.常见的有
每一个空间数据结构基本都是从一个现有已知的一维数据结构扩展到多维,了解它们的线性结构会帮助你判断它们是否适合于解决你的问题:
网格是一个连续的桶排序
二叉空间分割,k-d树,以及层次包围盒都是二叉查找树
四叉树和八叉树都是Trie树