Sunday, April 14, 2013


I wanted to get a little deeper into some methods for storing and retrieving information. With some research, I found that in CS terms I was thinking about data structures, so I hopped on my favorite internet book ordering behemoth and in a few days I had a copy of Ron Penton's Data Structures for Game Programmers. It comes highly recommended from folks at work, some of whom are even thanked in the front pages, so I know I'm on the right track with this one.

One tiny concern was that the book's examples are in C++, while I'm working with Unity in C#. Well, how big a deal could it be? I'll just re-write the example code and Bob's your uncle. It took me about a dozen pages to get in trouble.

Ron wants you to be sure and understand a few things up front. The first is big-O algorithm complexity analysis (which I'll tackle in another post .. someday) and the other is templates. These are functionally equivalent to C#'s generics, right? No problem. The first example I tried to port over was a C++ function for adding either floats or ints together, depending on which was passed in. Well, it turns out in C#, things like this

public T  Sum<T>( T p1,  T p2) 
     T sum;
     temp = p1 + p2;
     return sum; 

just straight up don't work. Why not? further research led me to an interview with lead C# architect Anders Hejlsberg, who I will quote on this very topic:
" C# generics, we guarantee that any operation you do on a type parameter will succeed. C++ is the opposite. In C++, you can do anything you damn well please on a variable of a type parameter type. But then once you instantiate it, it may not work, and you'll get some cryptic error messages. For example, if you have a type parameter T, and variables x and y of type T, and you say x + y, well you had better have an operator+ defined for + of two Ts, or you'll get some cryptic error message. So in a sense, C++ templates are actually untyped, or loosely typed. Whereas C# generics are strongly typed."
Undaunted (the book is big and wasn't cheap), I dove further online, turning up a set of C# files called the Miscellaneous Utility Libraryput together by a Google engineer named Jon Skeet. He and Marc Gravell (one of the Stack Overflow guys) put together this solution for doing what they call "maths" on their side of the pond in the context of generic classes in C#. A small download and a using statement later, I was stuck again, as the Unity compiler didn't want to recognize the construction Operator<T>, for reasons that still hover slightly beyond my understanding. 

The MiscUtil pages reference an article by one RĂ¼diger Klaehn, a "freelance developer in the space industry", which sounds like the coolest job ever. He articulates the problem succinctly:
"To constrain type parameters in C#/.NET, you specify interfaces that the type has to implement. The problem is that interfaces may not contain any static methods, and operator methods are static methods."
RĂ¼diger presents two solutions, one of which I sort of understand and the other, which is far more performative, I don't understand at all. Fortunately I doubt I'll need to use so many numerical generics every frame to cause a slowdown in Unity (how many would that take I wonder) so I felt confident going with the first option. 

I was mildly dumbstruck by the idea that you could just declare a function without a body like this:

public abstract T Add(T a, T b);

as long as it's something abstract that you plan to override. I was even more nonplussed by the idea that I could use

namespace Int32
//custom calculation function

to just reach into the guts of how Unity deals with basic numbers, and just scribble in the margins as it were. That's really cool. Finally, when I got to the following, my brain broke:

public class CalcMethods<T> where T: new()
//a generic adding method + whatever else you need

I've seen cases of putting code in a function definition, with what they call a lambda, and I suspect this is something similar, but it's still blowing my mind.

In any event, I now have a function that takes a List of either floats or ints, and adds them together, and its easily extensible to whatever other kinds of numbers might come up, so I guess I'm ready to continue. At this rate my side-quest through this data structures book will probably take about a decade. Better brew another pot.

No comments:

Post a Comment