Featured Blog | This community-written post highlights the best of what the game industry has to offer. Read more like it on the Game Developer Blogs or learn how to Submit Your Own Blog Post
In this post I describe some of the issues we encountered when we ported our C# Unity plugin to GameMaker, how we overcame the limitations of GameMaker's language, and what insight we gained into our design because of it.
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:
Grids are data structures that contain data of any type.
Grids can be any shape (any configuration of cells). It should be easy to make a new grid with the same shape (but different data) as a given one.
Grids are accessed through integer vectors (points), so that vector manipulations can be used the same way they are for rectangular grids.
It should be easy to get hold of all points of a grid in some sequence.
Grids contain only topological information (how cells are connected), no geometrical information (where the cells are supposed to sit in space).
Geometrical information is handled through a separate objects, called maps.
Maps can be transformed independently of the grid.
Different grid types can be handled uniformly where it makes sense (for example, you can implement graph algorithms for arbitrary grids).
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:
Point transformations (as delegates) make it possible to transform the internal coordinate system to any other system.
Delegate composition is used to make arbitrary maps (this features makes it possible to map grids onto weird surfaces).
Delegates are used to make certain algorithms more useful. For example, it allows users to specify custom cost functions for the A* path-finding algorithm.
As mentioned above, delegates (the test functions) are used to define arbitrary grid shapes.
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:
We decided not to implement grid point transformations. These are easy enough for users to handle externally using user-defined functions. It's a minor inconvenience.
To implement transformations on maps, we decided to limit the possible transformations to linear transformations. These are the most commonly used, and it allows us to represent the transformations as matrices, which are easy to compose. (This is not the end though; we really want to be at least able to support certain circular transformations, so that we can handle polar grids and linear grids uniformly).
The Unity A* method works on arbitrary cells. For GameMaker, we specify certain conditions on the cell (it must contain specific variables that can be accessed by the algorithm). This makes the algorithm much less flexible, but allows us to cover most common cases.
(Already explained above!)
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:
We found more elegant, compact ways to describe grid shapes that drastically simplifies the internal code used to combine these shapes.
We found the beauty of using matrices instead of arbitrary functions for representing map transformations, that also simplifies the map implementation drastically. Unfortunately, matrices limit these to linear transformations, but I am currently trying to find presentations that are a bit more general that we can use in both libraries (at minimum, I would like to have the circular transformations we use for polar grids too).
We got some insight on how dropping point type from the generics will play out. I am not sold on the idea quite yet, but it looks promising.
We got a useful alternative to sets and dictionaries using our own grids, which opens up many possibilities in algorithm design.
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.
Read more about:
Featured BlogsYou May Also Like
