Subscribe

Technical Tricks, Aug 2022

Technical Tricks, Aug 2022

By Yijia Chen

Today we’ll be talking about a few technical tricks that we used to speed up deploying multiple contracts for our first fully on-chain strategy game. You can try the game here.

Map initialization

In our game, each tile is denoted by its position and terrain type number (water, coast, …). After the map is generated using a combination of Perlin noise and custom algorithms, the map, which is represented as a 2D array of numbers, must be set in Solidity.

A typical map that houses 100 players for 1 hour requires roughly a 200×200 grid map. That’s 40,000 tiles to be initialized, and to initialize each, we need to set the terrain field in each of the 40,000 tile structs on-chain.

How can we initialize this large game map within a reasonable amount of time?

Naive solution

We first wrote a setMapChunk function, which allows the world creator to initialize a chunk of the map by passing in a 2D array of numbers, each number representing the terrain-base combination of one tile. We’ll refer to this combination as a tile type in the rest of article. In this instance 3 represents a water tile, and 5 represents a land tile with a city


function setMapChunk(Position memory _startPos, uint256[][] memory _chunk) external onlyAdmin {
    for (uint256 _dx = 0; _dx < _chunk.length; _dx++) {
        for (uint256 _dy = 0; _dy < _chunk[0].length; _dy++) {
            Position memory _pos = Position({x: _startPos.x + _dx, y: _startPos.y + _dy});
            uint256 _terrainId = _chunk[_dx][_dy];

            if (_terrainId >= 3) {
                // Note: temporary way to set base
                BASE_NAME _baseName = _terrainId == 3 ? BASE_NAME.PORT : BASE_NAME.CITY;
                Util._addBase(_pos, _baseName);
                _terrainId -= 3;
            }

            gs().map[_pos.x][_pos.y].terrain = TERRAIN(_terrainId);
        }
    }
}

The initialization is broken into 10×10 map chunks; otherwise, its gas consumption would exceed the gas limit. Using Hardhat on localhost, setting just a 100×100 map with a few dozen bases takes roughly 142 seconds. The problem becomes serious when players themselves deploy maps to play with others — we can’t expect them to wait 2 minutes for a custom game to be created.

Bit of clever math

We decided to use arithmetic encoding. The largest uint256 is 2^256–1, a number much larger than the number of tile types (which is 6 at the moment) we have. This means that every uint256 we use to store a tile type has a lot of “unused” space.

Now, here’s the intuition: Suppose we have only 2 tile types. We can then have each digit in a uint256 represent a tile, and therefore each integer representing 256 tiles. What if we use 6-arithmetic for 6 tile types? After some calculation, it turns out that the largest power of 6 smaller than 2^256 is 99, which means we can store up to 98 tiles in a single uint256 without overflowing. To be extra safe, we use 50.

Let’s run through a simple example by encoding the type numbers of 50 tiles in one uint256. The first tile would be encoded as TILE_TYPE_0×6⁰, the second tile as TILE_TYPE_1×6¹, etc. The resulting encoded uint256, C, would be the sum of individual encoded tile types.

Such encoding has an important property: The input tuple of tile types, denoted M = [TILE_TYPE_0, TILE_TYPE_1, … , TILE_TYPE_49], is uniquely decodable from the resulting uint256, C, from the operation. More rigorously, the operation is injective.

The decoding goes as follows: To fetch the tile type of the i-th tile, we first take the remainder of C divided by 6^(i+1). Since the types of all tiles with index greater than i are divisible by 6^(i+1), and only they are, the remainder should only contain the sum of all encrypted tile numbers whose index is at most i. Then, floor divide the remainder by 6^i. Since all tiles with index lower than i are smaller than this divider and thus yield 0 in the floor division, we get back exactly TILE_TYPE_i, the tile type of the i-th tile.

Corresponding code

In this new solution, we encode a 2D map of integer tile types into batches of encoded columns. Note that this step happens in TypeScript before the result is passed on-chain, so the duration is negligible.

export const encodeTileMap = (tileMap: TILE_TYPE[][], numInitTerrainTypes: number = 6, batchSize: number = 50): string[][] => {
  const result: string[][] = [];
  const numBatchPerCol = Math.floor(tileMap[0].length / batchSize);
  const lastBatchSize = tileMap[0].length % batchSize;

  let encodedCol: string[];
  let tempBatch: bigint;
  let k: number;

  for (let x = 0; x < tileMap.length; x++) {
    encodedCol = [];
    for (k = 0; k < numBatchPerCol; k++) {
      tempBatch = BigInt(0);
      for (let y = 0; y < batchSize; y++) {
        tempBatch += BigInt(tileMap[x][k * batchSize + y]) * BigInt(numInitTerrainTypes) ** BigInt(y);
        if (tempBatch >= MAX_UINT256) throw new Error('Encoding exceeds uint256 max size');
      }
      encodedCol.push(tempBatch.toString());
    }
    if (lastBatchSize > 0) {
      tempBatch = BigInt(0);
      for (let y = 0; y < lastBatchSize; y++) {
        tempBatch += BigInt(tileMap[x][k * batchSize + y]) * BigInt(numInitTerrainTypes) ** BigInt(y);
        if (tempBatch >= MAX_UINT256) throw new Error('Encoding exceeds uint256 max size');
      }
      encodedCol.push(tempBatch.toString());
    }
    result.push(encodedCol);
  }

  return result;
};

At the beginning of each player action functions such as a movement from one tile to another, we then check whether the tile is initialized or not, decoding its value.

    function _initializeTile(Position memory _pos) public {
        WorldConstants memory _worldConstants = gs().worldConstants;
        uint256 _batchSize = _worldConstants.initBatchSize;
        uint256 _numInitTerrainTypes = _worldConstants.numInitTerrainTypes;

        uint256 _encodedCol = gs().encodedColumnBatches[_pos.x][_pos.y / _batchSize] % (_numInitTerrainTypes**((_pos.y % _batchSize) + 1));
        uint256 _divFactor = _numInitTerrainTypes**(_pos.y % _batchSize);
        uint256 _terrainId = _encodedCol / _divFactor;

        if (_terrainId >= 3) {
            BASE_NAME _baseName = BASE_NAME(_terrainId - 3);
            _addBase(_pos, _baseName);

            if (BASE_NAME(_terrainId - 3) == BASE_NAME.OIL_WELL) {
                _terrainId = 1;
            } else {
                _terrainId -= 3;
            }
        }

        gs().map[_pos.x][_pos.y].isInitialized = true;
        gs().map[_pos.x][_pos.y].terrain = TERRAIN(_terrainId);
    }

It turns out that this approach is much more gas-efficient. We can initialize a 100 by 100 tile map in ~6.2 seconds using Hardhat on the same machine, a 23x improvement compared to the naive solution.

Wrangling with Foundry

This version of Curio uses the Diamond architecture along with Foundry for testing. Although there are many benefits to writing tests in Solidity, Foundry doesn’t provide a clean interface for JavaScript to be used in the test process. For instance, how do we initialize the tests with an auto-generated world map? Since our map generation is written in TypeScript, does this mean we need to rewrite the algorithm in Solidity again?

Luckily we discovered the -ffi cheatcode in Foundry, which allows a call of an arbitrary command. We used this to generate the map in TypeScript, encode the map using abi.encode, run the map gen code through a bash script, and pipe that encoded map back into Foundry to then be decode in Solidity and passed on as a large 2D array map variable. The same approach was used to get a list of all solidity function selectors in used in all of the diamond’s facets for initialization.

function getSelectors(string memory _facetName) internal returns (bytes4[] memory selectors) {
        string[] memory cmd = new string[](5);
        cmd[0] = "yarn";
        cmd[1] = "--silent";
        cmd[2] = "run";
        cmd[3] = "getFuncSelectors";
        cmd[4] = _facetName;
        bytes memory res = vm.ffi(cmd);
        selectors = abi.decode(res, (bytes4[]));
}

What we’re up to …

The team is busy collecting feedback from our first 2 demos while writing the yellow paper for our upcoming game. Thank you to the 500+ players who tried it out!

While we remain optimistic on what on-chain games can bring, we also acknowledge Solidity at its current stage is somewhat inflexible to craft truly complex worlds. Every day we ask ourselves things like:

  • How can we bring key lessons from traditional game design (networking, entity-component-system) on-chain? Which lessons are viable and which aren’t?
  • Solutions to bridge on-chain and off-chain compute without compromising composability? hmm…
  • What are truly crypto-native game mechanics (🤫)?
  • What are the tradeoffs between different ecosystems and languages for the future of on-chain games?

If these sound exciting to you, please reach out to team@curio.gg.