17 February 2019

Merge Dragons: Recursive Merging!

PC-master race, am I right? I usually don't play mobile games but there was a time when I did. There was also a time when I was playing mobile games to earn cash. It works, but extremely inefficient. (it's more efficient than my blog right now..) Anyways instead of playing Diablo Immortal, if you like puzzle games and build-up games, you can play Merge Dragons instead!

Merge Dragons

This is a mobile game that I came across using recommendations from an app that suggests you other apps and gives you points when you play them, which you can swap for gift cards or PayPal payment. Anyways Merge Dragons is a puzzle game that allows you to - as the name says it - merge objects of the same type to create new objects. You then travel through different levels that are so far extremely easy to play and challenges which timed levels that are hard enough that even I have my problems with some. So, the goal is to finish the main objective of these levels.

The levels reset every time you go into them, however, there's a camp that works similar to the levels except it doesn't reset. This means you can pretty much build up everything there. Hence I said puzzle and build-up games.

Merging Stuff

Let's get to the real deal. In this game there are two ways to merge things:
a) Merge three objects, which will return a higher level object.
b) Merge five objects, which will return two higher level objects.
Objects can be leveled up to a certain point, the level cap or maximum level of an object. This differs from the object category to the object category. Due to the rules and confinements of the levels, you will have a few issues given by the different types of objects. These issues are mainly:

  1. space, it takes to combine objects
  2. the object count, it takes to get the maximum
  3. the  time, this game can really eat your time, be careful
Under these circumstances, I am wondering... how much do you save by going for five instead of three objects and how much more space do you need?

Using Math :D

Have I mentioned that I wrote a math exam yesterday? Fun! Anyways let's get into it right away.

Merging With Three

First up, the basic merge contains three objects of your liking that are the same (but not exact!) to get out one of the higher ones. For example, we need 3x level one to get 1x level two. Then we need 3x level two to get one level three. Needing 3x level two for one level three means we need 3 * 3 = 9 levels one. If we follow this thought further we might notice that the numbers will go like this:
3, 9, 27, 81, 243, 729, ...
These are equal to the exponents of three:
31, 32, 33, 34, 35, 36, ... 
Notice that the exponent is equal to the level - 1 of the object. If we assume n is the level of the object we want to produce we need 3n objects of the lowest level (level one):
f(lvl) = 3(lvl - 1)     for lvl ∈ N and lvl > 1
Now for space... we need three-space to create the next higher one. This means we need at most three times each previous level. That gives us this function:
f(lvl) = (lvl - 1) * 3   for lvl ∈ N and lvl > 1
So, for a level five object we need 35 = 243 level one objects and a maximum of f(5) = (5 - 1) * 3 = 12 fields of space.

Merging With Five

Now we merge 5x level one and get 2x level two. This is not an efficient way to only get one of the next higher ones. However, it speeds things up. Ignoring the rest if we have 10x level one we get 4x level two giving us 1x level three. So respective to whether or not we end up with 1x level three or 2x level three we had five or less than five before. 

Technically the algorithm is:
  1. divide five: 10 / 5 = 2
  2. increase the level by one: level one -> level two
  3. multiply by two: 2 * 2 = 4
  4. round down: floor(4) = 4
  5. if the number is equal or greater than five go to 1. else go to 6.: 4 < 5: go to 6.
  6. if the number is greater or equal to three increase level by one: level two -> level three
  7. if the number is greater or equal to three, divide by three: 4 / 3 = 1.333...
  8. round down and done: floor(1.333...) = 1
Here's the python code:

import math
#algorithm
def algo1(amount):
    level = 1
    while amount >= 5:
        amount /= 5
        level += 1
        amount *= 2
        amount = math.floor(amount)
    if amount >= 3:
        amount /= 3
        level += 1
        amount = math.floor(amount)
    return amount,level

We can't reverse this algorithm due to the rounding. If we do it most efficient (only five-merges) we will have some leftovers. The motivation behind this is that we get the maximum at the end. If you want to get only one at the end you have to round everything off with three-merges. To reverse it we start off by either one or two (if it's higher you could merge it to a higher as well and calculate with that). If it's one it is equal to a merge of three. If it's two it's a merge of five. In each of the cases, we multiply with the respective value. We decrease the level and then we get into the loop. In the loop, we need to make sure that our number is always even as we can't get odd results when always doing five-merges if we do have an odd one we will add one to it. This is going to be one of the leftovers.
After that, we divide by two (as we always create two), next up we multiply by five (since we always need five to make a higher-level one) which results in the level decreasing again. Once we reach level one we stop.

If we wanted to make 1x level five object, for example, it would go like this:
  1. if equal to two: set to five else set to three: 1, set 3
  2. decrease the level by one: level five -> level four
  3. if it's odd add one to it: 3 + 1 = 4
  4. divide by 2: 4 / 2 = 4
  5. decrease the level by one: level five -> level four
  6. multiply with five: 4 * 5 = 20
  7. if it's level one, then stop, else go to 3.
Here's the respective python code:

import math
#algorithm
def algo2(amount, level):
    if amount == 2:
        amount = 5
    else:
        amount = 3
    level -= 1
    while level > 1:
        if amount % 2 == 1:
            amount += 1
        amount /= 2
        level -= 1
        amount = math.ceil(amount)
        amount *= 5
    return amount

The result is 65. If we use our function and iterate over the level increasing it we get the following numbers:
3, 10, 25, 65, 165, 415, 1040, 2600, 6500
vs
3, 9, 27, 81, 243, 729, 2187, 6561, 19683
Well... merging five saves us a lot of work, haha. Unfortunately, there's a downside.

Merging five takes a lot more space. How much? Well.. in the camp there's a setting to disallow merges unless you actively move one object onto a set of 2+ of the same type. If we assume we have this setting on it takes similarly to our merge three functions:
f(level) = (level - 1) * 5

Finish!

Well, is there a simpler way to calculate it? I don't know or have found one. You can basically use an approximate but I've checked the numbers and I haven't seen a simple relation between them to calculate them easier. I'm not sure if I make another post on the Formula for a five merge outside the camp. I guess it depends on how many views this post gets. Let's say.. a hundred views are enough to be worthy.

Oh and on a side note: Upgrading the dragons do not provide more work power, it only increases your dragon power for unlocking more area in the camp. Thus it actually decreases the actions your dragons can do. Decide for yourself which you prefer.


Liked the post? Noticed an error? Wanna discuss the content or leave a comment*? You can join or check into the discord to do so! (*Note: Comments are disabled to avoid saving user data on this website.)
>> Join Discord

About Me

My photo
I'm a junior game developer and software developer and I created this blog to share my ideas, thoughts and whatever I'm working on or doing.