首页 > 代码库 > COCOS2D-X 3.0新的数据结构

COCOS2D-X 3.0新的数据结构

2024-07-26 23:17:55   220人阅读





基础数据结构在游戏开发中至关重要，可能每一帧某个逻辑需要从一个数组中查找，删除，添加数据，或者从一个字典中快速存/取一个值，游戏引擎本身也要对UI树进行遍历，排序等操作。基础数据的操作速度影响着程序的性能，而基础数据的使用方法则影响着开发效率。当然我们应该尽量避免游戏中每一帧频繁的迭代和查找计算，应尽可能地将结果缓存起来。


C++标准库已经提供了数组(std::vector)，字典(std::map)等比较优秀的基础数据结构，然而它们不支持Cocos2d-x的内存管理方式(关于Cocos2d-x内存管理，参见第三章)。在Cocos2d-x 2.x及之前的版本中，Cocos2d-x提供CCArray和CCDictionary来结合Cocos2d-x的内存管理方式一起工作，但是它们却不能很好地支持标准库中的迭代器操作，这在一定程序上影响着开发效率。


Cocos2d-x 3.0用Vector和Map<K, V>代替了之前的CCArray和CCDictionary，新的容器类使用模板类来避免了不必要的数据类型转换，同时能够完美地支持标准库中的各种迭代操作，例如std::find()，std::sort()等等。实际上，在3.0中Vector和Map<K,T>是对标准库中std::vector和std::unordered_map<K,T>的封装，使其能够结合Cocos2d-x的内存管理方式。我们可以从以下三个方面来理解新的数据结构的特点。


1.2.6.1 Map<K,V>的性能


对于Map<T,V>，Cocos2d-x默认使用std::unordered_map，std::unordered_map将每个key值转化为hash值存储，并按照hash值排序，所以它不是实际的字典中Key或者Value值的存储顺序。unordered_map对于单个Key值的查找有更快的速度，它只需要将Key转化为hash值，然后做一次或者多次相等比较，其复杂度为O(n)，而std::map的find复杂度为O(log2(n))，它在每个元素之间使用小于比较。


std::unordered_map初始化的时候分配一定数量(通常很少)的buckets来存储Key/Value对，每个bucket对应一个hash值。hash值是基于buckets的数量来计算的，所以当新增元素的时候，一个bucket可能就会对应多个hash值，造成冲突，std::unordered_map就需要重新计算所有hash值(rehash)，这会造成一定的性能问题。所以如果你需要在短时间内插入一定数量的数据，最好使用resverve方法来设定buckets的数量，减少不必要的rehash计算。当然如果只是偶尔插入或者删除数据，则不必这么做，因为resverve会增加unordered_map的内存占用。


另一个需要注意的地方是std::hash的计算，std::unordered_map使用特殊的hash算法，当其类型为整数时，直接将其自身作为hash值，这减少hash值的计算量。所以，游戏中应尽量使用整型作为 Map<K,V>的Key值类型，这会大大提升Map<K,V>的性能，参见引用4和5。


1.2.6.2 与Cocos2d-x内存管理的结合


在2.x的使用场景中，CCArray和CCDictionary通常被分配在堆上，我们不得不需要考虑在适当的地方释放其内存。新的容器类不再继承自Ref(2.x中的CCObject)，新的容器类通常应该被分配在栈上来使用，这简化了内存管理，我们应该将精力放在容器元素而不是容器本身的内存管理上。


Vector中的T和Map<K,V>中的V必须是Ref类型，因为它们需要结合Cocos2d-x的内存管理方式一起工作。这简化了容器中元素的内存管理，这主要体现在两个方面。


以任何形式新加入到容器中的左值都会执行retain()方法使引用计数+1，以Vector为例，比如拷贝构造函数，赋值操作符，pushBack，replace，insert：




class MyClass : public Ref
{};


void testVector()
{
auto c1= new MyClass();
c1->autorelease();
auto c2=new MyClass();
c2->autorelease();


CCLOG(“reference count c1:%d & c2:%d”,c1->getReferenceCount(),c2->getReferenceCount());


Vector<MyClass*> v1;
v1.pushBack(c1);
v1.insert(1, c2);
CCLOG(“reference count c1:%d & c2:%d”,c1->getReferenceCount(),c2->getReferenceCount());


v1.popBack();
CCLOG(“reference count c1:%d & c2:%d”,c1->getReferenceCount(),c2->getReferenceCount());


Vector<MyClass*> v2=Vector<MyClass*>(v1);
CCLOG(“reference count c1:%d & c2:%d”,c1->getReferenceCount(),c2->getReferenceCount());


Vector<MyClass*> v3=v1;
CCLOG(“reference count c1:%d & c2:%d”,c1->getReferenceCount(),c2->getReferenceCount());
}


其输出为：


cocos2d: reference count c1:1 & c2:1
cocos2d: reference count c1:2 & c2:2
cocos2d: reference count c1:2 & c2:1
cocos2d: reference count c1:3 & c2:1
cocos2d: reference count c1:4 & c2:1


以任何形式从容器中移除的左值都会被执行release()方法使引用计数-1。比如析构函数，erase，popBack，replace，clear，这里读者自行测试，不再举例。


以上这些操作，在同一语句中都能明确计算其对元素引用计数的影响，这样可以很好的根据Cocos2d-x的内存管理规则对容器中的元素进行自动内存管理。但是下标操作符[]却返回一个左值T&，在同一语句中对容器元素造成的影响是不可估计的，例如语句：


v3[0]->release();


将会影响容器中元素的内存管理，所以Cocos2d-x的容器没有提供下标操作符，而我们应该用at方法来返回一个右值：


template
class CC_DLL Vector
{
public:
/** Returns the element at position ‘index’ in the vector. */
T at(ssize_t index) const
{
CCASSERT( index >= 0 && index < size(), “index out of range in getObjectAtIndex()”);
return _data[index];
}
};


1.2.6.3 移动语义


最后，新的容器类对于右值使用了C++11新的移动(move，见引用6，7)语义，它们实现了移动拷贝函数和移动赋值操作符，这样在使用右值时减少了一些不必要临时变量的生成和拷贝：


template
class CC_DLL Vector
{
public:
/** Move constructor */
Vector(Vector&& other)
{
static_assert(std::is_convertible<T, Ref*>::value, “Invalid Type for cocos2d::Vector!”);
CCLOGINFO(“In the move constructor of Vector!”);
_data = http://www.mamicode.com/std::move(other._data);
}


/** Move assignment operator */
Vector& operator=(Vector&& other)
{
if (this != &other) {
CCLOGINFO(“In the move assignment operator!”);
clear();
_data = http://www.mamicode.com/std::move(other._data);
}
return *this;
}
};


例如如下的使用：


Vector<MyClass*> getVector()
{
auto c1= new MyClass();
c1->autorelease();
auto c2=new MyClass();
c2->autorelease();


Vector<MyClass*> v1;
v1.pushBack(c1);
v1.insert(0, c2);


CCLOG(“reference count c1:%d & c2:%d”,c1->getReferenceCount(),c2->getReferenceCount());


return v1;
}


void testVectorMove()
{
Vector<MyClass*> v2=Vector<MyClass*>(getVector());
CCLOG(“reference count c1:%d & c2:%d”,v2.at(1)->getReferenceCount(),v2.at(0)->getReferenceCount());


Vector<MyClass*> v3=getVector();
CCLOG(“reference count c1:%d & c2:%d”,v3.at(1)->getReferenceCount(),v3.at(0)->getReferenceCount());
}


其输出为：


cocos2d: reference count c1:2 & c2:2
cocos2d: reference count c1:2 & c2:2
cocos2d: reference count c1:2 & c2:2
cocos2d: reference count c1:2 & c2:2


可见，上述的例子分别使用了移动拷贝函数和移动赋值操作符，这就减少了不必要的临时变量的生成了销毁。




COCOS2D-X的主线程


游戏开发中，对游戏对象模型设计并行系统往往是很困难的。一方面，游戏对象之间会存在大量的相互依赖，游戏对象也可能和多个引擎子系统所产生的数据相互依赖。另一方面，游戏对象会与其他游戏对象交流，有时候在更新循环中会多次交流，而交流的模式是不可预期且受玩家输入影响的。这使得游戏对象在多线程中更新变得困难。




虽然，理论上可以设计一些架构来支持并行更新游戏对象。但是从开发者的易用性等角度，大多数游戏引擎仍然是以单线程为主。但是在更底层的引擎子系统中，可以做到部分并行化，使其可以不影响上层的游戏对象模型，例如目前很多游戏引擎都将绘制从游戏引擎分离，使之可以在不同线程绘制。


Cocos2d-x目前仍然是一个单线程的游戏引擎，这使得我们几乎不需要考虑游戏对象更新的线程安全性。然而我们仍然需要关注一些情形如网络请求，异步加载文件，或者异步处理一些逻辑算法等等。


3.6.1 在主线程执行异步处理结果


有一些方法必须在主线程执行，例如GL相关的方法。另一些时候，为了保证如Ref对象引用计数的线程安全，我们也应该在主线程去执行这些操作。Scheduler提供了一种简单的机制，使可以在主线程上执行一个方法：


void Scheduler::performFunctionInCocosThread(const std::function &function)
{
_performMutex.lock();
_functionsToPerform.push_back(function);
_performMutex.unlock();
}


首先向Scheduler注册一个方法指针，Scheduler存储一个需要在主线程执行的方法指针的数组，在当前帧所有系统或者自定义的schedule执行完之后，Scheduler就会检查该数组并执行其中的方法：


void Scheduler::update(float dt)
{
if( !_functionsToPerform.empty() ) {
_performMutex.lock();
// fixed #4123: Save the callback functions, they must be invoked after ‘_performMutex.unlock()’, otherwise if new functions are added in callback, it will cause thread deadlock.
auto temp = _functionsToPerform;
_functionsToPerform.clear();
_performMutex.unlock();
for( const auto &function : temp ) {
function();
}
}
}


通过这样的机制，我们就可以将一个方法转移到主线程执行。这里需要注意的是这些方法在主线程被执行的时机是所有系统或自定义的schedule之后，也即在UI树遍历之前。


3.6.2 文件异步加载完成


在上面的机制中，所有向Scheduler注册的方法都会在该帧结束的时候被全部执行，如果对于一些简单的算法，这没什么问题，如图左边的function列表。但是对于一些比较耗时的计算，为了不影响游戏的性能，我们需要把一系列耗时的方法分布在每一帧去执行。


Cocos2d-x纹理的异步加载完成之后，需要将纹理上传至GL内存中，因此这个传输的过程必须要在主线程执行。但是上传纹理的glTexImage2D命令是一个耗时的操作，试想如果有多个图片同时完成加载，这些纹理要在同一帧上传至GL内存中，这可能会使UI界面出现卡顿的现象，造成不好的用户体验。


因此，Cocos2d-x的纹理异步加载回调使用了一个自定义的schedule来处理，在该schedule内部，检查已经完成加载的纹理，每一帧处理一个纹理，直至所有纹理被处理完毕，则注销schedule。最后纹理在主线程执行的情况图右边的file列表：


 一帧执行与跨帧执行


TextureCache向Scheduler注册一个更新回调addImageAsyncCallBack：


void TextureCache::addImageAsyncCallBack(float dt)
{
// the image is generated in loading thread
std::deque<ImageInfo*> *imagesQueue = _imageInfoQueue;


_imageInfoMutex.lock();
if (imagesQueue->empty())
{
_imageInfoMutex.unlock();
}
else
{
ImageInfo *imageInfo = imagesQueue->front();
imagesQueue->pop_front();
_imageInfoMutex.unlock();


AsyncStruct *asyncStruct = imageInfo->asyncStruct;
Image *image = imageInfo->image;


const std::string& filename = asyncStruct->filename;


Texture2D *texture = nullptr;
if (image)
{
// generate texture in render thread
texture = new Texture2D();


texture->initWithImage(image);


#if CC_ENABLE_CACHE_TEXTURE_DATA
// cache the texture file name
VolatileTextureMgr::addImageTexture(texture, filename);
#endif
// cache the texture. retain it, since it is added in the map
_textures.insert( std::make_pair(filename, texture) );
texture->retain();


texture->autorelease();
}
else
{
auto it = _textures.find(asyncStruct->filename);
if(it != _textures.end())
texture = it->second;
}


asyncStruct->callback(texture);
if(image)
{
image->release();
}
delete asyncStruct;
delete imageInfo;


–_asyncRefCount;
if (0 == _asyncRefCount)
{
Director::getInstance()->getScheduler()->unschedule(schedule_selector(TextureCache::addImageAsyncCallBack), this);
}
}
}


在向TextureCache发起一个异步文件加载请求时，TextureCache会向Scheduler注册一个更新回调addImageAsyncCallback，然后开启一个新的线程异步加载文件。在新的线程中文件加载完毕时，将其纹理数据存储在_imageInfoQueue中，主线程每帧被更新回调时检查其是否有数据，如果有则将其纹理数据缓存到TextureCache中，并上传纹理至GL内存，然后删除_imageInfoQueue中的数据。最后，当所有文件都加载完毕，则注销更新回调。


3.6.3 异步处理的单元测试


在主线程上执行所有逻辑算法，使程序复杂度大大降低，并且可以比较自由地在某些方面使用多线程。然而，Cocos2d-x这种回调机制也使得单元测试变得困难，因为它依赖于Cocos2d-x的主循环。


单元测试通常用来测试一个同步的方法，只要执行一下该方法，就知道其运行结果，单元测试甚至可以不依赖于太多的上下文，实际上太多的上下文使单元测试变得困难。


对于异步方法，人们通过给单元测试加入一个“等待时间”，来监听回调函数对某个布尔变量值的修改，并告知回调完成，从而完成其单元测试方法。通过这样的访问就可以测试异步方法。


然后，Cocos2d-x中的异步回调需要游戏循环来驱动，单元测试除了监听异步回调，还需要驱动游戏循环才能执行Schedule，这使得单元测试变得困难。在本书最后一章，我们将给出一种解决方案，使其能够测试Cocos2d-x中的“异步回调”。

COCOS2D-X 3.0新的数据结构


联系
我们