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.
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:
DYNAMIC_HASH_TABLE_DEFINITION(str_int_table, int, const char *, uint32,
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.
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:
int *array = 0;
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).
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:
gui_begin_window("my window", 16, 16, 64, 64);
if (gui_button(BUTTON_ID, 32, 32, 32, 32))
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
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:
as_claim_tex_by_name(const char *name, bool32 async);
as_claim_tex_by_id(uint32 id, bool32 async);
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.