When GameMaker announced their Marketplace, we thought it would be a good opportunity to port our Grids plugin for Unity (or at least, a part of it) to GameMaker. Here, I explain some of the issues we encountered in doing the port, and how we overcame the limitations of GameMaker's language.
C# is a wonderfully modern and practical language, and I love it. GameMaker's language, GML, is aimed at beginners, and hence lack many of the luxuries C# offers: there are no classes or structs, no delegates, you cannot overload functions (and a variable number of arguments does not work with GameMaker's extension mechanism), until very recently there were no enums, integers and floats are treated as one data type (or maybe not completely, many things seem to work magically which would make me very uncomfortable in other languages). GML does not have vectors or other geometrical objects. And most bizarrely, GameMaker does no memory management for the user. Data structures need to be destroyed explicitly! (On the flip side, GML does have 1D and 2D arrays, grids (similar to 2D arrays), maps (dictionaries), lists and some other data structures, so it is not such a computational desert as one would think.)
A note: We use "grid" and "map" as names for our data structures. GameMaker also use these terms for theirs. Our grids are similar to GameMaker grids - essentially 2D arrays, but is not limited to rectangular cells. Our maps can be thought of as two-way "dictionaries" (between world space and grid space), while GameMaker's maps are ordinary dictionaries mapping keys to values). The concepts are so clearly distinct in my mind that I did not even realise that it may be very confusing until I started to write a tutorial for the package… o.0 Below, unless otherwise specified, I always mean our grids and maps.
To a large degree, our design goals are based on those of our Unity plugin, and they reflect the core principle that underlies our thinking: Anyone can look up the few formulas necessary to implement a grid such as a hex grid. But in a real game, that does not bring you very far; you need building blocks which makes it easy to implement your game algorithms. So we wanted, as far as possible, to retain those features in our library that we believe make this possible. In particular, we wanted to retain these ideas:
We used GML's data structures to represent objects (instances of "classes").
For points we used arrays (so an array of two items represents a vector with an X and Y coordinate). We believe the syntax is straightforward enough so that users can manipulate the coordinates directly, without us having to provide interface functions. It also turns out that this is necessary to keep things fast.
We used lists for some simpler data structures, such as convex polygons and arbitrary polygons. These are mostly manipulated through interface functions.
For more complicated data structures, we used GM maps, where the entries are the "fields" of the object. We provide interface functions for all the manipulations we consider "public"; in general, users should not operate on map entries directly. (They don't even have to know they are working with maps in the first place).
Our library requires quite a bit of mathematics to make everything work, and we rely heavily on vectors for a lot of it. GameMaker does not support vectors (as data structures), so we had to roll out our own. We also had to roll out matrices, and other geometrical data structures, such as rectangles and polygons. About half the library is devoted to this low level math!
Most of it is quite straightforward, but we spent a relatively long time to get the right structures in place so that we can deal with grid shapes. (This was also true for our Unity plugin; a relatively large amount of complexity and code is involved in the shape technology.) For GameMaker, we finally settled on this definition of a shape: a shape is the union of intersections of half-planes. This definition is a compact description of most shapes that should arise in practice (and is flexible enough to describe any shape, even if it may be a bit cumbersome).
In contrast, our definition for Unity is: a shape is the set of points that return true for a test function. In practice, these test functions are nothing more than half-plane tests, but it also makes more complicated shapes easy to implement. However, the Unity implementation of the shape framework is surprisingly complicated, and it has fried my brain many times. The implementation in GameMaker is extremely straightforward, and I am quite pleased with it :-)
Our Unity plugin relies on delegates for some of its main features:
There is no obvious way to simulate delegates with GameMaker (at least not an easy and fast way). We had to solve each of the cases above using a different method, and in all cases we had to sacrifice some flexibility:
Many algorithms require iteration through all points in the grid. Because grids can be arbitrary shapes, we don't want the user to have to know the boundaries of the grid and construct valid points herself. We also want to hide the shape of the bounding shape used internally for the data container so that we can change this freely. Therefore, it makes sense to provide an iterator that will only return valid points.
Implementing a valid iterator is a little tricky, and it took a few tries to get right.
Many of our graph algorithms use sets (of integer points) dictionaries (with points as keys) internally. Because we cannot impose our own equality check on array comparisons (and so points cannot be compared by value), we could not use GameMaker's maps for this. Instead, we used boolean grids for hash sets, and grids for dictionaries.
Our C# library makes heavy use of generics. For the most part, it makes a lot of sense, and makes it easy for us to keep our different grids separate and still share a lot of the implementation. For example, it allows us to define methods such as Rotate60 on hex points that would not make sense on rect points, but still implement A* to work on any grid.
However, it comes at a cost. There are two problems with generics that we did not foresee.
The first thing is that it can make our library look scarier than it really is. Some methods take 5 template parameters, some of which may be generic themselves, and most with complicated type constraints that may themselves have generic components. I had one instance where I could not figure out what was the correct way to cast my parameters so that they would be accepted by a method. This is clearly undesirable! (And it can also scare the compiler; our generic version of Prim's maze generation algorithm compiles fine in Visual Studio, but not using Unity's C# compiler.)
The second problem is more severe. The AOT compiler (for iOS) cannot always work out what code to generate when type parameters are structs (as it is almost always throughout our library). Although there are workarounds to get the code generated, this makes our Unity library seem broken on iOS.
I have been playing around with the idea of changing the library to not be generic in the point type to reduce the effects of these two problems. This would be a dramatic change, and it is hard to predict what all the consequences would be.
Since GameMaker does not have the concept of generics at all, I got a chance to see some of the consequences of a library designed without generics.
Surprisingly, for the most part, it is rather pleasant. Everything looks a bit more direct and straightforward, and the implementation is cleaner in many cases. It also highlights some commonalities between grids that I did not consider before, and as a result strengthens the mathematical foundation of the library. A lot of the internal structural classes we had to write in the C# library are simply not necessary in the GameMaker version. The most surprising thing is how easy it would be to add other grid types. (One thing we learned with Grids for Unity is that making it easy to add new features does not make it easier to add documentation, examples and other supporting material for those features, so we are careful to not enter into a feature avalanche as we did before!)
I would never have guessed that implementing our ideas in a simpler (almost primitive) language could give us so much insight into the design of our C# library, and give us so many ideas for improving it, but it did:
Above all, the port highlighted the abstract fluffiness of our C# implementation in places, which will allow us to make our Unity plugin a bit leaner too. It's also a useful reminder of the benefits of implementing algorithms in different languages.