Types, Structures, and Classes

The first programming languages only supported operations on a closed set of data types. You could operate integers and floating-point numbers, but that was basically it. The reason for this simplicity was that at the assembly language level, these data types were the only ones available. Even today, anything beyond fundamental data types need to be defined, taken care of, and so on in a software layer. So it is not surprising that in the days when computer speed was a fraction of a megahertz, developers didn't feel the need to operate on anything but ints and floats. In fact, many hardware platforms of yesteryear didn't even support floating-point values, which were implemented in a software layer.

Some developers felt the expressive potential of programming languages was too limited and that creating large software applications was often impossible with such primitive tools. Thus, years went by, and the family of structured programming languages (C, Pascal, and so on) surfaced. In these languages, the concept of user-defined data types was introduced as an abstraction to allow developers to encode real-world data easily. If you needed to have a point in space built into your program, you could decide whether to store it in three variables, such as:

 float x,y,z; 

Or, by using this new paradigm, you could decide to store it in a user-defined type, which we will call point3D:

 typedef struct       {       float x,y,z;       } point3D; 

This new way of working allowed developers to write more compact, easy to follow code. For example, you could access the attributes (each individual element in the type) as follows:

 point3D p; p.x = 1; 

Even better, types could be built incrementally, so more complex types use other, less complex types, similar to the layers of an onion. The result was type hierarchies, which were useful for encoding real-world data with complex relationships. Clearly, user-defined types increased the expressive potential of programming languages, and the era of modern software development began.

However, some new problems appeared. Once you had a large type hierarchy, it was very likely that you would have a similarly large block of code full of operations on that data structure. In the previous point3D example, you would need operations to add, subtract, perform both dot and cross product, and so on. If you only had user-defined types, you were condemned to the following:

 point pointadd(point,point); point pointsubtract(point,point); float pointdotproduct(point,point); point pointcrossproduct(point,point); 

As your data structure grew, the accompanying code would also grow. Moreover, you would run into some naming problems, and your code would become a spider web full of #include statements. The size and complexity of your program was again compromised by the language's lack of features.

At this point in time, the second "revolution" in programming language technology took place. Again, the idea was to allow bigger programs with less internal chaos. Because user-defined types were generally considered a good idea, this concept was extended to allow each type to include the source code for its own access operations, so the type became a self-sufficient code and data module. These modules were called classes. Additionally, rules governing how classes could relate were established to mimic the real world. Classes could have descendants (inheritance), class members could be renamed so they used standard operators (operator overload), and so on. So, our point data would now become:

 class point3D       {       private:       float x,y,z;       public:       point(float , float, float);       ~point();       point operator+(point);       point operator-(point);       }; 

The advent of object-oriented programming (OOP) really pushed the maximum program size to unknown boundaries. Programs several million lines of code in size are not uncommon these days. Classes have basically become "black boxes," which you can share, recycle, and use with no real knowledge about their internals. By looking at the (hopefully well-documented) class definition, a programmer can effectively use a class much like a driver can use a car with no knowledge of how the engine works. Clearly, OOP benefited developers in two ways: It allowed them to build more structured programs that are easier to maintain, and it improved team-based coding where classes could be exchanged and shared between team members.

A number of improvements have been introduced in recent years, from visual languages to design patterns and the Standard Template Library (STL). Although none of the improvements has had the impact that OOP or user-defined types had, they have provided developers with constant advances that make work easier. For the sake of game development, design patterns and the STL are very useful. At the end of this chapter you will find a section on the STL, whereas the next chapter is completely dedicated to design patterns.

For now, we will focus on reviewing those data structures that are frequently used in game development, so we can reference them in chapters to come. Some of them will seem very simple, but quite likely some of them will also be new to you.