The Stack

A couple of levels on, and I’m once again finding myself spending a lot of my time clearing tar, not just because of those tar gates, but because clearing a room completely of tar has become a fairly common subject for Challenge scrolls. The mechanics of it are seeping into my dreaming mind, occupying my idle thoughts. Let me get some of this out in words.

Tar lies in multi-square puddles, which you can cut with your sword along any edge, except at the corners, which are vulnerable only to explosions — which is to say, invulnerable in rooms without bombs, which is most rooms. To remain stable, the puddles have to have a width of at least 2 in all places, both north-south and east-west; any square of tar that lacks a neighbor in either dimension will break off and start chasing you. Thus, the smallest stable configuration of tar is a simple 2×2 square. Since this puts all four tiles at a corner, such a square cannot be cleared. It’s the basic kernel of most unclearable tar shapes: if you can clear everything except a 2×2 square, you were doomed from the start. There are other invulnerable shapes, but they basically amount to multiple 2×2 squares stuck together by shared corners.

The basic clearable tar shape, on the other hand, is the 2×3 rectangle. Poke that in one of its vulnerable longer sides, and the remaining five squares break into monsters. This can be generalized. Given a 2xn strip, the only things you can do are cut off two rows at one end, or remove one row in the middle and split it into two pieces. If n is odd, you can cut off two rows repeatedly until it’s 2×3. If n is even, then it will still be even if you cut off two rows, and splitting it in the middle will always create one strip with an odd length and one with an even length; thus, you’re always going to wind up cutting it down to a 2×2 square at the end. So strips of this sort are solvable if their length is odd and unsolvable if their length is even. Many rooms have a checkerboard pattern on the floor, allowing you to tell odd from even at a glance.

Similar logic, which I’ll leave as an exercise for the reader, shows that a rectangle is solvable if and only if it has at least one odd side. It’s basically a matter of parity, an odd-or-even property that you can’t change with your sword, except with “odd” and “even” confusingly swapped: an odd length represents even parity and vice versa. That is, by assigning “even” to odd lengths, an nxm rectangle has even parity if either n or m has even parity, just as the product of two integers is even if either of them is even. It works out this way because of how splitting a rectangle into two pieces requires removing a row. When you split a rectangle in two, the pieces will have similar parity if the original had even parity, and opposite parity if the original was odd.

At any rate, all rectangles with even parity are solvable, but things get more complicated when we move beyond rectangles. You can have lumpy shapes with corners in inconvenient places that keep you from making the cuts you want. If you can reduce a shape to two separate 2×2 squares, it had even parity, but might still have been unsolvable. Odd parity is always unsolvable, though, no matter the shape. Assuming that Challenges are never completely impossible, it’s therefore safe to assume that the parity of any completely inert tar pool you’re supposed to clear will be even. But if there’s a Tar Mother in the room, making the tar expand at regular intervals, it’s possible for the parity to change. Thus, when you kill the Mother, it’s imperative to make sure that the remaining tar has the right parity if you intend to clear it all. I have no better way to do this for wiggly shapes than to attempt to clear it and see if it I wind up with a 2×2 square left over. But if I do, at least I know better than to keep trying from the same point.

OK, I started talking before about how the exponentially-stronger enemies in Gemcraft: Chasing Shadows inevitably overtake the player. That’s a good safe way to design things where the numbers get arbitrarily large; it’s the cornerstone of the Clicker genre, for example. And this is certainly a game where numbers can get large. After you win a battle, you have the option to keep going in “Endurance mode”, which means letting additional waves keep coming for as long as you’re capable of fending them off, the better to rack up lots of XP. In this mode, I’ve seen it get to the point where it’s expressing enemy hit points in scientific notation.

I’d like to go into more detail about the efficiency of gems, and how it’s possible to keep pace with the exponentiation for longer.

First of all, more powerful grades of gem are created by fusing gems. In general, you make a grade n+1 gem by fusing two grade n gems. There’s a hotkey for upgrading a gem, but using it is exactly equivalent, in both effect and cost, to creating a duplicate of the gem and then fusing them. Creating a grade 1 gem and fusing two gems are both primitive actions that cost a fixed amount of mana. Creating a grade n gem from these primitives would require 2^(n-1) grade 1 gem creations and 2^(n-1)-1 fusions.

Now, the damage that a gem does per hit varies with the color of the gem, but one thing is consistent: the damage per hit of a grade n+1 gem is less than twice that of a grade n gem. Given that the cost of a grade n+1 gem is more than twice that of a grade n gem, it may seem like it’s always worthwhile to deploy multiple low-grade gems rather than a few high-grade ones. But there are several confounding factors. For one thing, there’s only so much space on the board. I’ve been routinely getting my strongest gems above grade 20 lately, and there’s no way to deploy 2^20 grade 1 gems, because that’s more than a million gems. Also, high-grade gems fire more shots per second than low-grade ones, although there’s a cap to that. Sometimes you need to do lots of damage in one hit to punch through armor or overwhelm regeneration effects. There’s a trick where you cast a beam spell on a mana-leeching gem to get lots of mana-leeching done at once, and you need a high-level mana-leeching gem to get the most out of that.

Regardless, the cost of gems rises exponentially with level, and the damage they do also rises approximately exponentially. I haven’t crunched the numbers, so the “approximately” there could be hiding a significant factor, like a penalty that increases with the grade. But let’s assume it doesn’t and say that the two exponentials cancel out and the resulting damage-per-second-per-cost is basically constant. That means that the damage you can put out is proportional to the mana you’ve collected.

Yellow gems increase this by doing critical hits some of the time. In the original Gemcraft, with its overall lower numbers, critical hits were simply triple damage, and the chance of getting a crit increased with the grade of gem. But triple damage doesn’t mean a lot in the exponential world of Chasing Shadows, so it works differently: the grade increases the crit multiplier. (The chance of a crit still increases with grade, but caps out at 80% before too long.) The multiplier increases in the same not-quite-doubling way as the base damage, so the overall damage from yellow gems is proportional to the square of the mana you’ve collected. This is clearly going to track the increases in enemy strength for longer.

Add a white component, and you have an additional factor, which is harder to analyze. White gems give an additional multiplier to both damage and specials — which is to say, on a yellow gem, it increases damage twice, once as a bonus to the base damage and once as a bonus to the crit multiplier. However, this multiplier increases only linearly with gem grade — which is to say, it increases logarithmically with the mana you’ve invested in it. It also increases with the size of your mana pool, but that also only increases at exponentially increasing intervals, so let’s call the end result log(n)^3. It’s a bonus worth getting, but in the long run, it’s going to be insignificant compared to the quadratic and even linear increases from just upgrading ordinary gems. I’ve seen it said online that the multipliers from black gems start outstripping white gems at around grade 30, but I haven’t got there yet.

Orange gems increase the rate at which you collect mana. Each hit from an orange gem gives you a fixed amount of mana that increases with the grade of gem at a less-than-doubling rate, just like the damage does. So with orange gems, your rate of mana collection is proportional to the amount of mana you’ve collected? Wouldn’t this yield exponential growth, potentially disrupting the Clicker-like guarantee of eventually losing that I described earlier? I suppose that as long as the enemies are getting tougher at a faster exponential rate than your mana collection, they still win. But it seems risky: all it takes to make one exponential function greater than another is a sufficiently large constant scaling factor, and the rules here are complicated enough that it doesn’t seem unreasonable that a player could figure out some trick to provide it.

In my last post, I described a very effective combo using Kobold Elders and Kobold Shamans. By the end of map 4, I had two high-level heroes, one of whom was using this combo. The other, which had progressed around the map by a different route and had encountered different spells, was using a different technique, one that’s more elementary (so much so that I hesitate to call it a combo) but also quite effective: a deck made mostly out of rats and anger.

The common stink rat is the beginner’s monster for team red: it’s 1/1 and costs 1 mana to cast. Anger is an enchantment that gives all your creatures +1 to their attack power. This bonus stacks, so your damage potential increases with both the number of rats and the number of Angers. Of course, the same bonus applies to non-rats, and that’s important sometimes — I put a couple of bats into this deck as well, because a couple of the enemies had a spell called Flood that disables anything that can’t fly — but the rats were cheap and disposable, and the strategem works better with lots of creatures than with a few powerful ones.

Both of these decks have the advantage that they start damaging the opponent immediately: kobold shamans and stink rats both cost 1 mana, so you can summon them on your very first turn. But more importantly, they’re both O(n²). That is, your potential to do damage on a turn, barring interference, is roughly proportional to the square of the number of turns that have passed. Even though the amount of mana available to you increases with every turn, you still only get to draw cards at a constant rate per turn. So in the long run, the number of instances of a spell active at any moment is going to be linear on the more limiting factor, time. But the damage potential of these strategems is determined by the product of the number of instances of two different spells.

There are other combos with this property; it may in fact be a feature of every deck that wins at high levels. In fact, there’s one instance I’ve observed of a spell that’s O(n²) without a combo: Grass Snakes. Every time a grass snake hits the opponent hero for damage, its attack power (and health, but that’s not what I’m considering here) increases by 1. I suppose this means that a snakes-and-anger deck would be O(n³). [Edit: Not really, see comments.] (Actually, that combo is impossible: Anger is red, and snakes are green, and never the twain shall meet. But apparently there are a few rare green spells that have a similar buff-all-friendlies effect.)

But I doubt that such a deck would actually function as O(n³) in practice, because the bonus on the snakes is per-snake, which makes it vulnerable. Every time a snake dies, any bonus it built up dies with it. The other decks I described are more robust: if you kill my rat, the next rat I summon will be just as angry. Catching up to where you were is linear (that is, O(n)) on the number of rats killed. For snakes, in the worst case it’s linear on the number of turns the oldest snake was alive… which, now that I think about it, makes it also linear on the number of snakes killed, because both the maximum age and the number of snakes are linear on the number of turns played so far. I guess big-O notation doesn’t tell us everything.

Here’s a better analysis: If you can kill my (oldest) snakes at the same rate as I can summon replacements, my damage potential from snakes will never increase. Whereas in the rat/anger deck, a rat equilibrium will just slow me down from O(n²) to O(n), because I’ll still be casting Anger at a constant rate. Unless you have spells that remove enchantments and we have equilibrium there too. I suppose what I mean by “robust” is that disrupting it completely requires more things.