Tag: gpp-review

GPP读书笔记之Flyweight模式（二）

2014-09-02 by jennal·0 Comment

原文地址：http://gameprogrammingpatterns.com/flyweight.html

Flyweight模式是什么

Flyweight是一个非常简单的设计模式。它可能也是唯一可以从硬件上获得支持的设计模式。从名字可以看出，这是一个轻量级的设计模式，不仅仅体现在实现上，它也能大大降低内存的消耗，提高执行效率。它常被用在场景的开发中，特别是瓦片场景之类的，包含很多重复出现的子元素。

以瓦片地图（TileMap）举例，简单的说，Flyweight就是把瓦片的属性（成员变量）划分为两类

许多瓦片共有的属性，例如贴图、形状等
各个瓦片独有的属性，例如位置、旋转角度等

将共有的属性提取出来，每一个共有的属性做一个单例，所有的瓦片共享这些共有属性（保存引用或者指针）。这些共有的属性往往是加载缓慢的资源，那么在渲染时，只需要渲染一次，然后在不同的位置多次重绘，就可以大大降低内存消耗，提高执行效率。

以上是我粗浅的理解，原文给出了2个例子，来看原文的例子

简单的例子：森林中的树

作者很会讲故事，他说可以用简单的几句文字就能描述广阔的森林，但是用程序来实现，却不是那么简单的事情。当玩家看到满屏的树，图形程序员看到的是数百万个矩形每1/60秒被GPU渲染一次。

上千棵树，每棵树包含上千个矩形，即使你有足够的内存来保存整个森林的数据，渲染它们需要大量的数据占用从CPU到GPU的总线。

每棵树包含这些元素

多边形网格，来描述树的主干、分支以及树叶
枝干和树叶的纹理贴图
位置和朝向信息
其他一些信息，例如大小、色调，使得每棵树看起来都不太一样

它的代码大概是这个样子

class Tree
{
private:
    Mesh mesh_; //多边形网格
    Texture bark_; //枝干纹理贴图
    Texture leaves_; //树叶纹理贴图
    Vector position_;
    double height_;
    double thickness_;
    Color barkTint_;
    Color leafTint_;
};

class Tree

{

private:

Mesh mesh_; //多边形网格

Texture bark_; //枝干纹理贴图

Texture leaves_; //树叶纹理贴图

Vector position_;

double height_;

double thickness_;

Color barkTint_;

Color leafTint_;

};

它包含了很多数据，特别是多边形网格和贴图信息。这些数据太大了，以至于无法在一帧里面全部丢到GPU里面去渲染。幸运的是，老前辈们已经帮我们想到了解决的方案。

最关键的问题在于，虽然有几千棵树，但是他们大部分看起来是一样的。他们可是使用相同的多边形网格信息和相同的纹理来渲染。这样一来，所有的树可以共享相同的实例来进行渲染。

先来看看之前的对象结构

第一版森林结构图

我们可以把上面的类一分为二，提取出共有的属性到一个独立的类

class TreeModel
{
private:
    Mesh mesh_;
    Texture bark_;
    Texture leaves_;
};

class TreeModel

{

private:

Mesh mesh_;

Texture bark_;

Texture leaves_;

};

游戏中只需要包含一个TreeModel对象的实例，没理由在内存中保存相同的多边形和纹理几千次吧。所有的Tree的实例都可以引用这个TreeModel实例。

class Tree
{
private:
    TreeModel* model_;
    Vector position_;
    double height_;
    double thickness_;
    Color barkTint_;
    Color leafTint_;
};

class Tree

{

private:

TreeModel* model_;

Vector position_;

double height_;

double thickness_;

Color barkTint_;

Color leafTint_;

};

现在的对象结构看起来就像这样

第二版森林结构图

虽然这个结构看起来好了很多，我们大大减小了内存的开销。但这么做并没有给渲染带来什么好处，我们需要让GPU理解我们的共享资源，才能提高渲染速度。

数以千计的对象

为了减少GPU渲染的次数，我们需要只把TreeModel发送给GPU一次。然后，分别发送每棵树的其他信息（位置、颜色、大小）。最后，我们告诉GPU，“用那一个TreeModel的数据去渲染每一棵树”。

幸运的是，现在的显卡真的提供了这样的API支持。实现的细节超过了本书的范围，但是Direct3D和OpenGL都支持实例化绘制（Instanced Rendering）。

这两个API，都需要程序员提供两组数据，一组是共用的多边形/纹理等信息，用来告诉GPU绘制什么；另一组是位置、大小等的信息列表，用来告诉GPU在哪里以及如何绘制第一组数据。最后，只要调用一次绘制，整片森林就轻松带微笑地出现了。

Flyweight模式小结

现在大家已经看到了一个Flyweight应用的具体例子。这个例子简单到令人发指，也许有人会说，这根本就不是什么设计模式嘛，只是共享一个对象。没错，上面的例子，确实只共享了一个对象，那是因为这个例子足够简单、清晰、易懂。但是实际生产环境，想找到这样的例子，或许有些困难。后面会介绍稍微复杂的例子，还请大家稍安勿躁。

Flyweight解决的问题是，有太多的对象，却只有太少的内存。核心思想是，拆分对象，分解成共有的属性和特有的属性，把共有的属性独立成类的实例，让每个对象去共享这些实例。

复杂的例子：森林扎根的地方（地面）

地面将使用瓦片地图（tile-based）的方式来实现，有很多种类型的瓦片，例如：草地、土地、山、河、湖等等。

每个瓦片包含了以下的属性

移动代价，决定角色从这块瓦片上经过的移动速度
标记瓦片是否是水，决定这里是走人还是走船
渲染使用的纹理

游戏程序员特别在乎执行效率，所以他们认为没有必要把每一个瓦片的所有信息都放到内存里面，一般会用枚举来实现

enum Terrain
{
    TERRAIN_GRASS,
    TERRAIN_HILL,
    TERRAIN_RIVER
    // Other terrains...
};

enum Terrain

{

TERRAIN_GRASS,

TERRAIN_HILL,

TERRAIN_RIVER

// Other terrains...

};

世界地图的平面将由一个二维数组来组织

class World
{
private:
    Terrain tiles_[WIDTH][HEIGHT];
};

class World

{

private:

Terrain tiles_[WIDTH][HEIGHT];

};

实际使用瓦片的时候的代码是这样的

int World::getMovementCost(int x, int y)
{
    switch (tiles_[x][y])
    {
        case TERRAIN_GRASS: return 1;
        case TERRAIN_HILL:  return 3;
        case TERRAIN_RIVER: return 2;
        // 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...
    }
}

int World::getMovementCost(int x, int y)

{

switch (tiles_[x][y])

{

case TERRAIN_GRASS: return 1;

case TERRAIN_HILL: return 3;

case TERRAIN_RIVER: return 2;

// 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...

}

很显然，这样写可以运行的很好，但是却是很恶心的代码。移动代价（MovementCost）、是否是水（isWater），这些都应该属于是瓦片的数据，却被硬编码在了函数里面。应该把这些属性合并成一个瓦片类（Terrain），这不就是类（objects）设计的意义么？

class Terrain
{
public:
    Terrain(int movementCost,
            bool isWater,
            Texture texture)
    : movementCost_(movementCost),
      isWater_(isWater),
      texture_(texture)
    {}
    int getMovementCost() const { return movementCost_; }
    bool isWater() const { return isWater_; }
    const Texture& getTexture() const { return texture_; }
private:
    int movementCost_;
    bool isWater_;
    Texture texture_;
};

class Terrain

{

public:

Terrain(int movementCost,

bool isWater,

Texture texture)

: movementCost_(movementCost),

isWater_(isWater),

texture_(texture)

{}

int getMovementCost() const { return movementCost_; }

bool isWater() const { return isWater_; }

const Texture& getTexture() const { return texture_; }

private:

int movementCost_;

bool isWater_;

Texture texture_;

};

地图上需要成百上千的瓦片（Terrain），但我们并不希望创建这么多的实例。你应该察觉到了，上面的类，没有包含位置信息，这也是唯一的，每个瓦片（Terrain）不同的数据。所以整个瓦片（Terrain）都是上下文无关的，可以当做共有属性来使用。

因此，我们只需要保存每一种类型的瓦片（Terrain）一个实例就可以了。

class World
{
private:
    Terrain* tiles_[WIDTH][HEIGHT];
    // Other stuff...
};

class World

{

private:

Terrain* tiles_[WIDTH][HEIGHT];

// Other stuff...

};

数组中所有相同类型的Terrain指针，都将指向同一个实例。

Terrain指针示意图

当这么多Terrain的指针指向相同的实例时，如果动态创建Terrain对象的话，它们的生存周期就变得难以管理。简单的处理方法是，把它们放到World类里面

class World
{
public:
    World()
    : grassTerrain_(1, false, GRASS_TEXTURE),
      hillTerrain_(3, false, HILL_TEXTURE),
      riverTerrain_(2, true, RIVER_TEXTURE)
    {}
private:
    Terrain grassTerrain_;
    Terrain hillTerrain_;
    Terrain riverTerrain_;
    // Other stuff...
};

class World

{

public:

World()

: grassTerrain_(1, false, GRASS_TEXTURE),

hillTerrain_(3, false, HILL_TEXTURE),

riverTerrain_(2, true, RIVER_TEXTURE)

{}

private:

Terrain grassTerrain_;

Terrain hillTerrain_;

Terrain riverTerrain_;

// Other stuff...

};

绘制的代码是这样的

void World::generateTerrain()
{
    // Fill the ground with grass.
    for (int x = 0; x &lt; WIDTH; x++)
    {
        for (int y = 0; y &lt; HEIGHT; y++)
        {
            // Sprinkle some hills.
            if (random(10) == 0)
            {
                tiles_[x][y] = &hillTerrain_;
            }
            else
            {
                tiles_[x][y] = &grassTerrain_;
            }
        }
    }
    // Lay a river.
    int x = random(WIDTH);
    for (int y = 0; y &lt; HEIGHT; y++) {
        tiles_[x][y] = &riverTerrain_;
    }
}

void World::generateTerrain()

{

// Fill the ground with grass.

for (int x = 0; x < WIDTH; x++)

{

for (int y = 0; y < HEIGHT; y++)

{

// Sprinkle some hills.

if (random(10) == 0)

{

tiles_[x][y] = &hillTerrain_;

}

else

{

tiles_[x][y] = &grassTerrain_;

}

// Lay a river.

int x = random(WIDTH);

for (int y = 0; y < HEIGHT; y++) {

tiles_[x][y] = &riverTerrain_;

}

为了不让外部直接访问World的Terrain实例，我们还需要提供一个方法

const Terrain& World::getTile(int x, int y) const
{
    return *tiles_[x][y];
}

const Terrain& World::getTile(int x, int y) const

{

return *tiles_[x][y];

}

这样一来，World就不需要知道Terrain的细节，如果你需要得到一个Terrain的属性，可以这么做

int cost = world.getTile(2, 3).getMovementCost();

1	int cost = world.getTile(2, 3).getMovementCost();

这么做，我们就可以简单调用对象的API来获得它的属性。从枚举改写为类，几乎没有什么代价，毕竟指针比枚举大不了多少。

性能问题

有些人可能会关心，从枚举到指针的转变，会带来多大的性能损耗。答案是，几乎没有损耗，可能还有性能提升。

想知道详情的话，建议阅读原文。我只想做一个简单的总结，作者有句话说的非常好：优化性能的黄金法则，就是先做性能测试。没有任何测试，光靠自己想象，是很难模拟真实情况的。因为现代硬件上的优化，已经大大超乎普通人类的想象了。要在脑子里还原程序在硬件上运行的情况，几乎是不可能的事情。游戏的性能问题，也很可能不再是某个单一原因引起的。

作者实测的结果是，使用Flyweight修改后的代码，要比之前用枚举写的，跑得更快，但这取决于其他数据在内存中的结构。

在这里也给各位同学提个醒，千万别看到某段代码，就轻易下结论说，“这里肯定有性能问题”或者“这么写性能肯定没问题”，实践才是检验真理的唯一标准。

GPP读书笔记之Command模式（一）

2014-08-15 by jennal·0 Comment

最近在读一本开源的书《Game Programming Patterns》，关于游戏设计模式的，作者叫Bob Nystrom，在EA工作了好多年，整理了他8年来的经验，写成了这本书，最近会出版实体书。作者的文风非常风趣幽默，以至于我一开始读就有点停不下来了，所以打算写一系列读书笔记来表示对作者的敬意。

前面两个章节主要是用来鼓吹这本书有多么多么好（这是作者自己说的），不过还是读到了不少内容，关于程序设计的理解，为什么要做好的设计，代码写出来能运行不就好了吗？这可能是大多数外行人的看法，也许也是码农的看法，但是作为工程师来说，我们要设计结构良好的代码，为的是将来更容易升级和维护。可能开发出一个功能只需要2天时间，但将来可能需要花好几个月来升级和维护这个功能。并且在升级和维护的过程中是非常难去改变原有的设计的，除非全部推倒重写。这对于有多次推倒重写经验的我来说，真是说到心眼里去了。如果你花两天时间写了一坨屎，接下来，你将在粪坑里挣扎几个月。所以，请善待将来的自己，使用良好的设计模式和规范来进行开发。

进入正题之前，再扯点蛋，作者无数次提到GoF，是Gang of Four的缩写，四人帮？当然不是中国的四人帮。他们是联合撰写了《Design Patterns》这本书的人。

Command 模式是什么

GoF 是这么说的

Encapsulate a request as an object, thereby letting users parameterize clients with different requests, queue or log requests, and support undoable operations.

我的翻译：

把一个请求封装成一个实体，进而让用户可以使用不同的参数来构造不同的请求，把这些请求队列化，或者记录到日志里，甚至支持重做。

作者认为这句话毛病太多了，一方面是client存在歧义，另一方面列举了一堆Command模式能做的事情，但是无法涵盖所有的事情，所以读者如果想做的不在里面，就很可能失去兴趣。所以作者自己总结了一句更简练的话：

A command is a reified method call.

我的翻译：

Command是被实体化的函数调用。

Command模式很容易让人联想到

回调
第一类函数
函数指针
闭包
partially applied function（因为我不知道这个是什么，就不翻译了）

所以GoF后来还说

Commands are an object-oriented replacement for callbacks.

我的翻译：

Command是回调函数的面向对象实现。

代码时间

我简化了一下原文的例子，四个按钮有点多余，两个按钮就能说明问题啦，让我们想象超级玛丽的玩家操作处理代码（不考虑长按B加速的情况，这里只讨论点击操作）。

void InputHandler::handleInput()
{
  if (isPressed(BUTTON_A)) jump();
  else if (isPressed(BUTTON_B)) fire();
}

void InputHandler::handleInput()

{

if (isPressed(BUTTON_A)) jump();

else if (isPressed(BUTTON_B)) fire();

}

这段代码运行在游戏主循环中，已经可以满足一般游戏的需求。

可以配置的控制方式

但是这个时候策划说，让我们支持让玩家自己设置按键吧。作为开发，你一定会抓狂。不怕不怕，这种情况就是Command模式派上用场的时候了。

先定义一个基类

class Command
{
public:
  virtual ~Command() {}
  virtual void execute() = 0;
};

class Command

{

public:

virtual ~Command() {}

virtual void execute() = 0;

};

然后是子类

class JumpCommand : public Command
{
public:
  virtual void execute() { jump(); }
};
class FireCommand : public Command
{
public:
  virtual void execute() { fireGun(); }
};

class JumpCommand : public Command

{

public:

virtual void execute() { jump(); }

};

class FireCommand : public Command

{

public:

virtual void execute() { fireGun(); }

};

InputHandler也做一些修改

class InputHandler
{
public:
  void handleInput();
  // Methods to bind commands...
private:
  Command* buttonA_;
  Command* buttonB_;
};

class InputHandler

{

public:

void handleInput();

// Methods to bind commands...

private:

Command* buttonA_;

Command* buttonB_;

};

最后刚刚的处理代码变成了这样

void InputHandler::handleInput()
{
  if (isPressed(BUTTON_A)) buttonA_->execute();
  else if (isPressed(BUTTON_B)) buttonB_->execute();
}

void InputHandler::handleInput()

{

if (isPressed(BUTTON_A)) buttonA_->execute();

else if (isPressed(BUTTON_B)) buttonB_->execute();

}

角色引导

原文的标题是Directions for Actors，为什么把Directions翻译成引导，以我的理解，本章节的主要内容是，把jump函数从JumpCommand中取出来，Command不直接调用指定的函数，而是调用角色的成员函数，这样做的好处很明显，可以换角色操作了。所以功能引导从Command转换为角色。

在execute函数加入参数

class Command
{
public:
  virtual ~Command() {}
  virtual void execute(GameActor& actor) = 0;
};

class Command

{

public:

virtual ~Command() {}

virtual void execute(GameActor& actor) = 0;

};

所以JumpCommand就变成了这样

class JumpCommand : public Command
{
public:
  virtual void execute(GameActor& actor)
  {
    actor.jump();
  }
};

class JumpCommand : public Command

{

public:

virtual void execute(GameActor& actor)

{

actor.jump();

}

};

handleInput明显也不满足需求了，让它不再直接执行Command，而是返回Command

Command* InputHandler::handleInput()
{
  if (isPressed(BUTTON_A)) return buttonA_;
  if (isPressed(BUTTON_B)) return buttonB_;
  // Nothing pressed, so do nothing.
  return NULL;
}

Command* InputHandler::handleInput()

{

if (isPressed(BUTTON_A)) return buttonA_;

if (isPressed(BUTTON_B)) return buttonB_;

// Nothing pressed, so do nothing.

return NULL;

}

因为InputHandler明显不知道现在游戏中选择的是什么角色，所以这个时候把Command先返回出来，以供外部调用，这也是一种延迟调用。所以，我们得再来看看知道现在游戏中选择的是什么角色的某处代码，是怎么使用InputHandler的

Command* command = inputHandler.handleInput();
if (command)
{
  command->execute(actor);
}

Command* command = inputHandler.handleInput();

if (command)

{

command->execute(actor);

}

不知道大家有没有发现？这么做了以后，不仅仅是可以换角色了，角色的控制者也可以替换。不仅仅支持玩家通过按键输入来控制角色，还可以利用AI来控制角色。甚至可以使用不同的AI算法来控制不同的角色。还可以用来在某些情况下，使用AI自动控制玩家的角色，比如自动寻路，自动战斗。

下面不得不用一张图来加强理解

把Command放到队列/流中

如果把Command放到队列/流中，就像上图中间的部分，这样就有效地解耦了生产者（AI/玩家输入）和消费者（角色）。

撤销/重做

这是最后一个例子，也是Command模式最知名的应用场景。
如果一个Command对象可以做某件事，那是不是也可以让它撤销呢？撤销操作常用在策略类游戏，工具类应用程序会有更多这类需求，包括自己研发的游戏编辑器，如果你做了一个不能撤销的编辑器给策划用，策划会恨你的。

如果不用Command模式，你想实现撤销操作，会意外地发现那是多么困难的一件事。但是用Command模式来实现的话，就超级简单了。
下面让我们来实现一个回合制的策略类游戏，玩家可以移动自己的单位，也可以撤销移动。

下面是移动操作的代码

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_, y_;
};

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_, y_;

};

细心的你一定发现了这个类跟之前的不同，之前的角色是从execute传进来的，这个MoveUnitCommand是从构造函数传进来的。这是因为我们后续要做撤销操作，所以肯定要知道要对谁做撤销。这个例子也告诉我们，带参数的Command类，该怎么写。
延续之前的功能，MoveUnitCommand被实例化以后，可以在某一个特定时间点被调用，所以handleInput将这么被改写

Command* handleInput()
{
  // Get the selected unit...
  Unit* unit = getSelectedUnit();
  if (isPressed(BUTTON_UP)) {
    // Move the unit up one.
    int destY = unit->y() - 1;
    return new MoveUnitCommand(unit, unit->x(), destY);
  }
  if (isPressed(BUTTON_DOWN)) {
    // Move the unit down one.
    int destY = unit->y() + 1;
    return new MoveUnitCommand(unit, unit->x(), destY);
  }
  // Other moves...
  return NULL;
}

Command* handleInput()

{

// Get the selected unit...

Unit* unit = getSelectedUnit();

if (isPressed(BUTTON_UP)) {

// Move the unit up one.

int destY = unit->y() - 1;

return new MoveUnitCommand(unit, unit->x(), destY);

}

if (isPressed(BUTTON_DOWN)) {

// Move the unit down one.

int destY = unit->y() + 1;

return new MoveUnitCommand(unit, unit->x(), destY);

}

// Other moves...

return NULL;

}

可是这么做还是不能撤销啊，别着急，下面告诉你怎么撤销，首先要改写Command基类

class Command
{
public:
  virtual ~Command() {}
  virtual void execute() = 0;
  virtual void undo() = 0;
};

class Command

{

public:

virtual ~Command() {}

virtual void execute() = 0;

virtual void undo() = 0;

};

undo就是execute的反操作，用来撤销execute操作的，那么重做就是重新调用一次execute。
加上undo实现以后的MoveUnitCommand

class MoveUnitCommand : public Command
{
public:
  MoveUnitCommand(Unit* unit, int x, int y)
  : unit_(unit),
    xBefore_(0),
    yBefore_(0),
    x_(x),
    y_(y)
  {}
  virtual void execute()
  {
    // Remember the unit's position before the move
    // so we can restore it.
    xBefore_ = unit_->x();
    yBefore_ = unit_->y();
    unit_->moveTo(x_, y_);
  }
  virtual void undo()
  {
    unit_->moveTo(xBefore_, yBefore_);
  }
private:
  Unit* unit_;
  int xBefore_, yBefore_;
  int x_, y_;
};

class MoveUnitCommand : public Command

{

public:

MoveUnitCommand(Unit* unit, int x, int y)

: unit_(unit),

xBefore_(0),

yBefore_(0),

x_(x),

y_(y)

{}

virtual void execute()

{

// Remember the unit's position before the move

// so we can restore it.

xBefore_ = unit_->x();

yBefore_ = unit_->y();

unit_->moveTo(x_, y_);

}

virtual void undo()

{

unit_->moveTo(xBefore_, yBefore_);

}

private:

Unit* unit_;

int xBefore_, yBefore_;

int x_, y_;

};

可以看到代码中多了两个变量xBefore_, yBefore_，来保存MoveUnitCommand执行之前的状态（位置）。所以撤销操作，就是移动回之前的位置。当然，在外部要控制玩家的操作，执行完execute，就只能撤销，撤销完，就只能重做，以免产生不必要的误解。
读到这里，对于多个Command的撤销和重做，应该也已经有一些想法了吧。

多个Command的撤销/重做

这里只给出一张图，不做详细解释了。原文还有一段解释，但我觉得上图已经足够说明一切了。

最后，恭喜你，读完了。

Jennal's Blog

Jennal的技术博客

Tag: gpp-review

GPP读书笔记之Flyweight模式（二）

Flyweight模式是什么

简单的例子：森林中的树

数以千计的对象

Flyweight模式小结

复杂的例子：森林扎根的地方（地面）

性能问题

GPP读书笔记之Command模式（一）

Command 模式是什么

代码时间

可以配置的控制方式

角色引导

撤销/重做