Idle Obelisk Miner Dev Log #2

It has been way too long since I wrote my last post here. Lots of new stuff has been added to the game since then.
I want to talk about the new RNG system, the new account system I added, as well as the overflow issue with big numbers.

Checkbox Account System:

The new account system has been out for about 3 months now, and it’s been very successful.
The main reason I wanted to make a custom account system was because the cloud solutions that are offered by Google (Google Drive) and Apple (iCloud) had some very annoying issues to deal with.
One of the issues was the cloud save data suddenly being out of date, even if auto-saving was enabled or manual saves were being done regularly.
It wasn’t unusual to have a player message me telling me that they have a very old save in the cloud after changing to a new phone.
Other issues were that upload simply didn’t work for no apparent reason.

So I decided to look into making a custom cloud saving system.
I spent a while designing the whole system and ultimately decided to implement a login system using OAUTH2.
For anyone that does not understand what that means: It’s simply a way of being able to authenticate a user by letting them use already existing accounts, like their Google or Apple account.
As those are needed to download the game anyways I figured that this is the best solution.
The back-end itself is written in Go and uses PostgreSQL to store the save data.
All of the save data is backed up weekly via an off-site backup solution.

One positive side of using the Google/Apple solution was that the cloud storage of the user itself is used, so the storage burden doesn’t fall on me.
This however turned out to not be much of an issue, as the save data for IOM is very small, and compressed it is even smaller.
With the current signed-up user count of over 20k, it’s about 550 MB for the entire database.

Overall I am very happy with how the new account system worked out.
It allows us to do a lot of interesting things.
We can investigate bugs more easily and we can add features in the future that require saving something to the account, like Discord integration for example.

When Random Isn’t Actually Random:

It is surprisingly hard to test randomness.
We often got reports of random chances in the game feeling off or unlucky. The first time I investigated these it seemed that it was simply a case of RNG being RNG.
Sometimes even something with a high drop rate takes forever to drop, that’s just the nature of randomness.
But the reports just kept stacking up.
Some players even went as far as calculating drop chances and proving with statistics that something is wrong.
So I started to investigate again.

However, I started my investigation with an assumption that cost me a lot of time.
I assumed that the way we seed our drop tables is the main reason the RNG is off.

IOM uses seeding for different drop tables. This is to prevent things like opening a relic chest, not liking the result, loading the save from the cloud, and reopening the relic chest, hoping for a better result.
This works by having a random seed number for every drop table.
On the first ever game start the game generates a random number and a random increment for each drop table
Let’s say the player builds a statue:

1. We fetch the seed for the statue drop table
2. The GameMakers random generator is seeded with that seed, then the seed is incremented by a random preset amount.
Incrementing the seed is needed to make sure the result isn’t always the same.
3. We roll a random number to determine the statue that should be built.

// A rough example of how we seeded our randomness<code>
global.seed = 1234567;
global.seed_increment = 5;
random_set_seed(seed);
global.seed += global.seed_increment; // Increase the seed so the result will be different next time
var result = irandom(500);Code language: GML (gml)

At first what I thought is happening was that the incremental counting up of the seed was not random enough.
This led me down a rabbit hole of different things that I tested.
I even asked around in the community, but no one was able to figure out what my issue was.

At this point, I started to think my initial assumption about the cause of the issue was wrong.
My next step was to look at other reasons on why the RNG would be so wonky.
Maybe the type of code GameMaker uses to generate random numbers is outdated and simply doesn’t work well when seeded frequently.
Then one day I remembered a graphic I saw that was used to test random distribution and decided to test our current seeding system for the actual random distribution.
The idea is simple.
Roll a number from 0 to some high number multiple thousands of times and graph out how much of each number is returned.
Think of rolling a pair of dice thousands of times and writing down how often each number appears.

The results made it obvious what the issue actually was.
Before I explain, take a look at the test results I got:

For both images the x axis (bottom) represents numbers going up from 0 to 50000, the y axis (left) represents how many times that number was rolled from 0 to 2000.
Small note: Most of the results are not visible in the images because they require scrolling, but the images contain enough info to see the issue.

It is very clear to see that something is wrong with the first one.

While the first image does have a pattern to it, its not a pattern that is helpful.
The first image clearly shows that some numbers roll way more often then others, and some don’t roll at all.
If we want usable randomness we need a distribution that looks like the second image.
This is because if we roll a lot of numbers we want every number to roll about the same amount of times as any other number.
Because if that is not the case, the chances we set in the game are simply not correct.

The reason for what you see in the first image is simple.
GameMakers random number generator simply doesn’t work as intended if you seed it every time before you use it.
GameMaker uses the WELL512 algorithm, which uses some math to set an internal state to a pseudo random number.
For this algorithm to produce sufficiently random numbers it relies on this state being advanced by using the previous state to generate the next number.
Hugely simplified that looks like this:

// Set the seed
var seed = 12345;
state = seed * 2 * 4 * 3 / 5

// Then next time the generator is called
state = state * 2 * 4 * 3 / 5Code language: GML (gml)

Seeding the generator every time before we generate a random number leads to the number always being created from the first state of the algorithm. And that simply doesn’t work. Only using that first state to create random numbers means the WELL512 algorithm is not being used as intended, and that leads to the distribution being wrong.

Now that we know what’s wrong, how do we fix it?
Obviously we need to get rid of the seeding before every roll. But how do we prevent save scumming then?
That is actually a fairly simple problem to solve.
We simply need to save the actual state of the generator and load that from the save file instead of the seed.

The problem is that GameMaker does not support saving or loading this internal state.
The only other option would be to recreate the RNG code inside GML (Game Maker Language).
And out of sheer luck, someone in the GM community remade the RNG GameMaker uses inside GML just as I was at this step of figuring out what the problem was.
YellowAfterlife made a great extension for GameMaker that allowed me to add the necessary state saving/loading to our game.
He also made a blog post that goes into more specific detail about the RNG issue I talk about in this blog and how exactly the WELL512 generator works. You can read it here.

Using that extension I implemented a system in our game that automatically saves and loads a state for each loot table we have in the game. This also takes care of saving/loading the state for any new loot tables we might add.
And that’s in the game since version 1.8.25, and seems to be working nicely so far!

Big Numbers:

Lastly, I just want to talk about issues with big numbers in the game.
We recently fixed a bug with big numbers overflowing when reaching very large amounts.
This was an issue I was stuck on for a long time.
Initially we solved this problem by using a bigint library.
What these do is use arrays to represent numbers.
So internally 1356389 would be represented like this: [1,3,5,6,3,8,9]
The problem with this is it requires a lot more work to add new features because the library requires more steps for everything.

// Math without bigint is simple
var result = 5 *7;
// Not so simple with bigint
var big_seven = bigFromInt(7);
var big_five = bigFromInt(5);
var result = bigMul(big_seven, big_five);Code language: GML (gml)

While this isn’t a lot of work, it stacks up when having to do this everywhere.
So I started to try and find the root cause of the issue.
For the longest time, I assumed that it’s simply because our numbers are too big for GameMaker to handle.
But this is not actually the case.
GameMaker offers an enterprise subscription, which enables you to get access to GMs source code.
To figure out the issue I decided to take a look at the source code.
After a lot of testing it turned out the reason for our problem was the round function in GM.
We use a lot of rounding to get non decimal numbers.
This usually would not be an issue, but GM’s round() function has a quirk that makes it not work with any number bigger than 2⁶³.

GMs round uses bankers rounding, which is a way of rounding numbers to the nearest whole number, but with a special rule for exactly halfway numbers (like 2.5, 3.5, etc.).
Outside of these cases it does normal rounding.
Under 0.5 -> round down, above 0.5 -> round up.
But if it is exactly x.5 it will round to the nearest even number: 1.5 rounds to 2 and 2.5 also rounds to 2.
The reason for this being used in GM is:

1. A left over from GMs first version which was written in delphi.
2. It’s statistically more accurate.

Now this would not lead to the issue we run into.
The issue comes from the following.
Internally, GameMaker first calls llrint() to round the number, returning a long long. However, GameMaker internally uses doubles for numbers, causing precision loss when converting very large integers resulting in the overflow issues.

I solved this issue simply by doing the following:

#macro round non_bankers_rounding
#macro gm_round round

function non_bankers_rounding(num) 
{
    return floor(num + 0.5)
}Code language: GML (gml)

This is all for this Dev Log. I am really hoping to get out the next one sooner as these are fun to write!
Please either DM me on Discord or write a reply to this post for anything I should talk about in the next one.
Thank you for reading.

FrozenAra

P.S. There might be a code hidden in this post ;)