Game Engine Architecture

242 5. Engine Support Systems

so on, making sure to modulo the resulting indices into the valid range of the

table.

Linear probing tends to cause key-value pairs to “clump up.” To avoid

these clusters, we can use an algorithm known as quadratic probing. We start at

the occupied table index i and use the sequence of probes ij = (i ± j 2 ) for j = 1, 2,

3, .... In other words, we try (i + 1^2 ), (i – 1^2 ), (i + 2^2 ), (i – 2^2 ), and so on, remem-

bering to always modulo the resulting index into the valid range of the table.

When using closed hashing, it is a good idea to make your table size a

prime number. Using a prime table size in conjunction with quadratic probing

tends to yield the best coverage of the available table slots with minimal clus-

tering. See htt p://www.cs.utk.edu/~eij khout/594-LaTeX/handouts/hashing-

slides.pdf for a good discussion of why prime hash table sizes are preferable.

5.4 Strings

Strings are ubiquitous in almost every soft ware project, and game engines are

no exception. On the surface, the string may seem like a simple, fundamental

data type. But when you start using strings in your projects, you will quickly

discover a wide range of design issues and constraints, all of which must be

carefully accounted for.

5.4.1. The Problem with Strings

The most fundamental question is how strings should be stored and managed

in your program. In C and C++, strings aren’t even an atomic type—they are

implemented as arrays of characters. The variable length of strings means we

either have to hard-code limitations on the sizes of our strings, or we need to

dynamically allocate our string buff ers. C++ programmers oft en prefer to use

a string class, rather than deal directly with character arrays. But then, which

string class should we use? STL provides a reasonably good string class, but if

you’ve decided not to use STL you might be stuck writing your own.

Another big string-related problem is that of localization —the process of

adapting your soft ware for release in other languages. This is also known as

internationalization, or I18N for short. Any string that you display to the user

in English must be translated into whatever languages you plan to support.

(Strings that are used internally to the program but are never displayed to the

user are exempt from localization, of course.) This not only involves making

sure that you can represent all the character glyphs of all the languages you

plan to support (via an appropriate set of fonts), but it also means ensuring

that your game can handle diff erent text orientations. For example, Chinese