Brief Introduction

Some months ago I and a friend decided to collaborate on an NFT. We wanted to create a piece of retro-game art that could be arcade in spirit. Something engaging, fun that would at the same time need to push the limits of its own technology to come to life. The same attitude that brought many legendary arcade games to existence. Remember how Nintendo managed to make the 1st 3D game for the SNES, when that was not even imaginable for that type of hardware?

So we created the ArcadeGlyphs. Simply put, it’s a generative NFT that, once minted, creates a Snake game. The twist is that the collectors only get the initial state of the snake. The creature will advance every hour, guided by a greedy search algorithm. At the end of the game, the NFT turns (magic) into an animation of the game itself. The cherry on the top: we wanted to have NFT-prizes that the owners of the best game could claim “for free”.

Where is the complication? We wanted it to sit 100% on-chain. In the old days, if you wanted to make a mind-blowing game for a certain console, you had to be able to do it with the hardware that was already out there in the gamers’ houses. We wanted to give ourselves the same challenge.

In this article, we will explain in technical details part of the journey to minimize the gas needed to run the game so as to fit all that was needed within the block.


    Why Gas Matters

Quick intro about gas: it’s a unit of measurement of the amount of computation that some Solidity code requires. It is used to estimate the cost related to a Solidity function call. There are 2 potential issues related to it:
* It determines how much the user will have to pay for a transaction (a “write call”). The more the gas consumed, the higher the transaction’s cost.
* Read calls (so-called view functions in Solidity) should not be affected by gas, but each node may decide to still put some limits on it, to avoid resource exhaustion. These limits are not standard. Some allow double the actual gas limit, some less... It’s most importantly not clear what’s the Opensea configuration. One way to be safe is to keep it within the actual block gas limit.

Back to the NFT look: it shows the current state of the game if the game is in progress, and an animation otherwise. Both cases require the contract to be able to calculate the current state by using only
* the initial snake configuration (determined at minting time)
* the current block.

In a nutshell: it needs to simulate the game up until the current block. This was the only way to avoid transactions and still provide through-time-mutability.

The problem is that the simulation is an O(N) function, with N the number of moves. In the best case, the snake collides right away and not much needs to be calculated, but in the worst case, we might need to run through the full number of iterations.

Imagine a very lucky game that runs quite long. On a grid 11x11 the game could run beyond 400 iterations. On top of calculating the outcome of the game, the contract has to generate the SVG animation if the game is over (very gas-intensive). This should give you a hunch of why even saving 700 gas (this is the cost for an optimized log2 computation) could have a pretty perceivable impact at the end of the simulation.

The other point of saving on gas though comes from an extra feature we implemented: the token owners can redeem trophies for the best games. For example, collectors with a 42-score game could redeem the 1st place trophy (requiring at least 40 points). This “proof-of-score” requires running the whole simulation again. It would be cost-irrelevant for a view call, but in this case, the function needs (after the verification) to change the state of the blockchain, by transferring the trophy to the token owner. The final gas fee will then include the overhead of the “proof-of-score”, which is one of the fundamental reasons why gas efficiency was vital.


    Basic Operations

To simulate the snake game, the minimum set of operations that the logic has to support is:
* Collision detection: this can be between single points (e.g. head and apple), or multi-point objects (head and snake body)
* Movement: basically advancing the snake, either for real or while searching for the next best move
* Extension: the snake needs to grow, the more apples it eats

We can then implement the simulation roughly like this:

1: for each iteration
2: move snake according to strategy
3: if collision with wall OR snake body
4: then break
5: else if collision with apple
6: extend the snake
7: move apple

When the collector wants to see the state of their snake after (say) 21 hours, the contract would run 21 such iterations to define how the game looks at that time. Let’s remember that that is an oversimplified version of the real algorithm. Line 2 and 7, for instance, are a whole piece of logic by their own. And ‘move snake’ is not merely 1 statement, but it involves advancing the head and the tail. This is just to say that there are a lot of devils in the details of that seemingly simple loop.