Alright, here's another post about MUTA, our MMORPG project. I didn't work much on the game for nearly two months since the new year holidays, but I've since been picking up the pace, working the hours I could afford. Unfortunately, it's not that much, but evenings are still something as are weekends. The days are also getting longer and longer, and I've noticed in the past my productivity drops drastically in the middle of the winter when there's only a couple of hours of daylight. Thank goodness spring seems to be making it's way swiftly!

Since Christmas, I believe I alone have touched the codebase. This has a clear advantage: there's no way to get merge conflicts if you only merge from one branch. So, I have been cleaning up here and there, including in files I didn't previously touch personally (although I didn't do anything drastic in the case of such files.), reformatting, clarifying naming conventions, etc. I also implemented asynchronous asset loading proper and started adding support for creatures, but more on that later.

Getting rid of unneeded code

Something I have been wanting to do is getting rid of code that isn't needed. Obviously, the smaller, the better when it comes to codebases - I think we can all agree on that. And we did have some code that was practically duplicate.

For example, we originally had a hashtable implementation that preserved memory addresses and another hashtable that didn't. In the case of the first container, instead of increasing the amount of buckets when more space was needed, a new bucket was created and added to a linked list of buckets at index N. Now, that's not great algorithmically because obviously search time increases linearly with the amount of items in a bucket. But I thought it would be handy when you wanted to store items instead of pointers inside a hashtable, and also wanted pointers to those items to remain valid until the bitter end, even if the table was resized.

Well, turns out the first hash table was only used in one file, in our asset system, and even there the only reason for it's use was that this table was implemented first, back when the other hashtable had not been written yet.

So I got rid of the memory address preserving hashtable.

Less macros

Our containers, including the hashtables, have previously been implemented as C++-template-like C preprocessor macros - macros that define a new struct or structs and functions that manipulate said struct. Hence, to be able to use a container for a specific type, you have to first declare it by calling a macro, like this:

That's kind of cumbersome and not pretty. It's also difficult to read where the struct/function definition happens for anyone new to the codebase. So I would like to get rid of most of this stuff.

Dynamic arrays

The most common container type, dynamic array (vector in C++ lingo), was also implemented as a macro of this sort. So I decided to go through all of our dynamic arrays defined in this manner and replace them with a stretchy buffer like container, as I recently read Our Machinery was doing.

In case you don't know, a stretcy buffer is a group of C macros you put together to be able to create dynamic arrays on the fly. Instead of declaring specific dynamic array types, you declare a null pointer of the data type your array will contain, and then call macros like 'array_push(some_pointer)' or 'array_count(some_pointer)'. The macros will store the size and capacity of the vector at the beginning of the allocation and assign the pointer to point to the first element. For example:

There are a couple of methods to distinguish between a normal pointer and a stretchy buffer. You could do that by naming the varible or leaving a comment. I have taken to typedeffing the types like this: 'typedef int int_darr_t'.

Stretchy buffers only require a single function, which in our case looks like 'void *darr_ensure_growth_by(void *darr, uint32 grow_by, uint32 item_size)', and a bunch of one-liner macros. That simplifies things nicely, because our previous dynamic array definition macro was over a hundred lines long (it has now been erased), and different array types no longer need to be defined via a specific macro call.

By the way, I also made most dynamic containers have a growth rate of 2, meaning they double in size when they fill up. I thought this to be excessive before, but it turns out many standard libraries do this too. Dynamic strings I gave a growth rate of 1.5. In some places we used to have growth rates as small as 5% which was really bad for small groups of objects, leading to a lot of realloc calls (for example, in our GUI).

Other containers

We have some other container types, too. For example, we have a macro for declaring a dynamic object pool for a type, which allocates multiple objects when it needs to grow and provides a linked list-like interface. And of course, we have hash tables. I didn't do anything to these macros yet, because I wasn't sure if I wanted to, but also because of time. One could build a "typeless" hash table for example, but it would be difficult to choose the correct hash function and bucket size  without declaring them via a macro.

Thinking about dynamic memory allocation

When it comes to dynamic memory allocation, I think I'm somewhere between the extremes of liberal and conservative.  Th C++ way of thinking where everything is allocated dynamically is definitely not for me, and since I only really care about the PC as a platform, I also don't feel like I need to know the amount of memory I need beforehand (although I've done that out of curiosity before). The way I would describe my dynamic memory usage is: if it can be allocated statically, allocate it statically. Do that also when you know the absolute maximum amount of bytes an allocation may require. But it's ok to use dynamic arrays and the like when you really don't know.

That being said, I've been pretty liberal about freeing memory. I always let dynamic arrays and similar containers grow until the end of the program without freeing them in between, because I know at some point they will reach their absolute maximum. But I also have not gotten used to cleaning allocations up at the end of a program, since modern operating systems take care of that for you.

I've taken a step back in this thinking though and decided dynamically allocated recources must still be freed at the end of the program, never mind if the operating system is magically capable of doing that for you or not. That' because in larger programs, tracking memory leaks becomes a bit of a pain if you never clean anything up. Tools that track allocations, like AddressSanitizer and Valgrind, will report all leaks, and if you never free anything, the output won't really tell you much because there's a lot of noise.

So far I have added memory clean up to the MUTA client. Now if there is a leak, at least I will be able to tell where it is. I didn't give the same treatment to the server side programs yet however because the whole server side infrastructure will change drastically as the project goes on.

The case of GUI memory management

A sort of memory-related issue I also dealt with cleaning up was the way our GUI's memory was handled. This was due to an experiment I wanted to make when I first wrote the UI base.

MUTA's UI is an immediate mode style one. In the unlikely case you haven't heard of such a thing, take a look at Casey Muratori's  introduction or the popular Dear ImGui library. In short, instead of creating gui "objects", you call functions like this:

So, it becomes a little like writing HTML when you write, say, inner windows or such. The flow is easy to follow. Anyway, immediate or retained mode, a UI needs to store state, and state storage is what I've been cleaning up.

Have you ever though of what would happen if all your GUI memory was stored in a single, contiguous dynamic block? No? I have. I don't know what was going through my mind when I decided to implement MUTA's UI memory management in this fashion, but I was probably thinking of serialization and to a lesser extent, vague ideas of "cache coherence".

You know what happens when a dynamic memory block is resized? Pointers into it are invalidated if the block has to be moved. Storing a complex structure with many pointers like this may not be the best idea. But that's what I did.

What this lead to was that all pointers had to be stored as relative pointers, integer offsets into the main block of UI memory. This block contained everything, including many dynamic arrays. When a dynamic array had to be resized, we looked in the block if there was enough free space - if not, the whole block had to be resized.

It was a real pain, because you couldn't reliably use pointers even inside functions. If you had a pointer to, say, a window structure, and after fetching that pointer called a function that might move the main memory block of the UI (for example, by drawing some vertices), you had to fetch the pointer again using the aforementioned relative pointer. It was painful to me, and it was more painful to other people who tried touching the UI code earlier.

So I did away with all that. Now the UI has normal, individually allocated dynamic arrays. But at the same time, I removed many of the dynamic elements, beacuse they weren't needed. Some elements are now statically allocated, and there's simply a maximum limit to their number. Others, such as vertices and text formatting buffers are still stored dynamically, because it's hard to know the maximum amount of things such as that beforehand, and because I want the UI to be reusable in other projects.

Immediate mode GUIs are nothing new but I kind of want to write a little about MUTA's specific implementation at some point. Maybe I will, though there are still some features that need adding.

I've uploaded the current GUI API and implementation files here and here in case you're interested.

Adding creatures and NPCs

Cleaning up is the bulk of what I have done lately, but not everything. I added some messages concerning creatures to our protocol, which is rather easy using the MUTA Packet Writer application written by Lommi. The packet writer let's us define packets in a text file, from which it produces serialiazation functions and struct definitions.

So far I only added spawning and despawning, and made sure those work with interest areas (structures that define to whom information of nearby events is sent). Plus a GM command for spawning creatures to test things. But the system is surprisingly complicated to implement, because we will need a concept of what spawn points are, how creature IDs are handled, etc. We don't just want to spawn creatures into the world without any context - that may lead to bugs like unique NPCs spawning twice, or something worse. We also need a format to store those spawn points in, and lastly we're going to need scripting. The latter will probably be done with Lua.

Asynchronous asset loading

The asset system has seen some grand internal upgrades. Textures and sounds may now both be loaded asynchornously. This was possible before, but only in a half-assed, buggy kind of way. There's still work to be done here, but it kind of works.  There's also a sort of garbage collection mechanism in place which gets rid of unused assets after a while.

The asset API remains about the same as before. It looks something like this:

Clean up takes time, perfection is impossible

Everyone in software knows this, but there is no such thing as perfect code. There's always something to improve upon. And that's definitely something I came to think of once again while going through our codebase.

There are so many things I'd wish to do better. I want to clean up formatting, I want to touch this and that irrelevant "issue" because I know there's a more optimal solution. For example, I could do away with some slight branching in the updating of moving objects on the client side by separating the objects into two different arrays: idlers and movers. But this kind of thinking is treacherous. It's a 2D game, with only up to maybe a thousand mobile objects on screen at once. It just doesn't matter. But the engineer inside most programmers craves to take on the most minimal of issues.

Beautifying code is as treacherous as over-engineering. I could spend years making the code prettier, but if it does not significantly reduce the amount of time it takes to upkeep said code, it just isn't worth it. So, in the near future, MUTA's codebase will retain it's ugly macros and similar beauty flaws.

When the urge strikes to spend time on something that isn't worth it, I try to think of existing games. I'm certain no successful game has ever shipped without it's programmers thinking they could've done a lot better if only they'd had a little more time. Especially I think of Ultima Online, which was one of the first graphical MMOs and groundbreaking in a lot of ways, and yet most of it, according to Raph Koster, was written by a single programmer over the span of as little as three years. Now that's one heroic feat even from  a larger team of programmers, but it also signals to me that the codebase must have been pretty damn far from perfect.