Извините, ничего не найдено.

02.05.2012, 18:59

Строки в геймдеве довольно больная тема, некоторые люди используют их как будто это обычный прикладной софт, другие стараются оптимизировать выполнение, третьи никаких сил не прилагают и плывут по течению.

Давайте разберёмся в чём отличительная черта использования строк (текста в целом) в геймдеве ? Назову несколько предположений (теорий подтверждённых на практике).

1) Строки нужны только для интерфейса и общения с другими модулями (сервером, библиотеками и тд), строки не нужны для имен файлов, имен ресурсов, как имен игровых объектов
почему так ? Потому что любое имя файла, ресурса, объекта и тд можно представить в виде цифрового индекса, например просто занеся имена в табличку и записать вместо имени индекс.
Такой подход вполне работает в data-driven дизайне, игра состоит из движка, ресурсов и скриптов, мы эти ресурсы и скрипты "готовим" простой заменой текстовых идентификаторов на цифровые, а потом только уже отдаём их движку.
В code-driven подходе (большинство инди движков, даже блиц3д) такой подход вводится более болезненно, но вполне реально, например вместо :

Model * model = new Model("test.3ds");

пишем

#define MODEL_TEST 1
Model * model = new Model(MODEL_TEST);

2) Исходя из первого пункта можно вывести аксиому : мы всегда знаем размер нужных нам строк. И действительно, можно ввести искусственные ограничения на размер имени игрока, на текст новостей из интернета, на имя уровня, на что угодно.

Так, теперь у нас остались строки в интерфейсе и общении с другими системами. Давайте рассмотрим архитектурный подход std::string.
std::string находится в STL и является наиболее доступным для программиста C++ контейнером строк, отличительной чертой контейнеров в целом является принцип contain - они сами содержат данные которыми оперируют, те если рассматривать их со стороны модели MVC то это модель и отображение в одном лице, хотя часть контролёров выносится наружу (итераторы снаружи, всякие вставки-удаления в этом же классе).
То что std::string является контейнером очень удобно для прикладного программного обеспечения, мы можем передавать\получать строку и всегда будем иметь возможность оперировать ей как хотим, за это мы расплачиваемся постоянными аллокациями и долгим копированием, к примеру, без применения некоторых техник внутри контейнеров, следующий код довольно медленный :

std::string foo()
{
	return "abc";
}

И действительно, в данном случае нужно будет выделить кусок памяти, скопировать туда строку и тд.

Как это всё можно сделать куда вкуснее (и быстрее) ? Для этого нужно разложить по полочкам каждую архитектурную и идеологическую составляющую std::string (как и прочего подобного контейнера строк).

Начнём с того что контейнер по-сути является владельцем данных которых он хранит, из-за этого получается что когда вы хотите скопировать данные то получаете новый контейнер. Давайте подумаем какие могут быть владельцы в принципе :
1) код который сам себе резервирует место в памяти и потом сам его использует
2) код который получает данные извне, и сохраняет их для последующей модификации
3) сам бинарный код, когда вы пишете const char * foo = "123"; то "123" располагается в памяти вашей программы (откройте exe файл и проверьте)

А что же выпало из этого списка ? выпал вариант когда код получает данные, модифицирует их и возвращает результат.

Вы сейчас скажете что это просто передача по-ссылке и её можно так же применять к std::string, да, вы правы, статья называется "готовим вкуснее", а не "становимся вегетарианцами", те, я описываю механизм более простого управления владением строк, а не полной замены догмы.

И так, значит мы пришли к тому что у нас будет контейнер который является владельцем строк и он должен уметь проводить эмиссию строк.
Для простоты добавим еще одну аксиому : нам не нужно освобождать уже выделенные строки из контейнера (выпущенные деньги назад не отбираем), на первый взгляд это глупо, но если подумать это действительно можно обойти (если интересно - расскажу позже).

Представим примерно как будет выглядеть наш владелец строк :

class stringContainer
{
public:
	void Reserve(size_t size); // резервирует пул размером size байт
	void Clear(); // очищает весь пул
	
	string Allocate(size_t size); // аллоцирует строку размером size байт
	string Clone(const string & string); // клонирует строку и возращает клон

	size_t GetPoolSize() const; // размер пула
	size_t GetSize() const; // количество выделенных байт

protected:
	...
};

Теперь подумаем что же является собственно строкой ? Владелец у строки уже есть, и собственно строкой становится только указатель на владельца и смещение в нём (для простоты - вместо смещения используем указатель на саму C строку). Вспомним чуть раньше, владельцем может быть не только наш контейнер, но так же и сам бинарник, для поддержки этого предлагаю ввести два указателя - один для чтения\записи, другой только для чтения, что позволит нам сематически корректно поддерживать передачу и работу со строковыми литералами.

class string
{
public:
	string(const char * stringLiteral = NULL)
		:rawReadOnly(stringLiteral), raw(NULL), owner(NULL), size(0), length(0)
	{
		size = UTF8GetSize(rawReadOnly);
		length = UTF8GetLength(rawReadOnly);
	}

	string(char * stringData, stringContainer * setOwner, size_t setSize, size_t setLength)
		:raw(stringData), rawReadOnly(stringData), owner(setOwner), size(setSize), length(setLength)
	{
	}

	string(const string & other)
		:rawReadOnly(other.rawReadOnly), raw(other.raw), owner(other.owner), size(other.size)
	{
	}

	const char * c_str() const {return rawReadOnly;}

	char * GetRaw() const {return raw;}
	const char * GetRawRO() const {return rawReadOnly;}

	void SetSize(size_t setSize) {size = setSize;}
	size_t GetSize() const {return size;}

	void SetLength(size_t setLength) {length = setLength;}
	size_t GetLength() const {return length;}

	bool IsEqual(const string & other) const
	{
		if(rawReadOnly == other.rawReadOnly)
		{
			assert(owner == other.owner);
			return true;
		}
		else if(rawReadOnly && other.rawReadOnly)
			return !strcmp(rawReadOnly, other.rawReadOnly);
		else if(!(rawReadOnly || other.rawReadOnly))
			return true;
		else
			return false;
	}

	bool operator == (const string & other) const {return IsEqual(other);}
	bool operator != (const string & other) const {return !IsEqual(other);}

protected:
	const char * rawReadOnly; // указатель на read-only строку
	char * raw; // указатель на write-read строку

	stringContainer * owner;
	size_t size; // размер в байтах
	size_t length; // размер в буквах (поддержка utf-8)
};

Получаем что наш класс строки, который мы используем везде где нам нужно, совершенно не содержит данных строки, он стал очень легковесным и посмотрите на этот конструктор копирования ! теперь мы можем довольно быстро обмениваться строками, сохранять их к себе, и становится владельцами когда захотим, плюс обеспечивается поддержка строковых литералов из коробки, что лишает нас кучи проблем и не нужных аллокаций.

Всю малину портит то что нам нужно конструировать и форматировать строки. Привыкшие писать :

std::string a = "1";
std::string b = "2";
std::string c = a + b;

довольно сильно обламываются. Тут мы начинаем немного кусать кактус и вспоминаем что где-то это уже видели, да, такого к примеру не было с C строками это раз, такой функционал предоставляет std::stringstream и прочие. Как можно приготовить этот кактус вкусно ? нам понадобится написать класс который форматирует строку, и пишет результат в буферную строку, для упрощения форматирования воспользуемся sprintf и производными.

class stringConcate
{
public:
	stringConcate()
		:freePosition(0)
	{
	}

	stringConcate(const string & buffer)
		:buf(buffer), freePosition(0)
	{
	}

	void SetBuffer(const string & buffer)
	{
		buf = buffer;
		freePosition = 0;
	}

	stringConcate & Add(const char * formatStr, ...)
	{
		assert((freePosition + 1) < buf.GetSize());
		va_list args;
		va_start(args, formatStr);
		freePosition += vsprintf(buf.GetRaw() + freePosition, formatStr, args);
		va_end(args);
		assert((freePosition + 1) <= buf.GetSize());
		return *this;
	}

	string BakeToString()
	{
		buf.GetRaw()[freePosition++] = '\0';

		string result(buf);
		result.SetSize(freePosition);
		result.SetLength(UTF8GetLength(result.GetRawRO()));
		freePosition = 0;

		return result;
	}

private:
	stringConcate(const stringConcate & other) {}

protected:
	string buf;
	size_t freePosition;
};

Вроде как всё не так уж и плохо ? А позже кажется что даже и хорошо ! код становится более детерминированным, и не делает какой либо скрытой фигни, пример использования :

stringContainer container;
container.Reserve(16);
stringConcate concate(container.Allocate(16));

string a = "1";
string b = "2";
string c = concate.Add("%s%s", a.c_str(), b.c_str()).Add("temp").BakeToString(); // привычное нам C-форматирование

Add можно вызывать сколько хочется раз, а результат потом получать с помощью BakeToString.

У всего этого есть один нюанс, бесплатного сыра не бывает, но бывает магия, пример нюанса :

stringContainer container;
container.Reserve(16);
stringConcate concate(container.Allocate(16));

string a = concate.Add("1").BakeToString();
string b = concate.Add("2").BakeToString();
// вообще вот чисто технически, буфер перезаписан, строка a уже не валидна для чтения, ибо этот код не стал её владельцем

bool c = (a == b); // вернёт true, смотрите в реализацию IsEqual

Если вы внимательно следили, то поймете что это ошибка by-design ! Давайте подумаем как это можно обойти не выкинув при этом всё, скажем первое что бросается на ум - хранить с поинтером хеш строки, вполне разумная идея в общем-то, даже потом можем сравнивать хеши строк при различии указателей, только вот ... одинаковые строки с разными указателями бывают ОЧЕНЬ РЕДКО, конечно синтетические тесты могут быть любыми, но часто ли вы такое видели в реальной игре ? Перед нами стоит проблема того что мы имеем разные строки с одинаковым поинтером.

А теперь магия !

сверх быстрая хеш-функция для нашего случая :

size_t hash(const char * str)
{
	static size_t i = 0;
	assert(i < SIZE_T_MAX);
	return i++;
}

Немного дзена, и мы начинаем понимать всю суть оптимизации. Поскольку 4 млрда хешей на сессию (для 32 бит) это немного самонадеянно (прям как 1 гиг памяти алочить), то давайте сделаем хеш для каждого экземпляра string, это не космические технологии, дзен нам позволяет, и это крутой trade-off скорости на ассерт через 100-200 лет.
Каждый BakeToString мы просто будем увеличивать внутренний хеш буфер-строки, и всё, в итоге суммируя всё представленное выше получаем такую заготовку :

size_t UTF8GetSize(const char * str) { return strlen(str); }
size_t UTF8GetLength(const char * str) { ... }

class stringContainer
{
public:
	void Reserve(size_t size); // резервирует пул размером size байт
	void Clear(); // очищает весь пул
	
	string Allocate(size_t size); // аллоцирует строку размером size байт
	string Clone(const string & string); // клонирует строку и возращает клон

	size_t GetPoolSize() const; // размер пула
	size_t GetSize() const; // количество выделенных байт

protected:
	...
};

class string
{
public:
	string(const char * stringLiteral = NULL)
		:rawReadOnly(stringLiteral), raw(NULL), owner(NULL), size(0), length(0), hash(0)
	{
		size = UTF8GetSize(rawReadOnly);
		length = UTF8GetLength(rawReadOnly);
	}

	string(char * stringData, stringContainer * setOwner, size_t setSize, size_t setLength)
		:raw(stringData), rawReadOnly(stringData), owner(setOwner), size(setSize), length(setLength), hash(0)
	{
	}

	string(const string & other)
		:rawReadOnly(other.rawReadOnly), raw(other.raw), owner(other.owner), size(other.size), hash(other.hash)
	{
	}

	const char * c_str() const {return rawReadOnly;}

	char * GetRaw() const {return raw;}
	const char * GetRawRO() const {return rawReadOnly;}

	void SetSize(size_t setSize) {size = setSize;}
	size_t GetSize() const {return size;}

	void SetLength(size_t setLength) {length = setLength;}
	size_t GetLength() const {return length;}
	
	void PushHash() {++hash;}
	size_t GetHash() const {return hash;}

	bool IsEqual(const string & other) const
	{
		if(rawReadOnly == other.rawReadOnly)
		{
			assert(owner == other.owner);
			return hash == other.hash;
		}
		else if(rawReadOnly && other.rawReadOnly)
			return !strcmp(rawReadOnly, other.rawReadOnly);
		else if(!(rawReadOnly || other.rawReadOnly))
			return true;
		else
			return false;
	}

	bool operator == (const string & other) const {return IsEqual(other);}
	bool operator != (const string & other) const {return !IsEqual(other);}

protected:
	const char * rawReadOnly; // указатель на read-only строку
	char * raw; // указатель на write-read строку, если не 0 то совпадает с rawReadOnly

	stringContainer * owner;
	size_t size; // размер в байтах
	size_t length; // размер в буквах (поддержка utf-8)
	size_t hash; // хеш строки, возможно сравнивать только если указатели совпадают
};

class stringConcate
{
public:
	stringConcate()
		:freePosition(0)
	{
	}

	stringConcate(const string & buffer)
		:buf(buffer), freePosition(0)
	{
	}

	void SetBuffer(const string & buffer)
	{
		buf = buffer;
		freePosition = 0;
	}

	stringConcate & Add(const char * formatStr, ...)
	{
		assert((freePosition + 1) < buf.GetSize());
		va_list args;
		va_start(args, formatStr);
		freePosition += vsprintf(buf.GetRaw() + freePosition, formatStr, args);
		va_end(args);
		assert((freePosition + 1) <= buf.GetSize());
		return *this;
	}

	string BakeToString()
	{
		buf.GetRaw()[freePosition++] = '\0';
		buf.PushHash();

		string result(buf);
		result.SetSize(freePosition);
		result.SetLength(UTF8GetLength(result.GetRawRO()));
		freePosition = 0;

		return result;
	}

private:
	stringConcate(const stringConcate & other) {}

protected:
	string buf;
	size_t freePosition;
};

class foo // класс который принимает строку, сетапит по ней данные, но не владеет строкой
{
public:
	void SetString(const string & newString)
	{
		if(set != newString)
		{
			set = newString;
			SetupData(set);
		}
	}
	
protected:
	string set;
	
	void SetupData(const string & str)
	{
		...
	}
};

void test()
{
	stringContainer container;
	container.Reserve(16);
	stringConcate concate(container.Allocate(16));
	
	foo test;

	string a = concate.Add("1").BakeToString();
	test.SetString(a);
	
	string b = concate.Add("2").BakeToString();
	test.SetString(b); // вызовется SetupData, хотя foo::set уже не валидный

	bool c = (a == b); // вернёт false
}

class foo2 // а этот класс уже владеет строкой
{
public:
	foo2()
	{
		container.Reserve(256);
	}
	
	void Setup(const string & name)
	{
		ownName = container.Clone(name);
	}
	
protected:
	stringContainer container;
	string ownName;
};

void test2()
{
	foo2 a;
	a.Setup("test_test");
}

Вот и всё, резюмируя : мы получили довольно дешевый, быстрый, хорошо управляемый подход в реализации строк, требующий немного сноровки и дзена.

03.05.2012, 02:57

собственно статья вылилась в небольшую библиотеку : YASC - Yet Another String Class, лицензия MIT

https://bitbucket.org/jimon/yasc/wiki/Home
название классов немного отличаются, но принцип такой же, так же есть примеры

Randomize · 03.05.2012, 13:54

Сообщение от jimon

Потому что любое имя файла, ресурса, объекта и тд можно представить в виде цифрового индекса, например просто занеся имена в табличку и записать вместо имени индекс.
Такой подход вполне работает в data-driven дизайне, игра состоит из движка, ресурсов и скриптов, мы эти ресурсы и скрипты "готовим" простой заменой текстовых идентификаторов на цифровые, а потом только уже отдаём их движку.
В code-driven подходе (большинство инди движков, даже блиц3д) такой подход вводится более болезненно, но вполне реально, например вместо :

Model * model = new Model("test.3ds");

пишем

#define MODEL_TEST 1
Model * model = new Model(MODEL_TEST);

Дак это же DarkBasic стайл! Я помню как там все делали. Заводили массивы на текстуры модели и тд.

Dim Models(9999)
Dim Textures(999)

Чтоб не плодить константы. Честно говоря после этого B3D казался куда разумнее.

03.05.2012, 17:15

Сообщение от Randomize

Дак это же DarkBasic стайл! Я помню как там все делали. Заводили массивы на текстуры модели и тд.

Dim Models(9999)
Dim Textures(999)

Чтоб не плодить константы. Честно говоря после этого B3D казался куда разумнее.

В code-driven это действительно немного сложно использовать, но если у вас есть редактор для игры\движка, то все проблемы отпадают сами собой, в редакторе у вас все текстом, в движке все цифрами

Randomize · 03.05.2012, 17:20

Cразу представляю большой xml словарь на все ресурсы.
Хотя без такого словаря всё равно не обойтись.

moka · 03.05.2012, 18:35

Кстати Android имеет специально xml файл со строками, и рекомендуется использовать именно их по идентификатору который строиться при компиляции (или запуске), а не строки сразу в коде.

Жека · 12.05.2012, 07:42

В андроиде за счёт этого локализация упрощается, т.к. все строки в куче, ну и правка однотипных слов-выражений - если они в нескольких местах используются.